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 ?