Dijkstra's algorithm

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.

Breadth-first search on a grid

Breadth-first search on a grid

Preparing the grid

Getting the node from an object's position

In order to translate the world space to grid-space, we need to work out what node the object is in, so we can then store info in that node, and then use the node for pathfinding. We will most often have to use this function to get the AI's position and the target's position.

Getting a node's neighbours

To start the pathfinding process, we need to find the neighbours of each node. We can then programming the breadth-first search algorithm. Both of these functions are public so the AI can access them.

Implementing breadth-first search

The basic algorithm

We start off with the current node, which we can find using the AI's position and the nodeFromWorldPoint function we created. We add this node to a list named "openNeighbours" - we'll add to this list all the nodes that we are yet to check. In order to check through the list using a "flood fill" technique (which is the most common, and seemingly most natural method used), we get the neighbours of the current node using the getNeighbours function and add them to the openNeighbours list if they have not been checked already (they should be in the closedNeighbours list if so) and they are walkable. Once we are done checking all the neighbours we can remove the current node from openNeighbours and add it to closedNeighbours so it isn't checked multiple times. This process continues whilst the openNeighbours list is not empty.

The loop can be seen here:

I have also created a visual representation by colouring the current node being checked black whilst the process runs:

Finding a target node

We take the mouse position when the left muse button is clicked and store that position. The mouse position is then converted into game space by using raycasting that is built into Unity (The raycast will get the point that the mouse is aiming at according to the viewer). In the pathfinding process we can then use the raycast hit position and convert it into a node - this node is then taken as the target node.

Early Exit

With a target node, we can now exit the algorithm early so it doesn't check anything unnecessary if the target node has already been found. We do this by simply questioning whether the current node = the target node, if it is true, then we "break" out of the loop.

Here I've marked the target node green, so you can see that the algorithm stops at the correct position:

 

Creating a Grid for Pathfinding

Creating the grid in Unity

What the grid needs

Adjusting and representing the grid for debugging.

Firstly, we need to create two public integers (Numbers that can be accessed by any class) that control the width and length of the grid, and apply the main grid class to an empty object in Unity. The empty object will act as a manager for all our grid/pathfinding based classes and code. We only need the height and width variables as my demonstration will only handle pathfinding on a 2-dimensional scale.

We can see the variables in the properties window of the
empty object, and can adjust the variables accordingly.

Adding the public integers.

We then need to create a node class, which holds all the information for its relative grid node/square.

The node class stores whether the node is walkable, and the position of the node in the world.

Next we need to create a list of nodes the size of the grid, which is the grid's width times the grid's length. We then cycle through each node, giving it its world position and checking to see whether it is walkable or not. The node is then added to the list so it can be stored and used for later.

We then call the OnDrawGizmos function, which renders the specified shape onto the game screen. It's a debug tool as in the game we won't want to see the grid. The OnDrawGizmos function goes through each node in the grid, and renders a cube in the correct position and colours it red if it is not walkable (either there's an obstacle in the way or something else that I can pick). You can see the outcome here: