Building a fair race from DFS mazes and A* pathfinding

The AI Maze Game began as a focused experiment: generate a different solvable maze every session, then give the player an opponent capable of reading that space intelligently.

The design problem

A random maze is only useful when every generated layout is connected and completable. The opponent also needs to find a strong route without feeling like it is simply teleporting or cheating. That made generation, navigation, and game balance parts of the same problem.

Generating the play space

I used recursive Depth-First Search to carve passages between cells. The algorithm produces a spanning tree, so every cell remains connected and the finish is always reachable. Because the maze is generated at runtime, the player cannot solve the experience through memorization alone.

Generate maze → Build navigation graph → Place goal → Calculate route

Teaching the bot to navigate

The AI uses A* search with Manhattan distance as its heuristic. Open and closed sets keep the search controlled, while the heuristic fits the grid because movement happens along orthogonal connections. The resulting node path is translated into movement targets for the bot controller.

Keeping the race interesting

The shortest path is not enough to create good competition. Power-ups give the player temporary advantages and dead-end penalties make navigation decisions matter. These systems add uncertainty without undermining the maze logic.

What the project demonstrated

The project connected graph traversal, heuristic search, procedural content generation, game-state management, and moment-to-moment balancing in one playable system. It also reinforced the value of separating generation data from the visual representation of the maze.