More Fun With Pathfinding news - 0 A.D. Empires Ascendant

One of the problems with pathfinding is what to do when there is no path. That's common in normal gameplay - the player will tell a unit to walk to the middle of a lake, or to a tree inside a dense forest, or to a point on another island, or to a point inside an enemy city completely enclosed by walls.

The basic A* pathfinding algorithm handles that situation very badly: it's entirely short-sighted so it won't realise the target is unreachable until it's searched through every single reachable tile in the entire map (maybe tens of thousands), which is extremely slow (maybe tens of milliseconds). On the plus side, A* is able to easily find the tile which is closest to the target and still reachable from the source, which is usually what the player wants - tell a unit to walk into a lake and it'll move to the nearby shoreline, tell it to walk into an enclosed city and it'll walk up to the wall, etc. On the minus side, A* can't do that if we add the JPS performance optimisations to it, because of boring technical details.

So what we really need is a fast way to guarantee there is at least one path to the target, before telling the A* algorithm to find the best of all possible paths. If there isn't a path then we need to pick a new target that is nearby but is definitely reachable.

What I've added now is this: (click for larger image)

Each coloured region is a collection of cells, such that there is a path between any pair of cells in that region. See e.g. the maroon region near the top-center - a unit can move from any maroon cell to any other, but the vertical line of walls defines the edge of that region and there's a separate small light-grey region on the other side of the walls. There's no direct path from maroon cells to light-grey cells so they're detected as separate regions.

This is basically the same as a flood fill in a paint program, except we prevent any region growing larger than 64x64 cells, resulting in the patchwork pattern. The size limit makes it faster to handle dynamic changes (e.g. constructing or destroying buildings) - we can throw away a 64x64 chunk of data and recompute it, instead of recomputing the entire map at once.

When two regions are touching each other, there's a path from any cell in one region to any cell in the other. In this image, the white lines are linking all these adjacent regions. E.g. from the maroon region you can move to the region above, or below, or right, but not left.

Now we can easily tell if there is a path between two points anywhere on the map. For each point, check which region it belongs to, and then search along those white lines to see if there's a sequence of adjacent regions connecting the points. Instead of perhaps a million cells to search through, there's maybe two hundred regions, so this can be very fast.

If there isn't a path, we can easily pick a new target that there is a path to. First find every region that can be reached from the source, sort them by approximate distance from the original target, then check every cell within each reachable region until we've found the one that's precisely nearest the original target, and use that cell as the new target.

After all of this, we can now run the A* algorithm as normal, but with the guarantee that the A* will never have to deal with the unreachable-target case by itself, so we avoid its worst-case performance and allow the JPS optimisations. So that's nice.

This is basically the first part of the MM-Abstraction design (used by Dragon Age). But they use the high-level region graph to find actual paths, whereas I'm (currently) only using it for testing reachability. Their approach can compute non-shortest paths (potentially making units move in ways that look stupid to the player), and they have to include various hacks to minimise that problem and smooth out the paths. I think a better approach might be to use the high-level graph to compute a more accurate heuristic in the JPS-optimised A* algorithm, so that it still guarantees optimal paths but will tend to find the target in fewer steps. But that's future work and not needed at this stage.

Another difference is their design tries to optimise memory usage, whereas my implementation is pretty dumb and totally unoptimised and is happy to throw dozens of megabytes of RAM at the problem. I think my next steps are to ensure everything's working correctly and consistently, and integrate it properly with the rest of the engine, and then do some performance measurements and optimisations, and then it should actually be usable.

Philip Taylor
[aka Ykkrosh]