0 A.D. is a free, open-source, cross-platform real-time strategy (RTS) game of ancient warfare. It's a historically-based war/economy game that allows players to relive or rewrite the history of twelve ancient civilizations, from Iberia to Mauryan India, each depicted at their peak of economic growth and military prowess. Developed using Pyrogenesis, a ground-breaking new game engine custom-built to suit this project, 0 A.D. will give players a rich and entertaining real-time gaming experience.

Report article RSS Feed More Fun With Pathfinding

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.

Posted by Mythos_Ruler on Jan 25th, 2012

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]

Post comment Comments
itchyeye3
itchyeye3 Jan 27 2012, 1:01am says:

Very interesting :)

+4 votes     reply to comment
Orac|
Orac| Jan 27 2012, 3:01am says:

Cool stuff. Pathfinding is a personal gripe of mine in many games - glad to see that 0 A.D. will not be among them!

+3 votes     reply to comment
AirborneSn1p3r
AirborneSn1p3r Jan 28 2012, 8:04am says:

these are really intresting :) would like to see more ;)

+3 votes     reply to comment
Nova_Stihl
Nova_Stihl Jan 29 2012, 5:04pm says:

this hurts my head.

+1 vote     reply to comment
DaggerClassStudio
DaggerClassStudio Feb 3 2012, 8:40am says:

Interesting indeed :D

+3 votes     reply to comment
Meister_Wolo
Meister_Wolo Feb 4 2012, 6:39am says:

Great article! Thx

+3 votes     reply to comment
Post a Comment
click to sign in

You are not logged in, your comment will be anonymous unless you join the community today (totally free - or sign in with your social account on the right) which we encourage all contributors to do.

2000 characters limit; HTML formatting and smileys are not supported - text only

Icon
0 A.D. Empires Ascendant
Platforms
Windows, Mac, Linux
Developer & Publisher
Wildfire Games
Engine
Pyrogenesis
Contact
Send Message
Official Page
Play0ad.com
Release Date
TBD
Game Watch
Track this game
News
Browse
News
Report Abuse
Report article
Related Games
0 A.D. Empires Ascendant
0 A.D. Empires Ascendant Indie Single & Multiplayer Real Time Strategy
Related Engines
Pyrogenesis
Pyrogenesis GPL TBD
Related Groups
Wildfire Games
Wildfire Games Developer & Publisher with 20 members