A Comprehensive Investigation of Algorithms for Solving Mazes

Tao Zhu

doi:10.54097/czq2ah04

Authors

Tao Zhu

DOI:

https://doi.org/10.54097/czq2ah04

Keywords:

Maze-solving algorithm; wall-following; backtracking.

Abstract

The maze problem is a classic research topic in artificial intelligence, algorithm design, and path planning. Its core lies in exploring how to find an efficient path from the starting point to the target location within a maze, possessing both theoretical research value and practical application significance. This article provides a comprehensive review of multiple maze-solving algorithms. These include wall-following algorithm, backtracking algorithm, M-DFS, A* algorithm, as well as Maze-solving robot and computer mouse. This paper first provides detailed explanations of the principles for each method. Subsequently, this paper uses tables to clearly compare the Application Scenarios, Time and Space Complexity, and Disadvantages of each approach. Furthermore, this paper analyzes the shortcomings of each method and discuss the future development prospects of maze-solving techniques in light of current technological advancements. Overall, this paper offers readers in-depth explanations of several algorithms, enabling them to better understand the current state of the maze field and its future outlook.

References

[1]Saman ABS, Abdramane I. Solving a reconfigurable maze using hybrid wall follower algorithm. 2013.

[2]Prasetyo TA, Chandra R, Simamora B, et al. Pathfinding solving in maze game using backtracking algorithms. Jurnal CoreIT. 2023;9(1):2599-3321.

[3]Liu XF. M-DFS: A DFS algorithm for solving maze problems. Journal of Tonghua Normal University. 2008;(02).

[4]Barnouti NH, Al-Dabbagh SSM, Naser MAS. Pathfinding in strategy games and maze solving using A* search algorithm. J Comput Commun. 2016;4(11).

[5]Kumar R, Jitoko P, Kumar S, et al. Maze solving robot with automated obstacle avoidance. Procedia Comput Sci. 2017; 105:57-61.

[6]Wyard-Scott L, Meng Q-HM. A potential maze solving algorithm for a micromouse robot. In: IEEE; 1995.

[7]Guo CS, Gong T, Li L. A maze search algorithm for micromouse. Journal of Huazhong University of Science and Technology (Natural Science Edition). 2013;(S1).

[8]Niemczyk R, Zawiślak S. Review of maze solving algorithms for 2D maze and their visualisation. In: International Conference of Students, PhD Students and Young Scientists "Engineer of the XXI Century". Cham: Springer International Publishing; 2018.

[9]Wang A. OCaml-based recursive backtracking and Aldous Broder algorithms in solving maze challenges. In: AIP Conference Proceedings. Vol. 3194. No. 1. AIP Publishing LLC; 2024.

[10]Chan KH, Mustapha A, Lee SC. Shortest pathfinding in a standard rectangular maze using A* search algorithm. Int J Integral Eng. 2024;16(3):244-56.