How to choose and scale heuristics for A-star on a graph?

Question

I am trying to find the best and scale my cost function for my algorithm. I am following amit blog which explain that (http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#manhattan-distance).

I have a humanoid character first blue circle is the start configuration with the left foot (red). Then I expand a set a possible right footsteps (blue) and again with the left foot (red) until the center of the character reach the goal.

my heuristic look like : f = g + h;
with g = g + oneStepCost (distance between 2 footsteps) + TerrainCost (0 free, Infinity if obstacles); // Cost to go
h = distance between the middle of the character and the goal;

What do you think about this basic heuristics ? I feel using the Euclidian distance is the best suited for my configuration but Manhattan distance seems a lot faster.

On amit blog, he says that it is good to have a cost function = 1 for the minimum distance traveled but I don't really understand how to do that because my cost function is in meters.

Then, i might have lot of paths which are almost the same length. So, I have to break ties. So, if I use this formula : h *= (1.0 + p) with p <(minimum cost of taking one step)/(expected maximum path length) . For my case, minimum cost of taking one step = 0.10 m and maximum path length = (0.25 meter * 12 steps). Does it seems correct to you ? Any others tips in order to improve heuristics and not spending time for the path with almost the same length ?

Answer 1

manhattan vs euclid is just 2 extra multiplications and a square root. That is not worth worrying about.

What is important is that the heuristic underestimates the remaining path. This means that the heuristic must be equal or less than the actual shortest path from the current node to the destination.

Instead of calculating in meters you can calculate in decimeters (1 dm = 0.1 m). Any arbitrary linear scaling function can do but it's not really necessary.