A Performance Comparison of Binary Tree, Recursive Backtracking and Aldous-Broder Maze Generation Algorithms with BFS Solving in OCaml

This study aimed to compare the performance of three classical maze generation algorithms including Binary Tree, Recursive Backtracking, and Aldous-Broder in terms of both generation time and subsequent solving time using Breadth-First Search (BFS). Understanding the trade-offs between generation speed and solving efficiency is important for beginners in algorithm design and for applications such as game development and procedural content generation. All three generation algorithms and the BFS solver were implemented in OCaml. Experiments were conducted on a 250×250 grid with the start cell at the bottom-right corner and the goal at the top-left corner. Generation time per algorithm was measured as an average of 20 runs, repeated 50 times with different random seeds. Binary Tree had the fastest average generation time (0.0485 seconds), followed by Recursive Backtracking (0.1416 seconds), while Aldous-Broder was the slowest (4.2691 seconds). However, solving times showed a different pattern: Aldous-Broder produced mazes that were solved the fastest by BFS (0.0029 seconds), followed by Binary Tree (0.0089 seconds), with Recursive Backtracking yielding the longest solving time (0.0243 seconds). These findings indicate that no single algorithm dominates both metrics; the optimal choice depends on whether generation speed or solving speed is prioritized. The results support the hypothesis that Aldous-Broder's uniform spanning tree property leads to more efficiently solvable mazes despite its high generation cost.