Swarming ant Algorithms & Combat tutorial - Empires of the Undergrowth

Where does combat take place?

In Empires of the Undergrowth the majority of the combat takes place above ground in open spaces, where large armies of ants clash and fight for territory. The ants are born underground within the nest. Different types of ants are available, all with different abilities inspired by nature.

How are they controlled?

The ants are sent into battle with a single command. The player is able to send ants out to fight, keep them within the nest, or collect resources. Once soldiers are sent out to fight, the player no longer has any control over them. There were many ideas behind this approach to combat, including freeing the player up for more complex base management and simplifying micro to increase accessibility for casual RTS players.

Ant motion

As direct player control over the ants is relinquished, the soldiers have to find their own way into battle. The approach needed to produce fair, repeatable stable battle outcomes as well as look natural and feel satisfying for the player.

We wanted the ants to move around organically, acting as a group of individuals exhibiting swarm like behaviour. They needed to appear to move naturally and unpredictably as individuals, whilst having an overall predictable heading.

Leaving the nest

To begin with, we used a fairly ridged approach involving an invisible path between the player nest and opponent nest. In this setting the ants would leave the tunnel and arrange themselves on one of 6-12 pre-determined lanes on the path leading to the opponent’s nest entrance. This approach spawned a number of problems.

• Firstly, the ants would become bunched up together when they entered combat, struggling to move around each other
• Secondly, if they had left the path due to combat and combat was over, they needed to re-join the path. More often than not, re-joining the path was an inefficient way for the ant to reach its final destination, and felt both frustrating and unnatural.
• Lastly, despite having multiple lanes for the ants, as soldier numbers increased beyond around 30, the lanes became obvious and the ant’s movements looked pre-determined.

To solve these issues, we tried an alternative option of removing the path system altogether. Instead, each ant would head directly for their target location (in most cases, the opponent’s nest entrance). This lead to a very tightly packed, single file line of ants pushing against each other. We then added a periodic close-range scan for each ant. The ants would check for all other nearby ants within a certain radius and also store their squared distances. (By storing squared distances rather than true distances, we avoid using the relatively expensive square root function). Each friendly ant in the scan radius is given a weighting based on its distance from the scanning ant (closer is higher) and whether it is right or left of the scanning ant’s heading (multiplier of 1 or -1). This number is then used to push the ant at a right angle to its heading – if there are many ants on the right hand side of the scanning ant, then it will move to the left and visa-versa. This gives the effect of naturally spreading out the ants as they all march to the same heading. Also we can dynamically control by how much they spread out simply by altering a constant applied to each ant’s weighting. As a final touch, we added a small random factor to the ant’s forward velocity, this truly gives an organic look to the movement of a marching column of ants.

Heading for combat

One issue with the original path system for the soldier ants was that when two large forces of ants met, they would clump together in a big heap, struggling to reach their targets. What we needed was for the ants to spread out and use the open space around them. To get a good pre-spread on the ants, all we needed to do was increase the magnitude of the aforementioned constant that applies to the ant spreading weight. There was a problem with this though, we wanted the ants to start spreading out long before they entered combat (i.e., start spreading before enemy ants enter their scan radius).

One solution to make them spread out sooner was to increase their scan radius but unfortunately, scanning for other ants is a computational bottle neck which becomes more apparent as the scan radius increases. In the end we came up with a novel solution that could be thought of as being remarkably similar to real ant chemical trails. We added an additional multiplying constant to our spreading algorithm based on whether the friendly ant had found a target or not. This meant that even if an ant could not find an enemy ant within its scan radius, if one of the friendly ants did have an enemy in sight, the scanning ant could begin to react. This communication through friendly ants can actually be passed down a chain. As long as a line of ants are all within scan radius of each other, the one at the back knows if the one at the front is in combat. This meant that we could not only pre-spread ants before combat, but also steer their heading in the direction of enemies that are out of their scan radius (that they might otherwise pass by, heading on to the opponent nest entrance).

Entering combat

Once an ant has a definitive enemy target within its scan radius it will head towards it (or to the closest if there are multiple targets). Even with the pre-spreading, for large battles ants often find themselves blocked from their target by friendly ants. If they are unable to push past they need to try and find a way around the pack. Rather than using computationally expensive path finding algorithms based on the positions of all of the nearby ants, they instead do something really quite simple. If they are trying to move but cannot due to an obstruction, they change their heading either slightly right or left of their target. If they still cannot move forwards they will continue rotating in the same direction and trying to push forwards until eventually they start to move. (even if this means moving in the opposite direction to their target). Once they start moving they will gradually rotate back towards their target (which may be have changed as a result of regular scanning). If their movement is impeded again, they will go back to rotating away from the target. This has the effect of making the ant ‘feel’ its way around the outside of a large group of friendly ants until it is able to reach an enemy.

Further changes

There are still features to be added to the combat system. We are considering introducing a basic cluster-based combat director to give headings to ants which are out of range of friends who have a target heading.