Pathfinder cannot find path within one room

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