Thread: [TuxKart-devel] Ideas for AI
Status: Alpha
Brought to you by:
sjbaker
Menu
▾
▴
tuxkart-devel
|
From: Aly M. <mer...@ac...> - 2004-06-29 14:19:53
|
Here are a few ideas for features in the AI: 1. Decision Making =20 Here are a few ways I've thought of handling decisions for the AI. Basic behaviours: The AI would have a list of higher level actions to choose from, something like "visit point of interest", "make wide turn", "make sharp turn" as opposed to something like "go left", "go right", "fire". Value map: All points of interest on the map have a value associated with them, these values radiate outwards and overlay on top of each other. And the car just follows the path of optimal value. Modeling certain things might be tricky, e.g. getting the car to fire at another car might involve modeling the other car as a good point of interest if it is moving faster than you and you have missiles, otherwise they are to be avoided. 2. Difficulty This will have something to do with the decision making code but in general I was thinking that the AI would probably pick sub-optimal actions at random and this factor could be varied for different difficulty levels. I'm wondering if there might be a better way, any ideas? 3. Knowledge of World Again tied to decision making. I am thinking that the AI would only know about things it can "see". It could keep a list of points along the boundaries as checkpoints it has to pass through, and it would have a list of points of interest for stuff like other cars, obstacles, herrings, etc. Are there other suggestions, or is there any compelling reason to know about the entire track? Aly --=20 Aly Merchant mer...@ac... http://cobe.dyndns.org |
|
From: Ryan F. <rf...@gm...> - 2004-06-29 17:38:39
|
On Tue, 29 Jun 2004 10:21:14 -0400, Aly Merchant <mer...@ac...> wrote: > 3. Knowledge of World > > Again tied to decision making. I am thinking that the AI would only > know about things it can "see". It could keep a list of points along > the boundaries as checkpoints it has to pass through, and it would > have a list of points of interest for stuff like other cars, > obstacles, herrings, etc. Are there other suggestions, or is there > any compelling reason to know about the entire track? As far as the road goes, AI should know *exactly* where to go. We should assume that the AI player has played each track hundreds of times and knows it off by heart. Even after I play a track for 5 laps (depending on size) I know every single turn by the last lap. If the AI players are still having trouble remember turns after I've played the game a hundred times, it'll probably be quite easy to beat. Of course low-level difficulty can be a little sloppy on this. Not sure if this is exactly what you meant by entire track, but they should know about turns in advance (because human players will). -- Ryan |
|
From: Aly M. <mer...@ac...> - 2004-06-29 18:54:36
|
On Tue, Jun 29, 2004 at 11:38:37AM -0600, Ryan Flegel wrote: > On Tue, 29 Jun 2004 10:21:14 -0400, Aly Merchant <mer...@ac...> wrot= e: >=20 > > 3. Knowledge of World > >=20 > > Again tied to decision making. I am thinking that the AI would only > > know about things it can "see". It could keep a list of points along > > the boundaries as checkpoints it has to pass through, and it would > > have a list of points of interest for stuff like other cars, > > obstacles, herrings, etc. Are there other suggestions, or is there > > any compelling reason to know about the entire track? >=20 > As far as the road goes, AI should know *exactly* where to go. We > should assume that the AI player has played each track hundreds of > times and knows it off by heart. Even after I play a track for 5 laps > (depending on size) I know every single turn by the last lap. If the > AI players are still having trouble remember turns after I've played > the game a hundred times, it'll probably be quite easy to beat. Of > course low-level difficulty can be a little sloppy on this. >=20 > Not sure if this is exactly what you meant by entire track, but they > should know about turns in advance (because human players will). What I mean is how much knowledge it actually requires to do whatever it needs to do. The way I see it the AI will probably only care about the track it will reach in the next 5 seconds, or maybe it will track up to the next 2 turns in the road. It's not going to be doing a full search on the entire course -- so what does it need to know about to be a decent AI? In my opinion considering the entire track on each decision would be a waste of time, it should be able to get away with making a decision based on its current surroundings. In the implementation we're probably just going to keep the track in memory, but here I'm just talking about the algorithm. Aly --=20 Aly Merchant mer...@ac... http://cobe.dyndns.org |
|
From: Ryan F. <rf...@gm...> - 2004-06-29 19:54:24
|
On Tue, 29 Jun 2004 14:55:54 -0400, Aly Merchant <mer...@ac...> wrote: > > On Tue, Jun 29, 2004 at 11:38:37AM -0600, Ryan Flegel wrote: > > On Tue, 29 Jun 2004 10:21:14 -0400, Aly Merchant <mer...@ac...> wrote: > > > > > 3. Knowledge of World > > > > > > Again tied to decision making. I am thinking that the AI would only > > > know about things it can "see". It could keep a list of points along > > > the boundaries as checkpoints it has to pass through, and it would > > > have a list of points of interest for stuff like other cars, > > > obstacles, herrings, etc. Are there other suggestions, or is there > > > any compelling reason to know about the entire track? > > > > As far as the road goes, AI should know *exactly* where to go. We > > should assume that the AI player has played each track hundreds of > > times and knows it off by heart. Even after I play a track for 5 laps > > (depending on size) I know every single turn by the last lap. If the > > AI players are still having trouble remember turns after I've played > > the game a hundred times, it'll probably be quite easy to beat. Of > > course low-level difficulty can be a little sloppy on this. > > > > Not sure if this is exactly what you meant by entire track, but they > > should know about turns in advance (because human players will). > > What I mean is how much knowledge it actually requires to do whatever it > needs to do. The way I see it the AI will probably only care about the > track it will reach in the next 5 seconds, or maybe it will track up to > the next 2 turns in the road. It's not going to be doing a full search > on the entire course -- so what does it need to know about to be a > decent AI? Yeah, I think two turns ahead is all that is needed. I can't see the computer needing to know any farther in advance. -- Ryan |
|
From: Steve B. <sjb...@ai...> - 2004-06-29 22:26:52
|
Aly Merchant wrote: > What I mean is how much knowledge it actually requires to do whatever it > needs to do. The way I see it the AI will probably only care about the > track it will reach in the next 5 seconds, or maybe it will track up to > the next 2 turns in the road. It's not going to be doing a full search > on the entire course -- so what does it need to know about to be a > decent AI? Certainly, when you are racing for real (which is something I've actually *done*!) you need to consider the entry to the NEXT corner when you plan your entry to this one. So certainly two turns ahead would work. You might find that really good drivers would be looking further ahead - but in this case, your choice of the perfect racing line becomes more and more eclipsed by the other people on the track (who may NOT be following a good line) and by the needs to dodge missiles or collect items along the way. I'd be rather suprised if you could usefully plan further than two turns ahead. > In my opinion considering the entire track on each decision would be a > waste of time... Yes - I agree. The thing is that a TuxKart track is a dynamic place. You could possibly save a few tenths of a second by planning three, four turns ahead - but by the time you get there, everything will have changed and all that early planning would be wasted. With this genre of games, it's MORE about the gadgets and collectibles than it is about racing perfectly. ---------------------------- Steve Baker ------------------------- HomeEmail: <sjb...@ai...> WorkEmail: <sj...@li...> HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net -----BEGIN GEEK CODE BLOCK----- GCS d-- s:+ a+ C++++$ UL+++$ P--- L++++$ E--- W+++ N o+ K? w--- !O M- V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++ -----END GEEK CODE BLOCK----- |
|
From: Charles G. <ch...@ve...> - 2004-06-29 18:10:51
|
On Tue, 2004-06-29 at 10:21 -0400, Aly Merchant wrote: > 2. Difficulty > > This will have something to do with the decision making code but in > general I was thinking that the AI would probably pick sub-optimal > actions at random and this factor could be varied for different > difficulty levels. I'm wondering if there might be a better way, any > ideas? The difficutly should also dictate the speed at which the AI drives. I also don't believe we should make each driver in the race be of increased difficulty so it is hard to get to #1. Some people aren't game wizards and they'll find it frustrating if they can't win on easy. Each driver should have particular strengths suited to particular types of level so that they are more prone to success on certain levels. Of course, there should be weak opponents too. As for determining strong AI vs weak AI, if you could classify actions as "good, bad, or normal", where strong AI will use a mix of good and normal, medium AI use mostly normal actions, and weak AI a mix of bad and normal actions, and an invincible AI that only makes good choices. -- - Charlie Charles Goodwin <ch...@ve...> Online @ www.charlietech.com |
|
From: Oliver J. <ol...@po...> - 2004-06-29 22:14:25
|
On Tue, Jun 29, 2004 at 06:11:22PM +0000, Charles Goodwin wrote: > > I also don't believe we should make each driver in the race be of > increased difficulty so it is hard to get to #1. Some people aren't > game wizards and they'll find it frustrating if they can't win on easy. I'm not exactly sure what you mean here, but I think there should be an approach similar to Mario Kart - where the AI ahead of you becomes weaker, and the AI behind you becomes stronger (or maybe just adjust the speed). This causes the karts to bunch a bit more and means that a good player always has a threat of being overtaken, and a weak player always has a chance to overtake. > As for determining strong AI vs weak AI, if you could classify actions > as "good, bad, or normal", where strong AI will use a mix of good and > normal, medium AI use mostly normal actions, and weak AI a mix of bad > and normal actions, and an invincible AI that only makes good choices. But how do you define good choices? Is it better to take the corner in the fastest possible way, or to take it in a slower way that leads to collecting a powerup? Basically, what you're saying is that we need to define some heuristics to determine what actions to take. It's not as simple as good/bad/normal decisions. For example, taking a slower route to collect a powerup makes less sense if you are in the lead. |
|
From: Charles G. <ch...@ve...> - 2004-06-29 23:22:59
|
On Tue, 2004-06-29 at 23:24 +0100, Oliver Jeeves wrote: > > I also don't believe we should make each driver in the race be of > > increased difficulty so it is hard to get to #1. Some people aren't > > game wizards and they'll find it frustrating if they can't win on easy. > > I'm not exactly sure what you mean here, but I think there should be an > approach similar to Mario Kart - where the AI ahead of you becomes weaker, > and the AI behind you becomes stronger (or maybe just adjust the speed). This > causes the karts to bunch a bit more and means that a good player always has > a threat of being overtaken, and a weak player always has a chance to > overtake. No, I meant that 'easy' should be really easy (ie a young kid should be able to win after a big of practise), 'medium' should be a mild challenge but nothing for experienced gamers, 'hard' should be a challenge for most people, and 'invincible' should be damn near unbeatable. I really don't like the idea of relative speeds according to how well or not somebody is playing. Not only does that cause problems for players (they approach the same corner at full speed in two parts of the race, only full speed has changed), it's also a challenge for the AI (same corner problem). > Basically, what you're saying is that we need to define some heuristics to > determine what actions to take. It's not as simple as good/bad/normal > decisions. For example, taking a slower route to collect a powerup makes less > sense if you are in the lead. No, it wouldn't be that simple. But that was an example of classifying actions. You would probably add 'attacking', 'defensive', and 'neutral' so that you would have aggressive AI, defensive AI, and AI that just races as fast as possible. It needs thinking through by somebody, but if we can add a couple of categories for classifying actions then we can really give AI characters a bit of *character*... the Octopus and Killer Whale could be really agressive, for instance, whilst Tux and Gown could be really defensive. -- - Charlie Charles Goodwin <ch...@ve...> Online @ www.charlietech.com |
|
From: Ingo R. <gr...@gm...> - 2004-06-30 01:02:30
|
Charles Goodwin <ch...@ve...> writes: > I really don't like the idea of relative speeds according to how > well or not somebody is playing. Not only does that cause problems > for players (they approach the same corner at full speed in two > parts of the race, only full speed has changed), it's also a > challenge for the AI (same corner problem). I consider automatic handicap adjustment basically the best invention since sliced bread in game development and its really the only way to get interesting gameplay. Without it you either end up far behind everybody else or far ahead of everybody else, none of this is any fun. With automatic handicap adjustment however you get quite exciting races and very often races where the last few meters matter. It doesn't cause any problems for the player, since the player drives always the same (unless you do multiplayer with enabled auto-handicap of course), only the AI changes its speed and the number of bonuses it uses. The only thing that one needs to keep care of are upper and lower bounds for how much the AI gets slow down or speed up, else you get easily unrealistic situations where the AI almost halts or drives insanly fast (this bug is currently triggerable in Tuxkart). So handicap ranges might look like this: Speed: 0...........100% Easy: [----] Medium: [---] Hard: [-] Thus ensuring that easy always stays easy and adopts to any kind of weak player, medium always provides a good chalange for the average player and on hard people are really forced to not make much mistakes, since the hanticap won't get adjusted much at all. -- WWW: http://pingus.seul.org/~grumbel/ JabberID: gr...@ja... ICQ: 59461927 |
|
From: Steve B. <sjb...@ai...> - 2004-06-30 02:47:47
|
Charles Goodwin wrote: > I really don't like the idea of relative speeds according to how well or > not somebody is playing. Not only does that cause problems for players > (they approach the same corner at full speed in two parts of the race, > only full speed has changed), it's also a challenge for the AI (same > corner problem). The problem is that with no dynamic handicapping, the karts get spread out all around the track and you just never see any of them after about 30 seconds into the race. The track is about a mile around - if everyone is well spread out, the nearest kart is a quarter mile away - which puts it somewhere two corners away. You'll never see it. For some kinds of game, that's realistic - but the trouble for a MarioKart clone is that most of the fun is not in driving really well - most of it is in the powerups and collectables. Blowing people away with missiles and bombs and things that shrink the enemy do half size...stuff like that. But if the enemy karts aren't somewhere nearby, none of that interesting stuff happens and we are left with "just another race game". The trick is to do it subtly enough so it's not really noticable - and make it such that good driving will let you beat them despite their tendancy to speed up behind you. MarioKart certainly does this...so do most other 'fighting-with-racing' games that I've played. > It needs thinking through by somebody, but if we can add a couple of > categories for classifying actions then we can really give AI characters > a bit of *character*... the Octopus and Killer Whale could be really > agressive, for instance, whilst Tux and Gown could be really defensive. Yes. Some kind of noticable character 'personality' could add a lot of play depth. If you know in advance how your opponent tends to react then you can strategize about how to beat them. Some might require good driving, others need to be blown to bits with exploding herring...whatever. ---------------------------- Steve Baker ------------------------- HomeEmail: <sjb...@ai...> WorkEmail: <sj...@li...> HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net -----BEGIN GEEK CODE BLOCK----- GCS d-- s:+ a+ C++++$ UL+++$ P--- L++++$ E--- W+++ N o+ K? w--- !O M- V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++ -----END GEEK CODE BLOCK----- |
|
From: Steve B. <sjb...@ai...> - 2004-06-30 02:36:24
|
Oliver Jeeves wrote: > On Tue, Jun 29, 2004 at 06:11:22PM +0000, Charles Goodwin wrote: > >>I also don't believe we should make each driver in the race be of >>increased difficulty so it is hard to get to #1. Some people aren't >>game wizards and they'll find it frustrating if they can't win on easy. > > > I'm not exactly sure what you mean here, He's saying that you have some number of AI players - graded from easy to beat to very hard to beat. Then, if you are a beginner, you'll come in close to last - and as you get better, you'll come in higher and higher up the ratings until *FINALLY* you can win a race. If I've interpreted it right - I think this sucks as a game concept. Probably I don't understand either! > but I think there should be an > approach similar to Mario Kart - where the AI ahead of you becomes weaker, > and the AI behind you becomes stronger (or maybe just adjust the speed). Yeah - that's what Tuxkart's AI does now - and people who figure it out *hate* it. No matter how hard or well you drive, you just can't get far enough ahead to guarantee a victory. The way to win is to drive around badly (it doesn't matter - the AI will slow down to let you keep up) - then just before the finish line, work hard - and before the AI players notice, you'll win almost every time. Clearly that sucks. I don't see the problem with doing this to a *mild* degree - because it does make the game more interesting...but that can't be the mechanism for keeping the game interesting. In the end, the tried-and-tested way is to have some number of levels of difficulty. Since we don't want to design too many characters (it's a LOT of work), it makes sense to allow each character to play at different skill levels and with differently powerful kart physics so they play at the skill level the player asks for. > But how do you define good choices? Is it better to take the corner in the > fastest possible way, or to take it in a slower way that leads to collecting > a powerup? That's what puts the 'I' in AI! Probably what you do is to build these preferences into the AI's "Character". You know - the suave sophisticated Penguin drives as best he can, the maniac Octopus goes for the powerups every time. The other guys pick randomly with variously skewed probabilities. This possibly leads to 'richer' game play. If you know the Octopus is behind you, maybe you make more effort to nab the goodies before he does. If you know the Penguin is going to ignore them, maybe you take the best racing line and drop a bananaskin there because you guess he'll go that way. > Basically, what you're saying is that we need to define some heuristics to > determine what actions to take. It's not as simple as good/bad/normal > decisions. For example, taking a slower route to collect a powerup makes less > sense if you are in the lead. Yep. ---------------------------- Steve Baker ------------------------- HomeEmail: <sjb...@ai...> WorkEmail: <sj...@li...> HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net -----BEGIN GEEK CODE BLOCK----- GCS d-- s:+ a+ C++++$ UL+++$ P--- L++++$ E--- W+++ N o+ K? w--- !O M- V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++ -----END GEEK CODE BLOCK----- |
|
From: Steve B. <sjb...@ai...> - 2004-06-29 22:16:32
|
Charles Goodwin wrote: > I also don't believe we should make each driver in the race be of > increased difficulty so it is hard to get to #1. Some people aren't > game wizards and they'll find it frustrating if they can't win on easy. Yes - I agree. The game should be challenging - but not so hard that you have to play it every evening for a month before you can win a race. > Each driver should have particular strengths suited to particular types > of level so that they are more prone to success on certain levels. Of > course, there should be weak opponents too. Yes - although we can do that with the karts rather than the AI. If some guys have karts with great maximum speed but crappy accelleration then a course with long straights would favor them over karts with good accelleration but poor straightline speed. On a wiggly course, the reverse might be the case. It should be more intuitive to juggle those kinds of numbers than it is to adjust the AI. ---------------------------- Steve Baker ------------------------- HomeEmail: <sjb...@ai...> WorkEmail: <sj...@li...> HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net -----BEGIN GEEK CODE BLOCK----- GCS d-- s:+ a+ C++++$ UL+++$ P--- L++++$ E--- W+++ N o+ K? w--- !O M- V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++ -----END GEEK CODE BLOCK----- |
|
From: Steve B. <sjb...@ai...> - 2004-06-29 22:42:29
|
Aly Merchant wrote: > Basic behaviours: > The AI would have a list of higher level actions to choose from, > something like "visit point of interest", "make wide turn", "make > sharp turn" as opposed to something like "go left", "go right", > "fire". The ideal thing would be for the outputs of the AI to be identical to the inputs that the player provides via his controls. That way the same physics apply to AI and players. However, it may be that we can make life easier for the AI code by providing a different interface - or even allowing it to cheat by going in at a lower level than the player's inputs. > Value map: > All points of interest on the map have a value associated with them, > these values radiate outwards and overlay on top of each other. We'd need to write a tool to prepare that map. RAM storage for it might be a problem if it has to be held at high resolution for a large track. If you'd like a 5 lap race to last 5 minutes with average speeds of 60mph (reasonable for a GoKart) - then the course has to be a mile long. That could mean that the 'interest map' could easily need to be (say) 1000 meters on a side...I'd guess your map would need to be about 1 meter resolution? So we'll be eating about a megabyte for every byte we store in the map. On lower end systems, that could become a problem. If you only need a couple of bytes per location on the map, that might not matter - but if you needed a dozen bytes per location, the storage could kill us. > And > the car just follows the path of optimal value. Modeling certain > things might be tricky, e.g. getting the car to fire at another car > might involve modeling the other car as a good point of interest if > it is moving faster than you and you have missiles, otherwise they are > to be avoided. Things like collectibles (which might go away when someone collects them) and missiles make the map somewhat dynamic though. There are certain to be ways around that - but it has to be concidered. ---------------------------- Steve Baker ------------------------- HomeEmail: <sjb...@ai...> WorkEmail: <sj...@li...> HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net -----BEGIN GEEK CODE BLOCK----- GCS d-- s:+ a+ C++++$ UL+++$ P--- L++++$ E--- W+++ N o+ K? w--- !O M- V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++ -----END GEEK CODE BLOCK----- |
|
From: Charles G. <ch...@ve...> - 2004-06-29 23:10:32
|
On Tue, 2004-06-29 at 17:44 -0500, Steve Baker wrote: > The ideal thing would be for the outputs of the AI to be identical > to the inputs that the player provides via his controls. That way > the same physics apply to AI and players. Ooo yes, I like that approach. > However, it may be that we can make life easier for the AI code by > providing a different interface - or even allowing it to cheat by > going in at a lower level than the player's inputs. The notion of the AI cheating isn't the greatest feeling for a player. But it is a common approach in many games to add more challenge - to let the AI cheat rather than play well. Personally, I feel that it takes away from the game. I hate, for example, in Civ2 (and most likely Freeciv) on the harder difficulties the AI makes more money and gets more resources than you. It's not good, it makes decisions as bad as on lesser difficulties settings, it just gets to cheat. > > Value map: > > All points of interest on the map have a value associated with them, > > these values radiate outwards and overlay on top of each other. > > We'd need to write a tool to prepare that map. > > RAM storage for it might be a problem if it has to be held at high > resolution for a large track. > > If you'd like a 5 lap race to last 5 minutes with average speeds of > 60mph (reasonable for a GoKart) - then the course has to be a mile > long. That could mean that the 'interest map' could easily need to > be (say) 1000 meters on a side...I'd guess your map would need to be > about 1 meter resolution? So we'll be eating about a megabyte > for every byte we store in the map. On lower end systems, that > could become a problem. > > If you only need a couple of bytes per location on the map, that > might not matter - but if you needed a dozen bytes per location, > the storage could kill us. Each location would surely just be a point on the map. Scale and size really shouldn't matter. Put your thinking cap on Steve. ;) That was a very knee-jerk bit of reasoning on how you'd approach it. -- - Charlie Charles Goodwin <ch...@ve...> Online @ www.charlietech.com |
|
From: Jacob P. <st...@ap...> - 2004-06-30 01:03:45
|
Let's get a bit more specific on how the ai are supposed find it's way around the track. I think some kind of waypoint system would be nice to keep calculations down. -- Name: Jacob Persson Homepage: www.apollo.nu/~straver/ |
|
From: Steve B. <sjb...@ai...> - 2004-06-30 03:01:24
|
Jacob Persson wrote:
> Let's get a bit more specific on how the ai are supposed find it's way around
> the track. I think some kind of waypoint system would be nice to keep
> calculations down.
Well, that's pretty much what I have in TuxKart right now.
When I model a track, I build a second model which is just a set of
points that describe what I believe is a reasonable 'racing line'.
The AI attempts to follow that line.
However, there are some serious problems with that right now.
1) Think about a righthand hairpin turn (eg the first corner
in Oliver's math class where the 'walls' between the track
sections are very thin books and the track sections are very
wide). What happens is that if you are on the entry to that
curve and you hug the right-hand wall, you are actually closer
to the 'waypoint' on the other side of the wall than you are
to the waypoint on your side of the wall. This causes the AI
characters to head-butt the wall endlessly.
2) The waypoints are in 2D - not 3D. Hence, tracks with crossovers
in them (eg Gowns Bow) just flat out don't work. Head-butting
happens all the time in these tracks because the AI's forget
whether they are going over or under the bridge.
3) 3D waypoints don't work when there are jumps and such. The player
can sail over a waypoint at sufficient height that we cause problem
(1) but in 3 dimensions instead of 2.
4) Computer players only hit the powerups by luck.
5) You can't have tracks with alternative routes through them. There
is a really GREAT track on MarioKart'64 that's almost a maze. My
scheme can't cope with that.
6) You can't easily have tracks with dynamically changing routes through them.
I'd like stuff like large turntables that you have to hit at just the
right time if you want to take the shortcut - otherwise you're stuck
with taking the long way around. Things like in WaveRacer'64 where a
shortcut opens up only on the last lap.
So waypoints have their problems...maybe not insurmountable...but
certainly problems that you need to think through in the light of
my sad experience!
---------------------------- Steve Baker -------------------------
HomeEmail: <sjb...@ai...> WorkEmail: <sj...@li...>
HomePage : http://www.sjbaker.org
Projects : http://plib.sf.net http://tuxaqfh.sf.net
http://tuxkart.sf.net http://prettypoly.sf.net
-----BEGIN GEEK CODE BLOCK-----
GCS d-- s:+ a+ C++++$ UL+++$ P--- L++++$ E--- W+++ N o+ K? w--- !O M-
V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++
-----END GEEK CODE BLOCK-----
|
|
From: Charles G. <ch...@ve...> - 2004-06-30 03:21:19
|
On Tue, 2004-06-29 at 22:03 -0500, Steve Baker wrote: > When I model a track, I build a second model which is just a set of > points that describe what I believe is a reasonable 'racing line'. > > The AI attempts to follow that line. > > However, there are some serious problems with that right now. > > 2) The waypoints are in 2D - not 3D. Hence, tracks with crossovers > in them (eg Gowns Bow) just flat out don't work. Head-butting > happens all the time in these tracks because the AI's forget > whether they are going over or under the bridge. Well this is addressed by the aforementioned "2 corner" technique because you can't forget which corner you are heading towards, right? As for going over/under the bridge, you'd want to put a waypoint both on and under said bridge. > 1) Think about a righthand hairpin turn (eg the first corner > in Oliver's math class where the 'walls' between the track > sections are very thin books and the track sections are very > wide). What happens is that if you are on the entry to that > curve and you hug the right-hand wall, you are actually closer > to the 'waypoint' on the other side of the wall than you are > to the waypoint on your side of the wall. This causes the AI > characters to head-butt the wall endlessly. Perhaps waypoints should come in multiple forms, where for cases like hairpins you'd want two vectors (in / out angle) instead of a single point. > 3) 3D waypoints don't work when there are jumps and such. The player > can sail over a waypoint at sufficient height that we cause problem > (1) but in 3 dimensions instead of 2. Way points need to become 'only a guide'. There must be some way by which Tuxkart establishes whether a human player is a certain portion around the track to stop the player cutting across the track and missing out entire sections. The AI should use that as it's ultimate decision, then pick the nearest waypoint _ahead_ so that ones left behind are ignored once they are behind. > 4) Computer players only hit the powerups by luck. This is part of the decision making stuff, whether to hug the racing line or go for a power up. Again this would probably be done by overloading waypoints, a 'powerup waypoint' so to speak. > 5) You can't have tracks with alternative routes through them. There > is a really GREAT track on MarioKart'64 that's almost a maze. My > scheme can't cope with that. > > 6) You can't easily have tracks with dynamically changing routes through them. > I'd like stuff like large turntables that you have to hit at just the > right time if you want to take the shortcut - otherwise you're stuck > with taking the long way around. Things like in WaveRacer'64 where a > shortcut opens up only on the last lap. ...so we need a new scheme. ;) -- - Charlie Charles Goodwin <ch...@ve...> Online @ www.charlietech.com |
|
From: Steve B. <sjb...@ai...> - 2004-06-30 03:39:25
|
Charles Goodwin wrote:
> ...so we need a new scheme. ;)
The thing I'd like to consider is something like a 'vector field'.
A large array (and as I explained earlier - it would be LOTS of memory)
where for every (say) 2meter x 2meter square there would be (say) two bytes.
Packed into these 16 bits there would be:
1) The compass direction to steer along in order to reach the best
racing line in the optimal way from this point.
2) The distance to the nearest powerup that's further down the
track and 'reasonably' gettable without deviating wildly from
the racing line.
3) The direction to that powerup.
Armed with this information, the AI can figure out where to go if they
want a powerup, where to go if they want to just drive - and (using the
distance metric and the difference between the two directions) whether
they really want to go out of their way to collect said powerup.
Now - there are some complications.
The map changes when a powerup is collected. This change is far-reaching
and would result in a ton of complicated realtime calculations.
The good direction is sometimes blocked by another kart.
There is still a problem with bridges, crossovers, and dynamic things.
---------------------------- Steve Baker -------------------------
HomeEmail: <sjb...@ai...> WorkEmail: <sj...@li...>
HomePage : http://www.sjbaker.org
Projects : http://plib.sf.net http://tuxaqfh.sf.net
http://tuxkart.sf.net http://prettypoly.sf.net
-----BEGIN GEEK CODE BLOCK-----
GCS d-- s:+ a+ C++++$ UL+++$ P--- L++++$ E--- W+++ N o+ K? w--- !O M-
V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++
-----END GEEK CODE BLOCK-----
|
|
From: Charles G. <ch...@ve...> - 2004-06-30 04:13:04
|
On Tue, 2004-06-29 at 22:41 -0500, Steve Baker wrote: > The thing I'd like to consider is something like a 'vector field'. > > A large array (and as I explained earlier - it would be LOTS of memory) > where for every (say) 2meter x 2meter square there would be (say) two bytes. I really think this is an unecessary approach. If you model each waypoint as a vector with a direction (or two vectors in the case of turns) then you can easily work out where to head and how. A giant array full of vectors is memory consuming, hard to set up (imagine doing it manually) and complicated when things change. That's just doing it the hard way. Here's an example solution for the 'next waypoint' method. If you say a waypoint is a vector, when a kart passes the normal plane to the vector then it targets the next vector. This way, even if a kart takes a really wide birth or jumps over it, the kart cannot miss the waypoint. To make sure bad behaviour doesn't occur, you can add in extra conditions for when the angle to the normal is acute. It can all be done with simple (single or double) vector way points. A trackwide grid of vectors is just so overkill and so problematic. I would go as far to say that it would be _madness_! ;) -- - Charlie Charles Goodwin <ch...@ve...> Online @ www.charlietech.com |
|
From: Steve B. <sjb...@ai...> - 2004-06-30 05:32:56
|
Charles Goodwin wrote: > On Tue, 2004-06-29 at 22:41 -0500, Steve Baker wrote: > >>The thing I'd like to consider is something like a 'vector field'. >> >>A large array (and as I explained earlier - it would be LOTS of memory) >>where for every (say) 2meter x 2meter square there would be (say) two bytes. > > > I really think this is an unecessary approach. [ I'm playing devils advocate here - I want to discuss this some more to elicit deeper thinking without necessarily agreeing with everything I'm saying! ] 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. 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. The vector field approach gives you a fast, reliable way to get out of any situation. For any location on the map, you know simply and unambiguously how to get back to the racing line via the fastest possible route - even if you have to quite literally negotiate a maze to do it. I agree though that it's going to be hard to generate and that it'll consume quite a bit of RAM - so your way may be more practical (I believed that waypoints were the right thing to do when I first wrote TuxKart - but practical experience with trying to kludge around various practical problems leads me to wonder whether something different would help. We can attempt to fix the problems with waypoints by restricting the kinds of tracks we generate - but all of the exciting and interesting possibilities keep tripping up if you impose too many artificial design limitations. ---------------------------- Steve Baker ------------------------- HomeEmail: <sjb...@ai...> WorkEmail: <sj...@li...> HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net -----BEGIN GEEK CODE BLOCK----- GCS d-- s:+ a+ C++++$ UL+++$ P--- L++++$ E--- W+++ N o+ K? w--- !O M- V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++ -----END GEEK CODE BLOCK----- |
|
From: Charles G. <ch...@ve...> - 2004-06-30 06:11:17
|
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
|
|
From: Oliver J. <ol...@po...> - 2004-06-30 11:49:02
Attachments:
waypoints.png
arrows.png
|
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... |
|
From: Flash <fl...@da...> - 2004-06-30 12:29:15
|
Looks like a damned good idea, the pictures really make it clear to, this is what I tried to say with my picture to. I would just suggest on top of your pictures add points of interest and points of non interest which wil= l be the form of 'good' and 'bad' herrings so the AI can either try to go around them or try to catch them on top of just following the arrows. <quote who=3D"Oliver Jeeves"> > This is basically how I would have tried to tackle the problem, althoug= h 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 misunderstoo= d). > > 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 prov= en > 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 attache= d > 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. =3D=3D=3D=3D http://www.daaw.org - webhosting http://www.gamesleague.com - Games, servers, leagues and more |
|
From: Charles G. <ch...@ve...> - 2004-06-30 23:10:06
|
On Wed, 2004-06-30 at 12:58 +0100, Oliver Jeeves wrote: > 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). You understood me, but I explained it poorly. (It's been 5 years since I last did anything vector related, added to the fact it was 6am and I'd just finished a monstor programming session.) > 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... Yes! That is exactly the kind of compromise I was alluding to. That's probably the ideal solution to our problem. I was really (in my mind) giving double-meaning to waypoints, not just associating them with single points but also with areas. Your diagrams are an exact illustration of how I visualised it. Excellent. -- - Charlie Charles Goodwin <ch...@ve...> Online @ www.charlietech.com |
|
From: Aly M. <mer...@ac...> - 2004-06-30 06:19:47
|
On Wed, Jun 30, 2004 at 12:35:13AM -0500, Steve Baker wrote: >=20 > [ I'm playing devils advocate here - I want to discuss this some more > to elicit deeper thinking without necessarily agreeing with everything > I'm saying! ] >=20 > 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. >=20 > With waypoints, if I somehow get knocked off the road and there is a > wall between me and the waypoint, I'm completely stuck. >=20 > 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. >=20 > The vector field approach gives you a fast, reliable way to get out of > any situation. For any location on the map, you know simply and > unambiguously how to get back to the racing line via the fastest > possible route - even if you have to quite literally negotiate a maze > to do it. These are some of the problems I think the "optimum value" decision making algorithm could address. Walls are not things you want to encounter so they radiate a negative value, and if the AI finds itself face to face with a wall, it will notice that turning yields the optimum value. Now this probably wouldn't be as good as a fully tweaked vector map, but I think it would be able to yield a decent racing line. Also, you only need to calculate the values your possible destinations, so making a turn, going forward and going backwards put you at a certain destination and the value of a destination point can be calculated fairly easily. Waypoints would probably work their way in by being points of interest which radiate positive values. Also, if an algorithm like this is what you had in mind for generating the vector field in the first place, then using this approach you would only calculate the vectors you are interested in and you get things like bonuses and enemy car information added in. Whether this outweighs the speed of having a ton of precomputed information available is another matter. Aly |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X