Sign in to follow this  
Fisco

Used to think I was smart, need heuristic

Recommended Posts

Hi all, Been writing a vehicle, racing track simulation game for a year now. I was got everything working fine, but im still trying to generate the optimal racing line. Have tried the following, 1. Genetic Algorithm, 2. PSO algorithm (Particles, swarm to better solns) Did my Masters on this 3. Depth first search 4. A* First three produced excellent results for three corners, before running out of steam. Currently working on the A*. I cannot find or discover a good heuristic. Distance is a bad one, car will oscillate! Time is also a nono, will turn around and try cross the finish line immediately. The whole problem is how to determine the heuristic for the cost to the end goal... Since its where you started your car off, it will always try short cut! The algorithm is not important, but how to assign a good heuristic to a point on the track, with a direction and velocity. thanks Dylan.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fisco
Time is also a nono, will turn around and try cross the finish line immediately.


Why do you allow the car to turn around? It seems to me that just disallowing the car from going the "wrong way" would make this a perfect heuristic. You already need to know wrong way anyway to let the player know when he's going the wrong way. So since the data is already present (or should be) this seems pretty easy.

-me

Share this post


Link to post
Share on other sites
Simply disallowing wrong-way transitions will screw up A*'s performance if the heuristic isn't changed to account for it. Instead, I'd simply set up a couple of checkpoint lines along the track which the solution has to pass through.

Share this post


Link to post
Share on other sites
Using several checkpoints could make your problem a lot easier. How else would you even be able to check if someone had made a full lap?

EDIT: Got beaten to it... :)

Share this post


Link to post
Share on other sites
Thought about split points along the track. And fair enough, but I still have the problem of estimating the cost to the goal node?

Consider three nodes mid corner... A1, A2 ,A3. Each are an incremental distance from the apex of the corner. How would you estimate the cost from each of these nodes to the goal nodes? Possible ideas,

1. Calculate the total time for the track at say 100mph (underestimates the goal always). then minus the time for the current node, from the total. The downside, is the car will go as fast as possible into the corner.
2. distance to final node or split points, is no good.
3. blah... brain melt as always.

I will try the average velocity with check points, but sense that around corners, astar will splutter...

Share this post


Link to post
Share on other sites
What do you mean by "splutter" or "oscillate"? The A* heuristic doesn't need to be perfect (that's why it's a heuristic). As long as it doesn't overestimate, you'll get The Right Answer eventually. And I can't really see either of your proposed heuristic approaches underestimating too much.

Share this post


Link to post
Share on other sites
Sorry, by splutter I mean the lights dim, and not much happens. Far too expensive after three corners, never mind 20 corners. Thought about segmenting the track, and running iterative evolutionary algorithms, but fitting it together is not worth it, and its not optimal.

Oscillation occurrs when using distance as a metric, its tries to get as much distance as possible, with circling or osciallating generating the most distance. Distance=no good.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fisco
Oscillation occurrs when using distance as a metric, its tries to get as much distance as possible, with circling or osciallating generating the most distance. Distance=no good.

Wait... are you talking about distance travelled? Why not use distance to the finish line or next checkpoint?

Share this post


Link to post
Share on other sites
My first suggestion would be this:

Use distance to goal as the heuristic. Generate child nodes by plotting splines along the track - they should approximate the movement of the car very well and do it a lot faster than actually simulating the movement of the car exactly.

Share this post


Link to post
Share on other sites
I think what you're missing here is that the optimal line isn't necessarily the shortest line. You have to take acceleration and breaking into account.

Share this post


Link to post
Share on other sites
The end goal is not where you started the car, it is where you started the car after having gone all the way around the track. You can also split the track into different regions and find paths through each region, then splice the paths together. If the splicing is done on straight roads, it should be fairly simple to compute a pretty good path.

Share this post


Link to post
Share on other sites
Quote:
Original post by Horizon
I think what you're missing here is that the optimal line isn't necessarily the shortest line. You have to take acceleration and breaking into account.

Doesn't matter. A* only needs an admissible heuristic to find the optimal route, and in this case distance to goal is admissible due to it always underestimating the approximated cost from start to goal.

Share this post


Link to post
Share on other sites
I would try to modify the distance algo by adding the (unsigned) angle turned to the distance travelled. So it wont like oscillating around. Heuristific.

Share this post


Link to post
Share on other sites
There is a method in Appendix C of, http://remi.coulom.free.fr/Publications/Thesis.pdf
for analyzing racing lines. I tried to write something to create a racing line for my game at one point using this method, but never managed to get it converge on a solution.

Maybe you will have better luck. It does look to produce good results.

Share this post


Link to post
Share on other sites
Thanks everyone. Will let you know which method yields the best results. Will export everything from gnuplot. The track is kyalami, which is famous in our area.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this