Performance Verification of BFS For Unweighted Maze Solving: A Comparative Analysis with DFS and A* Via Ocaml Implementation

Hongjia Du

doi:10.54097/b1m57229

Authors

Hongjia Du

DOI:

https://doi.org/10.54097/b1m57229

Keywords:

DFS; BFS; A*; Maze algorithm.

Abstract

Maze solving is a key pathfinding problem with applications in robotic navigation and game Artificial Intelligence (AI). This study focuses on verifying Breadth-First Search (BFS)’s advantages in unweighted mazes, comparing it with Depth-First Search (DFS) and the A* algorithm via OCaml implementation. Five typical mazes (simple, complex, enclosed, empty, duplicate) were designed, with performance evaluated using metrics: path length, traversed nodes, solving time, and shortest path guarantee. Results show BFS consistently guarantees the shortest path (unlike DFS, which falls into depth traps) and has stable efficiency—outperforming A* in small/simple mazes by avoiding heuristic calculation overhead. BFS’s simplicity (relying on basic data structures) and strong adaptability across maze types confirm it as the ideal choice for unweighted maze solving. These findings also highlight its educational value as a baseline algorithm for introducing pathfinding concepts. Future work may extend to weighted mazes, heuristic refinements, and hybrid algorithms combining BFS with optimization strategies.

References

[1]Nilsson NJ. Principles of Artificial Intelligence. Tioga Pub Co; 1982.

[2]Aho AV, Hopcroft JE, Ullman JD. Data Structures and Algorithms. Addison-Wesley; 1983.

[3]Hart PE, Nilsson NJ, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern. 1968;4(2):100-7.

[4]Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 3rd ed. MIT Press; 2009.

[5]Bundy A, editor. Catalogue of Artificial Intelligence Tools. Springer-Verlag; 1984.

[6]Dong DJ, Dong SY, Zhang LL, Cai YZ. Path Planning Based on A-Star and Dynamic Window Approach Algorithm for Wild Environment. J Shanghai Jiao Tong Univ (Sci). 2024;29(4):725-36.

[7]Bagnall AJ, Zatuchna V. On the Classification of Maze Problems. In: Bull L, Kovacs T, editors. Foundations of Learning Classifier Systems. Stud Fuzz Soft Comput. Vol. 183. Springer; 2005. p. 305-24. doi:10.1007/11319122_12.

[8]Semizer Y, Yu D, Wan Q, et al. Effects of maze appearance on maze solving. Atten Percept Psychophys. 2025; 87:637-49. doi:10.3758/s13414-024-03000-7.

[9]Kozen DC. Depth-First and Breadth-First Search. In: The Design and Analysis of Algorithms. Texts Monogr Comput Sci. Springer; 1992. p. 19-32. doi:10.1007/978-1-4612-4400-4_4.

[10]Ren J, Li A. Depth First Search. In: Silicon Valley Python Engineer Interview Guide. Springer; 2025. p. 235-46. doi:10.1007/978-981-96-3201-5_15.