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

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

Flakky
Hi,

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
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.
Flakky
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 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

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP