# Used to think I was smart, need heuristic

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

## 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 on other sites
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
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
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
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
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
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
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
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
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.

1. 1
Rutin
25
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 14
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631757
• Total Posts
3002140
×