The Pathfinding Saga Continues news - 0 A.D. Empires Ascendant

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)