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/