Used to think I was smart, need heuristic
Author
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.
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
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.
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... :)
EDIT: Got beaten to it... :)
Author
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...
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...
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.
Author
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.
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.
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?
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
