Comparison between A*, BFS and DFS algorithms in 3D grids

Abstract

Pathfinding algorithms are computer algorithms that aim to find a path through a grid with obstacles. A pathfinding algorithm works by taking a search grid with obstacle cells, a source cell and a destination cell, and searching outward from the source cell until it finds the destination cell. This research paper compares three pathfinding algorithms when they are made to search a 3D grid instead of a 2D grid. The algorithms tested are the A* search, breadth-first search and depth-first search. Each of the three algorithms is used to search a series of 3D grids with increasing obstacle density to determine which performs the best in terms of time taken to find the destination, length of the resulting path, and the number of cells searched to find the destination. These three metrics are graphed for each algorithm against the obstacle density of the grids to compare them. The results of the experiment prove decisively that in a 3D graph, the A* search algorithm performs the best across all three metrics due to its nature as an informed search algorithm.