3. Pathfinder cannot find path within one room

Pathfinder cannot find path within one room


  • Recently I've found some of my creeps unable to reach their targets using moveTo. So I've tried to reproduce at shard2:

    JSON.stringify(new RoomPosition(42,19,'E51S18').findPathTo(new RoomPosition(34,12,'E51S18'))) returns: [{"x":41,"y":20,"dx":-1,"dy":1,"direction":6}] another time it returns: [{"x":41,"y":20,"dx":-1,"dy":1,"direction":6},{"x":34,"y":12,"dx":-7,"dy":-8,"direction":8}]

    Obviously an unexpected result.

    Or this one: JSON.stringify(new RoomPosition(1,44,'E54S19').findPathTo(new RoomPosition(4,11,'E54S19'))) returns [{"x":0,"y":43,"dx":-1,"dy":-1,"direction":8}]

    Maybe someone has a look?

    (Edited: Nothing passed a wall, but the paths are incomplete)


  • Which is the wall it passes through in E54S18?

    The E51S18 looks like it's just an issue with ops - it's a complicated room and moveTo with default options will sometimes fail. That's because the pathfinder has a default maximum operations of 2000. You can override this by passing maxOpts in the options arguement.

    EDIT: Same with the E54S19 one. The default arguments will do fine for most rooms, but anything requiring a lot of twists and turns or going back on yourself tends to be more expensive and will hit the ops limit sooner.


  • Thanks Tigga. That's really interesting. It shouldn't fail like this, should it? I guess my problem is solved.

    However the problem is still there for other players: I believe that it should always be possible to find a path inside of one room without any extra options. Most newbies rely on it. Maybe someone increases the default maxOps?

    1 Reply

  • Another problem: JSON.stringify(new RoomPosition(18,49,'E54S19').findPathTo(new RoomPosition(0,44,'E54S19'),{maxOps:100000})) returns [] every second tick and a path every other second tick. It seems to depend on https://screeps.com/a/#!/history/shard2/E54S19?t=20105689 Every time when the creep at 18,49 is in the room, that expression returns [] (tested in the console). The result is, that the creep doesn't move at all.

    Detail: The creep calls moveTo with the pathOptions: { visualizePathStyle: { stroke: '#ff0000' }, ignoreCreeps: false, reusePath: 0, maxOps: 100000 }


  • @xenofix said in Broken Pathfinder:

    Thanks Tigga. That's really interesting. It shouldn't fail like this, should it? I guess my problem is solved.

    However the problem is still there for other players: I believe that it should always be possible to find a path inside of one room without any extra options. Most newbies rely on it. Maybe someone increases the default maxOps?

    The other thing you can do if you're sure there is a path within a room is to set maxRooms to 1. That constrains the pathfinder somewhat and will prevent it exploring into other rooms.

    As for defaults - it's not easy. What if there is no path? How long should it carry on searching until it can prove there is no path? Often incomplete paths will actually do a pretty good job. Increasing maxOpts will likely have an impact on CPU, and will increase the cost of every impossible or surprisingly long path.

    IMO there comes a point where every Screeps player has issues with pathfinding, and has to dig in and figure out how they want to solve it. There's plenty of other issues that you'll bump into with moveTo as you keep going. Fortunately the game provides a lot of options for interacting with pathfinding - via options, via cost matrices and via direct access to Pathfinder.search. Many people have thousands of lines of code dedicated to going from one place to another, and still have issues from time to time. Getting it right is part of playing the game and things like moveTo are really just to get you started IMO.

  • Dev Team

    Feels like someone should write a detailed article about A* guts someday and explain the decisions behind default values. With gifs/pics and everything...

    But generally yes, @Tigga is right: pathfinding is a separate discipline of playing Screeps. Players are given the way of moving creeps which works good enough in most cases. But sometimes it happens that you must choose between pathing errors (which players can see) and stupidly high CPU consumption out of blue (which is much harder to find). Choosing the second would be... unwise.


  • There are awesome detailed articles by Red Blob Games:

    They are really helpful for understanding A*, tuning in-game PF and even implementing you own path-finding. Actually, built-in PF is pretty nice, but its parameters should be chosen carefully.


  • This post is deleted!

  • We still need a PathFinder.search specific write up.

    Some tidbits I've encountered over time:

    • It's not really A*, but jump point search.
      • what does that mean? I don't know, but I blame it every time it has unexpected behavior
    • The default heuristic of 1.2 finds non-optimal paths
      • 1 guarantees optimal but costs 50% more cpu.
    • Heuristic values above 10 or so screw with the algorithm and searches cost a lot more ops (though not a lot more CPU).
    • It will never produce a path that moves laterally on an exit tile
      • this is works well with exit tile teleportation
      • this interacts badly if you're movement constrained and on an exit tile. E.g you try to path a few tiles laterally will consume all ops and still produce an incomplete path.
    1 Reply
  • Dev Team

    @deft-code yes we do, to remove some misunderstandings at least, for example:

    • It's not jump point search because JPS is exclusively for uniform-cost grids (as far as I know; if you know an article or something which proves otherwise, please post the link). So it's not really A* but not really JPS either.
    • The default heuristic is 1 which finds optimal paths

  • @o4kapuk, You're correct. JPS is only for uniform cost grids and is fairly well researched. I've never found a paper about our odd A*/JPS combo.

    Was the documentation incorrect or did you change the default heuristicWeight to 1?

    While looking for original Heurisitic weight I figured out why heuristicWeight values above 10 act funny. They're capped at 9 in the code. We should update the documentation. (Or remove the cap if it isn't needed).

    1 Reply
  • Dev Team

    @deft-code The documentation was incorrect, now it's fixed.

  • Dev Team

    If you want to get some insights into the Screeps native PathFinder, the best way is to ask its author @The_General.


  • Luckily I know A* very well. But I always thought there are two implementations in screeps. One PathFinder written in C++ by General and a JS JPS version, which is the default in moveTo. The C++ PathFinder could be activated as default for moveTo by PathFinder.use(true), which is deprecated now. Did something change here? Is JPS still the default path finder or is it all PathFinder only now?

    1 Reply

  • @xenofix said in Pathfinder cannot find path within one room:

    Luckily I know A* very well. But I always thought there are two implementations in screeps. One PathFinder written in C++ by General and a JS JPS version, which is the default in moveTo. The C++ PathFinder could be activated as default for moveTo by PathFinder.use(true), which is deprecated now. Did something change here? Is JPS still the default path finder or is it all PathFinder only now?

    It's been the PathFinder by default for everything for a few years now.

  • Dev Team

    @xenofix Native PathFinder is JPS too, and it is activated by default unless you call PathFinder.use(false).