Non-optimal path from PathFinder.search?
-
From what I understand, the pathfinding is supposed to be using A*, implemented with the JPS symetry reduction algorithm. As a result, it ought to be returning the optimal path in any situation, or returning no path at all if the operation limit is reached without finding a solution. As you can see in this screenshot, it does not do so...
This path isn't just slightly sub-optimal, it is fully 50% longer than the optimal path.
(the '.'s are drawing of the paths between the sites; this was from some debug printing done in the survival, now training, room of the simulator, so it should be easy to reproduce.)
I'm not sure what could be causing this; the first thing that springs to mind is that a* can give sub-optimal results if an inadmissible heuristic is used, so it's possible that the implementation in screeps is using linear distance, which is inadmissible here since diagonal moves have the same cost as straight moves. One of the assumptions in the original work on JPS was also that diagonal moves cost sqrt(2) compared to straight moves' cost of 1, so it's possible the problem lies there as well, but I am not sufficiently familiar with the workings of JPS to say whether it would break it's optimality proof or not.
:edit: It occurs to me that it could simply be exiting early - in the screenshot example, in looking for a jump point after clearing the obstacle, it actually encounters the target. If it simply stops and returns there, rather than putting that jump point in it's open list, it might exit prematurely, skipping the chance for other paths to be fully explored.
-
just a follow-up, it only generates this sub-optimal path when a point near the south-east mine (the one @ 43,44) is used the first argument, origin, and a point by the controller is the goal; searching the other direction gives the correct, optimal path.
-
The results are indeed strange, but expected. [43, 44] and [22, 15] (room.controller) are both unwalkable. When the path finder can't find a complete path it will return a partial path which got the closest to the target. In the case where you're searching to [43, 44] the partial path just so happens to be a subpath of the optimal path. In the reverse the path finder managed to get closer by going around the obstacle, that's just a quirk of JPS. If you set the targets to walkable in the CostMatrix, or use range: 1 on your target you'll get an optimal path in either direction, because it will find a complete path in that case. You can also examine the `ops` property on the return value from PathFinder.search and notice that it uses far fewer operations because it's not exhausting the entire room.
I think this is a pretty common mistake new users run into with PathFinder. It is mentioned in the docs (see the "Important" section) but it may be worthwhile for us to add some kind of warning when requesting an impossible path.
