Interactivity and Movement

Implementing interactivity and movement

Creating waypoints

Retracing the path

In order to produce way-points for the AI to follow, the path needs to be defined by the pathfinding algorithm and then be turned into a usable format for the AI. To do this, we need to add a parent variable for each node, so we can retrace the path from the origin. We then reverse the path so it is in the correct order, going from start node to end node. The path of nodes is then converted into a list of positions, so the AI can then take the path and move from position to position. To make the AI go where we want it, we can make it move towards the next way-point using Unity's inbuilt "lookat" function, then move the AI until it is in proximity with the end node; this method is useful if physics are a key component for the game, but could trigger things such as jams and inaccuracies. Later on, we may need to simplify and smooth the path for a more realistic look.

Managing Units

We also need a way to select different and multiple units. We can do this via traditional techniques such as shift-clicking to select multiple units one by one and with a box-select that the player drags; this selects all units within the box. To create this technique we need to convert mouse position to world space and raycast, checking to see if a friendly unit was hit. Camera movement also needs to be achieved; the camera will need to be moved by screen edge-proximity in terms of the mouse as well as keyboard controls. Camera controls will also need to include zooming in and out as well as rotating. The box select method may need to be included by creating a collider and then checking all collided objects for units, however this could be bad for performance if a lot of objects are selected.

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:

AI Path-finding - Methods and Research

Methods of path-finding 

Base requirements

Graphs

In order to represent the map in a way the AI program can understand, I created a graph. A graph contains a set of nodes, which have data such as their co-ordinates in the game space, travel cost, and traversability. A path-finding algorithm will run fastest with the least number of nodes, due to the fact that less processing is required. 

    The algorithm can use the nodes of the graph to get AI positions relative to the graph, and to move AI to positions on the graph. Each node will have a parent node, so it can reconstruct the path back to the origin.

Breadth-First Search

The breadth-first search algorithm searches equally in all directions, which can be used both for AI, and in other applications such as procedural generation. On a grid this method may also be called "Flood Fill" as it checks progressively outwards from the origin unless the path has already been visited. Even if it finds the target node, the algorithm will not exit early, making the algorithm very unoptimised.

Early Exit

Breadth-first search is currently able to find paths to all nodes on the grid, which can be useful, but makes the algorithm slow. In order to make the algorithm faster, it can exit early, meaning once it finds its target node it stops and uses the first path it finds. However, this may not be the quickest path for the AI to follow.

Dijkstra's Algorithm

Movement Costs

Movement costs can be added to the nodes on the grid, for instance on hills or rivers that we either want the AI to have a preference to avoid or to move slowly across them. Dijkstra's algorithm takes into account movement costs by checking each new path's total movement cost with the current path's - if it's lower, then the new path becomes the current path and so forth.

Optimisation problems

Dijkstra's algorithm only takes into account the cost relative to how far it is away from the start position, the highest cost and untraversable paths are then put into a "checked" list so they don't get processed more than one time. What the algorithm doesn't take into account is the distance from the target node, so the algorithm could check nodes leading away from the target. This also makes it so the path is the shortest in terms of distance from the start node.

Heuristic Search 

In order to get the algorithm searching for a path in the direction of the target node rather than in all directions, we use "Greedy best first search". We can find the distance from each node using Pythagoras - square root(the difference in x coordinates, squared) + (the difference in y coordinates, squared). Greedy best first search uses the distance from the target rather than the start in order to prioritise the checking of nodes. However, this algorithm doesn't work as well when there's a lot of obstacles in the way.

A* Algorithm

The A* algorithm improves obstacle avoidance and the checking of less promising areas by using both the distance from the start and the distance from the target to find the optimal path. It simply adds each distance cost and chooses the node with the lowest cost. This means the path tries to stay as short as possible.