• Advertisement
Sign in to follow this  

Racing AI - part 47Million

This topic is 4721 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I know there are other threads on Racing AI, however none of them seem to take into account some of the problems I'm currently dealing with. I have a track. It could be any sort of whacky shape. It is marked along its route by a series of waypoints. So, obviously the AI should follow these? But not so fast! I run into a problem with a simple checkpoint->checkpoint following setup. Our cars use a fairly realistic physics model, so they can slide around alot. Often the AI is travelling too fast to intercept the next waypoint, or worse, if there are a long series of straight waypoints followed by a tight corner he will not 'see it coming' and just blast off into a tree someplace. My question then: What is a good way of connecting these waypoints together to form a more smooth line. Bezeir curves? I looked into them, but was confused as to how I would find if a given point is on the curve, near the curve, or whatever. The method used to connect the points would need a few features I think. I would need to be able to find the instantaneous radius (or average radius over a distance) at a given point on the curve, so I could take a series of these over a section of track and attempt to decide exactly what is a corner, and what is not. My cars AI already knows exactly what speed it must travel to turn a corner of a given radius, so if I had some way of checking ahead, I could plan braking points accordingly. Would it be best if the car attempted to keep itself ON the line? Aim itself at a dot on the line ahead some distance (with the distance based on its speed?) Would there be any difference between the two approaches? Any other methods used to follow a track? Maybe break it up into polygon sections and uh...do a little dance with them? Other problems: My AI will also need to take corrective measures to deal with understeer/oversteer/locked wheels, actions of other cars, and so on. Obviously these may (and WILL) conflict with the control inputs required to keep it on track. How do you decide which takes priority? Do you blend them together based on some weight factors? I've heard of Neural Nets for this kind of thing, but I dont know anything about them so I'd think it's sort of beyond my abilities to implement. I have a few ideas I'm going to look into, but I'd appreciate it if someone with more experience with this sort of thing could point me in the right, or at least a less wrong, direction.

Share this post


Link to post
Share on other sites
Advertisement
here's an alternative solution

http://www.ai-junkie.com/misc/hannan/hannan.html

Share this post


Link to post
Share on other sites
Usually: Move towards the next checkpoint.

Also, look two checkpoints ahead (or more), and see if anything is intersecting a line between you and the checkpoint.

If it is, then you start stearing and braking. (depening on when and where it is).

This would detect the hairpin turn, go into a skid, turn on full lock, and get it arround the corner (before correcting after the corner).

From,
Nice coder

Share this post


Link to post
Share on other sites
Quote:
Original post by fup
here's an alternative solution

http://www.ai-junkie.com/misc/hannan/hannan.html


That's a nueral network approach, and way beyond the scope of what I'm doing (I think?!).
Also that link doesnt actually mention anything specific enough to be useful. It's pretty much
"so I uh..made this AI that learns driving."
"how?"
"that's classified"
"oh."

Quote:
Original post by Nice Coder
Usually: Move towards the next checkpoint.

That was the first attempt and it is no where near sufficient. Often they miss the waypoint entirely, or spin out struggling to get near it at the last second.

Quote:

Also, look two checkpoints ahead (or more), and see if anything is intersecting a line between you and the checkpoint.
This would detect the hairpin turn, go into a skid, turn on full lock, and get it arround the corner (before correcting after the corner).


Can you expand on this? Looking a checkpoint ahead, what exactly am I looking for intersecting? Can this detect the severity of the turn? On some tracks it is necessary to brake 2-3 screen lengths in advance for a turn, and the AI struggles with this concept.

Share this post


Link to post
Share on other sites
Maybe you could something as, optimal angle thing to all the waypoints, So the Car tries to "enter" the waypoint at a good angle to hit the next waypoint... maybe? =)

Share this post


Link to post
Share on other sites
Quote:
That's a nueral network approach, and way beyond the scope of what I'm doing (I think?!).
Also that link doesnt actually mention anything specific enough to be useful. It's pretty much
"so I uh..made this AI that learns driving."
"how?"
"that's classified"
"oh."


My apologies for trying to help. Forgive me for taking the time from my busy day to reply. I'm terribly sorry.

Share this post


Link to post
Share on other sites
Here's just a simple idea, I've never messed with racing games, but I touched a bit the navigation for humvees in our game.

What I'd do is use steering behaviors to drive the car, this way you can easily take into account other cars. Now what I'd do about the curves, is to have a "detection radius" for the car based on its speed, and give waypoints a radius too based on their angle toward next waypoint... this way smooth curves wouldn't warn the AI as soon as say, a hair pin... This way the AI could plan ahead and brake a bit and say, move to the outside of the curve to steer inside the curve where its near the waypoint or something.

BTW, if you've never read about steering behaviors, check out Chris W. Reynold's web site. I guess you'd have to write a new (or combine multiple) behaviors to get a good steering behavior on the racing track, but I think it could be interesting to mess with this stuff.

The physics on the car could be an input to your steering behaviors, so it could take it into account and know where to aim to reach the way point.

Hope this helps

Good luck

Eric

Share this post


Link to post
Share on other sites
CombatWombat - Be nice. Not being complementary and nice, is a sure trip to ignoreland. Where you post anything and nobody cares. (note: This is not nice).

You go towards the next waypoint IF THE INTERSECTION TEST FAILS. (ie. there are no obsticals betweeen you and the waypoint two after this one).

From,
Nice coder

Share this post


Link to post
Share on other sites
Quote:
Original post by fup
My apologies for trying to help. Forgive me for taking the time from my busy day to reply. I'm terribly sorry.


I didnt mean it in any personal attack sort of way. Sarcasm doesnt travel well over the internet sometimes.
It was merely a way of saying "Thanks for your suggestion, but I've read that article and didnt find the content within to be entirely applicable to my current project". I've been here long enough to know being a complete dick gets you hit with the ban stick.

Quote:
Originial post by Nice Coder
You go towards the next waypoint IF THE INTERSECTION TEST FAILS. (ie. there are no obsticals betweeen you and the waypoint two after this one).

Currently the problem is not with objects blocking the path to the waypoint, but that the car cannot physically turn enough to reach it in time. Or it does something else entirely bizarre and its attempts to reach the 1st waypoint will ruin any chances it has at hitting the 2nd. Unless I'm misunderstanding what you mean by obsticals?

Currently I'm implementing some of the steering behavior type dealies suggest up there someplace, so maybe that will work.

Share this post


Link to post
Share on other sites
It seems that your problem is not about the waypoints, but at the speed to which your AI are trying to take change waypoints at. Any chance you can provide information with hitting a way point? For example, you said that there was a straight away with a series of way point eventually going on a sharp turn, couldn't you provide information to the AI that when it's getting close to that turn that it needs to slow down or will miss the corner completely?

Basically, it's not just about reacting once your on a curve, but before you actually hit the curve.

Shadx

Share this post


Link to post
Share on other sites
Quote:
Original post by Shadx
It seems that your problem is not about the waypoints, but at the speed to which your AI are trying to take change waypoints at. Any chance you can provide information with hitting a way point? For example, you said that there was a straight away with a series of way point eventually going on a sharp turn, couldn't you provide information to the AI that when it's getting close to that turn that it needs to slow down or will miss the corner completely?

Basically, it's not just about reacting once your on a curve, but before you actually hit the curve.

Shadx


This is the problem, exactly. And sort of what I was asking, maybe I should have hit up the math&physics forum with a more specific inquiry.
I've gotten something half figured out that I need to mess with more. I take a series of 3 points ahead and fit a radius to them, then compare that radius to the minumum turn radius of the AI car at his current speed, and if he cant make it, he calculates a braking distance and such.
The problem is, depending on how the map's waypoints are layed out, this does not always work. Maybe I just need to look further ahead than three points? Does anyone know a way of finding the (average?) radius of a bezier curve?

Share this post


Link to post
Share on other sites
CombatWombat,

I'm thinking something a bit different then "looking ahead". You do need to look ahead to interpolate the curve that you want your car to take, but I'm thinking that, a car, once achieving that way point, gets some info from it.

On a straight away lane, you would have
Waypoint 1 -> Give it all
Waypoint 2 -> Give er!
..
and once coming to a particular rough spot (big curve coming up in 4 way point let say)
Waypoint N -> Start reducing speed by 10
Waypoint N+1-> reducespeed by another 20
...

Note that when I say that the big curve is coming in 4 waypoints, I don't necessarily mean that you need to look ahead 4 waypoints, but when plotting those way points (making the AI path)you need to know that there's a sharp turn coming up ahead. You could automate all this using physics equations, but it's much more complicated...and over my head :) You can always start the easy way and improve on it later on.

Good luck,

Shadx

Share this post


Link to post
Share on other sites
Quote:
Original post by Shadx
CombatWombat,

I'm thinking something a bit different then "looking ahead". You do need to look ahead to interpolate the curve that you want your car to take, but I'm thinking that, a car, once achieving that way point, gets some info from it.


That's really not an option for a few reasons. It would be way too involved to repeatedly go back and forth between map editor and game testing to find the correct values to get the AI around the track quickly, but still safely. This is further complicated by the fact that all the AI cars are different, and may also have upgrades which makes them faster, turn differently, etc, meaning the values required for each AI driver would vary quite a bit.
This is a map editor which is built into the game for the USER to use, not just the developer. So fast and easy is a requirement.

Any indication of a turn would have to be interpereted geometrically simply from the positioning of the waypoints, and this is what I need suggestions on how to do most effectively.

Appreciate the help.

Share this post


Link to post
Share on other sites
You change how far it looks ahead, so that when it is impossible to hit a corner, you can calculate the braking distance,ect.

From,
Nice coder

Share this post


Link to post
Share on other sites
Hi,

I guess my solution would handle all the braking and other problems you seem to have, would you mind telling me why you didn't even seem to consider it, as you didn't reply to it?

Thanks

Eric

Share this post


Link to post
Share on other sites
Quote:
Original post by xEricx
Hi,

I guess my solution would handle all the braking and other problems you seem to have, would you mind telling me why you didn't even seem to consider it, as you didn't reply to it?

Thanks

Eric


Your solution is pretty much what we've resorted to using, and thus far it looks like it may work. We have the steering bahavior setup to follow a line connecting each waypoint.

The logic of "ok we're going to look ahead and find a sharp turn" is perfectly sound. The trick is in the actual implementation. Angle from one waypoint to the next does not tell you the radius of the turn by itself. If you must turn 30 degrees to hit waypoint2 after waypoint1, its easier if wp2 is 500 miles in the distance than if it were 10 feet ahead, yes?

My current solution to finding the radius of turns based on a 3 waypoints ahead is mediocre at best and I dont really trust it in all situations. I need a better way to take N-number of waypoints ahead and analyze the path they create purely geometrically from the coordinates of them. Maybe fit some kind of curve to them and check the derivative of it to look for inflection points (would indicate a point between curves). The problem is I dont know enough of any type of curves (or calc for that matter) to actually pull that off.

Share this post


Link to post
Share on other sites
As you go faster, you look further.

From positions + distances, you can work out what you need to stear. (pretty easily, atan2 (iirc) to get angle, then get the distance, and then figure out how much turn you need per unit of distance. (then you get how fast you are, to figure out how much turn you need per second).)

This is a molehill.
Getting this working for a lot of cars simultainiously is a mountain.

From,
Nice coder

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
As you go faster, you look further.

From positions + distances, you can work out what you need to stear. (pretty easily, atan2 (iirc) to get angle, then get the distance, and then figure out how much turn you need per unit of distance. (then you get how fast you are, to figure out how much turn you need per second).)

From,
Nice coder


The complicating factor is that our cars dont just "rotate" to turn. The car could slide out and generate alot of angular change per second, but this does not necessarily accelerate the car in a useful direction.

Although perhaps you are correct that I can use the angle between waypoints as well as the distance between them to describe the curve. Just a matter of working the exact forumlas to relate it to something the cars can understand.

I think I've got enough to go on for the time being. Thanks to all that yelled random things at me.

Share this post


Link to post
Share on other sites
Could you not "shoot" a beam of some sort out in front of the car and find where that beams goes off the track? (umm this is hard lol). You have waypoints, so I don't know how you find the width of the track, -maybe a certain left and right "normal" distance either side of the way point, so between the way points if this beam goes out side of the track or edges (lines made between the left/right normals, coneecting the way points), at least you might know you are either getting to a turn or something. Maybe combine ths with the way points or something. I don't know how this would help with spins or anything though.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement