[A18] Pathfnding issues. Pawns choosing suboptimal paths (medium/long distances)

[RemingtonRyder]

Pathfinding over long distances still seems to be a bit wacked. I've seen colonists traipse through mud and shallow water when there's much faster terrain nearby.

Also, it seems that strangely they will choose a path that goes off the road rather than stay on it, for some unknown reason.

Moderator's edit (Calahan) - This was incorrectly posted in the A18 feedback thread (so moving it to bugs where it belongs).

[attachment deleted by admin: too old]

[wwWraith]

I hope there would be more attention to this issue as it still exists in B18.1722 and it would be very bad to see it in the release.

I heard that pathfinding on the short routes were optimized. I believe it is so, but what is the threshold when the game treats it as "short": 8 tiles? 12? 16? I think even on such distances sometimes (though rare) I saw a very strange pathing decisions. And in the decently developed colony the pawns mostly have to go much longer distances even to get from their bed to the dinner room, or from the workbench to the items store, etc. After all, the difference in the path costs between the straight route with some obstacle and some go-around on short distances often is neglible so we don't win much from it. So I think that the optimization of the long routes should be prioritized.

I think in mostly any game when you have several pawns taking decently "long" trips (20+ tiles? is it really long?) you can see at least some of their routes are weird, more or less. It makes the player constantly frustrating and doesn't let to effectively use some interesting building designs and/or tactics. For example, once I spent several hours planning a colony to be mined in the caves around the lake. It was a new concept for me, and I was very excited. But then I realized that the pawns don't bother to use several carefully built bridges or at least soil strands and just keep swimming through the lake. I think they could even die from bleeding or starvation while trying to get to the bed or food. So I was very disappointed and had to abandon that colony.

This post doesn't contain new evidences, but there are reasons for it. The screenshots in the first posts are very indicative. Several similar ones were in the forums since previous alphas. Anyone observant enough can make a whole bunch of them in a few minutes. In the same time they are not easy to reproduce as changing the starting or target point just by 1 tile sometimes makes the route very different. But if it's not enough to consider this issue, I hope someone will at least tell what kind of info they'd want.

[angleof9]

The issue is that Rimworld breaks down parts of the map into 'chunks', which have their speed averaged based on the tiles within. Pawns used to do tile by tile searches for the most efficient path, but this was just too taxing on the system, and would slow the game down any time a pawn had to travel across the map. Now, with chunks and the new priority system for pathing, paths generally became slightly less efficient, but it became much quicker for the game to compute them, preventing frustration caused by lag.

[wwWraith]

I was suspecting the using of these "chunks". It can explain many weird situations (but not excuse them):

1. I am a monkey!

(tiles with the trees happened to be the centers of those "chunks" or other chosen points while their average pathcost is low)

2. The roads are for the weak!

(the road tiles happened to be the part of the "chunks" whose average pathcost were very high because of the stone chunks so the pawn avoids them)

Some other similar situations can be seen at https://ludeon.com/forums/index.php?topic=33027.msg386621#msg386621 (pawns don't respect roads and avoid crossing rooms with lot of furniture).

3. Swimming is fun!

(using the mod Biomes! - Caverns which made the deep water passable but with very high pathcost, movement speed was 4.2%, so crossing this lake could take a whole day or even more for injuried pawns; the yellow squares are just plans, they affect nothing)

4. Someone left the bottle with ether opened?..

(I can't explain it)

I think there could be made at least some improvements (if some completely different implementation can't be considered):

1. Make the threshold that differs fully calculated paths from the "long" ones that use simplified algorithm configurable in the options, so the players could decide to trade some FPS for paths efficiency.

2. Recalculate periodically some short part of the long path with the full algorithm. E.g. if the pawn goes from point P0 to point T and C1, C2, C3, C4, etc. are the "reference points" on it ("chunks" centers), recalculate the path from P0 to C2. When the pawn completes half of this distance (it will be at the new point P1 not necessary coinciding with C1), recalculate the path from P1 to C3, then from P2 to C4, etc. The trick is that the recalculated part won't end on some "chunk centers" this way so the pawn won't necessary have to get to these precarious points. I think it shouldn't hinder the performance significally as it'd be similar as that pawn was busy with some other things involving several short routes instead of 1 long.

Edit: maybe the typo in the topic name should be fixed (Pathfinding) so it won't cause confusions when searching.

[attachment deleted due to age]

[Razuhl]

Pathfinding in Rimworld is not implemented to find the fastest path between A and B. The search stops immediately once it has found ANY path that connects A and B.

Heuristics that do evaluate regions(the "chunks") determine the general heading of the path. Such an approach will fail harder the longer the path is(because the remaining length to the target increases the amout of guessing included in the calculated costs). An algorithm like this would be the A* but the A* does not stop once it has a connection it closes out by finishing all open alternatives. Thats why A* calculates the fastes path and rimworld calculates a path fast.