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.
gopher
@gopher
Posts made by gopher
-
RE: Non-optimal path from PathFinder.search?
-
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.
-
RE: strange pathfinding result?
ok, scratch that last conclusion, after using the new roomposition trick to send my guy back to 21,48 and trying repeated "moveTo(new RoomPosition(0,39,"W4S1"))" the result is him going south one... then flipping back and forth seemingly indefinitely.
-
RE: strange pathfinding result?
it is entirely possible that the optimal path actually *does* start by going south, then going back north through the 2nd exit on the west end of the two rooms, thus avoiding a big swamp in W4S1. I can't test this because once I cross back into W4S2, I can't see W4S1 anymore, and so can't call the room's getPosition. --- pre-submit-edit-- scratch that, by calling "new RoomPosition(...)" I can create a path to a room I can't see. Using that to test now if just repeatedly calling moveTo() with the target form that position works...
if so, guess this is a misunderstood feature rather than a bug, but I have to say it's highly unexpected behavior, at least for me. I would not expect, indeed, I would often not *want* a path from A to B within a room to involve leaving that room. I suppose I could prevent it by providing "maxRooms:1" with options... meh, anyway... yeah.
-
strange pathfinding result?
made my first inter-room creep earlier, and it seemed to be working fine until it tried to cross one particular boundary, where it repeatedly got stuck. I kept adding debug prints, and eveything seemed to be correct, except the creep was promptly moving south and crossing the wrong border back to where it came from.
Sent a test creep back tot he room later and the same thing happened to it. So hopped in the console and tried this, which is what the creeps were trying to do:
Game.rooms['W4S1'].getPositionAt(21,48).findPathTo(0,39,{serialize:true})
This returns "21495" which, as I understand serialized paths, is the start position followed by "down." Just that, no more path. Tried with PathFinder enabled and disabled, same results either way. Is this some feature I don't understand, or a very strange bug in the pathfinder?
-
"repairing" walls and ramparts not counting as construction?
Because reasons, I tried to have wasted energy as close to 0 as possible, and was tracking my numbers on the overview as a check; until I got my tower online and started building walls and ramparts. It seems that energy spent there either isn't counted at all, or isn't counted correctly, as I'm now showing roughly 50% "lost" (harvested - sum of all 3 spending categories), which lines up with my 2nd mine's output going entirely to my tower for beefing up defensive structures. Is this deliberate? if so, I'm curious for the rationale, otherwise, low priority and such obviously, but a fix would be appreciated!