News for hackers. Stuff that matters.
Re:PathFinding.js by jMyles on Sunday September 21, 2014 @11:46PM (#8349130)
In my first bit of play, I just tried to find cases where Manhattan lost to the others. It seems like Manhattan is not as good when faced with a plausible path only to be thwarted at the end - is this right?

Can you show a few cases where Manhattan loses by a landslide?

Re:PathFinding.js by roryokane on Monday September 22, 2014 @03:16PM (#8352041)
Manhattan is a heuristic for measuring distance, not an algorithm to find a path, so I wouldn’t really say it “loses”, rather it “is less applicable”. Manhattan, Euclidean, and Chebyshev are all just different ways of measuring distance (https://en.wikipedia.org/wiki/Taxicab_geometry, https://en.wikipedia.org/wiki/Euclidean_distance, https://en.wikipedia.org/wiki/Chebyshev_distance). Each algorithm uses the heuristic to measure how promising each possible path is (how close each path is to the goal according to that definition of distance, ignoring walls), and prioritizes the most promising paths.

Based on those definitions, I would guess that “Chebyshev” distance is almost always the most accurate heuristic to use when you check “Allow Diagonal”, because it will always be perfectly accurate if there are no walls in the way, unlike the others. Similarly, when “Allow Diagonal” is unchecked, “Manhattan” distance is the most accurate. And “Euclidean” distance is always the least accurate in this demo, because in this demo, paths are always constrained to 45° or 90° turns so that they stay on the grid, whereas Euclidean distance assumes that it is possible to move at arbitrary angles like 18.2° right from east.

Re:PathFinding.js by jMyles on Monday September 22, 2014 @04:31PM (#8352443)
I have found one example where Euclidean wins:

http://imgur.com/FgQ04k0

Re:PathFinding.js by applekor on Tuesday September 23, 2014 @12:03PM (#8356005)
Because Manhattan distance isn't an admissible heuristic for an 8-connected grid I think it breaks the A*'s guarantee of optimality. I don't have an example, but it might be a place to start looking.