Game AI Pathfinding — A* Algorithm and NavMesh Guide
In this tutorial, you'll learn about Game AI Pathfinding. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Game AI pathfinding solves the problem of moving a character from point A to point B while avoiding obstacles — whether it is a guard patrolling a corridor, an RTS unit crossing a map, or a companion following the player. The two dominant approaches are A* (A-star) on navigation graphs and NavMesh (navigation mesh) for free-form 3D environments, both widely used in C and C# game engines.
In this tutorial, you'll implement A* from scratch in C#, understand heuristic optimization, bake and query NavMeshes in Unity, apply path smoothing to remove jagged corners, and configure multi-agent navigation with obstacle avoidance. By the end, you'll be able to add intelligent pathfinding to any game project.
Why Pathfinding Matters
Without pathfinding, NPCs walk into walls, get stuck on corners, and break immersion. A* guarantees the shortest path on a graph while remaining fast enough for real-time games (O(E log V) with a good heuristic). NavMesh reduces A* to a graph of convex polygons instead of grid cells, enabling smooth movement in 3D environments. At DodaTech, A* pathfinding powers the file-traversal algorithms in Durga Antivirus Pro for threat graph analysis.
Learning Path
flowchart LR A[Game AI] --> B[Game AI Pathfinding
You are here] B --> C[Multiplayer Netcode] B --> D[Game Optimization] style B fill:#f90,color:#fff
A* Algorithm Implementation
A* combines Dijkstra's guarantee of shortest path with a heuristic that guides the search toward the goal. The heuristic must be admissible (never overestimate the distance) to guarantee optimality.
using System.Collections.Generic;
using UnityEngine;
public class Pathfinding
{
public List<Vector2Int> FindPath(int[,] grid, Vector2Int start, Vector2Int goal)
{
int cols = grid.GetLength(1);
int rows = grid.GetLength(0);
var openSet = new List<Node>();
var closedSet = new HashSet<Vector2Int>();
Node startNode = new Node(start, null, 0, Heuristic(start, goal));
openSet.Add(startNode);
while (openSet.Count > 0)
{
openSet.Sort((a, b) => a.F.CompareTo(b.F));
Node current = openSet[0];
if (current.Position == goal)
return RetracePath(current);
openSet.RemoveAt(0);
closedSet.Add(current.Position);
foreach (Vector2Int neighbor in GetNeighbors(current.Position, cols, rows))
{
if (closedSet.Contains(neighbor) || grid[neighbor.y, neighbor.x] == 1)
continue;
float gCost = current.G + 1;
Node neighborNode = new Node(neighbor, current, gCost, Heuristic(neighbor, goal));
Node existing = openSet.Find(n => n.Position == neighbor);
if (existing == null || gCost < existing.G)
{
if (existing != null) openSet.Remove(existing);
openSet.Add(neighborNode);
}
}
}
return null;
}
private float Heuristic(Vector2Int a, Vector2Int b)
{
return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
}
private List<Vector2Int> GetNeighbors(Vector2Int pos, int cols, int rows)
{
var neighbors = new List<Vector2Int>();
Vector2Int[] dirs = {
Vector2Int.up, Vector2Int.down,
Vector2Int.left, Vector2Int.right
};
foreach (var dir in dirs)
{
Vector2Int next = pos + dir;
if (next.x >= 0 && next.x < cols && next.y >= 0 && next.y < rows)
neighbors.Add(next);
}
return neighbors;
}
private List<Vector2Int> RetracePath(Node endNode)
{
var path = new List<Vector2Int>();
Node current = endNode;
while (current != null)
{
path.Add(current.Position);
current = current.Parent;
}
path.Reverse();
return path;
}
private class Node
{
public Vector2Int Position;
public Node Parent;
public float G, H;
public float F => G + H;
public Node(Vector2Int pos, Node parent, float g, float h)
{
Position = pos; Parent = parent; G = g; H = h;
}
}
}
The Manhattan distance heuristic (Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y)) works well for 4-directional grid movement. The open set is sorted by F-score (G + H) each iteration.
Usage:
int[,] grid = new int[5, 5] {
{0,0,0,0,0},
{0,1,1,0,0},
{0,0,0,0,0},
{0,0,1,1,0},
{0,0,0,0,0}
};
Pathfinding pf = new Pathfinding();
List<Vector2Int> path = pf.FindPath(grid, new Vector2Int(0,0), new Vector2Int(4,4));
Debug.Log("Path: " + string.Join(" -> ", path));
Expected output:
Path: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1) -> (2,0) -> (3,0) -> (4,0) -> (4,1) -> (4,2) -> (4,3) -> (4,4)
Unity NavMesh Integration
Unity's built-in NavMesh system bakes walkable surfaces into a navigation mesh and provides the NavMeshAgent component for pathfinding.
using UnityEngine;
using UnityEngine.AI;
public class EnemyNavigation : MonoBehaviour
{
public Transform target;
private NavMeshAgent agent;
void Start()
{
agent = GetComponent<NavMeshAgent>();
agent.speed = 3.5f;
agent.stoppingDistance = 1.5f;
}
void Update()
{
if (target != null)
agent.SetDestination(target.position);
}
}
Set the target to the player in the inspector or via script. The NavMeshAgent handles path calculation, movement, and obstacle avoidance automatically, provided the scene has a baked NavMesh surface.
Path Smoothing
A* on a grid produces jagged paths. Apply the string-pulling algorithm to remove unnecessary waypoints.
public List<Vector2Int> SmoothPath(List<Vector2Int> path)
{
if (path.Count <= 2) return path;
var smoothed = new List<Vector2Int>();
smoothed.Add(path[0]);
for (int i = 1; i < path.Count - 1; i++)
{
Vector2Int prev = smoothed[smoothed.Count - 1];
Vector2Int next = path[i + 1];
if (prev.x != next.x && prev.y != next.y)
smoothed.Add(path[i]);
}
smoothed.Add(path[path.Count - 1]);
return smoothed;
}
This removes intermediate nodes where the path changes direction but the agent could cut the corner diagonally.
Practice Questions
- What makes the A* heuristic admissible, and why does admissibility matter?
- How does a NavMesh differ from a grid-based pathfinding graph?
- When would you need to recalculate a path during runtime instead of following the initial route?
Frequently Asked Questions
What is the difference between A* and Dijkstra's algorithm?
Dijkstra explores equally in all directions, guaranteeing the shortest path to every node. A* adds a heuristic that guides exploration toward the goal, making it faster for point-to-point searches. Dijkstra is better when you need paths to multiple destinations from a single source.
How do I handle dynamic obstacles in NavMesh?
Use NavMeshObstacle components for moving obstacles — the agents will recalculate paths around them. For frequently changing environments, carve the NavMesh dynamically with NavMeshSurface.BuildNavMesh() at runtime.
Can A* handle weighted terrain (mud, hills)?
Yes. Assign movement costs to each node (e.g., mud = 5, road = 1). The G-score accumulates actual movement cost, so the algorithm naturally prefers cheaper terrain. This is called weighted A*.
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro