This article was originally published as: A COMPREHENSIVE AND COMPARATIVE STUDY OF DFS, BFS, AND A* SEARCH ALGORITHMS IN A SOLVING THE MAZE TRANSVERSAL PROBLEM
Original Article Link: Read Original Article
Download PDF: Click Here to Download PDF
Abstract
A search algorithm addresses the challenge of determining the shortest path from the start to the goal while avoiding all possible obstacles. In the quest to design realistic Artificial Intelligence in gaming, we use these algorithms to determine the movement of the agents. The search algorithms for finding the shortest path were implemented using a Maze transversal problem. An agent/player in a maze transversal problem needs a search algorithm to get to its destination and in the least time possible. This algorithm assists an agent/player to travel from the start node to the goal node. The implementation of inappropriate algorithms can alter the length of the computer process for determining the shortest path and the agent/player will have to wait longer as the execution process will take more time. In the Maze transversal problem, pathfinding algorithms, Depth first Search (DFS), Breadth First Search (BFS) and A star (A*) were used for the comparison. The comparison procedure was carried out by running the different algorithms in three (3) mazes with the same dimensions but different obstacles and monitoring the execution time and path length. The findings of this study suggest that the A* search algorithm should be used in the Maze transversal problem as it finds the shortest path to the goal in the shortest possible time and length.
Authors
- Princess Chinemerem Iloh (Teesside university UK)
Keywords
Pathfinding, Maze, Maze Solving, Artificial Intelligence, Search Algorithm, DFS BFS, A*
References
References not available for this article.
