Archive
Pathfinding study
How well could I implement A* and use it in a game-like scenario? A flexible pathfinder for turn-based games, from open 2D grids to 3D maps.
- Tech
- Unity, C#, Burst and jobs
Showcase: Applied to a test map from XCOM
I built a map from the layouts of XCOM: UFO Defense, which meant solving scaling problems when moving maps from an old isometric game into 3D.



Starting in 2D
I began with a straightforward A* pathfinder on a 2D grid, with obstacles to navigate around. A large part of the project then went into optimizing it, because the first version took over four seconds on a 255x255 map. I also added a no-corner-cutting rule and tested the result on a 255x255 map inspired by Baldur's Gate II. I also started experimenting with Jump Point Search, but never finished it.



Movement limits and terrain
Next came path limiting: an energy score that drops with each cell traversed, tested on a labyrinth. Variable cell costs then simulate rough terrain.


Moving to 3D
In 3D the challenges were inclines, slopes and paths passing through objects. I then extended it to drop off ledges when that gives the shortest path, and brought back walls that block movement in specific directions.






Reading the grid from the level
The final version ended up in a prototype with soldiers using time units for actions. There the grid isn't authored by hand: it's built from the colliders already in the level.
- Walkable cells. Two rays go down through each cell on each height level, one starting a level higher. The cell only counts if both land on the same point of the same collider, which proves there's room to stand.
- Slopes. The height of the surface inside a cell is stored in quarter steps, so inclines don't need their own rules in the level data.
- Walls. Eight short rays around each cell record which directions are open, in a single byte. A wall can then block one side of a cell without blocking the cell.
- Addressing. A position packs into a 32-bit key: 12 bits for x, 8 for height and 12 for z. Only walkable cells are stored, so empty space costs nothing, and neighbours are found with bit arithmetic on the key.
Time units and reachable cells
Selecting a unit first floods outward from its position with no heuristic, stopping where the cost passes the unit's time units. That gives the region it can reach this turn. A step costs 4 time units, or 6 diagonally.
A* then runs towards the clicked cell, using an octile distance as its heuristic, and the returned path only keeps cells inside that region. When there's no cell next to the current one but the way is clear, the search looks straight down for the first walkable cell, which is what makes dropping off a ledge possible.
Off the main thread
Longer paths exposed performance issues, so I moved the pathfinder to Unity's Burst and job system, which improved its performance significantly. Both searches are Burst-compiled jobs. Each request gets its own copy of the grid, made by a parallel job, so searches don't touch shared state. The open list is a heap from a third-party NativeHeap library, with a lookup beside it to tell whether a cell is already queued. A coroutine checks each frame whether the job has finished and collects the result, so the game keeps running while it searches.