Gamasutra: The Art & Business of Making Gamesspacer
Implementing Coordinated Movement
arrowPress Releases
March 24, 2018
Games Press
View All     RSS

If you enjoy reading this site, you might also want to check out these UBM Tech sites:


Implementing Coordinated Movement

January 29, 1999 Article Start Previous Page 2 of 3 Next

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
//The three formation states.

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 );

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.


Figure 3

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.

Figure 4

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).

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).

Figure 6

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.

Figure 7

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.

Figure 8

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.

Figure 9

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.

Figure 10

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.

Figure 11

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

Article Start Previous Page 2 of 3 Next

Related Jobs

Skydance Interactive
Skydance Interactive — Marina Del Rey, California, United States

Systems Designer
Tic Toc Games
Tic Toc Games — Burbank, California, United States

Insomniac Games
Insomniac Games — Burbank, California, United States

Director, Engine
Pixelberry Studios
Pixelberry Studios — Mountain View, California, United States

Software Engineering Manager

Loading Comments

loader image