I took a walk in the snow and promptly realized what my pathfinding issue was.  Essentially, the algorithm was going out of its way to intentionally find a bad path.

More precisely, the A* algorithm works by navigating step by step from the starting point, maintaining a list of possible incomplete paths and their estimated total costs.  (In my case, this estimate is the combination of the known cost of the incomplete path and the estimated cost to get from the end of the incomplete path to the intended destination.)  This list of possible paths is sorted so that the algorithm always tries to navigate closer to the destination by continuing on from the most promising partial path, i.e., the one with the smallest estimated cost.

The problem is, I had managed to sort that list in the wrong order, so every time it tried to pick the most promising path, it was actually picking the least promising path.  Specifically, C++ algorithms that need to know the order of elements take a function that can compare two items and say which should come first.  If there is a less-than comparison available, it will use that as the default ordering.  Usually, this means that smaller items come before larger items, which is what I wanted.  But for std::make_heap() and related functions (which I was using to maintain a priority queue), it wants to put the largest item first.  So it still uses the less-than operator, but in the opposite direction.  So when I implemented my less-than comparison to do the obvious thing (that is, it asserts that partial path A is less than partial path B when A’s cost is smaller than B’s cost), my priority queue then insisted that the most costly path had the highest priority.

To fix it, all I needed to do was to reverse the logic of the less-than operator.  Partial path A is less than partial path B when A’s cost is greater than B’s cost.  It might look backwards, but it does the right thing.  The annoying part is, I’ve run into this before, probably multiple times, and yet I never remember to get it right the first time, urgh.

loopy pathfinding

Visiting my neighbor is so hard!

So now I have a working algorithm, but it exposed a new bug.  Given the way I’ve represented origins and destinations, if an origin and destination are attached to the same segment of road, there is currently no way to navigate directly from one to the other down that road.  Instead, it has to go the the very end of that segment of road, and from there try to figure out how to get back to the same segment so that it can arrive at the destination.  Leads to the loopiness seen in the attached image.  That’ll be a harder bug to fix.  I’ll probably just engineer around it:  If origin and destination are on the same road segment, don’t even try to pathfind; just go directly there.  A bit of a hack, but it’s a prototype, right?

No Comments

Leave a comment