Coordinated Unit Movement

By
Dave C. Pottinger
Gamasutra
January 22, 1998
Vol. 3: Issue 3

Originally
Published in Game Developer Magazine, January, 1999.

Coordinated Unit Movement

Introduction Movement Issues Facing Game Developers Simple Movement Algorithm Collision Determination Discrete vs. Continuous Simulation Predicted Positions Unit to Unit Cooperation Basic Planning Basic Definitions

The basic goal of any collision determination system is to find out if two units have collided. For the time being, we'll represent all collisions as two-entity collisions. We'll cover compound collisions (collisions involving three or more entities) next month. Once a collision is found, each entity needs to know about the collision in order to make appropriate movement decisions.

Basic collision determination for most strategy games consists of treating all units as spheres (circles in 2D) and doing a simple spherical collision check. Whether or not such a system is sufficient depends on the specific requirements of a game. Even if a game implements more complex collision - such as oriented bounding boxes or even low-level polygon to polygon intersection tests - maintaining a total bounding sphere for quick potential collision elimination will usually improve performance.

There are three distinct entity types to take into account when designing a collision system: the single unit, a group of units, and a formation (see Figure 2 below). Each of these types can work well using a single sphere for quick collision culling (elimination of further collision checks). In fact, the single unit simply uses a sphere for all of its collision checking. The group and the formation require a bit more work, though.

Figure 2 Collision entities.

For a group of units, the acceptable minimum is to check each unit in the group for a collision. By itself, this method will allow a non-grouped unit to sit happily in the middle of your group. For our purposes, we can overlook this discrepancy, because formations will provide the additional, more rigid collision checking. Groups also have the ability to be reshaped at any time to accommodate tight quarters, so it's actually a good idea to keep group collision checking as simple as possible.

A formation requires the same checks as a group, but these check must further ensure that there are no internal collisions within the formation. If a formation has space between some of its units, it is unacceptable for a non-formed unit to occupy that space. Additionally, formations generally don't have the option to reshape or break. However, it's probably a good idea to implement some game rules that allow formations to break and reform on the other side of an obstacle if no path around the obstacle can be found.

For our system, we'll also keep track of the timing of the collision. Immediate collisions represent collisions currently existing between two objects. Future collisions will happen at a specified point in the future (assuming neither of the objects changes its predicted movement behavior). In all cases, immediate collisions have a higher resolution priority than future collisions. We'll also track the state of each collision as unresolved, resolving, or resolved.