Formation Game AI

This post is dedicated to explaining the AI technique of formations and in with it the idea of coordinated movement

Formations are useful for basically any genre of game: RTS, RPG, sports games, basically anything you can think of. If you want units to move as a squad in any sort of way in your game, formations are a great and easy way to achieve this. I implemented a pretty basic form of it in a Unity3D project and will show various snippets of it in this post for help with implementation

Basic Concept

A formation consists of a leader slot, and however many other slots are needed to create the desired formation. For the most basic implementation, the leader of the formation is the only thing that is controlled, if movement is involved, and every other slot of the formation is based on the leader. Any steering or obstacle avoidance is only handled by the leader, which means that it has to account for the entire formation when trying to avoid obstacles, making it only really useful for an outside environment with minimal obstacles.

Examples of various four-unit formations(Artificial Intelligence for Games, Ian Millington)

Two-Level Formation Steering

As mentioned, the most basic implementation is only really useful for wide areas and not for indoor environments. To help solve this issue, you can implement something called two-level formation steering. There will now be two levels of steering, one level being used by the leader to move around formation slots, and the other level being the individual units steering to those slots themselves. By making every unit in the formation have its own steering and avoidance, the leader won’t have to account for the collision and avoidance of the formation as a whole anymore. The role of the leader is now solely to just keep updating the formation slot positions/orientations as it moves.

Representation of how units will avoid obstacles themselves (Artificial Intelligence for Games, Ian Millington)

Since each unit now has its own avoidance and steering, if the leader has avoidance related to it as well, then anytime it avoids an object, it will end up skewing every other unit in the formation at the same time. To prevent this, the leader is made invisible and its collision and avoidance is removed. This way the leader can help keep the formation in the correct spots without having to worry about avoiding objects itself and messing up the formation.

Implementation

Implementing formations is actually quite simple if you don’t implement some more advanced methods that I will mention a little later. A two-level formation is the most effective way to implement it I feel and it is also relatively easy with an engine like Unity that has built in path finding and obstacle avoidance.
To start out, you need to create a basic formation, which will just be an array of positions that formation units will be placed at relative to the leader position. In my implementation, I created two different formations of four units that you could switch back and forth from, one being a cross shape, and one being a line.

Setting up the positions of the formation slots

I also created a separate array of the same size as the formation that is used to hold the units that will be in the formation. When the leader who holds this formation script is moved, it will be updating its own position and be sending to the units within the formation their updated destinations. Since the formation slots are all relative to the leader, finding where each unit in the formation needs to go is as simple as adding the slot position to the leader position.

Updating destinations of the units in the formation

Since this is a two-level formation steering, the units of the formation each have their own steering and avoidance, which in Unity, will be a navmesh agent. All that has to be done in this case for the technique to function correctly, is to set each units navmesh destination to be its position in the formation. This way if any obstacles are in the way, Unity is automatically avoiding them on its way to the formation slot.

Function within the formation units that sets its path finding to go for its formation slot

Optimizations

What I implemented is about as simple as it can get for an effective formation that can fulfill any basic need you would need for a formation, but with some more advanced techniques it could be a little more effective. There two main issues that my simple implementation comes across, the formation can get ahead of an member that is busy avoiding obstacles, and when switching positions the units can get a little jumbled on their way to their positions.

One unit is lagging behind the formation(can also see average position of all units with axis)

To fix the issue of a lagging unit, there are a couple solutions. The most simple way is to just reduce the max speed of the leader to be around half that of the units, to make it harder for the formation to get too far ahead. This however constantly slows the formation even if there is not that high a chance for the formation to ever be behind. A better way of solving this is by keeping the leader on a sort of leech, making its position be based on the average position of the units, so if one unit is far behind, then the whole formation will be held back to allow it to keep up. Resolving it is a little more complicated than just setting a position, but if you want to learn a little more I recommend looking at around pages 149-151 of Artificial Intelligence for Games(Second Edition) for more.

Units getting clumped changing from the cross formation to the line formation

The problem I mentioned of units getting clumped up when switching between positions is created because each unit has a set index in both the formation unit array and formation slot array. To prevent this jumbling as much as possible it is recommended to make each unit go to the slot that is closest to its position before the switch. This way both the time to get into the formation will be shorter, and the units will be less likely to interfere with each other.

Closing Thoughts

Formations are a very useful technique that can be used in just about any game out there, so I hope I was able to show a lot about it and give some insight on how to implement it :]

Sources Used
“3.7 Coordinated Movement.” Artificial Intelligence For Games Second Edition, by Ian Millington and John Funge, Morgan Kaufmann Publishers, 2009, pp. 144–167.
Warm,Jeremiah “Coordinated Movement”, http://www.jeremiahwarm.com/coordinated-movement.php
Campbell, Ryan. “How to Implement Squads and Formations.” Battle of Brothers, 18 Sept. 2014, http://battleofbrothers.com/sirryan/how-to-implement-squads-and-formations-part-1/.