A* when cost isn't distance: pathfinding for board games

In Two years to find a path I told the story of Empire Builder's pathfinding: the algorithm I already knew, and the bugs that took me far too long to find. This is the practical companion to that post.

If you want to learn A* from scratch, start with Amit Patel's introduction at Red Blob Games. It's where I learned the basics, and I still go back to it. This post assumes you've got the basics and picks up where most tutorials stop: when the cheapest route and the shortest route are two different things.

All of the code here is a simplified example written for this post, not our production code. It's plain C# that works in Unity.

The thirty-second refresher

A* finds the cheapest route between two points on a graph. It keeps a list of candidate locations to explore, and it always explores next the one with the lowest score, where:

score = cost so far + estimated cost remaining

The "cost so far" is exact: it's what you've actually paid to get there. The "estimated cost remaining" is a guess, and as long as that guess never overestimates, A* is guaranteed to find the cheapest route.

Everything below is about getting those two numbers right when cost means money.

The board is a graph

An Empire Builder map is a field of mileposts on a hex grid, so each milepost has up to six neighbors. Every milepost is a node, and every step between neighbors is an edge. If you've never worked with hex coordinates, Red Blob Games also has the definitive guide to hex grids; the example uses the axial coordinates described there.

What makes this harder than a typical tutorial is the price list. Building track costs money, and the price depends on where you build:

So the pathfinder's job isn't "find the shortest route." It's "find the route that costs the least money," and those can look very different.

Costs live on the move, not the place

Here's the part that tripped me up. Terrain belongs to a milepost: building into a mountain costs $2M, no matter where you came from. But a river doesn't belong to either milepost. It sits between them. Whether you pay for a crossing depends on which two mileposts you're moving between.

That means you can't price a step by looking at one location. You need both ends:

// What it costs to build one step from `from` to its neighbor `to`.
public int StepCost(Hex from, Hex to)
{
    int cost = TerrainCost(mileposts[to]);

    if (waterCrossings.TryGetValue(Edge(from, to), out int water))
        cost += water;

    return cost;
}

Water crossings are stored by the pair of mileposts, in either order:

// Water sits *between* mileposts, so the key is the pair, in either order.
static (Hex, Hex) Edge(Hex a, Hex b) =>
    a.Q < b.Q || (a.Q == b.Q && a.R < b.R) ? (a, b) : (b, a);

If you model a river as a property of a milepost instead, you'll either charge for crossings that never happen or miss crossings that do. Neither is fun to debug.

Make sure the cost actually gets added

This one sounds too obvious to mention. It was one of my two bugs. Our code calculated the cost of crossing water correctly and then never added it to the total:

// The bug: calculated, then forgotten.
public int StepCost(Hex from, Hex to)
{
    int water = WaterCrossingCost(from, to);
    return TerrainCost(mileposts[to]);
}

Nothing crashes. The routes look reasonable. The pathfinder just quietly ignores rivers, and players pay for it. On a small test map for this post, ignoring water picked a route costing $16M when a $14M route existed. On a real map, with rivers everywhere, it's much worse.

The fix is one line. The lesson is to test your cost function by itself: hand it a step across a river and check the number.

Rank by the whole score

My other bug was in the line that picks which candidate to explore next. It was effectively choosing by distance instead of by the full score:

// The bug: closest to the goal wins, regardless of what it cost to get there.
int score = EstimateRemaining(h, goal);

// The fix: what you've paid plus what you expect to pay.
int score = costSoFar[h] + EstimateRemaining(h, goal);

Rank by distance alone and the search charges toward the goal in a straight line, no matter what's in the way. On the test map, that version built straight through a band of alpine mileposts for $18M instead of going around for $14M. Fixing this one improved routes all over the map, especially through the Alps, where expensive mileposts are packed together.

Keep the estimate honest

Now the subtle one. The estimate of what's left must never be more than the real remaining cost. If it overestimates, A* can settle for a more expensive route because it wrongly thinks the cheaper one costs too much.

On a uniform grid, that's easy: the estimate is the distance. When steps cost different amounts, it's tempting to multiply the distance by something realistic, like the cost of the terrain you're standing on. Don't. If you're standing on an alpine milepost, that multiplies the remaining distance by $5M per step, even if the rest of the route is cheap clear terrain.

The safe choice is to assume every remaining step is the cheapest kind there is:

// The cheapest any single step can ever be. The estimate depends on this.
const int CheapestStep = 1;

// A guess at what's left to pay. It must never be more than the real cost,
// so assume every remaining step is the cheapest kind there is.
public int EstimateRemaining(Hex from, Hex goal) =>
    Hex.Distance(from, goal) * CheapestStep;

It feels too pessimistic, and it does make the search explore a little more than it otherwise would. But it's always correct. If your game has steps that cost nothing (in Empire Builder, building within a major city is free), the cheapest step is $0, and your estimate has to account for that, too.

Putting it together

Here's the full search loop:

public List<Hex> FindCheapestPath(Hex start, Hex goal)
{
    var open = new List<Hex> { start };
    var closed = new HashSet<Hex>();
    var costSoFar = new Dictionary<Hex, int> { [start] = 0 };
    var cameFrom = new Dictionary<Hex, Hex>();

    while (open.Count > 0)
    {
        // Explore the candidate with the lowest (cost so far + estimated cost remaining).
        Hex current = open[0];
        int best = costSoFar[current] + EstimateRemaining(current, goal);
        foreach (var h in open)
        {
            int score = costSoFar[h] + EstimateRemaining(h, goal);
            if (score < best) { best = score; current = h; }
        }

        if (current.Equals(goal)) return Rebuild(cameFrom, goal);

        open.Remove(current);
        closed.Add(current);

        foreach (var next in current.Neighbors())
        {
            if (!mileposts.ContainsKey(next) || closed.Contains(next)) continue;

            int newCost = costSoFar[current] + StepCost(current, next);
            if (!costSoFar.TryGetValue(next, out int oldCost) || newCost < oldCost)
            {
                costSoFar[next] = newCost;
                cameFrom[next] = current;
                if (!open.Contains(next)) open.Add(next);
            }
        }
    }

    return null; // No route.
}

Picking the best candidate by scanning a list is simple and fast enough for a board-game map with a few thousand mileposts. For bigger graphs, swap the list for a priority queue.

I checked this example against a brute-force search on a test map with rivers and alpine terrain, and it found the true cheapest route.

using System;
using System.Collections.Generic;

// A milepost on a hex grid, in axial coordinates (see Red Blob Games' hex grid guide).
public readonly struct Hex : IEquatable<Hex>
{
    public readonly int Q, R;
    public Hex(int q, int r) { Q = q; R = r; }

    static readonly Hex[] Directions =
        { new Hex(1, 0), new Hex(1, -1), new Hex(0, -1), new Hex(-1, 0), new Hex(-1, 1), new Hex(0, 1) };

    public IEnumerable<Hex> Neighbors()
    {
        foreach (var d in Directions) yield return new Hex(Q + d.Q, R + d.R);
    }

    // Number of steps between two hexes, ignoring cost.
    public static int Distance(Hex a, Hex b)
    {
        int dq = a.Q - b.Q, dr = a.R - b.R;
        return (Math.Abs(dq) + Math.Abs(dr) + Math.Abs(dq + dr)) / 2;
    }

    public bool Equals(Hex other) => Q == other.Q && R == other.R;
    public override bool Equals(object obj) => obj is Hex h && Equals(h);
    public override int GetHashCode() => (Q * 397) ^ R;
    public override string ToString() => $"({Q},{R})";
}

public enum Terrain { Clear, Mountain, Alpine, SmallCity, MediumCity, MajorCity }

public class BuildPathfinder
{
    // Build costs in millions, from the Empire Builder rules.
    static int TerrainCost(Terrain t)
    {
        switch (t)
        {
            case Terrain.Clear: return 1;
            case Terrain.Mountain: return 2;
            case Terrain.Alpine: return 5;
            case Terrain.SmallCity:
            case Terrain.MediumCity: return 3;
            case Terrain.MajorCity: return 5;
            default: throw new ArgumentOutOfRangeException(nameof(t));
        }
    }

    // The cheapest any single step can ever be. The estimate depends on this.
    const int CheapestStep = 1;

    readonly Dictionary<Hex, Terrain> mileposts;
    readonly Dictionary<(Hex, Hex), int> waterCrossings; // river = 2, lake or inlet = 3

    public BuildPathfinder(Dictionary<Hex, Terrain> mileposts, Dictionary<(Hex, Hex), int> waterCrossings)
    {
        this.mileposts = mileposts;
        this.waterCrossings = waterCrossings;
    }

    // Water sits *between* mileposts, so the key is the pair, in either order.
    static (Hex, Hex) Edge(Hex a, Hex b) =>
        a.Q < b.Q || (a.Q == b.Q && a.R < b.R) ? (a, b) : (b, a);

    public void AddWaterCrossing(Hex a, Hex b, int cost) => waterCrossings[Edge(a, b)] = cost;

    // What it costs to build one step from `from` to its neighbor `to`.
    public int StepCost(Hex from, Hex to)
    {
        int cost = TerrainCost(mileposts[to]);

        if (waterCrossings.TryGetValue(Edge(from, to), out int water))
            cost += water;

        return cost;
    }

    // A guess at what's left to pay. It must never be more than the real cost,
    // so assume every remaining step is the cheapest kind there is.
    public int EstimateRemaining(Hex from, Hex goal) => Hex.Distance(from, goal) * CheapestStep;

    public List<Hex> FindCheapestPath(Hex start, Hex goal)
    {
        var open = new List<Hex> { start };
        var closed = new HashSet<Hex>();
        var costSoFar = new Dictionary<Hex, int> { [start] = 0 };
        var cameFrom = new Dictionary<Hex, Hex>();

        while (open.Count > 0)
        {
            // Explore the candidate with the lowest (cost so far + estimated cost remaining).
            Hex current = open[0];
            int best = costSoFar[current] + EstimateRemaining(current, goal);
            foreach (var h in open)
            {
                int score = costSoFar[h] + EstimateRemaining(h, goal);
                if (score < best) { best = score; current = h; }
            }

            if (current.Equals(goal)) return Rebuild(cameFrom, goal);

            open.Remove(current);
            closed.Add(current);

            foreach (var next in current.Neighbors())
            {
                if (!mileposts.ContainsKey(next) || closed.Contains(next)) continue;

                int newCost = costSoFar[current] + StepCost(current, next);
                if (!costSoFar.TryGetValue(next, out int oldCost) || newCost < oldCost)
                {
                    costSoFar[next] = newCost;
                    cameFrom[next] = current;
                    if (!open.Contains(next)) open.Add(next);
                }
            }
        }

        return null; // No route.
    }

    public int PathCost(List<Hex> path)
    {
        int total = 0;
        for (int i = 1; i < path.Count; i++) total += StepCost(path[i - 1], path[i]);
        return total;
    }

    static List<Hex> Rebuild(Dictionary<Hex, Hex> cameFrom, Hex goal)
    {
        var path = new List<Hex> { goal };
        while (cameFrom.TryGetValue(path[path.Count - 1], out Hex prev)) path.Add(prev);
        path.Reverse();
        return path;
    }
}

What I'd tell myself two years ago

• Price the move, not the place. Anything that sits between locations, like rivers, walls or borders, belongs to the step.
• Test the cost function on its own. Most pathfinding bugs aren't in the search. They're in what you tell the search things cost.
• Rank by cost so far plus the estimate. Never by distance alone.
• Keep the estimate pessimistic. Assume the cheapest possible step. A slower search that's right beats a fast one that's wrong.