AI Teams, Unit Health and Basic Combat

AI teams

The teams are represented by a public integer so the information can be accessed by other AI units. At the moment there are only two teams, 0 and 1. When the program starts, I check whether the unit is in team 1 or 0; if it's on team 1 then I colour the mesh red.

Health

The health is represented by the blue numbers. In order to display the health on the screen, I used Unity's OnGUI function. The function loops through each AI unit, gets the position relative to the screen, and renders the text on the screen in the appropriate position each frame.

Combat

On each frame, each unit checks a sphere with a radius of 2 to check if there is any AI nearby; if the AI is on the enemy team, is not the current target and the current unit is not attacking anything else, then the "attack" co-routine is run. Whilst the target is still alive and within the radius, then the current unit attacks and takes 1 health from the enemy AI per 0.5s.

Finished Result:

Statistics After Binary Heap Optimisation

Moving - With Binary Heap Optimisation

The binary heap is only used whilst the algorithm is running, so we'll only be taking the movement statistics.

Frame time whilst moving (20x20 grid):

1/0.0013 = 769 fps

Frame time whilst moving (50x50 grid):

1/0.0025 = 400 fps
Frame time whilst moving (100x100 grid):

1/0.015 = 66 fps

As you can see, binary heap optimisation has roughly doubled performance, and has also made frame drops less noticeable at 50x50. The algorithm could be optimised further, but a more significant way to lower frame time is by changing the map representation.

Binary Heap Optimisation

Binary Heap Optimisation

Insertion

A binary heap splits nodes into two branches exponentially. It sorts nodes from lowest to highest movement cost so that the lowest number in the group is always the first element in the array. In order to insert an object into the heap it is first placed at the end of the heap as shown as the blank circle in the diagram:

The value is then compared to it's parent (in this case, the 6); if the value is higher than 6 it is in the correct position, if it is less than 6 then the two values swap position. This continues until the value is in the correct position.

How the code sorts up the list:

Extraction

In order to extract from the heap, we remove the top element and replace it with the bottom element (Remove 2 and move 14). Then we check 14 against each of it's children (3 and 6) and swap accordingly with the lowest value child to move the lowest value to the top of the heap.

How the code sorts down the list:

Why the binary heap is useful

Inserted nodes now only have to check against a maximum of 2 other values in the case of the diagram, whereas normally the code would cycle through each node in the array until the lowest value is found.

Extracted nodes may be a bigger optimisation as instead of moving the entire array of nodes by one value if the first node is removed (which takes up a lot of computing power), the first value is removed, replaced and then the replaced node only needs to check four other nodes in the case of the diagram.

Current Statistics

Idle

Here's the current frame time when the program is idle and not receiving any commands:

As you can see, due to the simplicity of the sphere object, the frame rate is barely effected.
We can work out how many frames per second the user is getting using this method:
1/0.0008 (Frame time in seconds) = 1250 fps (Frames per second)
1/0.0009 = 1111 fps
There is only a large amount of fps difference due to the fact the the unit measures would cause inaccuracies because of Unity's rounding to the nearest 0.1ms.

Selecting

The frame time whilst selecting units:

1/0.0011 = 909 fps
This slight increase in frame time is due to the rendering of the selection highlights. Not much can be done about this, plus the rendering would be done on the fast GPU, meaning that we need not worry too much unless there is a considerable amount of selected units on the screen at once; this is a simple fix, however, as LOD and texture quality at a distance can be adjusted to improve fps without a visual degradation.

Moving

Frame time whilst moving (20x20 grid):

1/0.0013 = 769fps
Frame time increases as expected with more units, however even this small decrease in performance could be optimised by having multiple units use the same path.

Frame time whilst moving (50x50 grid):

1/0.0040 = 250fps
Now we can start to see a significantly large drop in fps, and if more units are added (which will almost certainly happen in an RTS) then the game will not be able to cope with the amount of requests, causing it to skip frames and stutter.

Frame time whilst moving (100x100 grid):

1/0.0300 = 33fps
This is an unacceptable frame drop, and this is without complicated visuals or large amounts of units. 
To improve frame times, processes could be split across frames or the actual process could be optimised.

Optimisations

Algorithm Adjustments

Binary Heap

Binary heap optimisation adjusts the way the program stores, gets and sets node information. The binary heap prioritises nodes in hopes of achieving a solution more quickly.

Pros:

Fairly simple to implement.

Provides optimisation for any situation.

Cons:

None.

Map Representation

Navmesh

A navmesh is one of the most commonly used representations of maps. The program takes the geometry of each level, gets each triangle and creates a new grid of simplified polygons that each act as a node. Although very hard to implement from scratch, a navmesh is particularly useful when working with procedural terrain. Unity and Unreal Engine both have native navmesh implementation, however Unity's cannot be fully adjusted whilst the program is running, meaning games with destructible terrain will not be able to use this.

Pros:

Algorithm can be customised to produce an appropriate map representation.

Can be used in any situation, though most useful in terms of procedural terrain.

Reduces the amount of nodes needed to represent a map.

Does not need to be hand placed like way-points, but can serve many of the same purposes.

Cons:

Harder to implement.

Can't be placed by hand for scripted events.

Waypoints

Waypoints are often hand placed nodes for the AI to use. Each waypoint will store information about its neighbours for the algorithm to use.

Pros:

Allows for scripted events, particularly useful for story based games (such as in Uncharted 4)

Can be hand-placed.

Waypoints could be customised. (For instance, the AI could be made to crouch behind cover at a certain waypoint, like Uncharted 4).

Can minimise the amount of nodes needed for a map.

Cons:

Has to be hand-placed.

Hierarchical Representation

A hierarchical representation will use different levels of map representation. For instance, the largest map representation could be a country, followed by a county, then a town, then a road. The AI may not need to use the smallest levels in order to path-find, depending on the situation.

Pros:

Simple to implement.

Significant optimisation on large maps.

Cons:

Few cases where this representation would be relevant.

Conclusion

I have chosen to add binary heap optimisation to my project, as it one of the most easy to implement steps, and provides optimisation in any circumstance. I have decided to keep my current implementation of map representation, as it would be better to change it once levels have been made for the game for maximum optimisation and relevance so I don't run into any obstacles.

Sources:

http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html

https://en.wikipedia.org/wiki/Binary_heap

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html

https://www.binpress.com/tutorial/unity3d-ai-navmesh-navigation/119

http://allenchou.net/2016/05/a-brain-dump-of-what-i-worked-on-for-uncharted-4/

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.