Implementing Coordinated Movement
January 29, 1999 Page 3 of 3
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.
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 collision detection 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
- Archer Jones. The Art of War in the Western World. Oxford University Press, 1987. ISBN 0-252-01380-8. This is a great book if you're looking for information on historical formation usage.
- Bjorn Reese's page of pathfinding/ navigation links is at http://www.imada.ou.dk/~breese/ navigation.html
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].
Page 3 of 3