# Used to think I was smart, need heuristic

## Recommended Posts

Fisco    122
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 on other sites
Palidine    1315
Quote:
 Original post by FiscoTime 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 on other sites
Sneftel    1788
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 on other sites
Captain P    1092
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 on other sites
Fisco    122
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 on other sites
Sneftel    1788
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 on other sites
Fisco    122
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 on other sites
Sneftel    1788
Quote:
 Original post by FiscoOscillation 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 on other sites
Hnefi    386
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 on other sites
Horizon    145
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 on other sites
Vorpy    869
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 on other sites
Hnefi    386
Quote:
 Original post by HorizonI 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 on other sites
Gagyi    192
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 on other sites
CombatWombat    673
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 on other sites
Fisco    122
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.