Authors : Atharv Patil

Volume/Issue : Volume 10 - 2025, Issue 2 - February

Google Scholar : https://tinyurl.com/5n7rf76r

Scribd : https://tinyurl.com/msaabywj

DOI : https://doi.org/10.5281/zenodo.14915594

Abstract : AI pathfinding is essential for autonomous transport and many other industries, for example, bot movement inside video games, navigation, and logistics in mapping applications. This paper compares DFS (depth-first search), BFS (breadth-first search), Dijkstra, and A* (A-star) algorithms. A* uses adaptive training to locate the direction needed to move from the start point to the endpoint, and proceeds to move only in that direction. Dijkstra and BFS expand in all directions, updating the least recent node in the case of BFS, or at random with Dijkstra. Lastly, DFS has a set algorithm with a priority of directions that update on the most recent node. The objective of pathfinding is to help the algorithm navigate from point A to point B in a manner where it does not cross obstacles, but still in the fastest time. Results are still ongoing in this ever-changing field; however, in conclusion, A* has proved to be the most efficient at balancing speed with results. Results from the analysis prove that A* was the fastest at completing the computing and traversing while loading the fewest number of nodes. DFS took the longest and Dijkstra loaded the most nodes and took the longest to compute.

References :

4. Graham, Ross, et al. “Pathfinding in Computer Games.” ARROW@TU Dublin, arrow.tudublin.ie/itbj/vol4/iss2/6/. Accessed 2. Aug. 2024. https://arrow.tudublin.ie/itbj/vol4/iss2/6/ Computer, Pathfinding This article is about the design of AI pathfinding technologies concerning game design. Use of top-down simulations similar to my part of the secondary data analysis.
5. “Pathfinding Using AI Algorithms.” Baza Wiedzy Politechniki Warszawskiej, 1 Jan. 1970,repo.pw.edu.pl/info/bachelor/WUTc1a5c774c8442e78b129cbde56fc1fa/. https://www.google.com/url?sa=t&rct=j&q=&e src=s&source=web&cd=&ved=2ahUKEwj47J SAxNWHAxV2STABHauKEX0QFnoECBUQAQ&url=https%3A%2F%2Frepo.pw.edu.pl%2Fdocstore%2Fdownload%2FWUT8aeb20bbb6 964b7da1cfefbf2e370139%2F1-s2.0-S0952197617301227-main.pdf&usg=AOvVaw15nWVV ZFQgr6W7gB91Mc7s&opi=89978449 Neural Network, AI Talks about the detection of body parts which is useful in being able to differentiate different objects when pathfinding. It also provides a graph on the tree of detection.
6. Stout, Bryan. “Smart Moves: Intelligent Pathfinding.” Gamasutra - Smart Moves: Intelligent Pathfinding, Game Developer Magazine, July 1997, folk.idi.ntnu.no/agnar/it272/pekere/local/pathfi nding.htm. Pathfinding, Algorithms Shows the differences in training costs for maneuvering models around obstacles. Demonstrates how pathfinding logic of punishments and incentives work to change.
7. Anisyah, Ani Siti, et al. “Route Optimization Movement of Tugboat with A∗ Tactical Pathfinding in Spin 3D Simulation | Request PDF.” Researchgate.Net, research gate, Dec. 2015, www.researchgate.net/publication/307802157_Route_optimization_movement_of_tugboat_with_A_tactical_pathfinding_in_SPIN_3D_simulation. Pathfinding, Reward Systems, Simulation Demonstrates the optimization of a tugboat using A*. This is shown by using fuel as a punishment to influence the tugboat to choose the shortest path.
8. “View of Cooperative Pathfinding.” Aaai.org, 2024, ojs.aaai.org/index.php/AIIDE/article/view/1872 6/18503. Accessed 10 Aug. 2024. Pathfinding, Collective This paper shows the difference in different pathfinding algorithms of A*. Demonstrates the difference within variations of incentive models, including Manhattan and Elucid.
9. Geeks for Geeks. “Breadth First Search or BFS for a Graph.” Geeks for Geeks, Geeks for Geeks, 20 Mar. 2012, www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/. Accessed 10 Aug. 2024. Algorithms, Pathfinding Shows the time necessity as a punishment/reward for BFS. Also provides code in various languages for BFS to disclose how the reward system works while using a node map to simplify the algorithm.
10. Wikipedia Contributors. “A* Search Algorithm.” Wikipedia, Wikimedia Foundation, 28 June 2024, en.wikipedia.org/wiki/A*_search_algorithm#:~:text=13%20External%20links-,Histo ry,algorithm%20for%20Shakey’s%20path%2 0planning. Accessed 10 Aug. 2024. Algorithm, Formula Gives the mathematical equation for A* and the history of the development. Also provides more understanding of path trees and the reward and search system of A*.
11. Aglubagerry. “A* Search Real-Life Application.” Medium, Medium, 10 Oct. 2023, medium.com/@aglubagerry/a-search-re al-life-application-2bd175624952. Algorithm, Applications Provides examples of the real-life applications of A*. Also depicts how A* is used in specific cases and how it is essential to those tasks.
12. Schulz, Frank & Wagner, Dorothea & Weihe, Karsten. (1999). Dijkstra’s Algorithm On-Line: An Empirical Case Study from Public Railroad Transport. Algorithm Engineering. 1668. 110-123. 10.1007/3-540-48318-7_11. Algorithm, Applications, Pathfinding Compare the distances with the pathfinding of German public railroads. Describes the application of Dijkstra's algorithm in this use case.
13. Burger, Alewyn & de Villiers, Anton & Vuuren, J.H.. (2013). Two algorithms for secure graph domination. JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing. 85. Algorithm, Applications Uses DFS to differentiate parts of a search tree. Checks for specific categories using DFS and provides the results of the tree with symbols.
14. Abd Algfoor, Zeyad & Sunar, Mohd Shahrizal & Kolivand, Hoshang. (2015). A Comprehensive Study on Pathfinding Techniques for Robotics and Video Games. International Journal of Computer Games Technology. 2015. 1-11. 10.1155/2015/736138. Pathfinding, Simulation, Reward Systems Reviews the last 10 years of pathfinding algorithms and their development. Gives areas for future growth and current areas being explored. Delves into real-life examples in robotics and video games.
15. Kilic, Kemal & Mostarda, Leonardo. (2021). Heuristic Drone Pathfinding Over Optimized Charging Station Grid. IEEE Access. 1-1. 10.1109/ACCESS.2021.3134459. Pathfinding, Applications Uses a grid of nodes on a 2d field as pathfinding heuristics for the indoor drone. Calculates charging times factored in for the overall speed of the indoor drone path. Additionally, this paper provides information on having multiple heuristics monitored at once using various metrics. algorithm results, as well as a history of all algorithms and their applications.
16. Permana, Silvester & Bintoro, Ketut & Arifitama, Budi & Syahputra, Ade. (2018). Comparative Analysis of Pathfinding Algorithms A *, Dijkstra, and BFS on Maze Runner Game. IJISTECH (International Journal Of Information System & Technology). 1. 1. 10.30645/ijistech.v1i2.7. Algorithms, Collective Compares A*, Dijkstra, and BFS to find what performed best in a grid format. Analyzes the number of nodes searched compared to traveling speed on average.
17. Kaur, Navneet, and Deepak Garg. “Analysis of the Depth First Search Algorithms.” Gdeepak.Com, Thapar University, www.gdeepak.com/pubs/Analysis of the Depth First Search Algorithms.pdf. Accessed 28 Jan. 2025. Algorithms, Analysis Analyzes DFS algorithms using visual graphs to explain the methods DFS searches by Highlights areas for the algorithm’s improvement, while mentioning how it works. Provides code for DFS that was used to base the paper off.
18. Pardede, Sara Lutami. “A Review of Pathfinding in Game Development.” Cloudfront.Net, CEPAT Journal of Computer Engineering, May 2022, d1wqtxts1xzle7.cloudfront.net/91399669 Accessed 28 Jan. 2025. Algorithms, Analysis, Pathfinding Depicts several algorithms using a 2d grid-based node network to visually simplify them. Explains the use of Dijkstra for finding the shortest path in Japanese districts using the public road system.