[erikbern]

I wrote the code and you're wrong :)

1. Diagonal moves have a slightly higher weight. 2. I have an edge weight of 100 to go through another person. This makes it possible to go _towards_ the right direction even though there is no path 3. For the perpendicular lines method, the distance is modified to 1e-3 4. A* doesn't work because the heuristic becomes pretty useless when you have moves that are very "cheap": you need a lower bound that's pretty much zero

So for all those reasons, I just went with plain old Dijkstra!

[munificent]

> A* doesn't work because the heuristic becomes pretty useless when you have moves that are very "cheap"

I don't see where you have cheap moves. If your move costs are unit for straight lines, slightly longer for diagonal (i.e. probably close to sqrt(2)), and much longer for obstacle, then A* will work fine. The lower bound is just the usual Cartesian or Manhattan (depending on your diagonal cost) distance.