Gamasutra - Features - Coordinated Unit Movement


				\|\|\|\|

By Dave C. Pottinger
Gamasutra
January 22, 1999

Originally
Published in
Game Developer Magazine,
January, 1999.

Letters to the Editor:

Write a letter

View all letters

Features

Basic Planning

Contents

Introduction

Movement Issues Facing Game Developers

Simple Movement Algorithm

Collision Determination

Discrete vs. Continuous Simulation

Predicted Positions

Unit to Unit Cooperation

Basic Planning

Basic Definitio ns

Planning is a key element of unit cooperation. All of these predictions and calculations should be as accurate as possible. Inevitably, though, things will go wrong. One of the biggest mistakes we made with the Age of Empires' movement was to make every decision within a single frame of reference. Every decision was always made correctly, but we didn't track that information into future updates. As a result, we ended up with units that would make a decision, encounter a problem during the execution of that decision, and then make a decision that sent them right back on their original path, only to start the whole cycle over again the next update. Planning fixes this tautology. We keep around the old, resolved collisions long enough (defined by some game-specific heuristic) so that we can reference them should we get into a predicament in the future. When we execute an avoidance, for example, we remember what object it is that we're avoiding. Because we'll have created a viable resolution plan, there's no reason to do collision checking with the other unit in the collision unless one of the units gets a new order or some other drastic change takes place. Once we're done with the avoidance maneuver, we can resume normal collision checking with the other unit. As you'll see next month, we'll reuse this planning concept over and over again to accomplish our goals.

Simple games are a thing of the past; so is simple movement. We've covered the basic components necessary for creating a solid, extensible movement system: a state-based movement algorithm, a scalable collision determination system, and a fast position prediction system. All of these components work together to create a deterministic plan for collision resolution.

Next month, we'll extend these concepts to cover higher-order movement topics, such as group movement, full-blown formation movement, and compound collision resolution. I'll also go into more detail about some implementation specifics that help solve some of the classic movement problems.

For Further Info

Take a look at Craig W. Reynolds' Boids work at http://hmt.com/cwr/boids.html.
Steven Woodcock's Game AI web site is located at http://www.cris.com/~swoodcoc/ai.html.
Also see Patrick Winston. Artificial Intelligence, 3rd ed. (Addison-Wesley, 1993.)

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 dpottinger@ensemblestudios.com.

Basic Definitions