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 Pathfinding Update -- 24 January 2012

We need two separate pathfinders (one for planning long-range paths that avoid rivers and buildings and walls etc, and one for finding short-range diversions around other units while following the long-range paths), and there are problems (like units getting stuck) when the two pathfinders disagree on whether a unit can fit through a gap. In an ongoing discussion, we look at some pitfalls and opportunities for improvement in this area.

Posted by Mythos_Ruler on Jan 24th, 2012

As mentioned previously, we need two separate pathfinders (one for planning long-range paths that avoid rivers and buildings and walls etc, and one for finding short-range diversions around other units while following the long-range paths), and there are problems (like units getting stuck) when the two pathfinders disagree on whether a unit can fit through a gap.

What the game currently does is like this: (click for larger image)


The grid pattern on the terrain shows the tiles (each split into 4x4 small cells). The cavalry unit has been told to walk from by the water up to the flag.

The long-range pathfinder works with tiles: the red-shaded tiles are impassable (blocked by buildings or water or steep terrain), and the green- and yellow-shaded tiles are where the pathfinder has searched to find the shortest path. It's finding a path that travels through a piece of wall, because the wall is too narrow to have blocked an entire tile.

The short-range pathfinder works with the cyan squares. Each building (and each tile that is blocked by water or steep terrain) has a square around it. Instead of using tiles, it moves between the corners of the squares, making sure it never crosses one of the cyan edges (since then it would collide with an obstacle). The thin red line indicates the path it's found, walking around the edges of the walls and then heading towards the flag. In this case it luckily doesn't have to diverge too much from the long-range path (which went straight through the wall) so it works okay, but in other cases the inconsistency is a problem.

I've been changing it to instead look like:


The long-range pathfinder is basically as before, but instead of using whole tiles it uses the small cells, so the red/green/yellow-shaded regions are a much higher resolution. That means it can fairly accurately represent small obstacles like the wall, without hugely over-estimating or under-estimating its size.

The short-range pathfinder no longer uses a single square around a building(/wall/etc) - it computes the cyan edges to exactly match the boundary of the red-shaded (impassable) cells. The little yellow circles indicate corners that the path can go between. If the long-range pathfinder found a path, it's guaranteed that the short-range pathfinder will be able to find the same path (or a better one), assuming no dynamic obstacles (i.e. other units) get in the way, because they're using the same cell-based view of passability.

I think that's good - it means the pathfinders now have some better correctness guarantees, and can make some simplifying assumptions (e.g. the long-range pathfinder doesn't have to worry about the short-range pathfinder moving a unit onto an impassable tile), and that makes it easier to implement optimisations to improve performance without worrying about breaking everything.

Philip Taylor [aka Ykkrosh] 
WFG Programming Team 

Post comment Comments
Tpiom
Tpiom Jan 25 2012, 7:17am says:

This was a most interesting article for a... non developer to read. Thanks for explaining! :)

+8 votes     reply to comment
ZeusLT
ZeusLT Jan 25 2012, 3:12pm says:

Thank you

+1 vote     reply to comment
Kark-Jocke
Kark-Jocke Jan 25 2012, 7:13pm says:

Cool :)

+1 vote     reply to comment
MrEmjeR
MrEmjeR Jan 28 2012, 6:32am says:

With going from 4x4 cells to 1x1, doesn't this mean that the pathfinder now is 16 times as expensive with calculations?

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

sexy

+1 vote     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.
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.
0 A.D. Indie Single & Multiplayer Real Time Strategy
Related Engines
Pyrogenesis
Pyrogenesis GPL TBD
Related Groups
Wildfire Games
Wildfire Games Developer & Publisher with 20 members