How I implemented A* pathfinding in Unity C# (with DFS maze generation)

Unity game developer Abdul Fahad Shahbaz implemented A* pathfinding and DFS maze generation in C# for an AI-driven 3D maze game. The procedural maze is generated using iterative Depth-First Search, and a custom A* pathfinder navigates the grid-based maze in real time, avoiding Unity's built-in NavMesh which cannot handle runtime-generated geometry.

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 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 scene AStarPathfinder is constructed → receives the same MazeCell , grid → knows cell sizes and world origin Enemy spawns → calls FindPath enemyGridPos, playerGridPos → receives List of world waypoints Enemy 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 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