Re: "Smart" movement

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

Bob Carragher wrote:
> 
> One quick question about towns:  will units continue to enter
> towns, unless the towns are full?  Let's say that you have a
> town which is the "pass" for a mountain range, and you have a
> bunch of armor on one side trying to make their way to the
> other side.  Will 2 armor enter (or pass through) the town in
> one turn?  Or will only 1 armor enter the town in one turn (and
> leave it the next)?

Is this a trick question? :-)  If transports (such as towns) are
between a unit and its destination, it will pass through each
one, not caring who else might be in the towns.  It's possible
that there are latent bugs in routefinding, but I don't know of
any that have been found but not fixed.

> How is distance defined?  Is it the number of cells separating
> the unit from the destination, regardless of terrain or unit
> occupation in the intervening cells?  Or are terrain and unit
> occupation taken into account?

No, the distance measurement is purely a formula, does not account
for any possible blockage.  This is partly because the situation
can change; if the pass is congested but I won't get there for four
more turns, there will be probably be room by the time I arrive.

> If it's the former, then in the example I showed (where an armor
> was sitting on a peninsula that jutted towards the destination,
> but was a dead-end), there is no direction that brings the unit
> closer to its destination.

That's right.

> > 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.
> 
> I guess this also depends upon the algorithm that sequentially
> picks units.  I know you have an algorithm which tries to pick
> units that are in a general area before moving on to another
> general area.  Is it possible for one unit to always be picked
> as one of the last ones in an area?

Networking forced some changes here.  Now unit movement always
happens in a consistent order, so that all games running in tandem
produce the same results.  The find-nearest algorithm is now
restricted to an interface's choice of which unit to present to
the player next.

> Is it possible to implement a maze-tracing scheme?  That is,
> one could conceivably imagine turning on a maze-tracing option
> where if you click on a destination, then a route is traced and
> highlighted.  You then click again to "accept" the route for the
> unit.  Or, you can try to modify the route.  The point is that
> the unit does its best to trace this route, deviating from it
> only when it absolutely must.  (E.g. the unit will stall rather
> than continue on the path if a unit blocks its path, unless the
> cell in which it is stalled causes it to lose fuel, etc.)

That would be really really cool.  We already have a bit of artwork
for arrows in the different directions (for wind display), so that's
available to use.  Another way to display is to copy the CivCTP
approach of updating intended route as the mouse moves around, and
use control-click or some such to set explicit intermediate points.

> This option could also be tailored so that it doesn't activate
> unless at least n cells separates the unit from its destination
> (as the armor rolls) -- and that preference could be set up on
> a unit-type basis or in general.  (E.g. an infantry moves only
> 1 cell at a time, so you might want to trace this for distances
> greater than 10 cells, but a jeep [used in my "abstract" period
> world for transporting ground troops] moves 3 cells at a time,
> so this might be activated only for distances greater than 20
> cells.)

If you had the on-screen feedback, then you would always know if
the unit was going to take a crazy route, and you could move the
mouse closer in, set a waypoint, then do routefinding only from
the last waypoint.

> Is this already implemented?  Is it too much hassle, or would
> cause a blow-up in memory?

It's certainly not implemented now!  It would be some work, but not
a ridiculous amount, and I don't think the memory consumption would
be huge, because the waypoints would just be tasks, and there is
already machinery to manage task queues effectively.  My big concern
would be compute time on large worlds.  Since a really twisted maze
route might have to wander all over the world, the algorithm to
compute the route might have to scan hundreds of thousands of cells,
so it needs to be possible to restrict the area being searched.

Stan