A* Pathfinding in My RTS

A wall in the way

After selection, formations, and attacking, an obstacle made the movement system’s weakness obvious. A unit knew where it wanted to go, but a straight line to the destination was not always walkable.

The navigation grid

My world is 5,000 units wide. With 40-unit cells, that gives me 125 cells across. The grid records which cells are blocked by obstacles. Before searching, I convert the start and destination from world positions into grid coordinates and check whether either cell is blocked.

A* in plain terms

I start at the unit’s cell and keep a set of cells to explore. For each candidate I track the cost of the route traveled so far and an estimate of the distance left. I explore the most promising cell, check its walkable neighbors, and remember a neighbor’s parent whenever I find a cheaper way to reach it.

A straight step costs 1. A diagonal step costs about 1.414. When the search reaches the destination, I follow the parent cells backward, reverse that sequence, and convert the cells into world-space waypoints. If no route exists, the function returns an empty path.

open = { start }
cost[start] = 0

while open is not empty:
    current = cell with the lowest (cost + estimated remaining cost)
    if current is the destination:
        rebuild the path through parent cells

    for each walkable neighbor of current:
        new_cost = cost[current] + step_cost(current, neighbor)
        if new_cost is cheaper:
            cost[neighbor] = new_cost
            parent[neighbor] = current
            add neighbor to open

return empty path

Where I’m at

The first path around static obstacles works. The next movement problem is how groups share space. Buildings and moving units need different handling from a permanent wall.

Previous: formations and attacking · Shape RTS on Typhoon Labs