Pathfinding

There are many applications for finding the best route from a starting point to a destination. In games and maps, this this is to find the physical route from two points. Here, when we talk about best route, it's not necessarily the shortest route in number of jumps, but the route which costs the least.

The basic algorithms start with breadth first search (BFS), which looks at all the possible choices starting with those closest to the starting point. Depth first search (DFS) isn't really viable since the map could be quite big and even if we did discover an solution, we wouldn't know if it was the shortest path. If the cost of edges between nodes are different, even BFS isn't sufficient since it is dependent on the number of jumps. In order to account for this, Dijkstra's algorithm is used. Dijkstra's traverses nodes assigning distances that it takes to go to any node from the initial node. If a node is assigned a lower distance value through traversal, it is kept in the priority queue for future traversal. This repeats until we encounter the target node.

A* and variants

The A* (A-star) search algorithm builds on Dijkstra's algorithm by introducing a heruistic in addition to the cost from the initial node. A heruistic is an approximation of the cost it takes to get to the goal or simply how far we think it will take to get to the goal from a particular node. If we guarantee that the heruistic function never underestimates the distance from a particular node to the goal then A* will be able to find an optimal path.

For many applications where the terrain being traversed is static, navigation meshs (navmesh) are baked, or generated, beforehand. Navigation meshes are a simplified graph representation of a map which marks key points and branches as nodes and the interconnections between them. This would mean that instead of every grid square being a node, each room and hallway might be a node. By doing this simplificaiton up front, we can drastically reduce the amount of nodes which need to be traversed when we try to find a path. In mapping applications, we would be able to simplify the map to have nodes only at intersections.

Replanning

As we encounter more complicated real world situations, we see that there are many situations where costs are adjusted as we are making progress along our path. This may be due to a lack of knowledge of certain costs or changing situations such as a weather storm which blocked a road. In these situations we need to replan our route. While we could recalculate the route like we did originally, having a route and previous knowledge helps us with replanning our new route. There are a number of papers exploring this topic.

Further Reading