Implementing Coordinated Movement

Part of the fun of working in the game industry is the constant demand for technical innovations that will allow designers to create better games. In the real-time strategy (RTS) genre, most developers are focusing on improving group movement for their next round of games. I'm not talking about the relatively low-tech methods currently in use. Instead, I'm referring to coordinated group movement, where units cooperate with each other to move around the map with intelligence and cohesion. Any RTS game developer that wants to be competitive needs to look beyond simple unit movement; only the games that weigh in with solid coordinated movement systems will go the distance.

In this article, the second and final part of my coordinated unit movement series, we'll take a look at how to use the systems that we considered in the first article to satisfy our coordinated group movement goal. We'll also examine how we can use our coordinated movement fundamentals to solve some classic, complex movement problems. While we will spend most of our time talking about these features through the RTS microscope, they can easily be applied to other types of games.

Catching Up

Last week (Coordinated Unit Movement), we discussed a lot of the low-level issues of coordinated unit movement. While pathfinding (the act of finding a route from point A to point B) gets all of the press, the movement code (the execution of a unit along a path) is just as important in creating a positive game experience. A game can have terrific pathfinding that never fails to find the optimum path. But, if the movement system -isn't up to par, the overall appearance to the players is going to be that the units are stupid and can't figure out where to go.

One of the key components to any good movement system is the collision determination system. The collision system really just needs to provide accurate information about when and where units will collide. A more advanced collision system will be continuous rather than discrete. Most games scale the length of the unit movement based on the length of the game update loop. As the length of that update loop increases, the gap between point A and point B can get pretty large. Discrete collision systems ignore that gap, whereas continuous systems check the gap to make sure there isn't anything in between the two points that would have created a collision with the unit being moved. Continuous collision determination systems are more accurate and more realistic. They're more difficult to write, though.

Another important element for coordinated unit movement is position prediction. We need to know where our units are trying to go so that we can make intelligent decisions about how to avoid collisions. Although building a fast position-prediction system presents us with a number of issues, for this article, we can assume that our collision determination system has been augmented to tell us about future collisions in addition to current collisions. Thus, each unit in the game will know with which units it's currently in collision with and which units it will collide with in the near future. We presented several rules for getting two units out of collision in last month's article.

All of these elements work together to create the basis for a solid, first-order (single unit to single unit) coordinated movement system. The core thing to keep in mind for this article is that we have an accurate, continuous collision determination system that tells us when and where units will collide. We'll use that collision system in conjunction with the collision resolution rules to create second order (three or more units/groups in collision) coordination.

Group Movement

Looking at the definition of a group (see sidebar at right), we can immediately see that we need to store several pieces of data. We need a list of the units that make up our group, and we need the maximum speed at which the group can move while still keeping together. Additionally, we probably want to store the centroid of the group, which will give us a handy reference point for the group. We also want to store a commander for the group. For most games, it doesn't matter how the commander is selected; it's just important to have one.

One basic question needs to be answered before we proceed, though. Do we need to keep the units together as they move across the board? If not, then the group is just a user interface convenience. Each unit will path and move as if the player had issued individual commands to each group member. As we look at how to improve on the organization of our groups, we can see that there are varying degrees of group movement cohesion.

Units in a group just move at the same speed. Usually, this sort of organization moves the group at the maximum speed of its slowest unit, but sometimes it's better to let a slow unit move a little faster when it's in a group (see Figure 1 below). Designers generally give units a slow movement speed for a reason, though; altering that speed can often create unbalanced game play by allowing a powerful unit to move around the map too quickly.

Units in a group move at the same speed and take the same path. This sort of organization prevents half of the group's units from walking one way around the forest while the other half takes a completely different route (see Figure 2 below). Later, we'll look at an easy way to implement this sort of organization.

Units in a group move at the same speed, take the same path, and arrive at the same time. This organization exhibits the most complex behavior that we'll apply to our group definition. In addition to combining the previous two options, it also requires that units farther ahead wait for other units to catch up and possibly allows slower units to get a temporary speed boost in order to catch up.

So, how can we achieve the last option? By implementing a hierarchical movement system, we can manage individual unit movement in a way that allows us to consider a group of units together. If we group units together to create a group object, we can store all of the necessary data, calculate the maximum speed for the group as a whole, and provide the basic decision making regarding when units will wait for other units (Listing 1).

Listing 1. BUnitGroup.

//********************************************************************
// BUnitGroup
//********************************************************************
class BUnitGroup
{
public:
BUnitGroup( void );
~BUnitGroup( void );

//Returns the ID for this group instance.
int getID( void ) const { return(mID); }

//Various get and set functions. Type designates the type of the group
//(and is thus game specific). Centroid, maxSpeed, and commander are
//obvious. FormationID is the id lookup for any formation attached to
//the group (will be some sentinel value if not set).
int getType( void ) const { return(mType); }
void setType( int v ) { mType=v; }
BVector& getCentroid( void ) const { return(mCentroid); }
float getMaxSpeed( void ) const { return(mMaxSpeed); }
int getCommanderID( void ) const { return(mCommanderID); }
BOOL getFormationID( void ) const { return(mFormationID); }
BOOL setFormationID( int fID );

//Standard update and render functions. Update generates all of the
//decision making within the group. Render is here for graphical
//debugging.
BOOL update( void );
BOOL render( BMatrix& viewMatrix );

//Basic unit addition and removal functions.
BOOL addUnit( int unitID );
BOOL removeUnit( int unitID );
int getNumberUnits( void ) const { return(mNumberUnits); }
int getUnit( int index );

protected:
int mID;
int mType;
BVector mCentroid;
float mMaxSpeed;
int mCommanderID;
int mFormationID;
int mNumberUnits;
BVector* mUnitPositions;
BVector* mDesiredPositions;
};

The BGroup class manages the unit interactions within itself. At any point in time, it should be able to develop a schedule for resolving collisions between its units. It needs to be able to control or modify the unit movement through the use of parameter settings and priority manipulation. If your unit system only has support for one movement priority, you'll want to track a secondary movement priority within the group for each unit in the group. Thus, to the outside world, the group can behave as a single entity with a single movement priority, but still have an internal prioritization. Essentially, the BGroup class is another complete, closed movement system.

The commander of the group is the unit that will be doing the pathfinding for the group. The commander will decide which route the group as a whole will take. For basic group movement, this may not mean much more than the commander being the object that generates the pathfinding call. As we'll see in the next section, though, there's a lot more that the commander can do.

Basic Unit Formation

Formations build on the group system. Formations are a more restrictive version of groups because we have to define a very specific position for each unit within the group. All of the units must stay together during group movement in terms of speed, path, and relative distance; it doesn't do any good to have a column of units if there are huge gaps in that column while it's moving around the map.

The BFormation class (below)manages the definition of the desired positions (the positions and orientations that we want for each unit in the formation), the orientation, and the state of the formation. Most formations that a game uses are predefined; it's useful to make these easy to edit during development (via a text file or something else that a nonprogrammer can manipulate). We do want the ability to create a formation definition on the fly, though, so we'll take the memory hit and have each formation instance in the game maintain a copy of its own definition.

Listing 2. The BFormation Class

//********************************************************************
// BFormation Class
//********************************************************************
class BFormation
{
public:
//The three formation states.
enum
{
cStateBroken=0,
cStateForming,
cStateFormed
};

BFormation( void );
~BFormation( void );

//Accessors for the formation's orientation and state. The expectation
//is that BFormation is really a data storage class; BGroup drives the
//state by calling the set method as needed.
BVector& getOrientation( void ) { return(mOrientation); }
void setOrientation( BVector& v ) { mOrientation=v; }
int getState( void ) const { return(mState); }
void setState( int v ) { mState=v; }

//The unit management functions. These all return information for the
//canonical definition of the formation. It would probably be a good
//idea to package the unit information into a class itself.

BOOL setUnits( int num, BVector* pos, BVector* ori, int* types );
int getNumberUnits( void ) const { return(mNumberUnits); }
BVector& getUnitPosition( int index );
BVector& getUnitOrientation( int index );
int getUnitType( int index );

protected:
BVector mOrientation;
int mState;
int mNumberUnits;
BVector* mPositions;
BVector* mOrientations;
int* mTypes;
};

Under this model, we must also track the state of a formation. The state cStateBroken means that the formation isn't formed and isn't trying to form. cStateForming signifies that our formation is trying to form up, but hasn't yet reached cStateFormed. Once all of our units are in their desired positions, we change the formation state to cStateFormed. To make the movement considerably easier, we can say that a formation can't move until it's formed.

When we're ready to use a formation, our first task is to form the formation. When given a formation, BGroup enforces the formation's desired positions. These positions are calculated relative to the current orientation of the formation. When the formation's orientation is rotated, then the formation's desired positions will automatically wheel in the proper direction.

To form the units into a formation, we use scheduled positioning. Each position in the formation has a scheduling value (either by simple definition or algorithmic calculation) that will prioritize the order in which units need to form. For starters, it works well to form from the inside and work outward in order to minimize collisions and formation time (see Figure 3 below). The group code manages the forming with the algorithm shown in Listing 3.

Listing 3.

Set all units' internal group movement priorities to same low priority value.
Set state to cStateForming.
While state is cStateForming:
{
Find the unfilled position that's closest to the center of the formation.
If no unit was available
Set the state to cStateFormed and break out of forming loop.

Select a unit to fill that slot using a game specific heuristic that:
Minimizes the distance the unit has to travel.
Will collide with the fewest number of other formation members.
Has the lowest overall travel time.

Set unit's movement priority to a medium priority value.
Wait (across multiple game updates) until unit is in position.
Set unit's movement priority to highest possible value. This ensures that
subsequently formed units will not dislodge this unit.
}

So, now that we have all of our swordsmen in place, what do we do with them? We can start moving them around the board. We can assume that our pathfinding has found a viable path (a path that can be followed) for our formation's current size and shape (see Figure 4 below). If we don't have a viable path, we'll have to manipulate our formation (we'll talk about how to do this shortly). As we move around the map, we designate one unit as the commander of our formation. As the commander changes direction to follow the path, the rest of our units will also change direction to match the commander's; this is commonly called flocking.

We have a couple of ways to deal with direction changes for a formation: we can ignore the direction change or we can wheel the formation to face in the new direction. Ignoring the direction change is simple and is actually appropriate for something such as a box formation (Figure 5).

Wheeling isn't much more complicated and is very appropriate for something such as a line. When we want to wheel, our first step is to stop the formation from moving. After rotating the orientation of the formation, we recalculate the desired positions (see Figure 6 below). When that's done, we just go back to the cStateForming state, which causes the group code to move our units to their new positions and sets us back to cStateFormed when its done (at which point, we can continue to move).

Advanced Formation Management

So, now we've got formations moving around the map. Because our game map is dynamic and complex, it's possible that our planned path will be invalidated. If that happens, we'll need to manipulate the formation in one of three ways.

Scaling unit positions. Because the desired positions are really just vector offsets within a formation, we can apply a scaling factor to the entire formation to make it smaller. And a smaller formation can fit through small gaps in walls or treelines (see Figure 7 below). This method works well for formations in which the units are spread out, but it's pretty useless for formations where the units are already shoulder to shoulder (as in a line). Scaling the offsets down in that case would just make our swordsmen stand on top of each other, which isn't at all what we want.

Simple ordered obstacle avoidance. If we're moving a formation and we encounter a collision with another game entity (either a current collision or a future collision), we can assume that our path is still viable, with the exception of this entity being in the way. The simple solution is to find the first place along our formation's path where it will not be in collision with the entity and reform our formation at that spot (see Figure 8 below). Thus, the line of infantry will break, walk around the obstacle, and reform on the other side. This solution can fall apart fairly easily, though, so it's important to realize when the reformation position is too far along the path to be of use. If the distance around the obstacle is far enough that it interferes with the reformation of your group, then you should just repath your formation.

Halving and rejoining. While simple avoidance is a good solution, it does dilute the visual impact of seeing a formation move efficiently around the map. Halving can preserve the visual impact of well-formed troops. When we encounter an obstacle that's within the front projection of the formation (see Figure 9 below), we can pick a split point and create two formations out of our single formation. These formations then move to the rejoin position and then merge back into one formation. Halving is a simple calculation that dramatically increases the visual appeal of formations.

Path Stacks

A path stack is simple a stack-based (last in, first out) method for storing the movement route information for a unit (see Figure 10 below). The path stack tracks information such as the path the unit is following, the current waypoint the unit is moving toward, and whether or not the unit is on a patrol. A path stack suits our needs in two significant ways.

First, it facilitates a hierarchical pathfinding setup (see Figure 11 below). Game developers are beginning to realize that there are two distinctly different types of pathfinding: high-level and low-level. A high-level path routes a unit around major terrain obstacles and chokepoints on a map, similarly to how a human player might manually set waypoints for a unit. A low-level path deals with avoidance of smaller obstacles and is much more accurate on details. A path stack is the ideal method for storing this high- and low-level information. We can find a high-level path and stuff that into the stack. When we need to find a low-level path (to avoid a future collision with that single tree in the big field), we can stuff more paths onto the stack and execute those. When we're done executing a path on the stack, we pop it off the stack and continue moving along the path that's now at the top of the stack.

Second, a path stack enables high-level path reuse. If you recall, one of the key components to good group and formation movement is that all of the units take the same route around the map. If we write our path stack system so that multiple units can reference the same path, then we can easily allow units to reuse the same high-level path. A formation commander would find a high-level path and pass that path on to the rest of the units in his formation without any of them having to do any extra work.

Structuring the path storage in this manner offers us several other benefits. By breaking up a high-level path into several low-level paths, we can refine future low-level segments before we execute them. We can also delay finding a future low-level path segment if we can reasonably trust that the high-level path is viable. If we're doing highly coordinated unit movement, a path stack allows us to push temporary avoidance paths onto the stack and have them easily and immediately integrated into the unit's movement (see Figure 12).

Figure 12

Solving A Compound Collision

For our purposes, compound collisions are defined as simultaneous collisions between more than two units. Most games will have a practical upper limit to how many units can be involved in a compound collision. Still, as soon as a collision involves more than two units, programmers generally end up writing a lot of spaghetti logic that breaks way too easily. But we'll get avoid that situation by reusing the movement priorities and doing some simple scheduling.

If we have a compound collision between three units (see Figure 13 below), our first task is to find the highest-priority unit involved in the collision. Once we've identified that unit, we need to look at the other units in the collision and find the most important collision for the highest priority unit to resolve (this may or may not be a collision with the next highest-priority unit in the collision). Once we have two units, we pass those two units into the collision resolution system.

As soon as the collision between the first two units is resolved (see Figure 14 below), we need to reevaluate the collision and update the unit involvement. A more complex system could handle the addition of new units to the collision at this point, but you can get good results by simply removing units as they resolve their collisions with the original units.

Once we've updated the units in the collision, we go back to find two more units to resolve; we repeat this process until no more units are involved in the collision.

You can implement this system in two different areas: the collision resolution rules or the collision determination system. The collision resolution rules would need to be changed in the way in which they units higher and lower priority; these rules aren't particularly difficult to change, but this modification does increase the complexity of that code. Alternatively, you can change the collision determination system so that it only generates collisions that involve two units at a time; you still have to find all of the units in a collision, though, before you can make this decision.

Solving The Stacked Canyon Problem

One of the ultimate goals of any movement system is to create intelligent movement. Nothing looks more intelligent than a system that solves the stacked canyon problem. The stacked canyon isn't a simple problem to solve upon first inspection, but we can reuse some simple scheduling to solve it once we have our coordinated unit movement in place.

The first step is to identify that you have a stacked canyon problem. This step is important because it's needed to propagate the movement priority of the driving unit (the unit trying to move through the stacked canyon) through to the rest of the units. We could just let each unit ask other units to move out of the way based on its own priority, but a better solution to use the priority of the driving unit - after all, that's the unit that we really want to get through the canyon. Identifying a stacked canyon problem can be done in a couple of ways: noticing that the driving unit will push the first unit into a second unit or looking at the driving unit's future collision list to find multiple collisions. Whichever method is used, the pushed unit should move with the same priority as the driving unit.

Once we've identified the problem, we have a fairly simple recursive execution using the coordinated movement. We treat the first pushed unit as the driving unit for the second pushed unit, and so on. Each unit is pushed away from its driving unit until it can move to the side. When the last unit moves to the side, the original driving unit has a clear path by which to move through the canyon.

A nice touch is to restore the canyon units to their original states. To do this, we simply need to track the pushing and execute the moves in the reverse order from which the units moved to the side. It's also useful to have the movement code recognize when the driving unit is part of a group so that the rest of the group's units can move through the canyon before the canyon units resume their original positions.

Tips

Optimize this general system to your game. A lot of extra computation can be eliminated or simplified if you're only doing a 2D game. Regardless of whether you're doing a 2D or 3D game, your collisiondetection system will need a good, highly optimized object culling system; they're not just for graphics anymore.

Use different methods for high and low level pathing. To date, most games have used the same system for both solutions. Using a low-level solution for high-level pathfinding generally results in high-level pathfinding that's slow and not able to find long paths. Conversely, a high-level pathfinder used for low-level pathfinding creates paths that don't take all of the obstacles into account or are forced to allow units to move completely through each other. Bite the bullet and do two separate systems.

No matter what you do, units will overlap. Unit overlap is unavoidable or, at best, incredibly difficult to prevent in all cases. You're better off simply writing code that can deal with the problem early. Your game will be a lot more playable throughout its development.

Game maps are getting more and more complex. Random maps are going to be one of the key discriminating features in RTS games for some time to come. The better movement systems will handle random maps and also take changing map circumstances into account.

Understand how the update affects unit movement. Variable update lengths are a necessary evil that your movement code will have to be able to handle. Use a simple update smoothing algorithm to make the most of the problems go away.

Single update frames of reference are a thing of the past. It's impossible to do coordinated unit movement without planning. It's impossible to do planning if you don't track past decisions and look at what's likely to happen in the future. Any generalized coordinated unit movement system needs to be able to recall past collision information and have future collision information available at all times. Remember that minor variations during the execution of a collision resolution plan can be ignored.

No Stupid Swordsmen

Simple unit movement is, well, simple. Good, coordinated unit movement is something that we should be working on in order to raise our games to the next level and make our players a lot happier in the process. With these articles, we've laid the foundation for a coordinated unit movement system by talking about topics such as planning across multiple updates and using a set of collision resolution rules that can handle any two-unit collision. Don't settle for stupid swordsman movement again!

For Further Info

After several close calls, Dave managed to avoid getting a "real job" and joined Ensemble Studios straight out of college a few years ago (just in time to the do the computer player AI for a little game called AGE OF EMPIRES). These days, Dave spends his time either leading the development of Ensemble Studios' engines or with his lovely wife Kristen. Dave can be reached at [email protected].