Formation Movement for Real-Time Strategy Games

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.

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.

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.

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.

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.