Pathfinding and Navigation

Abstract

Pathfinding is the algorithmic interpretation and implementation of attaining the shortest route(s) from a given source(s) to destination(s). While the paradigm falls under generic graph theory, there has been much research about different heuristic algorithms. The fundamental aspects of choosing the best-fit (least cost) route implies certain heuristics to be followed. In this section we will try to understand the different concepts of heuristic search algorithms, starting from basic Dijkstra Algorithm to variants of A* (A star). The need for different search algorithms is extremely essential since generic exhaustive algorithms such as breadth-first search (BFS) and depth first search (DFS) are not feasible for games, simulations, and robotics. As we proceed into the depths of each heuristic algorithm, we will encounter different trade-off metrics being employed, from time complexity to space complexity. We will also explore the fundamental aspects of navigation meshes and how to create an intelligent pathfinding agent that gets rewards when it reaches and finds the target object.