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

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 ?

• If your character can go diagonally, them you must use euclidean distance. Mar 14 '17 at 6:51

• It lets you set a step cost of 1 but that's not really important as long as you have enough accuracy and you are consistent. By heuristic I mean h Oct 14 '15 at 11:03