Pathfinding

[B@R5uk]

Lately I'm wandering: how can such little difference between endpoints lead to such drastic divergence of resulting paths pathfinding algorithm return for them (see images below). As someone who has a little bit of skill in programming (like implementing A* for once) I'm quite curious.

[fritzgryphon]

This is just a guess, but I think the Rimworld pathing baises the path toward the destination as a heuristic to speed up the calculation. 

In the first example, the destination is more south, so the beginning of the path dips south through the wood and tables.

In the second example, the destination is directly east, so the dip is not present.

edit:  It's also possible the path is broken up into segments that are calculated individually, then stitched together.  Solving the path in pieces would be much faster than trying to do the whole thing at once.

[B@R5uk]

In the first example, the destination is more south, so the beginning of the path dips south through the wood and tables.

No, that's not it:

[fritzgryphon]

I think sometimes there is a bias.  I certainly notice it on extremely long outdoors paths.  In this case, the first half of the path beelines to the destination, then it smartens up at the chunks.




https://www.reddit.com/r/RimWorld/comments/50ukdy/we_havent_automated_this_yet_weekly_qa_thread/d77rd9f/

The pathfinder sacrifices accuracy for computation speed, especially when generating long paths. If they don't follow the optimal path, that would be why.

I wonder if anyone can find out by looking into the code.

[B@R5uk]

If game sometimes decides to compute fast and not to compute accurate then there should be a choice in settings for user to make. Isn't it? The way game behaves now forces me to do a lot of micromanagement. Also, I've been observing that animals choose fastest route even when they haul some corpse across entire map. So, are they smarter than human pawns?

[LWM]

It's complicated and kind of inefficient, and I would love to re-do the pathing system (and region system), when I have a lot of time, a sunny place to work, a cat dozing next to me, less stress, and ample warm frothy coffee drinks.

Depending on how long quarantines go on, I may get there yet!

Anyway, from what I remember off the top of my head, the algorithm tries to head straight towards the target while it's far away and then recalculates as it gets closer.  I think animals may just be getting lucky in their path selection.

[B@R5uk]

LWM, you talk like you are the one who did this system. =D Or is there a way to mod game to change pathfinding?

[Canute]

There allready was such a mod
Better pathfinding
https://ludeon.com/forums/index.php?topic=26563.0
But with A17 it shouldn't be nessesary anymore.

But we player never was 100% satisfied with the vanilla pathfinding anyway.

[B@R5uk]

But we player never was 100% satisfied with the vanilla pathfinding anyway.

Of course we don't! Why would any reasonable path finder choose zigzag path in thick snow on uncovered soil over stright clear roofed lighted concrete road? I mean there is just too much difference between 45% speed and 100% speed. Plus zigzag is longer unless diagonal cell distance is the same as adjacent one.

[LWM]

LWM, you talk like you are the one who did this system. =D Or is there a way to mod game to change pathfinding?

No, but I'm a mathematician, and the pathing algorithm has always irritated me 

There's certainly ways mods can change how pathing works, it's just gonna be a lot of work...

[B@R5uk]

As I understand, the problem with performance cost of honest pathfinder (like A*) is that it looks through a lot of cells to find best route. When there are large open spaces with almost the same walk speed it's truly wasteful. This problem can be solved by introducing a layer (or two) of supercells like 8x8 and 64x64 and having algo to find route over this supergrid of large cells first. When there is a rough estimate (which will skirt obstacles just as fine as honest route) algo will look for detailed route confining its search to some neighbourhood of rough estimate.

When honest A* has a complexity roughly of square of distance between endpoints of path, this modified algo will have linear complexity on fine layer of cells. When there are more than two layers only roughest one will have square complexity.

[LWM]

That layering of regions was exactly what I was thinking about.

[FrodoOf9Fingers]

Redoing the pathfinder system isn't hard, You would just need to write a new pathfinder system, and then patch the old pathfinder function to do nothing but call the new pathfinder.

I've seen the code, and did some stuff with multithreading (no fruits from this, don't ask) around it before.

As far as I can tell, diagonals take the same amount of time as the 4 cardinal directions. Easy to test with 2 pawns with the same move speed, and queueing a corner path for 1 colonist (at least, this is how I tested it). I assume that bases with diagonal paths are more efficient for this reason, even if the walls todo so take more space/ cost more (or are single square uglies)

[LWM]

Redoing the pathfinder system to take larger regions into account and to judge distance based on travel paths from region to region - and adjusting regions to better fit - might be a bit more complex

[k2ymg]

The game uses A*,  and uses two heuristic functions. 1 is uses simple move cost, 2 is calculates average cost of the regions.

When the counts of searched cells  over the specified threshold, the function switched 1 to 2.

2 takes not good path.