This is the mail archive of the xconq7@sourceware.cygnus.com mailing list for the Xconq project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

"Smart" movement


Hello again!

I guess it's too much fun to delurk.  B-)

I have another item for the standard (introductory) game.  The
algorithm which determines how units move from one sector to
another (which is separated by some distance) has exhibited
somewhat strange behavior.  Unfortunately, I don't have a
saved copy of the game, although hopefully it will be easy to
duplicate.

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):

                           ..      ..
                          ....    .X1.
                       ..  ..  ..  ..  ..
                      ....    .X2.    .X3.
                   ..  ..  ..  ..  ..  ..  ..
                  ....    ....    town    .bb.
               ..  ..  ..  ..  ..  ..  ..  ..
              ....    ....    ....    ....
           ..  ..  ..  ..      ..      ..
          ....    ....
           ..  ..  ..
              ....
           ..  ..  ..
          ....    ....
           ..  ..  ..
              .X4.
           ..  ..  ..      ..
          .X5.    town    .YY.
           ..  ..  ..  ..  ..
              .X6.    ....
               ..  ..  ..  ..
                  .X7.    .aa.
                   ..  ..  ..
                      ....
                       ..

Note:  this is not to imply that the rest of the world is not
known or somehow invisible.  Just that the unit cannot traverse
the other sectors (e.g. the towns border on the ocean, and
armor units cannot tread over water).

So, let's say that you have an armor unit at hex "aa" (in the
lower righthand corner), and you click on sector "bb" (in the
upper righthand corner).  There are several obvious choke points
(which I define to be single hexes which, if permanently blocked,
would eliminate all feasible paths for the infantry from "aa" to
"bb").  I've labelled them "X1" through "X7."  Clearly, hex "X4"
is a choke point.  But the other are as well if one assumes that
a unit will not enter a town (or any other unit) unless explicitly
told to.  My experience is that this is the case.  So, for example,
if one parks an infantry at any of these other locations, the
armor unit will be blocked.

Anyway, my experience is that the armor unit will eventually
end up stuck at location "YY."  Although that is obviously a
dead-end, it is the closest location to bb if any of the choke
points "X4" through "X7" are occupied when the algorithm which
determines paths is applied to said armor unit.

In the particular game that I was playing, this scenario happened.
There were other towns near this section of the world that were
producing infantry and armor, and they would slowly make their
way either around (in the case of infantry) or through (in the
case of armor) these choke points, although some would be
selected to go to the local minimum (hex "YY").

Bottom line:  is this reasonable behavior?  I think the answer
should be "no," but I can't come up with a way around the
problem that doesn't make the algorithm horribly complicated.
For example, one could allow units to enter the towns (something
that seemed disabled or disallowed in the introductory game),
and use them to go around the choke points (in effect eliminating
those choke points).  Also, one could allow the algorithm to
examine the goals of those units blocking the choke points -- if
their object is to move to a point beyond the immediate choke
point, then (hopefully) they would eventually accomplish that
goal, and so those units that would become stuck at local minima
would somehow queue up behind the ones ahead of them and eventually
move towards their goal after the blocking units clear.

In the first case, there might be side effects which players would
be surprised by.  For example, a town might fill up, and not be
able to produce anything, even if its production might normally
be completed.  Or a transport might fill up and move in a
direction counter to the goal of the unit.

In the second case, how do you know that the blocking units' goals
will enable them to clear the choke points.  Worse, you might have
units heading in opposite directions through the choke points, and
this might create a deadlock!

(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-)

Thanks for listening to my written thoughts!

				Bob

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]