Jump to content
  • Advertisement

ntroPi

Member
  • Content count

    5
  • Joined

  • Last visited

Community Reputation

450 Neutral

About ntroPi

  • Rank
    Newbie

Personal Information

  • Role
    Game Designer
    Programmer
  • Interests
    Programming
  1. I should have written explicitly, that the diffs are supposed to be absolute values. Wanted to keep it short, as it is only a minor point of my post. Manhattan_8(Point P1, Point P2) { xDiff = abs(P1.x - P2.x); yDiff = abs(P1.y - P2.y); return min(xDiff, yDiff) * sqrt(2) + abs(xDiff - yDiff); } So it would come out to xDiff = 0, yDiff = 200 in your example, which gives the expected result (200). Thx for the feedback :-)
  2. If you want 8 direction movement, your heuristic should support that. Creating an "8 direction manhattan style estimate" between two points should be no big deal. (dist = min(xDiff, yDiff) * sqrt(2) + abs(xDiff - yDiff)) Now to make A* really lightning fast there is an counter intuitive tip: Make the heuristic under/overestimate the distance to the target so it doesn't backtrack as much to go around an obstacle. This is exactly what everyone says the A* heuristic must never do, because now it will no longer be guaranteed to calculate a correct shortest path at all. But usually in games you don't care about the path being 100% the shortest one. The upside are crazy performance gains up to a factor 10! In extreme cases like labyrinth style maps the results can be very wrong though. You'll have to experiment a little as I did that a long time ago and don't remember what the best factor was exactly. You'll know when you've hit the sweet spot. CPU time will drop like a stone and the paths should still look mostly optimal. Hope this helps :-) Edit: Postprocessing/smoothing a found path can reduce the introduced error, especially in the more obvious suboptimal cases like running into a dead end.
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!