The A-Star Algorithm

A-Star Pathfinding

Individual unit requests

First of all, we need to tie the existing pathfinding algorithm to each unit so the player can move them individually. I've written this code in the unit manager class so that when the player right clicks, all highlighted/selected units are queued for pathfinding.

This runs the "startPath" function in each object's basic unit class. This function queues the unit for pathfinding with the unit's current position. When pathfinding is complete, the path manager class then runs the callback function, which in this case is "onPathFound".

The "onPathFound" function stops any current movement coroutines and starts a new movement coroutine if the pathfinding algorithm was successful. The movement coroutine moves the ai in the direction of the next waypoint until is has reached proximity with it, then continues to the next waypoints in the list. The velocity is normalised because otherwise, the ai would have a greater velocity for further waypoints.

Path request manager

The path request manager queues each unit one by one so that multiple states of the algorithm aren't running at once, reducing performance. It does this by creating a "struct" (as of Microsoft's documentation, a struct is a value type that encapsulates groups of related variables)¹. The struct stores the start, end and callback variables. When a path is requested, a new struct is created with the unit's pathfinding information. It then queues this request and attempts to process the next request in the queue (if the queue's size is greater than zero and it is not currently processing, then it starts the process). Also, once a current process has finished, it also tries to process the next request and activates the callback with the success boolean and found path.

Turning the algorithm into a more efficient and accurate a-star algorithm

In order to transform the algorithm into an a-star algorithm, new variables must be added to the nodes. The gcost is the total cost of movement from the star node to the next node. The hcost is the total cost of movement from the next node to the end node. The fcost is the total cost of the node (gcost + hcost). The algorithm now checks whether the new gcost of the node is less than the current gcost or whether the open list does not contain the new node (If the node hasn't been checked already). It then applies the gcost and hcost of the new node so they can be read later. The next node is now the parent of the current node (This is stored in a new variable within the node class) and is added to the open list.

This new piece of code cycles through all available node in the open list and checks them to see if their fcost is lower than the current node. If so, that node now becomes the current node, is removed from the open list and is added to the closed list.

Once the pathfinding process has finished, it tells the path request manager after retracing the path, passing the waypoints. To retrace the path, the function simply gets the end node and finds its parent and so on. It then reverses the path so that the unit can follow it.

1. https://msdn.microsoft.com/en-us/library/ah19swz4.aspx

Camera Movement

Camera Movement

Keyboard controls

We'll be using common key-binds WASD to control the camera and pan it across the play area. To zoom, page up and page down can be used as to not conflict with possible future key-binds.

The input axis "horizontal" and "vertical" take into account both WASD keys and arrow keys to add force to the camera's container object which also has a rigid-body element. There isn't a equivalent axis for page up and down in Unity's inputs, requiring the creation of one manually. However, for efficiency I have simply coded the inputs. The downside of this, however is that the player can't adjust the key-bind. This shouldn't be a problem at the moment, though as a control menu hasn't been implemented.

The code is simple; if page down is pressed then the camera's container gets a downwards force added which means the whole rig is consistent and doesn't leave us with any bugs that we might have whilst not using a rigidbody element.

Mouse controls

The mouse controls will consist of two things:

Scrolling via the mouse wheel and panning by moving the mouse to the edge of the screen.

This requires a proximity check which can be achieved by comparing the mouse position with screen positions.

Here, the mouse minimum boundaries are simply 30 units, which I deemed a good number for responsiveness and it is not too big as to disrupt the flow of gameplay in the center of the screen. The maximum boundaries are the screen width and height subtracted by 30. If the mouse cursor crosses these coordinates, then the camera is panned in the corresponding direction.

Next, we need to zoom using the mouse wheel. Unlike page up and down, the scroll wheel has a dedicated input axis already implemented within Unity, so we'll be using that.

I added the code to an original addforce function, however I needed to invert the scroll wheel axis and multiply it by 35 in order to get a big enough movement that feels natural.

Currently there is no need to add a rotation control to the camera, however if obstructing buildings and objects are added then this will be implemented. A lot of RTS games such as Starcraft and League of Legends don't include a rotating camera because often it isn't needed and sometimes even disorientates the player due to the change of perspective.

Selection

Selection

Basic Unit Selection

In order to select units I created a new "Unit Manager" class in which I can store and manage all the unit's information. A unit is selected by ray-casting relative to the mouse position, then checking if the object hit was an AI unit. If so, then the unit's projector element is enabled to provide feedback of the player's action.

We need a way to select single units at once, however so to do this I created a list of units so that when a new unit is selected with the left mouse button then it loops through all currently selected units, disables them and then removes them from the list.

To select multiple units now, the player must hold down shift which disables the removing loop.

Finally, one of the most common features in an RTS that improves usability is a box select. A box select lets the player drag a box that selects any unit inside it, allowing for quick mass-selection compared to shift-clicking. This was achieved by checking if the mouse had been clicked and dragged a small distance which would then trigger the creation of the selection box. The selection box is created by storing the mouse's original position and creating a rectangle to the current mouse position. Visually, the box is made up of a 1px white image that is repeated. A lower opacity is used in the middle for clarity. The colour of the box can be changed in Unity's editor and can be transferred to in-game easily at anytime.

The only other features to add consist of combining the multiple ways to select units. Later on, when enemy ai are involved the function will have to be updated as to not select them.

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.