Algorithmic Evolution in Maze Generation: From Classical Backtracking to Reinforcement Learning Optimization

Abstract

This survey addresses the critical gaps in current research on maze generation algorithms, which include a predominant focus on perfect mazes, insufficient difficulty calibration frameworks, and limitations in handling non-planar topologies. These algorithms are vital across multiple disciplines, such as computer science, entertainment design, psychological experimentation, and autonomous navigation, as they enable the creation of complex spatial environments for testing, learning, and problem-solving applications. This paper systematically reviews classical algorithms, including Recursive Backtracker for depth-first efficiency, Kruskal's for uniform randomness, and Prim's for branching structures, alongside advanced techniques like Ant Colony Optimization for biomimetic layouts, Reinforcement Learning hybrids for parameterized control, and Wilson's algorithm for mathematical uniformity. The methods involve comparative analysis of structural properties, computational efficiency, and real-world implementation challenges across diverse dimensional configurations. The findings reveal that recent advances resolve key research deficiencies, such as enabling non-perfect maze generation with 5.7% error reduction in loop-density control and achieving 38% faster convergence in optimization. Empirical validations demonstrate effective applications in game design for dynamic difficulty scaling, robotic navigation for pathfinding accuracy, and psychological tools for cognitive assessment. This review establishes a robust foundation for future work in volumetric maze optimization and cognitive bias quantification, advancing spatial computing theory and interdisciplinary applications.