You are invited to Log in or Register a free Frihost Account!

What is the best heuristic for a* (and other optimization)?


After some trouble I finally figured out A* and I'm using it for node based pathfinding. Currently I use Pythagoras for heuristic since Manhattan would not be practical unless I would be building cities in my games which all have the same shape. I've read that there is also the euclidean heuristic (and the squared variate) and I read something about tie-breaking.

I wonder what is the best heuristic for node based world which is applicable to any situation.

For optimization I thought of adding a cost to dead ends unless the target node specified is a dead end. In that case all non dead end nodes would have a cost. Does anyone here have another suggestion?

Thanks Smile
I don't think there is a single best heuristic. It's a trade off between speed or accuracy. Manhattan is good because it is easy and efficient to compute the heuristic. If you want to move diagonally you better use Pythagoras instead (like you do).
As I have understand it euclidean heuristic is good if you want to move at any angle, but I'm not sure how that should work.

The choice of heuristics and other optimizations will depend very much on how the search space will look like.
Thanks for the reply.

I think I need to do a few things.
Benchmark all heuristics, comparing the paths produced with paths using 0 for an heuristic and see which one is the best. If I am corrent the only way to get a path which is not the shortest is to use an overestimated heuristic which can not happen using the Pythagoras heuristic am I right?

For testing I have created a environment with poison disk scattered nodes. I just need some more heuristics before I am satisfied Smile The scenario is probably going to look like that. Probably less nodes but still.

Example of world and example of a path found.
I will probably place the nodes myself to make it better but still. Demonstration Smile
Related topics
What;s the best movie?
Best Movies
Lord Of The Rings Trilogy, The best of the three vote
What Anime Series do you like best?
The BEST 404 error page ever!
Short Jokes
The best car advert ive seen for a long time
Try this program!!
Best free MMORPG?
Optimization is spelled wrong
What is the best antivirus progrem?
Inadvertent keyword stuffing? Google inconsistencies... social bookmarking and Search Engine
The Best Photo Optimizer
Reply to topic    Frihost Forum Index -> Scripting -> Others

© 2005-2011 Frihost, forums powered by phpBB.