Greetings, Captain!
We're now three months into Boat Crew, and today's Developer's Diary will be of the short and sweet variety. The last two weeks have been mostly focused on working on the Supply System, which will form the backbone of the campaign. In the meantime, the map has also been expanded.
You may have noticed that the Roadmap is rather conspicuously missing; that's because we figured it would make more sense to post it only when a step has been advanced. In the meantime, you can check it at the original Roadmap post.
Now let's get down to it.
The Travelling Salesman Problem:
Those of you acquainted with Computer Science or programming may have heard of the Travelling Salesman Problem, which is essentially the question: Given N cities to visit, what is the shortest path the salesman can take to visit those N cities once each and make it back to his starting point? Our supply system, as we talked about in the previous Developer's Diary, is basically this problem, except we do not have the condition of returning to the initial point. The naive solution to the Travelling Salesman problem requires us to make N! calculations.
As of the current state of the Campaign map, we have 38 bases. Suppose that you captured just half of them; there would be 19 bases and thus 19! potential routes to evaluate, that is, roughly 121 quadrillion. If you felt adventurous and captured one more base, the number jumps up to 2 quintillion. And this is before we include that there are 3 inflow points per faction, and these calculations need to be done often. This is a complete non-starter, and while there are faster algorithms to solve the TSP, solving it to practically perfect accuracy is something we felt was a waste of developer time and a waste of player's time too as it would create long loading times just to calculate the perfect supply route.
So instead of this, we've decided on a simpler in-house approach that, in practice, should follow the 10 rules of supply line generation we talked about in the previous diary almost all of the time:
1. For each of the 3 inflow points of each faction, to the Solomons, 2000 routes are randomly generated.
2. Bases are sorted by distance to the inflow point, the first half of the bases are used for attempts.
3. A route is generated by attempting addition of random bases to the route, 2 * number of bases of attempts are made. Bases that already exist on the route or create a smaller than 45 degree angle on the route are not added on attempt.
4. Every addition causes a resorting of (all) bases by distance to the latest addition. Again first half (of all) are used for further attempts.
5. The route generations are sorted based on the number of bases they cover.
6. First half of those routes are used for the actual base to base pathfinding.
7. Pathfinding is done and the routes are again sorted by a formula:
(Distance of inflow point to first base +
(sum of base to base vectors * .5) +
total length of route) / (number of bases squared)
8. The best performing routes are randomly selected by the game, after evaluating in game conditions. The few routes that are selected at the same time maximize the number of bases visited in total.
Above is an example of a route we generated, though the line art itself is a placeholder. We will be testing and iterating on this approximation, but this methodology should create the optimal route or something very close to it most of the time.
Map Situation
Meanwhile, the maturation of the map continues. As said before, we now have 38 bases with the addition of the islands Bougainville and Choiseul, along with some name changes to the existing ones to be more related to history. The map pathfinding network was also recreated to have smoother route generation. Our commissioned map artist is currently working on New Britain, New Ireland, East New Guinea and some other assorted islands, so we'll have more on that soon as well!
Goals for the Next Cycle:
For the next cycle, we want to have wrapped up the supply system and moved on to the resource system for the player. We'll have more on the design of the resource system next week, so even if it's not finished by then, we'll be talking about it!
That will be all, Captain!
T.T.