Re:Trying to improve buffet lines using simulations
by munificent on Friday October 18, 2019 @12:22PM
(#21292680)
> 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.
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!