Posted by Abdul Fahad Shahbaz — Unity game developer based in Lahore, Pakistan. Portfolio: fahadshahbaz.fun
In my latest Unity project — an AI-driven 3D maze game — I needed two things to work together: a maze generator that creates a unique, fully-connected layout every run, and an enemy AI that could navigate those mazes intelligently in real time.
The challenge? The maze is procedural. That means I can't bake a navmesh ahead of time or rely on Unity's built-in navigation system. Every time the player starts a run, a brand new maze is generated — and the enemy has to find its way through it from scratch.
I solved this with two algorithms working in tandem:
Depth-First Search (DFS) to generate the maze
A* pathfinding to navigate it
In this post I'll explain both implementations with working C# code taken directly from the project. By the end you'll have a self-contained AStarPathfinder class you can drop into any Unity maze project.
My portfolio (see the full project): https://fahadshahbaz.fun/works/AI-Maze-Game
The problem with Unity's built-in NavMesh
Unity's NavMesh is excellent for static environments. But procedural mazes create geometry at runtime — walls are instantiated, corridors are carved, the whole layout is different every time. By the time the maze is ready, it's too late to bake a navmesh without adding significant frame time.
I needed a pathfinder that:
Works on a grid, not a mesh
Knows which cells have walls between them (not just which cells exist)
Converts grid coordinates back to world-space Vector3 positions the enemy can walk to
A custom A* implementation turned out to be the cleanest fit.
Part 1: Generating the maze with DFS
Before we can pathfind through a maze, we need a maze. I used iterative Depth-First Search (also called "recursive backtracker") because it produces long, winding corridors that feel natural for a 3D game — not a grid of perfect squares.
The algorithm works like this:
Start at a random cell, mark it visited
Pick a random unvisited neighbour
Remove the wall between the current cell and that neighbour
Move to the neighbour and repeat
If no unvisited neighbours exist, backtrack to the previous cell
Repeat until all cells are visited
Every cell in the grid is a MazeCell — a simple data structure that tracks which of its four walls (left, right, front, back) are still standing.
csharp
public class MazeCell
{
private bool rightWall = true;
private bool leftWall = true;
private bool frontWall = true;
private bool backWall = true;
public bool HasRightWall() => rightWall;
public bool HasLeftWall() => leftWall;
public bool HasFrontWall() => frontWall;
public bool HasBackWall() => backWall;
public void RemoveRightWall() => rightWall = false;
public void RemoveLeftWall() => leftWall = false;
public void RemoveFrontWall() => frontWall = false;
public void RemoveBackWall() => backWall = false;
}
The generator keeps a Stack to track the path for backtracking. When it carves a passage between cell A and cell B, it removes A's wall facing B and B's wall facing A — so both cells agree on the opening.
csharp// Example: carving a passage to the RIGHT
currentCell.RemoveRightWall();
grid[next.x, next.y].RemoveLeftWall();
The result is a MazeCell[,] grid where every cell knows exactly which of its walls are still standing. This is the data structure the A* pathfinder reads directly.
Why DFS over Prim's or Kruskal's? DFS produces mazes with a single long main path and fewer dead ends — which feels more fun to race through. Prim's produces mazes with many short dead ends, which is better for puzzle games. For a time-pressure race game, DFS was the right call.
Part 2: A* pathfinding through a wall-aware grid
Here is the full AStarPathfinder class from the project.
csharp
using System.Collections.Generic;
using UnityEngine;
public class AStarPathfinder
{
private MazeCell[,] grid;
private int width;
private int depth;
private float cellSizeX;
private float cellSizeZ;
private Vector3 originOffset;
public AStarPathfinder(
MazeCell[,] grid,
int width,
int depth,
float cellSizeX,
float cellSizeZ,
Vector3 originOffset = default)
{
this.grid = grid;
this.width = width;
this.depth = depth;
this.cellSizeX = cellSizeX;
this.cellSizeZ = cellSizeZ;
this.originOffset = originOffset;
}
I pass in cellSizeX, cellSizeZ, and originOffset so the pathfinder can convert grid coordinates back to Unity world space at the end. The maze cells live in a logical grid (integer indices), but the enemy AI needs real Vector3 positions to move to.
The Node class
csharp
class Node
{
public int x, z;
public float g, h;
public float f => g + h;
public Node parent;
public Node(int x, int z)
{
this.x = x;
this.z = z;
}
}
Each node holds:
x, z — grid coordinates (I use Z for depth, matching Unity's coordinate system)
g — cost from the start node to this node
h — heuristic estimate to the goal (Manhattan distance)
f — total estimated cost (g + h); this is what A* uses to prioritise nodes
parent — the node we came from, used to retrace the path at the end
The main search loop
csharp
public List<Vector3> FindPath(Vector2Int start, Vector2Int end)
{
List<Node> open = new List<Node>();
HashSet<(int, int)> closed = new HashSet<(int, int)>();
Node startNode = new Node(start.x, start.y);
Node endNode = new Node(end.x, end.y);
open.Add(startNode);
while (open.Count > 0)
{
// Pick the node with the lowest f score
Node current = open[0];
foreach (var n in open)
if (n.f < current.f)
current = n;
open.Remove(current);
closed.Add((current.x, current.z));
// Goal reached — retrace the path
if (current.x == endNode.x && current.z == endNode.z)
return Retrace(current);
foreach (var neighbor in GetNeighbors(current))
{
if (closed.Contains((neighbor.x, neighbor.z)))
continue;
float newG = current.g + 1;
Node existing = open.Find(n => n.x == neighbor.x && n.z == neighbor.z);
if (existing == null)
{
neighbor.g = newG;
neighbor.h = Manhattan(neighbor, endNode);
neighbor.parent = current;
open.Add(neighbor);
}
else if (newG < existing.g)
{
existing.g = newG;
existing.parent = current;
}
}
}
return null; // No path found
}
A few things worth noting:
The open list is a plain List. A textbook A* implementation uses a priority queue (min-heap) for O(log n) extraction of the lowest-cost node. For my maze sizes (up to 20×20 = 400 cells), a linear scan is fast enough and keeps the code simple. If you're pathfinding on large grids (100×100+), swap this for a SortedSet or a proper priority queue.
The closed set is a HashSet<(int, int)>. This gives O(1) lookups — much faster than a list for checking whether a cell has already been processed.
All step costs are 1. Since we're moving on a uniform grid (each cell is the same size), every step costs the same. If you had terrain weights (mud = 2, road = 0.5), you'd add those here.
FindPath returns null if no path exists. The caller should always check for null before using the result.
The heuristic: Manhattan distance
csharp
private float Manhattan(Node a, Node b)
{
return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.z - b.z);
}
Manhattan distance counts how many steps it would take to reach the goal if there were no walls — purely horizontal and vertical moves. It's the correct heuristic for a grid where you can only move in four directions (no diagonals).
Why not Euclidean distance? Euclidean distance (sqrt(dx² + dz²)) would also work, but it can overestimate the true cost on a grid that doesn't allow diagonal movement. Manhattan distance is admissible — it never overestimates — which guarantees A* finds the optimal path.
The key insight: wall-aware neighbour detection
This is the part that makes this implementation specific to maze navigation. Standard grid A* checks whether adjacent cells exist and aren't obstacles. Maze A* needs to check whether the wall between two cells has been removed.
csharp
private List<Node> GetNeighbors(Node node)
{
List<Node> neighbors = new List<Node>();
MazeCell cell = grid[node.x, node.z];
// RIGHT — can we move to (x+1, z)?
if (node.x + 1 < width && !cell.HasRightWall())
neighbors.Add(new Node(node.x + 1, node.z));
// LEFT — can we move to (x-1, z)?
if (node.x - 1 >= 0 && !cell.HasLeftWall())
neighbors.Add(new Node(node.x - 1, node.z));
// FRONT — can we move to (x, z+1)?
if (node.z + 1 < depth && !cell.HasFrontWall())
neighbors.Add(new Node(node.x, node.z + 1));
// BACK — can we move to (x, z-1)?
if (node.z - 1 >= 0 && !cell.HasBackWall())
neighbors.Add(new Node(node.x, node.z - 1));
return neighbors;
}
Each direction check has two parts:
Bounds check — don't walk off the edge of the grid
Wall check — only add the neighbour if the wall between them has been removed
This is why the MazeCell wall data is so important. The A* algorithm doesn't know the maze was generated with DFS — it just asks each cell "which of your walls are open?" and treats open walls as valid moves.
Converting back to world space
csharp
private List<Vector3> Retrace(Node endNode)
{
List<Vector3> path = new List<Vector3>();
Node current = endNode;
while (current != null)
{
Vector3 pos = new Vector3(
current.x * cellSizeX + originOffset.x,
0.5f,
current.z * cellSizeZ + originOffset.z
);
path.Add(pos);
current = current.parent;
}
path.Reverse();
return path;
}
}
Retrace walks backwards through the parent chain from the goal to the start, building a list of grid positions. Then it reverses the list so it runs start → goal.
Each grid position is converted to a world-space Vector3 by multiplying the cell index by the cell size and adding the origin offset. The y is hardcoded to 0.5f — the vertical centre of a floor-level cell in my scene.
The enemy AI then moves along this list of Vector3 waypoints using Vector3.MoveTowards.
How the enemy uses the path
Once FindPath returns a list of world-space positions, the enemy AI follows them in sequence:
csharp// In the enemy MonoBehaviour
private List<Vector3> path;
private int waypointIndex = 0;
void Update()
{
if (path == null || waypointIndex >= path.Count) return;
Vector3 target = path[waypointIndex];
transform.position = Vector3.MoveTowards(
transform.position,
target,
moveSpeed * Time.deltaTime
);
if (Vector3.Distance(transform.position, target) < 0.05f)
waypointIndex++;
}
The pathfinder is called once when the enemy spawns (or when the player reaches a certain distance away) and the result is cached. For a small maze, recalculating every few seconds is totally fine — but you could also recalculate only when the player changes cells to save performance.
Putting it all together
Here is the flow from game start to enemy movement:
MazeGenerator runs DFS
→ produces MazeCell[,] grid (walls carved)
→ instantiates wall GameObjects in the sceneAStarPathfinder is constructed
→ receives the same MazeCell[,] grid
→ knows cell sizes and world originEnemy spawns
→ calls FindPath(enemyGridPos, playerGridPos)
→ receives List of world waypointsEnemy MonoBehaviour
→ follows waypoints with MoveTowards
→ recalculates path every N seconds (or on player cell change)
The two systems share the MazeCell[,] grid as their single source of truth. The generator writes to it; the pathfinder reads from it. No intermediate data structures, no duplicate wall tracking.
Performance notes
For a 15×15 maze (225 cells), FindPath runs in under 1ms on device. That is fast enough to call every frame if needed, but I recalculate once every 2 seconds in practice, which keeps CPU usage negligible.
If you scale up to larger grids:
Replace the open list with a priority queue. The linear scan for the lowest-f node is O(n) per iteration. At 50×50+ cells this becomes noticeable. C# doesn't have a built-in min-heap, but you can use SortedSet with a custom IComparer, or pull in a priority queue from a NuGet package.
Use a pooled node allocator. Calling new Node() inside a tight loop allocates heap memory and can cause GC spikes. For frequent pathfinding, consider pooling nodes or using a struct-based approach.
Cache the path and recalculate on demand. Don't recalculate every frame unless the maze or player position changes.
What I learned
Building a custom pathfinder instead of relying on Unity's NavMesh taught me a few things:
NavMesh is not always the answer. For dynamic, procedurally generated environments, a grid-based pathfinder that understands your data model (in this case, MazeCell walls) can be simpler, faster, and more accurate than baking a mesh at runtime.
The heuristic matters more than the data structure — at small scales. At maze sizes I'm working with, swapping the list for a heap makes almost no measurable difference. Picking the right heuristic (Manhattan vs Euclidean) has a much bigger effect on path quality.
Wall-awareness is the whole point. Standard A* treats cells as either passable or impassable. Maze pathfinding is more nuanced — a cell is passable from some directions and not others. Encoding that in GetNeighbors rather than as a binary obstacle grid is cleaner and more accurate.
Wrapping up
Here is a summary of everything covered:
DFS generates a connected maze by carving walls between cells, tracked in a MazeCell[,] grid
AStarPathfinder reads that same grid and uses wall data (not obstacle maps) to determine valid moves
Manhattan distance is the correct admissible heuristic for a four-directional grid
Retrace converts grid indices back to world-space Vector3 waypoints
The enemy AI follows those waypoints with Vector3.MoveTowards
The full project — including the maze generator, enemy AI, and more — is in my portfolio:
https://fahadshahbaz.fun/works/AI-Maze-Game
If you have questions about the implementation or want to see the DFS generator code in full, drop a comment below. And if this helped you build something, I'd love to see it.
Abdul Fahad Shahbaz is a Unity game developer based in Lahore, Pakistan, specializing in mobile games, WebGL, and AR. Portfolio: fahadshahbaz.fun
Top comments (0)