So, this follows straight from the last post about the change of heart regarding HPA*.  The new system is slightly different, but generally simpler. Below, I'm going to describe how it works.

Prerequisites

The basic input of this system is a move cost map (a value per pixel) as well as the city locations. To implement this system, we need A* for graphs and grids, as well as a function to calculate a delaunay triangulation as well as a dijkstra map.

Part 1: Connectivity

First calculate a delaunay triangulation of the cities. This looks something like the below (ignore the red edges)

From the triangulation we make a graph. For each graph edge (which is a city-to-city path), we run A*-grid at max quality settings. This calculates a nice path of least-resistance, it's the "road" if you wish. The path results look like the first image of the post. For 250 cities, we get about 750 paths. For each of those paths, we also calculate and store the traversal cost.

Part 2: Arbitrary point-to-city support

When we need to go from A to B, where the distance between A and B is great, we naturally want to stop at cities to restock etc. So, the final path will look like A -> city0 -> city1 -> ... -> cityN -> B. This step precalculates infromation for fast calculation of A -> city0 and cityN -> B.

For each of the eight directions, we calculate a dijkstra map using a slightly customized move cost function: movement towards the direction has less cost, therefore is preferred. The targets of each dijkstra map are all the city locations.

After we calculate all dijkstra maps, we now need to calculate, for each point in the map and for each of the eight directions/maps, the direction towards the least cost. The direction needs 4 bits to store (eight directions plus 1 bit to mark if it's a no-direction), so direction maps for 8 directions will then cost 32 bits per pixel, which is not bad.  And we won't need the dijkstra maps any more; these direction maps can provide us with a best path to a city given a main, general direction.

This concludes the precalculations, and it will hopefully make sense in the next part.

Part 3: Runtime pathfinding

We have points A and B. From point A, we calculate which of the 8 directions leads more towards B. We pick the dijkstra direction map computed in part 2 above and traverse it till we reach a node, also recording the path while we're at it. We apply the same process with point B, but we use the inverse direction. So now, we have 2 nodes in the graph, and we run A*-graph to calculate the best path between them. The cost function uses the precalculated traversal costs from part 1.  So now, we have: 1) fine path from A to closest city c0 2) fine path from B to closest city cN 3) coarse path between cities c0 and cN. This is all we need to calculate a continuous path from A to B. Some examples below -- Red is A -> city0, Black is cityN -> B and magenta is the concatenation of precalculated city-to-city paths. If you zoom in, white points along the path are the cities.

Notes, failure cases and future work

On average, using a Ryzen desktop processor, at max A* quality, it takes 0.22ms per path in Release configuration, or  3.37ms in Debug. For future reference. The cached memory needed for the entire pathfinder (graphs, precalculated paths and direction maps) is about 1.5 MB.

Path coalescing. When calculating the fine paths, every time we calculate one, we can reduce the cost of traversing those tiles just by a little bit. This is akin to making a natural forest path. The first path it's traversed, it's wild and kinda tough to get through. Make 1000 people walk on the path, and it's now a bit easier. Make 1000000 walk the path and it should now be very distinct compared to its surroundings.  By reducing the cost a little bit, the path network looks a bit "neater".  Following are images of non-coalesced, slightly coalesced and heavily coalesced. More is not always better.

Embarking/disembarking at random locations. If I want to go to Hawaii, I don't take the road to the nearest beach and drop a ship and sail. I'd go to a port. So, when calculating movecosts, we can add an additional embark/disembark costs if we're about to make a change from a water tile to a land tile and vice-versa, unless one of the two tiles is a city. This beautifully controls the movement via the cost multiplier. Set it to infinity, and we're just not allowed to change to water/land unless via a port. Set it very high, and embarking at any other point is only when absolutely necessary. The good part is that we can identify those points and make them simple ports in the game, as apparently they are naturally exactly that!

Redundancy on short paths. Sometimes, to go from A to B we end up with the following:

This happens as we're forced to find city nodes, and we pick nodes based on the general direction that we're heading. Thankfully, we can just add a simple length check like:

2|AB| < (|Ac0| + |c0c1| + |c1B|)

to identify if the coarse path is unnecessary. In those cases, we run an A*-grid to calculate the path between A and B.

 

Backtracking. Sometimes we get the following sort of backtracking:

If you look at the black path, it goes backwards. Sometimes I can explain it as before we embark on a long trip, we make sure to go to a nearby city to restock, even if it takes us off-route. There are of course other ways to solve it, and they are easy but still need a bit of work, so this is marked as not-important.

More nodes. If the number of graph nodes is deemed too low, and I'm not happy with the large distance between cities, we can always add more nodes. The "optimal" way (not in terms of performance, but of results) of doing it is using a simple loop:

  1. Calculate the dijkstra map
  2. Find largest score (point furthest away from anything)
  3. Add the scoring point into the feature list
  4. Go to 1, until a desired max score is reached

This step should happen before the delaunay triangulation.