A Study on the Performance Based on Aldous-Broder Randomness and A* Structured Generation

Abstract

The objective of this research was to analyze how different maze generation algorithms manage the trade-off between efficiency and randomness. Maze generation is significant in artificial intelligence, robotics, and game design, where performance and (structural variety directly influence outcomes. The methods involved implementing Aldous-Broder and A* algorithms in OCaml on standardized grid-based mazes. Aldous-Broder relies on random walks to generate uniform spanning trees, while A* applies heuristic-driven search to guide wall removal. The experiments were conducted across various maze sizes, with execution time, branching factor, and corridor length as core metrics. Each configuration was tested through repeated trials to capture variance, and results were summarized using median values and dispersion analysis. This design ensured fairness in comparison while emphasizing scalability and structural differences. The results show that Aldous-Broder achieves uniformity but at high computational cost, whereas A* provides faster generation but creates biased layouts. The findings highlight the inherent trade-off between structural neutrality and efficiency, pointing to hybrid solutions as a promising direction.