A* Pathfinding in Unity: Build Smarter Game AI with Heuristics

Introduction: Why A* Pathfinding Matters in Modern Games

From NPCs navigating complex terrains in open-world RPGs to autonomous agents in real-time strategy games, pathfinding is the backbone of intelligent movement. The A* algorithm, with its balance of optimality and efficiency, remains the gold standard. In this tutorial, you'll implement A* step by step in Unity, focusing on the Cs7632 assignment requirements. We'll explore cost functions, heuristic estimates, and incremental search—all while drawing parallels to trending topics like AI in gaming and autonomous navigation.

Understanding the A* Algorithm

A* combines the actual cost from the start (G) with an estimated cost to the goal (H) to prioritize nodes: F = G + H. With an admissible heuristic (never overestimates), A* guarantees the shortest path. In games, this means your AI character won't take unnecessary detours.

Key Components

• Cost Function (G): The cumulative cost to reach a node. In our implementation, we use Euclidean distance between nodes.
• Heuristic Function (H): An estimate of remaining distance. Common choices: Manhattan, Euclidean, or null (for Dijkstra).
• Open and Closed Sets: Open set contains nodes to evaluate; closed set contains nodes already processed.

Implementing Cost and Heuristic Functions

You must implement two functions: Cost(Vector2 nodeA, Vector2 nodeB) and two heuristics: HeuristicManhattan and HeuristicEuclidean. The provided CostNull and HeuristicNull are used by other algorithms.

public float Cost(Vector2 nodeA, Vector2 nodeB)
{
    return Vector2.Distance(nodeA, nodeB);
}

public float HeuristicManhattan(Vector2 nodeA, Vector2 nodeB)
{
    return Mathf.Abs(nodeA.x - nodeB.x) + Mathf.Abs(nodeA.y - nodeB.y);
}

public float HeuristicEuclidean(Vector2 nodeA, Vector2 nodeB)
{
    return Vector2.Distance(nodeA, nodeB);
}

Why Euclidean? It's consistent and often used in grid-based games. Manhattan is faster for 4-directional movement. Trend alert: Just as AI in self-driving cars uses heuristic estimates to plan routes, your game AI uses these to navigate virtual worlds.

Building the Incremental A* Search

The core method FindPathIncremental is called repeatedly until a path is found. It uses callbacks for node count, node retrieval, and adjacency lists. The state is maintained across calls via searchNodeRecords, openNodes, closedNodes, and returnPath.

Initialization

When doInitialization is true, reset all data structures and add the start node to the open set with its estimated total cost.

if (doInitialization)
{
    searchNodeRecords.Clear();
    openNodes.Clear();
    closedNodes.Clear();
    returnPath.Clear();

    var startRecord = new PathSearchNodeRecord
    {
        NodeIndex = startNodeIndex,
        FromNodeIndex = -1,
        CostSoFar = 0,
        EstimatedTotalCost = H(getNode(startNodeIndex), getNode(goalNodeIndex))
    };
    searchNodeRecords[startNodeIndex] = startRecord;
    openNodes.Enqueue(startNodeIndex, startRecord.EstimatedTotalCost);
    currentNodeIndex = startNodeIndex;
    return PathSearchResultType.InProgress;
}

Main Loop (One Step per Call)

Each call processes one node from the open set. If the open set is empty, return Partial (or Complete if goal reached). Otherwise, dequeue the node with smallest F value. If it's the goal, reconstruct the path and return Complete. Else, expand its neighbors.

if (openNodes.Count == 0)
{
    // No path: reconstruct closest node to goal
    return PathSearchResultType.Partial;
}

int currentIndex = openNodes.Dequeue();
var currentRecord = searchNodeRecords[currentIndex];
closedNodes.Add(currentIndex);
currentNodeIndex = currentIndex;

if (currentIndex == goalNodeIndex)
{
    // Reconstruct path
    return PathSearchResultType.Complete;
}

// Expand neighbors
List<int> neighbors = getAdjacencies(currentIndex);
foreach (int neighborIndex in neighbors)
{
    if (closedNodes.Contains(neighborIndex))
        continue;

    float tentativeG = currentRecord.CostSoFar + G(getNode(currentIndex), getNode(neighborIndex));
    if (!searchNodeRecords.ContainsKey(neighborIndex) || tentativeG < searchNodeRecords[neighborIndex].CostSoFar)
    {
        var neighborRecord = new PathSearchNodeRecord
        {
            NodeIndex = neighborIndex,
            FromNodeIndex = currentIndex,
            CostSoFar = tentativeG,
            EstimatedTotalCost = tentativeG + H(getNode(neighborIndex), getNode(goalNodeIndex))
        };
        searchNodeRecords[neighborIndex] = neighborRecord;
        if (openNodes.Contains(neighborIndex))
            openNodes.UpdatePriority(neighborIndex, neighborRecord.EstimatedTotalCost);
        else
            openNodes.Enqueue(neighborIndex, neighborRecord.EstimatedTotalCost);
    }
}

return PathSearchResultType.InProgress;

Handling Partial Paths and Closest Node

If the goal is unreachable, A* must return a path to the node closest to the goal. To find it, after the open set empties, iterate through searchNodeRecords of closed nodes and pick the one with smallest H to goal. If ties, pick the one with smallest G from start.

int closestIndex = -1;
float bestH = float.MaxValue;
float bestG = float.MaxValue;
foreach (var record in searchNodeRecords.Values)
{
    if (!closedNodes.Contains(record.NodeIndex)) continue;
    float h = H(getNode(record.NodeIndex), getNode(goalNodeIndex));
    if (h < bestH || (h == bestH && record.CostSoFar < bestG))
    {
        closestIndex = record.NodeIndex;
        bestH = h;
        bestG = record.CostSoFar;
    }
}
// Then reconstruct path from start to closestIndex

Testing with Different Heuristics

By swapping G and H callbacks, you can run Dijkstra (null heuristic) or Greedy Best-First Search. For example, use HeuristicNull for Dijkstra: it ignores heuristic, exploring equally in all directions. Use HeuristicManhattan for Greedy Best-First: it rushes toward the goal but may not find optimal path.

Trend Connection: AI in Gaming and Beyond

Pathfinding isn't just for games. Autonomous drones use similar algorithms to navigate. In the gaming world, titles like Fortnite and Call of Duty rely on A* for enemy AI. Even in AI app development, pathfinding concepts apply to recommendation systems and network routing. Understanding A* gives you a foundation for more advanced AI topics.

Common Pitfalls and Debugging Tips

• Infinite loops: Ensure you mark nodes as closed after processing.
• Wrong heuristic: If overestimating, A* may not find optimal path. Stick to admissible heuristics.
• Priority queue issues: Use UpdatePriority when a node's cost improves.
• Null or zero heuristics: Fall back to Euclidean distance as specified.

Conclusion

You've now implemented A* pathfinding in Unity. This skill is crucial for game AI and beyond. Experiment with different heuristics and see how they affect performance. For more, check out our other tutorials on Dijkstra's algorithm and Greedy Best-First Search. Happy coding!