Comparative Analysis of Breadth First Search (BFS) Algorithm and A* Algorithm
In path planning there are several methods that can be used. The methods that can be used for path planning are the Breadth First Search (BFS) algorithm and the A* algorithm. The method used depends on the environmental conditions. Doing path planning in each environment with different methods so that you can find out how the performance of each method is. So the purpose of this study is to compare the BFS algorithm with the A* algorithm in doing path planning. The comparison process was carried out in five test environments. The test environment used is without obstacles, obstacle traps, simple obstacles, maze obstacles and narrow obstacles. Comparison of the BFS algorithm and the A* algorithm based on the execution time and the number of nodes required to perform path planning. The results show that the path search from the starting point to the destination point can be completed using the BFS and A* algorithms. Both the BFS and A* algorithms produce the same path costs. The difference occurs in the nodes required by the BFS and A* algorithms to generate a path from the starting point to the destination point. The BFS algorithm requires more nodes than A* to reach the destination point. The difference in the number of nodes makes the execution time different. The execution time of the BFS algorithm takes longer than A*. Based on the tests that have been carried out, the A* algorithm is faster in planning paths. But in the maze test environment there is a slight time difference. On BFS it takes the fastest time of 4.09 seconds and on A* it takes the fastest time of 3.88 seconds. And in the maze environment, there are quite a few differences in the number of nodes, namely 26 nodes. This proves that A* is not always far superior to BFS.