The Maze Game

How I Built Pathfinding Systems for Puzzle Games

I started with a simple grid-based maze generator and spent three days debugging why the pathfinder kept returning paths that cut through walls. The issue was a floating-point precision error in the A* heuristic calculation. When coordinates were very close together, the open-set sorting would occasionally prefer a node that visually lay outside the traversable area. The fix was rounding all distance calculations to six decimal places before comparing them. This is the kind of problem you only notice when you have actual players reporting impossible routes. The core loop of any maze game runs on two systems: the generator and the solver. The generator creates a traversable graph by starting with a solid block of cells and recursively removing walls using a randomized depth-first search or Wilson's algorithm if you need uniform spanning trees. The solver then finds paths through that graph using BFS for shortest unweighted routes or A* when you want heuristic-guided exploration. Both systems operate on the same adjacency representation, so they must agree on what counts as walkable. Disagreement between them is the most common source of bugs I see in shipped titles. Here is the practical setup I use for a Java-based implementation. The grid is a two-dimensional array of Cell objects, each holding four boolean wall flags and a list of neighbor references. The generator runs once at level start and writes its result into a byte-encoded bitmap that the solver reads without touching the Cell layer. This separation means the solver can be swapped for different algorithms without regenerating the maze. I cache the generated maze as a 16-byte-per-row bitset, which reduces memory usage by about sixty percent compared to the full Cell object model.

The pathfinding itself is straightforward A* with Manhattan distance as the heuristic. The open set is a TreeSet ordered by F score. The closed set is a boolean array aligned to the grid dimensions. When the algorithm finds the target, it reconstructs the path by following parent pointers backwards. I always include a visited check before adding neighbors to the open set, otherwise the algorithm degenerates to exponential time on dense grids. The worst case for this particular setup is roughly forty milliseconds per level on a mid-range CPU, which is plenty fast for real-time play. One edge case that cost me a week of debugging involves diagonal movement. If you allow diagonal traversal, the heuristic must be adjusted to Chebyshev distance instead of Manhattan, or the algorithm will overestimate costs and return suboptimal paths. I learned this the hard way when a player reported that the exit was reachable in fewer steps than the solver claimed. The discrepancy was exactly the diagonal shortcut that my heuristic was ignoring. Changing the heuristic to max(|dx|, |dy|) fixed it immediately. Another issue is open-set overflow with large mazes. The TreeSet implementation of the open set has O(log n) insertion and removal, which is fine for small grids but becomes a bottleneck above twenty by twenty. I switched to a bucket-based priority queue using coordinate hashing, which brought the performance down to roughly ten milliseconds on a one-hundred-by-one-hundred grid. The tradeoff is about two hundred extra lines of code, but the speed difference is noticeable during level transitions.

The Maze Game also needs consistent state management when the player moves. I store the player position as a separate coordinate that gets updated on each input frame, not inside the maze generation tick. This prevents the solver from calculating paths for stale positions. When the player teleports or the level restarts, the input handler clears the path cache before updating the position. Without this, you get phantom paths that lead to the previous level's exit. There are genuine downsides to this approach that beginners often miss. The primary limitation is that A* with a static grid cannot handle moving obstacles. If you need dynamic environment changes, you have to rebuild the graph or switch to a different algorithm entirely. D* Lite is the standard alternative, but it adds significant complexity and roughly doubles the implementation time. For most puzzle games, static mazes are sufficient, and the extra engineering cost is not justified. A secondary limitation is memory usage on very large mazes. The closed set boolean array scales linearly with the grid size, so a one-thousand-by-one-thousand grid requires about one megabyte just for visited tracking. The path bitmap adds another quarter megabyte. This is manageable on modern hardware, but it becomes a constraint on mobile devices where memory budgets are tighter. I encountered this during a port to Android and had to implement a chunked closed set to keep the heap under fifty megabytes per level.

If you want a working implementation to study, the source code for this exact setup is available on GitHub under the repository name maze-game-pathfinder. It includes the Cell model, the DFS generator, the A* solver with both Manhattan and Chebyshev heuristics, and the bucket priority queue optimization. The README has setup instructions for running the reference implementation, which takes about five minutes on a standard Java 21 environment. The commit history documents the diagonal movement bug and the open-set overflow fix with before-and-after benchmarks. The maze generation quality depends heavily on the randomness source. I use ThreadLocalRandom for single-threaded generation because it is faster than SecureRandom and the mazes do not need cryptographic security. SecureRandom added about twelve milliseconds per level, which is negligible for menu screens but noticeable during rapid level replay. For the released version, I stuck with the faster option and accepted the lower entropy. Testing is where most projects stall. I wrote a property-based test that generates one thousand random mazes per run and verifies that every cell is reachable from the start position using BFS. If any cell is unreachable, the test fails and prints the seed. This caught the diagonal heuristic bug before it reached players. The test suite runs in about three seconds, which fits comfortably inside a pre-commit hook.

The final detail that matters is visual path smoothing. Raw A* output contains unnecessary turns where the algorithm bounces between adjacent open cells before committing to a direction. I added a post-processing step that removes collinear waypoints, reducing the visual path length by roughly fifteen percent without changing the actual shortest distance. Players notice this even if they cannot explain why, and it makes the gameplay feel more responsive.