A COMPREHENSIVE AND COMPARATIVE STUDY OF DFS, BFS, AND A* SEARCH ALGORITHMS IN A SOLVING THE MAZE TRANSVERSAL PROBLEM
Keywords:
Pathfinding, Maze, Maze Solving, Artificial Intelligence, Search Algorithm, DFS BFS, A*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.
Downloads
Published
How to Cite
Issue
Section
License
Open access and copyright policy
The journal offers access to the contents in the open access system on the principles of non-exclusive license Creative Commons (CC BY 4.0). Thus, the authors are required to agree with that policy. In this regard, authors will be asked to complete a submission card with a copyright transfer agreement that specifies detailed descriptions of the copyright transfer. The submission card is provided via email before the publication.
Publication fee
IJSSASS is a self-funded journal. For this reason, the journal handles a publication fee. The current publication fee is provided on the journal’s Web site in the section Instruction for authors. Thus, the publication fee that is required for manuscript processing is clearly stated on our website