Dig Trig

Dijkstra's Algorithm

Dijkstra's Algorithm calculates the shortest path from one node to another node by evaluating the cost to travel each node.

1. Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.
2. Mark all nodes as unvisited. Set initial node as current.
3. For current node, consider all its unvisited neighbors and calculate their tentative distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 1.4, the distance to B through A will be 6+1.4=7.4. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance.
4. When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal.
5. If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node) as the next "current node" and continue from step 3.

In this grid, I am setting the cost of traversal to be 1.0 for nodes directly above/below/right/left and 1.4 for nodes diagonally adjacent (1.4 = sqrt(2)). I am making terrain type be a multiplier. Green grass is x1, Brown rock is x2 and Blue water is x3. This represents difficulty in traversing the terrain (eg rock is twice as difficult to traverse than grass). Black void is considered impossible to traverse. Once a path to the target is found, it backtracks to the start finding the best path(s).

Controls:

   Find Pathing Clear Pathing Clear Grid          Randomize Terrain