Re: "Smart" movement

[Stan Shebs <shebs at shebs dot cnchost dot com>]

Bob Carragher wrote:
> 
> The basic problem seems to be when there are congestion points
> between the current location of a unit and a destination point,
> and there are "local minima" that the unit can be trapped in.
> Let me try to illustrate.  Let's say that the traversable world
> roughly resembles the following (although the entire world is
> visible):

You're quite right that units can be trapped in local minima.
I'm skeptical about your observation of congestion points,
because there isn't anything in the code that treats towns
differently - if the only option to get somewhere is to enter a
town, the unit will just do it.  Just to be sure, I tried out
a case similar to yours, and the infantry strolled right through.

There a couple ways in which congestion points might appear to
exist.  First, if there is a choice of directions, units choose
one randomly.  Second, terrain might be constraining movement.
Third, the random choice is weighted by a number of factors,
such as terrain healthiness and unit mobility (see compare_directions
in task.c).

The routefinding algorithm right now is purposefully minimal;
this is so units don't go off and do something really stupid
while you're not looking.  It identifies two classes of directions,
the 1 or 2 directions that get the unit 1 cell closer to its
destination, and the 2 directions that don't change the distance.
The algorithm will fail rather than let the unit move further away,
since without a path plotted all the way to the destination,
there's no assurance that the unit will get there.

So first the unit tests the 1 or 2 directions and if there is
a choice, it randomly chooses (with weighting as described above)
one of them to try first, but eventually tries all if the actual
move action doesn't work.

If we can't get closer, then we have to try one of the other two
directions.  This is a little trickier, because we need to
remember which direction we're trying, so that if one fails,
we know to go back and try the other one.  So there is a state
variable that keeps track of whether we're sidling around to the
left or to the right.  Once we've chosen, we stay on the same
sideways path until we find a cell that gets us closer, or are
completely blocked sideways as well, in which case we give up
and ask the player what to do.  (An amusing failure mode is a
land unit trying to get to an island in the middle of a perfectly
circular lake; it will orbit the lake forever.)

The AI has an additional option at this point, which is to push
a task telling the unit to try moving to a new location off to the
side, then try the original task again.  But it may take the
opportunity to assign the unit to a different job instead.

If all this seems lame, well it is.  There should be a maze-solving
algorithm that sits over this.  Maze-solving may result in a
complicated path that takes too long - perhaps you just want to
get a unit to the closest shoreline so it can get picked up by
a transport that's almost done building - so there needs to be
some player control over when it's used.  (If anybody wants to
code this, use the distance-mapping algorithm as described in
various books; scratch memory layers are available for this.)

> (Please feel free to tell me that you've already gone over this
> hundreds of time both by yourselves and on this ML, and I should
> pay closer attention.  B-)

It's been gone over a lot, but it's certainly not a "done" area.

> Thanks for listening to my written thoughts!

Thanks for thinking and writing them!

Stan