3
\$\begingroup\$

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. enter image description here

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 ?

\$\endgroup\$
  • \$\begingroup\$ If your character can go diagonally, them you must use euclidean distance. \$\endgroup\$ – Bálint Mar 14 '17 at 6:51
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer ! Why is it better to calculate in decimeters than in meters ? by heuristic you mean h or f ? Thanks ! \$\endgroup\$ – Snoopyjackson Oct 14 '15 at 10:59
  • \$\begingroup\$ 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 \$\endgroup\$ – ratchet freak Oct 14 '15 at 11:03
  • \$\begingroup\$ And do you think it is better to take the distance between the feet and the goal as cost function or the distance between the character and the goal ? \$\endgroup\$ – Snoopyjackson Oct 14 '15 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.