Re: [TuxKart-devel] Ideas for AI

[Charles G. <ch...@ve...>]

On Wed, 2004-06-30 at 00:35 -0500, Steve Baker wrote:
> Where a vector field really scores is when the polygonal representation of
> the track is very complex.   With any kind of waypoint representation, there
> is an underlying assumption that you can't get stuck behind a wall or
> something.  Preventing that from happening in the absence of other
> information is really hard.
> 
> With waypoints, if I somehow get knocked off the road and there is a
> wall between me and the waypoint, I'm completely stuck.

Many, many games have AI for 3d path finding.  I refuse to believe it is
that difficult.

> Similarly, if I'm somehow pushed off course and ended up somewhere where
> there is a shorter route to the waypoint-after-next than going to the
> next waypoint - then I'm probably going to mindlesslyy turn right around,
> drive to the waypoint that was supposed to be next and then take the long
> way to the waypoint after that.

I get the feeling you just didn't read properly my comment on how to
avoid this with vector way points.

Use the vector's NORMAL PLANE to negate this.  I could be mixing
terminology here, so I'll do a little diagram:

if 'y' is up, 'x' is across, and 'z is out of the screen:

      |
      |
      |
______|_______

If your vector is (in this case) 'y', then what I refer to as the normal
plane is that flat bottom line but extending outwards (ie along the 'z'
axies) as well as across (ie along the 'x' axis).

If your two way points are roughly in a straight line (ie not too much
of a difference between vector angles) then it's incredibly difficult to
be closer to one vector without having cross the NP of said vector.

But... that's not enough, obviously.  There are tight curves in Tuxkart,
we have to account for those.

We already submitted that we need to think about 2 waypoints at a time,
and this is actually a convenient way of _always_ heading for the right
waypoint.  Consider waypoints w1, w2, w3, and w4.

If you consider both the next waypoint and the waypoint beyond it - w1
and w2 - and if you cross the NP of w1 then you make your secondonday
(w2) waypoint the primary waypoint (ie move from [w1,w2] to [w2,w3]).
If you cross the NP of w2, then the next way point needs to be the
previously unconsidered tertiary waypoint (ie move from [w1,w2] to [w3,
w4]).

So that handles curves.

Next scenario, shortcuts.  Well, we just add extra waypoint here and you
go into decision making mode.

But then you could still have _really_ awkward spots.  Well, the way to
go about them could be an amalgamtion of approaches.  Perhaps waypoints
could be associated with areas rather than just points.  That way you
can switch waypoints when a kart enters an area without having to really
think about it.  It also drops the memory requirements because you can
just have single way points for large areas.

Also, with vector waypoints, the kart doesn't need to head straight for
said waypoint, it can always aim at an angle that puts it on target for
the next waypoint.

Thinking about it, a combination of a scalable vector field and
waypoints is probably the best approach.  The advantage of a 3d vector
field is that it will work well for things like bridges and jumps where
a kart could fall onto a different section of the track.  Making it
scalable is important for ensuring the track isn't difficult to manage.

It all needs thinking through both mathematically and problematically
but I really think we can address this efficiently and relatively simply
without resorting to something as dire as a micro-structured vector
field like you're suggesting - remember that it has to be 3d makes that
an even worse proposition.
-- 
- Charlie

Charles Goodwin <ch...@ve...>
Online @ www.charlietech.com