A Comparative Analysis of DFS, Eller’s and Wilson’s Algorithms for Maze Generation

Abstract

Due to their theoretical importance and wide range of practical applications, maze generation algorithms have received significant attention. The generation of a perfect maze, which is defined as a structure with only one path between any two points, can be done using different algorithms that have distinct features and trade-offs. The purpose of this paper is to evaluate the performance of three widely studied methods, Deep-first Search (DFS), Eller's algorithm, and Wilson's algorithm, across time complexity, space complexity, and randomness. DFS is fast and simple, but tends to create long winding paths with structural bias. Eller’s algorithm constructs mazes row by row, ensuring efficiency and memory savings while balancing connectivity and randomness. Wilson’s algorithm, though slower and more memory demanding, is capable of producing uniform mazes with high randomness, making it useful for benchmarking and testing scenarios. The comparative results show that all three algorithms achieve linear time complexity but differ substantially in spatial efficiency and maze characteristics. These findings highlight the practical importance of algorithm choice: DFS is suited for real-time applications requiring speed, Eller’s provides a compromise between efficiency and diversity, and Wilson’s offers unbiased randomness for research or AI applications. Insights from this study are used to guide the selection of maze generation algorithms for different computational and applied contexts.