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.
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.
Quote from: fritzgryphon on April 10, 2020, 09:50:48 AMIn 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:
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://imgur.com/vTJ0xOl.jpg)
https://www.reddit.com/r/RimWorld/comments/50ukdy/we_havent_automated_this_yet_weekly_qa_thread/d77rd9f/
QuoteThe 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.
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?
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.
LWM, you talk like you are the one who did this system. =D Or is there a way to mod game to change pathfinding?
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.
Quote from: Canute on April 10, 2020, 12:18:00 PMBut 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.
Quote from: B@R5uk on April 10, 2020, 12:11:55 PM
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 :P
There's certainly ways mods can change how pathing works, it's just gonna be a lot of work...
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.
That layering of regions was exactly what I was thinking about.
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)
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
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.
I made a pathfinder mod with basic A*. It is always takes best path. I'm not feel any lug, but I didn't test other env., like laptop, linux or mac. (I use Core i7-4771, 3.5GHz.)
Also, I made a A* with region-to-region cost calculation. It was not best, but better than vanilla. However, it was bad performance. To do R-to-R efficiently, we need modify Region class but we can't.
Anyway, if you use modern pc, basic A* is not bad.
The 2 main problems of the simplified algorithm (using some regions instead of single tiles) are that if some region has a lot of obstacles (e.g. stockpiles, rooms with furniture, trees alongside a road), it sees its movement penalty as high in average and will avoid to cross that region at all rather than trying to find a clear way through it; and probably it sets transitional waypoints to the centers of those regions, thus zigzags.
What about trying a compromise: calculate a "rough" path at long distance using that (or any other?) simplified algorithm, then choose some point on it about 20 tiles from the start and calculate an exact path to it using the "honest" algorithm; then, when the pawn moves some tiles (10-15 - the idea is that the pawn won't yet enter the region to which that transitional point belonged; probably it'll be easier to do just every few seconds), repeat it, finding a new simplified path from the current position and a new transitional point 20 tiles away, etc. This way the pawn will always move on exact segments, reducing said problems (especially the second one, because the pawn will never be forced to go to those regions' centers or whatever).
If my description is not clear enough but anyone is interested, I can try to explain better.
The approach I had envisioned was something like this:
Make a bunch of regions (where everything in a region is roughly reachable from elsewhere in the region). For each region, calculate the distance from one neighbor to another, cache the data with the region. Calculate distance using region-traversal calculations.
You'd still need some basic estimate, which will still cause problems in some cases, but ?
I'm afraid this "adaptive" regions division might be even harder to code and more resource hungry (it will require frequent map-wide recalculations, ideally with any change on map including moved items). And there still will be problem with finding what points inside those regions should be used transitionally.
I had been assuming that it would only recalculate regions when things pawns cannot cross get built.
Would you be interested in sharing your code, by the way?
Unfortunately I still didn't learn C#, thus no real code :(
Joint venture, wraith try to write down the algorithm in some mathematical forumla and LWM could try to put it into some C#.