Implementing Dijkstra's algorithm
Preparing the grid and node classes
Movement Costs
In order to accurately represent different types of terrain, nodes could have a movement cost. For example, a unit may move slower through grass and therefore to find the quickest path, the AI would prefer to take a faster path. To store the movement cost information, we need to create a new variable in the node class:
Detecting movement costs
One method of detecting different types of terrain is to use the same function as when we needed to detect unwalkable objects. We do this for each node and set the movement cost accordingly. For more advanced terrain and cleaner code a class for each terrain could be made that stores things such as movement cost, colour and texture, however for this purpose the movement cost can just be set manually.
The algorithm
Checking nodes
We check each node as we did before, but this time we need to calculate the distance of each node from the start and then assign that to the node's cost. We use Pythagoras to calculate the distance from each node, and then the node is added to the openNeighbours list.
Priority Queue
A priority queue is used to prioritise the checking of nodes by using the distance of the nodes from the start position. I've done this by looping through the openNeighbours list and comparing each node which then results in the lowest cost node which is now the current node. This process repeats until the target node is found. The results of the algorithm include shorter paths, a higher efficiency (This may not be the case when using my method of looping through the list to find the lowest node and an optimisation such as a binary heap could be used) and the interactivity and avoiding of different terrains.
The algorithm can be seen to avoid the blue, more difficult to cross terrain in favour of the grey, faster ground. However, the algorithm does check the cyan at the end when the grey path has a greater distance and is therefore slower than moving through the cyan. If a path were to be calculated, though, the grey path would take priority in this case as the blue nodes were only checked, but did not result in a faster path.
