Pathfinder cannot find path within one room

Tigga

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.

o4kapuk

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.

Mototroller

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.

deft-code

This post is deleted!

deft-code

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.

o4kapuk

@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

deft-code

@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).

o4kapuk

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

artch

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

Xenofix

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?

Orlet

@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.

artch

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