Re: [TuxKart-devel] Ideas for AI

[Oliver J. <ol...@po...>]

On Wed, Jun 30, 2004 at 06:11:51AM +0000, Charles Goodwin wrote:
> 
>       |
>       |
>       |
> ______|_______
> 
> 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.

This is basically how I would have tried to tackle the problem, although I 
don't think you've explained it as well as you could have (either that, or 
you're describing something completely different, and I've misunderstood).

Firstly, let me say that the 'array of arrows' type approach would work 
relativly well - it's the approach using in Micromachines, so it's proven to 
work, although even Micromachines had its bugs. And I think this would have 
exactly the same problems on as figure-8 as there are currently.

But anyway...

I think having vectors as way points is a good idea. It can (and should)
still be thought of in 2D; you have your line through the centre of the
track, and crossing this line you have many waypoint lines [see attached
picture]. Rather then having the AI aim for particular points then, the best
route (not taking into account powerups) is to find the shortest path
through the next few way points.

This allows for the AI to use heuristics like 'going for a powerup is ok as 
long as I'm still heading towards the next waypoint'.

This will work with tracks that cross, as the waypoints are in order and the
AI can always head for the next one, and this method can also be extended to
take into account shortcuts.

Waypoints would have to be positioned so that any line between two adjacent 
waypoints does not hit any obsticle, and the waypoints need to go close 
enough to the edge of the track so that the AI can't 'miss' the waypoint and 
end up circling back.

On another note, I think the 'array of arrows' method could _possibly_ be
improved by instead of having a huge array, splitting the map into 'areas'
and having directions assigned to each of these areas. If you had an array,
many adjacent arrows would be pointing in the same direction, and there would
be a lot of duplicate information. I have attached another diagram. The
question is whether using this method, you could cut down the amount of areas
significantly enough so that the extra information used to store the
boundaries of the areas doesn't make it less efficient...