Complexity Comparison and Analysis of Maze Algorithms

Abstract

Maze generation and solving algorithms are widely used in areas such as path planning and game design. However, existing research has primarily focused on optimizing the performance of individual algorithms. To address this limitation, this study analyzes four maze generation algorithms and four maze-solving algorithms. The article firstly introduces the core principles, implementation and key characteristics of each algorithm. It then systematically evaluates their time complexity and space complexity. The results show that among the generation algorithms, the binary tree algorithm is the most efficient but produces biased maze structures. The Prim's algorithm generates highly complex mazes at the expense of substantial space and time requirements. Among solving algorithms, A-star algorithm achieves optimal ideal efficiency Ω(n) when equipped with a well-designed heuristic function. BFS and DFS are highly efficient, but they can only fit unweighted paths. This study provides a theoretical basis for algorithm selection. Future work will involve experimental measurements of the actual runtime performance of these algorithms.