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

[Rock5]

why would my pawn path like this?

http://prntscr.com/dvodl0

edit: drafting him and having him haul it again has him make a normal path towards it

I've noticed it do weird paths like that too.

[Zhentar]

Slight "hooks" near the end of the path are a known weakness of the current version; I've been experimenting with ways to reduce that tendency without sacrificing too much performance. mason_water's example is a pretty extreme case though; are others seeing it behave that poorly?

This looks like an obvious misspathing. The optimum path looks to be under that little hill in the middle. Instead it goes up, after rounding the mountain, instead of searching in a straight line to the target.

It does look like going under that hill would be faster, but not by very much; only about 30 ticks if I'm counting right; only going a few tiles further than it needs to. That is well within the quality of path I intend for them to pick.

[lost_RD]

It does look like going under that hill would be faster, but not by very much; only about 30 ticks if I'm counting right; only going a few tiles further than it needs to. That is well within the quality of path I intend for them to pick.

I count 13 extra cells travelled for the given path compared to optimal. That seems like more than 30 ticks.

[Rock5]

I don't mind that it's not the most optimal path if it's close enough but what I don't understand is, shouldn't it look primarily for the closest path in a straight line to the target first? I don't understand why it went up in preference to going straight.

[lost_RD]

It reeks of jump point

[Zhentar]

I count 13 extra cells travelled for the given path compared to optimal. That seems like more than 30 ticks.

You must be looking at Mason's screenshot, which is that bad. Rock5's is not.

I don't mind that it's not the most optimal path if it's close enough but what I don't understand is, shouldn't it look primarily for the closest path in a straight line to the target first? I don't understand why it went up in preference to going straight.

That's what the Vanilla pathfinder does. If it worked well, none of us would be in this thread now.

My pathfinder uses a heuristic based on RimWorld's region system, which composes groups of passable cells into a larger unit (each region can be up to 12 cells by 12 cells, so 144 cells or less). Estimating the distance between each linked region lets the heuristic account for large obstructions (like walls and mountains), as well as some chokepoints, like doors. Smaller obstructions that don't completely cross a region are effectively invisible to the heuristic, so it doesn't always make the right choices when it encounters them.

Jump Point Search only works on uniform cost grids, so it's useless for RimWorld.

[faltonico]

Please apply
Want to see YOUR mod in RimWorld?

[milon]

^ ditto

Also, subscribed!

[EldVarg]

Anyone get this to work with MarsX? It looks like no improvements in pathfinding.

[AnNyeong]

https://i.gyazo.com/45479094c0dcee30be8da002e1f89d8d.jpg
I guess he likes to walk?
I mean, this ain't no zig-zag. That's a straight up 10-15 times longer detour for no apparent reason...

[AnNyeong]

Sorry for double post but...
https://i.gyazo.com/17d1496910b7f53a0767e36468a9f9dc.jpg
Again...
https://i.gyazo.com/603d1dd82189edd567e86b8fb3aebed5.jpg
Drafting/undrafting fixes it obviously but... How can I fix that?

[Zhentar]

Do you have path avoid zones set up?

If it's not avoid zones, then probably your region linkages are broken. Save & reload should fix it. If it's happening frequently, then you've either stumbled on an obscure Vanilla bug, or another mod's bug.

[AnNyeong]

Do you have path avoid zones set up?

If it's not avoid zones, then probably your region linkages are broken. Save & reload should fix it. If it's happening frequently, then you've either stumbled on an obscure Vanilla bug, or another mod's bug.

https://i.gyazo.com/20ee5505468ff9581bc7472f9beeefff.png

This is my modlist/order
Didn't seem to recreate so far, we'll see.
It seemed to be only with wood and that specific steel skip. Kinda weird.

I don't think I have anything else related to pathing.

[Jaridan]

@Zhentar did the tweak you made a while ago, that got alphabeaver2 to find a path within 15k nodes compared to 160k, get rid of the problem with animal pathing?



Someone posted this on the steam comment section today :
Modlist from the log :

Code Select Expand

Log uploaded on Friday, January 27, 2017, 1:08:25 AM
Loaded mods:
Core: (no assemblies)
HugsLib[2.3.3]: HugsLib(0.16.0.0)
PhiClient: Newtonsoft.Json(3.5.0.0), websocket-sharp(1.0.2.59611), SocketLibrary(1.0.0.0), PhiData(1.0.0.0), PhiClient(1.0.0.0)
GHXX Tech Advancing: TechAdvancing(1.0.0.0)
Medieval Times: (no assemblies)
Mountain Miner (A16): MountainMiner(1.0.6198.5249)
Efficient Light: (no assemblies)
Feed The Colonists: (no assemblies)
LT-DoorMat: RimWorld-DoorMat(1.0.0.0)
A World Without Hat: AWorldWithoutHat(1.0.6198.19125)
Weapon Tech: (no assemblies)
Trading Spot: Rimworld - TradingSpot(0.0.0.0)
Better Pathfinding: BetterPathfinding(1.0.0.0)
DeadMansClothing: DeadMansClothing(0.16.1.0)
AC-Enhanced Crafting [A16]: AcEnhancedCrafting(1.0.0.0)
Refugee Stats: RefugeeStats(1.0.0.0)
Hand Me That Brick: HandMeThatBrick(1.2.16.0)
JTReplaceWalls: JTReplaceWalls(1.0.0.0)
Rimsenal - Storyteller pack: (no assemblies)
Core Driller: (no assemblies)
Repair Workbench: RepairBench(1.0.0.0)
EdB Prepare Carefully: EdBPrepareCarefully(0.16.1.4)
OSHA Compliance: OshaCompliance(1.0.6207.13087)
Let's Be Honest Here: (no assemblies)
Expanded Prosthetics and Organ Engineering: (no assemblies)
The Mad Rabbits of Caerbannog: Caerbannog(1.0.6198.18118)
Step Away From The Medicine: StepAway(1.0.6216.43174)
I Can Fix It!: ICanFixIt(1.0.6224.40794)
Crafting Hysteresis: CraftingHysteresis(1.0.6207.15385)
JTZoneButtons: JTZoneButtons(1.0.0.0)
Pests: $HugsLibChecker(0.2.0.0), Nandonalt_Pests(1.0.0.0)
Caravan Dogs: (no assemblies)
AC-Enhanced Hauling: AcEnhancedHauling(1.0.0.0)
Animal Tab: BetterAnimalsTab(1.0.0.0)
A Dog Said...: (no assemblies)
Mad Skills - Tiered: MadSkills(0.0.0.0)
Fermenting Cooks: (no assemblies)
Cooks Can Refuel: CooksCanRefuel(2.16.0.0)
TAG Trait: (no assemblies)
More Vanilla Turrets: (no assemblies)
ED-Laser Drill: ED-LaserDrill(1.0.0.0)
Sustainable Drill: (no assemblies)
MineItAll: MineItAll(1.1.0.0)


"i keep getting some sort of issue where animals are trying to path to something but log says they are reaching search limit and everytime it does that my game freezes for a second. ive got the log here https://gist.github.com/7ad3e738740ba2374b5d9ae230c2facd

i can fix the problem temporarily by changing their allowed areas, but it just pops up again with another animal. its getting impossible to play the game."
(lots of trash in the log cause of phiclient mod, starting line for error is 1764)

Code Select Expand

"Alpaca944947 pathing from (79, 0, 158) to Thing_RawPotatoes1967256 hit search limit of 160000 cells."

edit: just to be on the safe side and because i'm paranoid about this(lol) i reupdated steam to ensure it's on 1.4.1 (which it should've been anyway, but making sure doesn't hurt)

[Zhentar]

The change didn't entirely eliminate the possibility of encountering the error, just should have made it much less likely to actually happen.

Logs don't help for troubleshooting this (if I had it log everything I needed there would be probably several megabytes of text). Save games are ideal, but screenshots (showing the pathing pawn and where they are trying to go) still help quite a bit.