Basic Ideas in Pathfinding

Dijkstra's algorithm

Dijkstra's is a very well known pathfinding algorithm that finds the shortest paths between nodes by traversing the nodes in the order of least distances.

Explanation

We first assign the distance to all nodes as infinity except the one we start at, which is assigned a 0. At each step, we move to the neigbouring node which has the least distance assigned to it. We then assign the distances to all the adjacent nodes based on the distance to the current node, added to the edge weight, ie, the distance between the nodes. We only assign distances to a node if it is lesser than the distance we had already achieved. A remarkable property of this algorithm is that, whenever we 'move' to a node, it's distance is fixed, and that is the shortest distance.

Implementation

for (int i = 1; i <= n; i++) distance[i] = INF;
distance[x] = 0;
q.push({0,x});
while (!q.empty()) {
int a = q.top().second; q.pop();
if (processed[a]) continue;
processed[a] = true;
for (auto u : adj[a]) {
int b = u.first, w = u.second;
if (distance[a]+w < distance[b]) {
distance[b] = distance[a]+w;
q.push({-distance[b],b});
}

Generally, a priority queue (denoted by q) is used that always has the maximum valued node at the top. Since we are interested in the minimum value, we use negative values instead of modifying the data-structure.

Notice how the algorithm checks it's neighbouring nodes in the order they were added (which could be any random). This could highly affect computation time since we might analyse nodes in the 'wrong' (less efficient) order and end up doing more calculations than needed. That is where A-star adds some sort of direction to the processing of nodes.

A-star algorithm

A-star is the most popular path-finding algorithm in use today. It is an extension of Dijkstra's and uses some other information to proceed with the processing of nodes.

Explanation

The algorithm always goes in the direction which it feels might lead to the shortest path using estimations based on a heuristic's function. We define a new function f(n) = g(n) + h(n). Unlike Dikjstra's at each step, which uses only the distance to the node (g(n)) we also use an estimation of how far the node might be from it's end goal (h(n)). In most cases, the heuristics function will be a Manhattan Distance (Fast Distance) or a Euclidean Distance (Actual Distance).

Implementation

The implementation of A-star is almost the same, except, instead of only calculating distance at each node, we calculate the distance + heuristic (g + h).

Theta Star

In most games, the easiest way to represent the terrain is by using grids. Since, Terasology is voxel based, it makes it even easier. However, this poses some problems for pathfinding. Since the neighbours to every node are available in the 8 directions, it limits our path possibilities to 45 degree paths which may not necessary be the shortest path. That's where Theta star steps in. This is an extension to A star with a difference in the update vertex step (The step where we move to a node). The parent of a node can be any node which has a line of sight to the current node, not just it's neighbour. //Implementation and detailed explanation TODO since not too relevant.

https://arxiv.org/pdf/1401.3843.pdf