Formation Movement for Real-Time Strategy Games
“Maintaining unit formations in an RTS game is an interesting and challenging AI problem. The goal of this research project was to solve the problem as completely and generically as possible, so that other developers may be able to form conclusions about how best to implement such a system for their own projects. Whereas much of the extant research focuses on one specific area of the larger problem, we will attempt to provide developers with a concrete example of such a system in action as well as an exploration of the problem space.”
As a teenager playing real-time strategy games like Starcraft, I would often marvel at how units were able to get around the map without getting stuck on terrain. My curiosity could have ended there, but as an aspiring programmer I wanted to know how things were working under the hood. I knew enough about pathfinding to understand that the problem wasn't easy to solve for a single unit, let alone two dozen.
That knowledge didn't stop me from being critical of games with poor unit movement, however. When playing Total Annihilation, it frustrated me that giving a move order to a large group of units resulted in them stumbling across the map in an uncoordinated fashion, often interfering with each other along the way. I found myself wishing that the AI were “smart” enough to march everyone from point A to point B in lockstep.
This is why I chose coordinated unit movement as the topic for my thesis project at The Guildhall at SMU.
Building a formation
I spent several months researching coordinated movement. I learned that games such as Age of Empires and Supreme Commander were capable of moving units around in formation in precisely the way I had envisioned years earlier. What was mysterious to me from a game development standpoint was how individual units could cooperate with each other and stay in formation all the way to the destination. Having each unit follow a path to the destination individually would result in the same awkward movement that I had experienced while playing TA. There had to be a way for the entire formation, as a whole, to follow a path to the destination, with individual units breaking formation as needed to avoid obstacles.
![Some formations up close.](thesis-formations.png)
Some formations up close. The shape of each formation is automatically determined based on the number of units.
What I ended up with was a system for generating a localized formation for an arbitrary set of units. Each unit was assigned an individual standing location measured from the center of the formation, which I termed “slots”. Units would then follow their formation slot through the world as the entire formation moved along a path to the destination of each move order.
Pathfinding as a group
After reviewing options for static collision avoidance, I decided to take a page from the Supreme Commander playbook and have units fall back on shared “flowfield” information to navigate around obstacles. A flowfield is a grid of tiles simulating a fluid body, typically with a vector indicating the flow direction and velocity of the fluid at that generalized location.
![A flowfield.](thesis-flowfield.png)
When units cannot maintain their own formation position, they fall back on flowfield information to move dynamically around obstacles.
There are some common pitfalls with the typical flowfield implementation. Units can get stuck easily at local minima. Runtime generation can be computationally expensive and also memory-intensive.
Since I was primarily interested in using information to speed up shared pathfinding, I decided to compress the vector information down to an enum
representing a cardinal direction: north, south, east, or west. Tiles acted more like breadcrumbs leading units to the shared destination of the formation. If at any point a unit could not reach its formation slot, it would simply look at the flowfield information at its feet and follow the breadcrumbs ahead some distance. Specifically, it would find the waypoint leading closest to the destination that it could see, i.e. that could be reached via a straight-line path, and would then walk directly toward this waypoint.
Zooming in on the test bed application
To effectively test and demonstrate this system in action, I created a C++ test bed app with OpenGL and GLFW. It contains some of the basic RTS gameplay elements, including terrain, units, and a scrolling camera.
![A large map with a few formations.](thesis-test-bed-app.png)
The test bed application, showing a large map with a few formations. Dark areas on the map represent impassable terrain.
With the mouse, the player is able to select units and issue move orders. Each move order groups selected units into a formation, causing them to form up and then march to the destination in rank and file.
![An animation showing units forming up.](thesis-selection.gif)
Drag selecting units in multiple formations and then issuing a move order forms a new formation from the selected units.
A special thank you
I couldn't have done it without my incredible professor and thesis advisor, Squirrel Eiserloh. Thank you for the invaluable advice and much-needed feedback that prepared me for success with my defense.