Pathfinding in Warman sits on top of the terrain system. The map is not a flat plane. It has cliffs, elevated platforms, ramps between height levels, and water that may or may not be passable. The pathfinding needs to handle all of this while running in a lockstep simulation where every client must compute identical results.
The 3D Grid
The grid is three-dimensional: X and Z map to the terrain surface, Y maps to height levels. Each terrain cell gets subdivided by a density factor (currently 2, so each 1x1 terrain cell becomes a 2x2 cluster of pathfinding nodes). The Y axis is determined by the cliff layer's height range. If the tallest cliff in a room is 4 units high, the grid allocates enough Y levels to cover that plus a buffer.
Nodes are only created where terrain is walkable. Cliff-occupied cells, non-walkable texture types (like deep water or void), and out-of-bounds positions produce no nodes. The grid is sparse: a 30x30 terrain room with one height level creates about 3,600 nodes, not the 30x30xN that a fully-filled 3D array would suggest.
Ramp Nodes
Ramps are the trickiest part. A ramp connects two height levels, so the nodes on a ramp cell need interpolated Y positions. Warman divides the ramp's height transition into eighths: the lower pair of nodes sits at 1/8 and 3/8 of the height step, the upper pair at 5/8 and 7/8. This creates a smooth slope that units can walk along without teleporting between height levels.
The interpolation depends on the ramp direction. A north-facing ramp raises the nodes along the Z axis, while an east-facing ramp raises them along the X axis. Each of the four node positions within a cell gets a different height offset based on this direction.
Surface Connectivity
One of the more important optimisations is surface detection. After the grid is built, a BFS (breadth-first search) runs from each unvisited node, flooding outward through walkable neighbours to discover connected regions. Each region becomes a "surface," a HashSet<Node> that contains every node reachable from every other node in the set.
A* Implementation
The A* itself is standard: a binary heap for the open set, a HashSet for the closed set, Manhattan distance as the heuristic (since diagonal movement costs the same as cardinal on a grid). Neighbours include all 16 adjacent positions: 8 horizontal (4 cardinal + 4 diagonal) at the same Y level, plus 8 more one Y level up and down. This handles stepping onto and off of ramps and cliff edges.
Diagonal movement has a constraint: a unit can only move diagonally if both adjacent cardinal cells are walkable. The constraint stops units from corner-cutting through walls. If a unit is at position (5, 5) and wants to move to (6, 6), both (6, 5) and (5, 6) must be walkable. Otherwise the diagonal is blocked.
AstarModifiers
After the grid is built from terrain data, AstarModifier components get a chance to change it. These are MonoBehaviours placed in the level that can add, remove, or modify nodes. A bridge doodad might add walkable nodes at a specific height that don't correspond to any terrain cell. A blocked doorway might mark nodes as non-walkable. Modifiers run in priority order and can create multi-height platforms that the terrain system alone can't represent.
After all modifiers run, the surface BFS recalculates so connectivity stays accurate.
The Agent
The AstarAgent sits on each unit and handles actual movement. When a unit wants to move, the agent receives a direction vector, calculates the desired position, and checks if the target node is walkable. If it is, the unit moves there. If not, the agent tries axis-separated movement (first X only, then Z only) to enable wall-sliding. Without it, the player would get stuck on diagonal walls.
The agent also handles a subtle problem with ramps. Units moving along ramps can have their Y position drift slightly off-grid due to interpolation. If the current position fails to resolve to a valid node, the agent snaps the Y back to the last known good node's position before processing the next move. That fixes the "stuck on ramp edge" problem where a unit's Y is technically between two grid levels and neither one claims it.