HPA* - bad decision?

1.5 years ago I wrote a post about my implementation of HPA*, and I was quite happy with it. At that time, I did make some assumptions about movement in the overworld:

  • Lots of units calculate pathfinding in the overworld
  • Movement mode is by land, water or air (walking/riding, swimming/sailing or flying)
  • Each unit can support multiple movement modes, each with their own speed
  • Each unit could have traits that affect the movecosts in a subset of biomes (pirates faster over sea, dwarves faster in mountains, etc)

The way the pathfinding system currently works is based on a unique "move cost map" ID, which is generated based on any movecost modifiers and movement modes. So, for the overworld map, we could have several IDs:

  • walking, no modifiers
  • walking, faster in coastal terrain
  • flying
  • flying, faster over sea
  • walking and flying, walking faster in forest
  • swimming, walking
  • ....

Each of those needs a unique pathfinder. Problem is, HPA*:

  • Needs quite a bit of storage
  • Needs a lot of precalculations
  • Works well when many units share the same HPA* data structure

Currently, I'm a bit closer into putting units (NPC parties) on the map, and I've made some horrifying realization, which one might notice from the above: The unbounded potential combinations will dwarf the benefits that HPA* will offer, as I can't guarantee that many units will share the same data structures. So, that's my research of an optimized pathfinder out of the window. Oh well.

Updated constraints/assumptions

So, my issue now is that I can have many movecost maps and many units per movecost map (although for the latter, I don't know how many). Also, the map is going to be at least 512x512. So, how to deal with the issue of efficient pathfinding for the overworld? Constraints and assumptions. At the moment, I make the following assumptions:

  1. Lots of NPC parties moving in the world (say N, could be thousands)
  2. At worst case, each NPC party has its own movecost ID; a function to calculate the cost of a tile that has unique parameters for each party.
  3. When NPC parties travel great distances, it is logical to assume that they stop for supplies and a good night's sleep to every city they can find
  4. When NPC parties travel across the sea, they possibly don't carry their own boats, so they would go to a port, and board a ship to go to another port
  5. NPC parties would generally travel well-trodden roads, rather than going through the wilderness
  • From (1) and (2) I can conclude that caching movecost maps is prohibitive, due to 512x512xN storage requirements.
  • From (3), (4) and (5) I can conclude the the paths that NPCs will typically follow, are between cities, and that actually makes perfect sense.
  • From (4) I can conclude that a path between cities is either fully on land, or fully on water

Forming a new pathfinder

So, from the above, another pathfinding system slowly springs into existence, that is centered around city-state locations. I'll be using grid A* and graph A* implementations. The grid A* calculates fine-granularity paths (a list of 2d integer points adjacent to each other) and the graph A* calculates coarse-granularity paths (a list of indices to the graph's points)

  • Create a delaunay triangulation using the city-state locations
  • Create a graph from the triangulation results: nodes are city locations, edges are city-to-city connections
  • For each graph edge, run the grid A*
    • If the edge connects port cities in different landmasses, use a water-only move cost map, without modifiers
    • Otherwise, use a land-only move cost map, without modifiers
    • The results are paths between each pair of connected city points

When a unit needs to go from A to B, the following calculations take place:

  • Identify the closest city to A in the general direction of B: c0
  • Identify the closest city to B in the general direction of A: c1
  • Calculate a path A -> c0, using the grid A*
  • Calculate a path c1 -> B, using the grid A*
  • Calculate a path c0 -> c1, using the graph A*

From the above, we can walk along a fine-granularity path from A to B, using a large amount of precalculation.

But wait... still no unbounded movecost map handling?

If you've noticed from the above, I haven't resolved one issue: the reason I rejected HPA* was because of the unbounded number of movecost maps. But, what do I do here? I just use basic movecost maps without modifiers (a land-based one and a water-based one)! So why is this any better? Well, this actually makes more sense, as

  • Well-trodden paths are generally preferred
  • Cities are always part of a long path, as it should be. HPA picked arbitrary points on cell edges.
  • Sailing routes are handled naturally.
  • The majority of units has average movement capabilities, and that means no modifiers
  • How fast units move can still be individually calculated, and that's not expensive.

Conclusion for now

The above now has to be implemented, and I've also got some other thoughts for a data structure that will allow precalculation of all potential paths A->c0 and c1->B with just a little more storage, so that pathfinding in the overworld is always reduced in a graph search with a max of about 250 points and 750 edges.