Analysis of a Range of Optimisation Pathfinding Algorithms

Pathfinding algorithms are used for finding the shortest path in satellite navigation systems, artificial intelligence in computer games, and routing data packets over the internet, as well as a variety of other purposes in computer systems. However, the universal problem encountered in each of these applications of pathfinding algorithms is that there is no ‘perfect’ pathfinder. Pathfinding algorithms that were guaranteed to find the shortest path were typically time and resource-consuming, whereas non-resource-intensive algorithms were unreliable in finding the ideal shortest path.

In order to mitigate the compensation between reliability and performance, computer scientists were able to develop algorithms that combined both the methods used in non-resource demanding pathfinders (Greedy Best-First search) with those utilised in ‘optimal’ pathfinders (Dijkstra’s algorithm). Aiming for a balance between the two extremes, A* (A Star) search algorithm became commonplace in the gaming industry, being flexible in purpose and proven as the most optimally efficient pathfinder possible. Still, A Star search is still not perfect for every application as the implementation is relatively complex compared to a simple pathfinding algorithm like Breadth-First Search, which utilises solely a queue data structure.

As a consequence of the variety of pathfinding algorithms available, many computer programmers are uncertain on what method to use to best suit the purpose of their program. A basic peer-to-peer network that would need to check every node in the network could simply use breadth-first search, whereas a navigation system with traffic warnings and different terrains would need to use Dijkstra’s algorithm to take the cost of a certain path into account. Usually, the ‘best’ pathfinding algorithm to implement is subjective, but some algorithms are better suited and more optimised for a specific purpose than others.

The problem being investigated in my project is the method in which computers dynamically calculate the shortest path from a single starting point to a destination, and how to decide on the pathfinding algorithm with the most suitable characteristics for a particular program.