A Comparative Study of Maze-Solving Algorithms: Performance, Complexity, and Practical Applications in AI and Robotics

Computer Engineering

Maze-solving is a fundamental problem in computer science and artificial intelligence, with applications in fields such as robotics, video games, and navigation systems. This paper presents a comparative study of several classic maze-solving algorithms, including Depth-First Search (DFS), Breadth-First Search (BFS), A* Algorithm, Dijkstra’s Algorithm, Random Mouse Algorithm, and Wall-Following Algorithm. Each algorithm is evaluated based on performance metrics such as execution time, space complexity, number of nodes expanded, and path length. The study includes implementations of each algorithm and an analysis of their performance across multiple test cases, including mazes of varying sizes and complexities. Through experimentation, we determine the strengths and weaknesses of each algorithm, providing insights into their suitability for different maze-solving scenarios. The findings highlight that while DFS and BFS offer simplicity, A* and Dijkstra provide optimal pathfinding at the cost of increased computational overhead. This paper aims to guide researchers and practitioners in selecting the most appropriate maze-solving algorithm for their specific applications.

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.