A formation is a structure for units to move within. This can be used in games to make the AI look more realistic.
In the above example the first part is the movement of units that all act on their own to get to an end point. These units could have simple behaviors to avoid colliding with each other but don't have any knowledge of the group as a whole. The line formation on the other hand has to have an outside system with knowledge of where everything in the group can be. This system can be ran with one unit leading a group or an external formation manager, managing all of the positions and movement of the desired positions. This post will focus more on an external system managing units rather than a leader but many of the concepts can be applied to both.
Dave Pottinger in an article called "Implementing Coordinated Movement" discusses many strategies of how to create and move formations. Researching these ideas I gained a good understanding of how the basics of formation movements work. Formations have slots that units fill and follow. A formation should have multiple states such as currently forming, formed, and moving along a path. A formation that is currently forming has units in it that have not yet filled a slot. It is often important to plan out the order in which units join the formation and can be worth it to have the units join one at a time. This is especially notable when creating a box formation.
Dave Pottinger in an article called "Implementing Coordinated Movement" discusses many strategies of how to create and move formations. Researching these ideas I gained a good understanding of how the basics of formation movements work. Formations have slots that units fill and follow. A formation should have multiple states such as currently forming, formed, and moving along a path. A formation that is currently forming has units in it that have not yet filled a slot. It is often important to plan out the order in which units join the formation and can be worth it to have the units join one at a time. This is especially notable when creating a box formation.
This problem can easily be avoided with some planning. One way of approaching this is having each slot get filled one at a time. The order for filling the slots would be based on their distance from a reference point. When a slot gets chosen it will then choose the best available unit based on a heuristic value. This heuristic value can be created by taking into account factors such as distance, and ease of travel based on obstacles in the way of the path. For this situation it would make sense to have the reference point be the center position because that is the most likely point to get blocked off. If however the formation was created in a corner the center may not be the best choice. In this case using the center point will often result in the part closest to the corner being blocked off as the last unit attempts to go into place. These sort of things depend on the environment of your particular game.
Now that we have formed our formation, according to the way our states work, we can move. In all formations the units will be simply following their assigned slots in the formation. The formation itself and the slots will move using its own logic. Depending on the shape of the formation depends how it should move and rotate. In some cases the rotation doesn't matter much because the formation will look good regardless of the direction it is moving.
However, as seen in this example, with a line formation it must rotate in order to look correct. This can be done rather simply by stopping the formation and reforming it based on the new desired rotation.
I made a tech demo in order to understand some of these ideas in action. In this demo you can see square formation with the center as a reference point when it is not made at the corner of the screen. It also shows movement with both box and line formations as previously described.
This is just a simple example of formation movement but in a full game there would be many more obstacles to deal with. If a unit within the group gets far away from a point it needs to act accordingly. The article "Realistic Behavioral Model for Hierarchical Coordinated Movement and Formation Conservation for Real-Time Strategy and War Games" discusses a movement strategy to help solve this issue. Each unit has three movement states, slow, normal, and fast. Based on various factors such as the units distance for its slot it may switch between states. But regardless it will stay within the constraints of the fastest and slowest states. I implemented this in my tech demo based on the distance but it is not very noticeable due to lack of obstacles and collisions.
In the book, "Artificial Intelligence For Games" by Millington, Ian, and Jon Funge, there is a section on scale-able formations. This is a formation such as a defensive circle that can get larger based on the number of units. This can be done fairly simply by increasing the radius of the circle allowing for more slots to be added.
Formations are often used in RTS games. In this case there are many units that group and move together across a complex map. In this situation path finding algorithms would be necessary to figure out a path that the entire formation could go but we won't go into that here. Another game that formations can be used in is a battle ships like game. In this situation a player could be the captain of a fleet of ships and have a formation follow him in an intelligent manner. These are just a few examples of where formations can be used.
As discussed earlier in order for formations to work well a lot of planning is needed. Making these plans and acting on them takes a decent amount of CPU time. Because of this it is important to consider how complex you want to make your formations based on your platforms restraints. On PC it is entirely possible to utilize the CPU power of modern day machines to have really well working complicated algorithms that create intelligent formation movement. This is not to say it can't be done on platforms such as mobile because it most certainly has; it is just important to tone down the complexity of the AI for a platform such as mobile to allow it to run smoothly. This technique can be used on most platforms if the complexity and efficiency are considered with the platform in mind.
References:
Mamdouh, Abdulla M., Ahmed Kaboudan, and Ibrahim F. Imam. "Realistic Behavioral Model for
Hierarchical Coordinated Movement and Formation Conservation for Real-Time Strategy and
Games."IAENG International Journal of Computer Science (2012): n. pag. Web.
Millington, Ian, and John David Funge. Artificial Intelligence for Games. Boca Raton: CRC, 2009. Print.
Pottinger, Dave. "Gamasutra - Coordinated Unit Movement." Gamasutra Article. N.p., 22 Jan. 1999. Web.
04 Dec. 2013.
Pottinger, Dave. "Gamasutra - Implementing Coordinated Movement." Gamasutra Article. N.p., 29 Jan.
1999. Web. 04 Dec. 2013.
