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 content 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 on

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

Comments
Tpiom
Tpiom

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

Reply Good karma Bad karma+8 votes
ZeusLT
ZeusLT

Thank you

Reply Good karma Bad karma+1 vote
Kark-Jocke
Kark-Jocke

Cool :)

Reply Good karma Bad karma+1 vote
MrEmjeR
MrEmjeR

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

Reply Good karma Bad karma+1 vote
DaggerClassStudio
DaggerClassStudio

sexy

Reply Good karma Bad karma+1 vote
Post a comment
Sign in or join with:

Only registered members can share their thoughts. So come on! Join the community today (totally free - or sign in with your social account on the right) and join in the conversation.

Icon
0 A.D. Empires Ascendant
Platforms
Windows, Mac, Linux
Developer & Publisher
Wildfire Games
Engine
Pyrogenesis
Contact
Send Message
Homepage
Play0ad.com
Release date
Game watch
Start tracking
News
Browse
News
Share
Related Games
0 A.D. Empires Ascendant
0 A.D. Empires Ascendant Real Time Strategy
Related Engines
Pyrogenesis
Pyrogenesis GPL
Related Groups
Wildfire Games
Wildfire Games Developer & Publisher