Fix closed set usage in AStar

[eruonna]

A node should only be added to the closed set when it is expanded, not when it is added to the queue. Before then, the algorithm could still find a shorter path to it, even with a monotone heuristic.

This can result in the same node appearing multiple times in the priority queue, so when pulling a node off the queue, check if it is already closed and if so, skip it. This is not a correctness issue; it merely avoids redundant effort.

A simple example of why this is needed in the 6 topology:

  # # # # # 
 # 1 2 # 3 #
# 4 5 6 7 # 
 # # # # # 

When pathing from 4 to 3, note that nodes 1 and 5 have the same heuristic value (h = 3), as do 2 and 6 (h = 2). First 4 is expanded, leaving the algorithm indifferent between 1 and 5 (both have h = 3, g = 1). First, 1 will be visited (because of how neighbors are ordered). This will add 2 with h = 2, g = 2. Next, 2 will be visited (both 2 and 5 have the same f value, but h(2) < h(5), so 2 will be selected first). This will add 6 with h = 2, g = 3. Next, 5 will be visisted because f(5) = 1 + 3 = 4 and f(6) = 3 + 2 = 5. Now from 5 we should add 6 to the queue with h = 2, g = 2. But in the current implementation, 6 will already be marked as done. So the final path found will be 4 -> 1 -> 2 -> 6 -> 7 -> 3, clearly not optimal.

With the proposed change, 6 will not be marked done until it is expanded, allowing the optimal path to be found.

[ondras]

Hi @eruonna,

thanks for the patch as well as a perfect explanation!

I have just returned from a vacation and my intelectual skills are currently far too low to full review your proposed change, but you have my full trust. I will merge this.

If you feel like finalizing this issue, try re-building rot.js (make rot.js, make rot.min.js) and sending a PR with the newly created bundles. Or just give me some time and I will re-build myself.

Thanks again!

[ondras]

Rebuilt.

[ondras]

@eruonna I just noticed that your PR broke several unit tests for A*. Would you have a moment to check that out?

[ondras]

I believe I found the cause and fixed it: d14cb8a .

The condition order prevented the [fromX, fromY] point to be added to the path, effectively making all paths impossible. Damn, how could have this slipped in?