Long and short term goals
I've concentrated on the task of finding paths from one place to
another. However, a lower level 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, path-finding 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.
I've concentrated on path-finding, 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 (which takes longer to compute).
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". Gamedev has an article about splines for 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 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. 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.''
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.