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 The Pathfinding Saga Continues

Slow continued pathfinding work. In particular, trying to get all the parts of the game to interact correctly with the new navcell-passability concept. It's important for the design to be clear on what its concepts actually are, so this is my attempt at describing the conceptual details of what I'm trying to implement now. (I'll probably copy this as documentation on the wiki when it's cleaned up and implemented properly.)

Posted by Mythos_Ruler on Feb 12th, 2012

Day 14 of the Pathfinding Saga

Slow continued pathfinding work. In particular, trying to get all the parts of the game to interact correctly with the new navcell-passability concept. It's important for the design to be clear on what its concepts actually are, so this is my attempt at describing the conceptual details of what I'm trying to implement now. (I'll probably copy this as documentation on the wiki when it's cleaned up and implemented properly.)

First we start with a map like this: (click image for larger and higher quality version)

There's some small units, a large unit (the siege tower), a building, a fence, and some water (with steep terrain around its edges). Units are "dynamic obstructions" - they move around frequently, and they need to perform pathfinding operations, and they generally can't pass through each other. Buildings and fences are "static obstructions" - they don't move, and units can't pass through them.

Dynamic obstructions have a "footprint radius", measured in high-precision units (i.e. not quantised to tiles), corresponding loosely to the graphical size of the unit. Dynamic footprints don't have a separate width vs height, nor an orientation. They don't have a precise shape - they're sort of squares, or sort of circles, or sort of neither, depending on how you look at them.

Static obstructions have a square footprint with width, height, and orientation; or a circular footprint with radius.

Terrain can also block units. Terrain is split into fairly large tiles, and each tile might be passable or impassable, depending on water depth, steepness, etc.

Each unit belongs to a "passability class", which defines the exact limits on water depth, steepness, etc, that should be used for that unit's movement.

The pathfinder uses a "navcell grid", which stores a boolean passability value for every navcell on the map, per passability class. Navcells are smaller than terrain tiles (currently there's 4x4 navcells per tile). ("Navcell" is just a term for the tiles used for navigation, to distinguish them from terrain tiles). The navcell grid is computed from terrain passability and static obstructions, like so: (click for bigger and better)

Here the thin dark blue lines indicate the footprints of all obstructions. Note that the impassable cells from the large building are strictly inside its footprint shape; we take a conservative approach so that if you tell a (zero-sized) unit to walk to the building, it can walk all the way up to the footprint edge without stepping onto any impassable tiles. Unfortunately this mean the fence is invisible to the navcell grid, since it's too narrow to strictly contain any cells. We should enforce that no static obstruction footprints should be that narrow (i.e. narrower than 2*sqrt(2) navcells).

The navcell grid only blocks a unit if that unit's central point enters an impassable tile (regardless of the unit's size). To cope sensibly with large units, each passability class defines a "clearance" value. Navcells within that distance of an obstruction are considered impassable. For standard units with a clearance of 1 navcell we get:

For large units with a clearance of 4 navcells we get:

This stops the large unit moving too close to the buildings or water. (Note that the fence now blocks some navcells. We expand the footprint shape by the clearance, and then compute which navcells are strictly contained within the expanded footprint. In contrast, terrain passability is computed with a kind of blur filter to expand the initial grid outwards by the clearance distance.)

The navcell grid ignores dynamic obstructions entirely. The long-range pathfinder finds paths across the navcell grid. It allows moves from one passable navcell to another if they're horizontally or vertically adjacent (not if there's only a diagonal connection).

The short-range points-of-visibility (POV) pathfinder is based on high-precision (i.e. not navcell-aligned) horizontal/vertical obstruction edges, and finds paths at arbitrary angles. It goes like:

The cyan lines are the obstruction edges that the POV pathfinder will not cross. The green/yellow tiles are the long-range pathfinder's output, and the thin red line is the POV pathfinder's output, for the cavalry unit to move eastwards.

For terrain and static obstructions, the POV pathfinder uses the navcell grid: it adds cyan edges around the red cells. That means a unit can move so that its central point is right up to the impassable cells, regardless of the unit's size. The clearance (used when computing the navcell grid) is what stops the unit walking too close to a building.

Dynamic obstructions are not on the navcell grid, so the POV pathfinder adds a cyan square around each dynamic obstruction's footprint. To prevent units' footprints overlapping, each of those squares is expanded by the footprint radius of the unit that's moving. (When the cavalry unit moves up to the cyan line around an archer, the cavalry's footprint will touch the archer's footprint (dark blue square).)

One slightly dodgy thing here is that a unit's clearance and footprint radius may not be the same. If the footprint is larger than the clearance, the unit might be able to get close enough to a static obstruction that their footprints overlap. I think that's probably not a problem, but I'm not certain yet and will need to clarify.

Given those concepts, the rest of the passability-related code can (mostly) be derived:

  • Whenever a unit moves by a step, we have to check for collisions in case the pathfinder returned an invalid path (e.g. because the world changed since it computed the path). That means checking the movement is along a sequence of passable navcells; and that it doesn't intersect any dynamic obstruction footprints expanded by the moving unit's radius.
  • When a unit is spawned (e.g. from training in a building), we have to pick a valid spawn point that is on a passable navcell and isn't inside an expanded dynamic obstruction.
  • When deciding whether it's valid to place a new building, it doesn't really matter what we do. It's easiest to just verify that the new building's navcell shape doesn't touch any already-impassable navcells (computed with a clearance of 0) - that'll prevent it intersecting existing buildings or invalid terrain. When telling an AI where it can place a new building, we can give it a conservative approximation of that navcell grid.
  • When placing a building on top of units, we need to tell those units to get out of the way before starting construction. To find precisely which units are affected, we need to look at the new building's navcell shape, expanded by the clearance of each unit that might be in the way, and tell any unit standing on a to-be-impassable tile to move away. But that sounds kind of nasty to implement - ought to find a better way...
  • When a unit moves to a static obstruction (to gather resources, or to melee-attack, etc), we can tell the POV pathfinder to stop when it reaches the edge of a high-precision oriented square or a circle, corresponding to the building's footprint. (That avoids the problem when you tell a load of units to attack an enemy building, of having them line up in an ugly stairstep pattern corresponding to the navcell outline). But we need to guarantee that square/circle is not inside the building's impassable tiles, else units will never quite reach it. So we need to expand the static obstruction's footprint by at least the unit's clearance value to guarantee it will be reachable. (Maybe we should actually compute the unit's footprint radius plus its specified minimum attack/gather/etc range, and use that value if it's larger than the clearance, to allow more control over the behaviour without breaking that guarantee.)

-- Philip (aka Ykkrosh)

Post comment Comments
TribalBeat Feb 13 2012, 1:02am says:

Looking forward to seeing a better pathfinding system in game. Keep up the good work!

+8 votes     reply to comment
Darthturtle Feb 13 2012, 5:19am says:

People always complain about pathfinding in a RTS. This is the first time I've seen the process described in detail, and I now have an idea of why good pathfinding is so hard to do.

+9 votes     reply to comment
AirborneSn1p3r Feb 13 2012, 7:06am replied:

its funny how simple the concept, yet how hard it is to put into practice

+1 vote     reply to comment
Riccars Feb 13 2012, 3:29pm replied:

It's so simple to imagine how the units should move but its another story when you have to think of that in programming languages.

+1 vote     reply to comment
necron15 Feb 13 2012, 5:35pm says:

Always an interesting article. Looking forward to seeing it in action.

+2 votes     reply to comment
Krej Feb 14 2012, 10:29am says:

i want roads (dig ur own roads ingame yo)

+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

0 A.D. Empires Ascendant
Windows, Mac, Linux
Developer & Publisher
Wildfire Games
Send Message
Official Page
Release Date
Game Watch
Track this game
Report Abuse
Report article
Related Games
0 A.D. Empires Ascendant
0 A.D. Empires Ascendant Single & Multiplayer Real Time Strategy
Related Engines
Pyrogenesis GPL TBD
Related Groups
Wildfire Games
Wildfire Games Developer & Publisher with 21 members