I’ve concentrated on the task of finding paths from one place to another. However, an equally important question is: once I have a path, how do I move along it? The most obvious answer is moving in a straight line from one location to the next. However, you might also want to move in a curve, or have multiple levels of movement. You may want to treat the locations as a low-priority goal from which you deviate. A higher level question is: where do you want to go? Unless you first answer the higher level question, pathfinding is not very useful. Certainly, one form of goal setting is asking the user to click on the destination. However, you may have automated tasks as well—exploring, spying, attacking, and building are common ones.
Unit movement#
I’ve concentrated on pathfinding, which reduces the problem of moving from one location to another with the many smaller problems of moving from one space to an adjacent space.
You could move in a straight line from one location to the next but there are alternatives. Consider the four movement paths on this diagram:
The red path is the standard approach: move from the center of one square to the center of the next. The green path is somewhat better: move in straight lines between the edges between the tiles, instead of the center of the tiles. You might also try moving in straight lines between the corners of tiles. The blue paths use splines, with dark blue being low order splines and light blue being a higher order spline.
Lines between corners and edges of tiles will be the shortest solution. However, the splines can make your units seem less mechanical and more “alive”. It’s a cheap trick but not a great one. There are better ways to handle movement.
If your units cannot turn easily, you may want to take that into account when plotting a movement path. Craig Reynolds has a great page about steering[1] that has a paper about steering and Java applets demonstrating various behaviors. If you have more than one unit moving along a path, you may also want to investigate flocking[2]. Craig recommends that instead of treating paths as a list of places your unit must visit, you treat paths as “a guideline, from which you deviate reactively as conditions require.”
If you’re using grids for pathfinding, your units are not constrained to grids, and movement costs are uniform, you may want to straighten the paths by moving in a straight line from one node to a node far ahead when there are no obstacles between the two. If you’re using navigation meshes, look at the funnel algorithm[3].
Behavior flags or stacks#
Your units may have more than one goal. For example, you may have a general goal like “spying” but also a more immediate goal like “go to the enemy headquarters”. In addition, there may be temporary goals like “avoid that patrol guard”. Here are some ideas for goals:
- Stop: Stay in the current location
- Stay: Stay in one area
- Flee: Move to a safe area
- Retreat: Move to a safe area, while fighting off enemy units
- Explore: Find and learn about areas for which little information is known
- Wander: Move around aimlessly
- Search: Look for a particular object
- Spy: Go near an object or unit to learn more about it, without being seen
- Patrol: Repeatedly walk through an area to make sure no enemy units go through it
- Defend: Stay near some object or unit to keep enemy units away
- Guard: Stay near the entrance to some area to keep enemy units out
- Attack: Move to some object or unit to capture or destroy it
- Surround: With other units, try to surround an enemy unit or object
- Shun: Move away from some object or unit
- Avoid: Stay away from any other units
- Follow: Stay near some unit as it moves around
- Group: Seek and form groups of units
- Work: Perform some task like mining, farming, or collecting
For each unit you can have a flag indicating which behavior it is to perform. To have multiple levels, keep a behavior stack. The top of the stack will be the most immediate goal and the bottom of the stack will be the overall goal. When you need to do something new but later want to go back to what you were doing, push a new behavior on the stack. If you instead need to do something new but don’t want to go back to the old behavior, clear the stack. Once you are done with some goal, pop it from the stack and start performing the next behavior on the stack.
Waiting for movement#
It is inevitable that the movement algorithm will run into obstacles that were not there during the pathfinding process. An easily implemented technique is based on the assumption that the other obstacle will move first. This is particularly useful when the obstacle is a friendly unit. When an obstacle is in the way, wait some amount of time for it to move. If it still hasn’t moved after that period of time, recalculate a path around it or to the destination. If the obstacle is detected ahead of time, your unit can simply walk slower to give the other unit more time to get out of the way.
It is possible that two units will bump into each other, and each will wait for the other to proceed. In this case, a priority scheme can be used: assign each unit a unique number, and then make the lower numbered unit wait for the higher numbered unit. This will force one of the units to proceed if both are waiting. When obstacles are detected ahead of time, the lower numbered unit should slow down before reaching the expected point of collision.
Coordinated movement#
The technique described above does not work when units are trying to move through a narrow corridor. If one unit stands still while the other tries to go around, the corridor can’t be used by both units. One unit will block it while the other one will take a long path around.
It should be possible for the second unit to communicate with the first one, and ask it to back up. Once the corridor is clear, the second unit can pass through, and then the first unit can go through. This may be complicated to implement unless you can identify the corridors beforehand. For randomly generated maps, it could be very difficult to determine where the corridor is and how far the first unit needs to back up.