Shortest Pathfinding in a Standard Rectangular Maze using A* Search Algorithm

Abstract

Mazes are defined as a complicated system that consisted of paths or passages that causes confusion. A large-sized maze can be difficult or impossible to be solved by hand due to high time consumption. This paper presents a solution based on the A* algorithm to find the shortest route. A* algorithm is a searching algorithm that is used to find the shortest path between the initial and the final state. Two heuristic approaches are used and compared using the Manhattan and Euclidean distance. In this paper, A* algorithm is used to solve several sizes and several types of rectangular maze and is evaluated based on the average time in solving a maze for one hundred times under various scenarios. Performance evalution includes mazes with wider paths and multiple routes. Limitations arise when dealing with mazes lacking start or end points. The performance comparison favours Manhattan distance due to its efficiency over Euclidean distance. Further exploration is recommended, including the evaluation of both heuristics on larger, more complex mazes. Additionally, the study identifies the A* algorithm’s need for modification to handle mazes without defined starting or ending points. This research underscores the suitability of the Manhattan distance heuristic and suggests potential extensions of the A* algorithm to dynamic, changing, and multi-agent maze environments.