Path Findings & Dijkstra’s Algorithm

Illustration of Dijkstra’s algorithm search for finding path from a start node (lower left, red) to a goal node (upper right, green)

Through the development of my project; SourFang, I needed to implement a tile based movement function. With a bit of research I stumbled upon Dijkstra’s algorithm. The algorithm is designed to fix a single point ( a Node) as the source point (the current position) and find the shortest and most cost effective path to a destination ( a new Node).

This algorithm was particularity useful for me while creating my grid. I created a map that had impassable terrain and areas that I wanted to slow the player as they moved through it. Not only did I need a method to recognize this but also one that would find the most cost effective route to the desired destination.

Dijkstra’s algorithm creates an array of dictionaries that calculate the distance between nodes and all neighboring nodes. To accomplish this, we must first set the source point to 0 and all other nodes as infinity then created a list for these nodes and mark them as “Unvisited”. Once a destination has been provided, starting from the source point, the algorithm will then “talk” to all neighboring nodes and assess their value and will begin mapping the shortest and most cost effective way to reach that point( for example, if the source node has a value of 0 and Node A has a value of 5 while Node B has a value of 8, the algorithm will determine that Node A will be the best node to move to).

Once the source point has moved to a new node, the algorithm will then update and mark all previous nodes as “Visited” meaning it will now ignore previous nodes as a potential path to the destination.

Dijkstra’s algorithm to find the shortest path between a and b.

Dijkstra’s method isn't the only method used for cost effective path finding. A* (A-Star) provides another method for reaching this goal and is in fact used more commonly than Dijkstra’s algorithm but comes with the cost of more code and outside functions. A* is a derivative of Dijkstra’s that cuts down on the size and time of map that must be explored, if additional functions and code exists.

Illustration of A* search for finding path from a start node to a goal node

The reason I chose Dijkstra’s algorithm over A* was due to the fact that Dijkstra’s method uses less code and provides a 100% guarantee way to reaching a destination in the shortest way possible, it may be more taxing and time consuming for the path system to be identified, but at the cost of quality I felt it suited my needs perfectly. A*, from what I have gathered, tends to create awkward and unusual pathways when attempting to navigate to the destination.

It wasn’t easy easy at first trying to get all this to function properly but through a bit of patience and drama the errors slowly dwindled.

For future projects, I’ll most likely stick to Dijkstra’s if the need arises for a path finding function. It’s cost effective and reliable and is the source that many other algorithms tend to draw from for path finding.

REFERENCES:

Dijkstra’s Algorithm

A* Algorithm