[A16] Better Pathfinding (v1.5.2 update 2/22)

Started by Zhentar, October 02, 2016, 07:43:01 PM

Previous topic - Next topic

Zhentar

Better Pathfinding

Vanilla pawns have a tendency to make some... odd... decisions when finding their way to their destination. Like going out of their way to avoid those nice, fast paths you built to slowly trudge through dirt, snow, and debris. Better Pathfinding brings an end to that, teaching pawns (friend and foe alike) to take sane, near-optimal paths - while trying to keep performance near Vanilla.

PathAvoid is compatible with Better Pathfinding.

A16
A16 1.5.2 Download
Version 1.5.2 Changelog

  • Fixes index out of bounds error
Version 1.5.1 Changelog

  • Fixes errors when pathing to large Things
Version 1.5 Changelog

  • Fix handing for negative path costs (floors that make pawns move faster)
  • Crazy good performance improvements in some edge cases
  • Better path quality in some edge cases
Version 1.4.3 Changelog

  • Fix broken foolery from 1.4.2
Version 1.4.2 Changelog

  • Improved path quality on easy paths
Version 1.4.1 Changelog

  • Fixed a bug where pawns would path through corners that should be impassible
  • Significantly improved performance and path quality when path costs are high (e.g. thick snow over ice or marsh, pathing outside of allowed areas)
Version 1.4 Changelog

  • Updated for A16
  • Fancy new "Bidirectional Pathmax" algorithm for big performance improvement in some cases
  • Improved performance when pathing outside of allowed areas
  • Fixed some errors

Note that for A16 I have to use a MapComponent to tie pathfinder instances to maps. This means disabling Better Pathfinding will cause an error to be logged when you load a game saved while Better Pathfinding was enabled, but it is benign and can be safely ignored. It can be safely added to existing games with no errors.

A15
Download Link: https://github.com/Zhentar/BetterPathfinding/releases/download/1.3.2/Better.Pathfinding.v1.3.2.zip

Version 1.3.2 Changelog

  • Fixed rare pathfinding failure

Version 1.3.1 Changelog

  • Probably fixed a bug

Version 1.3 Changelog

  • Prevents freezes & crashes with flooring that speeds up pawn movement.
  • Improves performance in some cases, particularly in open terrain.
  • Hopefully prevents pathfinding errors on very large maps.

Version 1.2.1 Changelog

  • Fixes exceptions cause by v1.2
  • Performance improvement

Version 1.2 Changelog

  • Fixes sapper pathfinding failure on very large, difficult to path maps.
  • Fixes Vanilla pathfinding bug where sappers thing they can walk on water
  • Improves pathfinding performance for "smart" raiders
  • Paths with impassible destination cells (e.g. mining, repairing) now use the improved logic, rather than falling back to Vanilla logic.


Version 1.1 Changelog

  • Fixed sapper pathfinding bug so that they won't try to go straight through rock. They will now be moderately smarter about pathfinding than Vanilla. (still planning to tweak this a bit, but wanted to get the fix out now)
  • Fixed a bug that was causing the funny diagonal bits in some paths, as well as some other sub-optimal pathfinding. Unfortunately, this had a significant performance cost in some cases
  • Taught the heuristic about doors. This doesn't improve paths but significantly improves performance on paths through or near doors, especially if the shortest path would be through a door that is forbidden.
  • Improved heuristic handling of rough terrain, significantly improving performance in open, outdoor areas.
  • Other misc small optimizations.


Comparison images:

Vanilla Pathfinding
The colored squares show which tiles the pathfider has examined while looking for the best path to the destination. You can clearly see the usual behavior for long paths here - it tries to go straight towards the destination, only going around when it runs into something. It didn't even try to avoid the marshy bit at the beginning of the path!

The path chose here is 10% longer than the optimal path.


If We Used A Naive Admissable Distance Heuristic
This test used a simple octile distance heuristic. This is the standard "right" way to implement an A* pathfinder, and it always chooses an optimal path.

You can see it looks at an awful lot more tiles (even though many are "obviously" stupid and not going to work), which carries a pretty significant performance cost. That performance cost is why this isn't how Vanilla works.


The "Better Pathfinding" Way
Like the octile distance, we get an optimal path here, but we only look at two thirds as many tiles! You can see it's quite a bit smarter - it knows there's a mountain in the way. It doesn't explore every nook and cranny hoping to find a way through the mountain, and it gives up on going around to the left when it finds the marsh. Most of the tiles explored are through the plains area, basically hoping to find a road to cross it faster. (This raises the obvious question, why didn't I put a road in for my promo pics to better demonstrate my algorithm's cleverness? This is why I'm a software developer and not a marketer)

Version 1.1 - Look at all the performance!

Vanilla & Admissable Heuristic
With very hard paths like this one, the Vanilla pathfinder and the simple optimal heuristic have very nearly identical performance. Both find the optimal path, by searching a very large area.


The "Better Pathfinding" Way
This round, I thought ahead and used a layout that better demonstrates the brilliance of my approach! On the right side, there's a door but it's forbidden. It knows that door is forbidden, so it doesn't even try to find a way through there; it knows not to to go down the dead ends.

However, you can also see that a number of the cells are more opaque than others. This is a new behavior in 1.1; sometimes it needs to revisit cells it has already visited once. This part isn't so clever, particularly since it's revisiting some of them half a dozen times, but in the end, it finds the optimal path in 1/4th the time that Vanilla takes.

License: Do whatever the hell you want with this. No credit required.
Source is on Github here: https://github.com/Zhentar/BetterPathfinding


EldVarg

Woho! Tried out an earlier version of this and it was good :).

Crossbowman

Somehow, I saw your name, saw the title, and though we have never met, I had a good feeling about this mod. So far, it looks excellent; my colonists finally take the roads I built for them instead of trudging through filthy swamps and fetid pools of stagnant pond water, and they finally stop trampling my crops in the fields and instead take the stone paths paved along the rims. Occasionally they do have the odd sort of behaviour where they unnecessarily take a diagonal path instead of a straightaway, but otherwise, it's exciting to see that my colonists behave more like human beings now!

As far as performance goes, there is a noticeable hit when all colonists are awake, so my guess is that the performance decrease is more severe for when there are lots of pawns who need to go to set destinations. Animals wandering around the map seem to have no real effect, so that is good. A big thumbs up from me!

Zhentar

Yeah, I've noticed it takes funny diagonal cuts occasionally. I think it's because my heuristic slightly breaks consistency (around the corners of regions, moving one tile closer to the goal can result in the heuristic incorrectly claiming that it moved further away from the goal). There should be a way to fix it, but I haven't tried yet.

I believe the main performance concern for the vanilla pathfinder was not the common cases dragging down average FPS, but rather worst cases causing hitching/jank. If that is true, then this mod shouldn't cause any performance problems, because it performs as well or better than Vanilla in the really bad cases that I've tested.

BetaSpectre

+1 This mod looks really nice. I'm sticking to vanilla cause I think it's more realistic that people IRL might not know the optimal paths.
░░░░░░░░░░░░░░░░░─╤▌██ |
░░░░░░░░─╤▂▃▃▄▄▄███████▄▃|
▂█▃▃▅▅███/█████\█[<BSS>█\███▅▅▅▃▂
◥████████████████████████████████◤
                           TO WAR WE GO

iceteazz

 _ Nice work, i gonna test it now, thx alot :)

Dingo

Been waiting for this ever since you posted your attempt on Reddit :)

huyderman

Quote from: BetaSpectre on October 02, 2016, 10:55:22 PM
+1 This mod looks really nice. I'm sticking to vanilla cause I think it's more realistic that people IRL might not know the optimal paths.

Sure, people might not know the optimal path. But unlike vanilla, people IRL can spot an obstacle ahead before they're standing right in front of it... Or would stick to the road or walk around a march... We do a lot of micro-optimizations to how we walk without thinking about it, and IMHO the results of the optimized pathfinding here is closer to how people actually plan a route than vanilla.

kcirdor

People may not know the optimal path their first trip, maybe not even their second trip.  But after 100 trips they better damn well know the best past to take. Also, the Pawns make so many dumb decisions like hauling that 4 stack of steel from across the map, and then going right back to the same location and hauling that 6 stack of steel that was just barely out of range for multi stack pick up previously.  Thanks for the mod.  This is just a straight forward installation for a mod, right? Drop in the mod folder?

Dingo

You drop the folder into RimWorld/Mods just like any other mod.

EldVarg

#10
Quote from: huyderman on October 03, 2016, 07:09:10 AM
Quote from: BetaSpectre on October 02, 2016, 10:55:22 PM
+1 This mod looks really nice. I'm sticking to vanilla cause I think it's more realistic that people IRL might not know the optimal paths.

Sure, people might not know the optimal path. But unlike vanilla, people IRL can spot an obstacle ahead before they're standing right in front of it... Or would stick to the road or walk around a march... We do a lot of micro-optimizations to how we walk without thinking about it, and IMHO the results of the optimized pathfinding here is closer to how people actually plan a route than vanilla.

Exactly! Vanilla pathfinding is very very stupid, and they never learn. Making roads was completely useless.

re1wind

I don't think it's a case of knowing/finding the "optimal path", but rather not doing stupid things like walking through a marsh or making large diversions that don't make any sense.

biship


deliveryservice

is the area colored in rainbow, means calculated area for optimal path?
So it's become narrower, then it means it's more memory friendly?

Thirite

Great mod, works well with my existing large mod collection with no errors.