Better PathfindingVanilla 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.
A16A16 1.5.2 DownloadVersion 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.
A15Download Link:
https://github.com/Zhentar/BetterPathfinding/releases/download/1.3.2/Better.Pathfinding.v1.3.2.zipVersion 1.3.2 Changelog- Fixed rare pathfinding failure
Version 1.3.1 ChangelogVersion 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 PathfindingThe 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 HeuristicThis 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" WayLike 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 HeuristicWith 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" WayThis 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
Author
Topic: [A16] Better Pathfinding (v1.5.2 update 2/22) (Read 151410 times)