2.5D Grid-Pathfinding in Stronghold Crusader

Games like Stronghold Crusader (Firefly Studios, 2002) use a graphics style that's commonly referred to as 2.5D. This post explains an approach to implementing pathfinding for agents on a 2.5D grid. It also covers how specific challenges of the genre were solved, and how the pathfinding can be extended.

For pathfinding agents on a 2.5D grid, an adapted form of the A* algorithm is used. In case you're wondering what the A* algorithm is: in an earlier article I explained how it works. But what exactly does 2.5D mean? Well, it means that graphics are placed and rendered in two-dimensional space, but the resulting image is meant to give the impression of depicting three dimensions.

Stronghold Crusader (Firefly Studios, 2002)

Units need to be able to climb onto walls when a suitable ramp is present. Groups of units need to be able to move to a target position with a single command and take up their own positions there. Both problems were solved by having the individual nodes of the A* algorithm carry, instead of a boolean saying whether the node is walkable or not, information about both the vertical height of the node and whether a unit already occupies it. With these two pieces of information, rules can be defined for the A* algorithm.

A neighboring node only counts as walkable if its height difference doesn't exceed a predefined value x. This rule makes it possible to model both stairways and slopes in the terrain. If x = 5 and neighboring tiles form a connected wall formation as shown in the next figure, an agent is able to compute a path from point A to point B.

Typically, players don't want to move just a single unit to a desired point, but a whole group of units. This raises the issue that not all units can have the same target position. This problem is solved by assigning each unit its own target position (around the position of the mouse cursor) before a path is calculated. Another issue relates to positioning the group of units when the target point lies on a wall.

To position a group of units with a single target position, the group is iterated over. The first unit claims the target node for itself. For each further unit, suitable nearby nodes are selected. During selection, all nodes are sorted by height and then by distance to the target node. Prioritizing height in the sort means units tend to position themselves on nearby nodes that have the same or a similar height to the target node.
For example, if a group of ranged units is sent to node B, the units take up the remaining nodes on the wall instead of choosing the directly neighboring nodes above, to the right, and to the left of point B.

With pathfinding of this kind, it's possible to place units on open terrain or convoluted wall structures without needing to use a different algorithm. This not only reduces the potential for errors but also improves the maintainability of the code.