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

[RemingtonRyder]

Thanks for the update!

[JerryBi]

bug fixed , thank you.

[biship]

I don't know if your mod is causing this, but haven't seen this error until I installed your mod today (on a new game). Using 1.2.1.

Code Select Expand

Exception ticking Maskinnen: System.NullReferenceException: Object reference not set to an instance of an object
  at RimWorld.PawnUtility.AnyPawnBlockingPathAt (IntVec3 c, Verse.Pawn forPawn, Boolean actAsIfHadCollideWithPawnsJob, Boolean collideOnlyWithStandingPawns) [0x00000] in <filename unknown>:0
  at Verse.AI.Pawn_PathFollower.NeedNewPath () [0x00000] in <filename unknown>:0
  at Verse.AI.Pawn_PathFollower.TryEnterNextPathCell () [0x00000] in <filename unknown>:0
  at Verse.AI.Pawn_PathFollower.PatherTick () [0x00000] in <filename unknown>:0
  at Verse.Pawn.Tick () [0x00000] in <filename unknown>:0
  at Verse.TickList.Tick () [0x00000] in <filename unknown>:0

Oh, It happened while a pawn was rescuing another pawn that died in their arms! The pawn that was recusing still showed a path to the hospital bed, but the dead pawn was on the ground and the recusing pawn wasn't moving. Stuck!

[Tynan]

Very interesting. Just from a really cursory look at the code, it looks like you're doing some kind of region-level path cost caching. Is this hierarchical pathfinding, or cost caching, or what?

[Zhentar]

The algorithm is still the Vanilla A* algorithm, except that it will revisit closed nodes. I'm using the region system to create a high accuracy, low cost heuristic. There's actually nothing cached across pathfinding calls - I had planned to but the calculations turned out to be cheap enough that there's little need to.

The heuristic starts with an A* search (called Dijkstra in the code because I only recently added the heuristic to it) to traverse a RegionLink graph from the destination to the start, building a map of estimated costs for the regionlinks (using the octile distance between the centers of the regionlinks), and the cheapest regionlink for each region. Then, when calculating the heuristic cost for each cell, it just calculates the distance to the cheapest regionlink for the current region, and adds on the cost.

[Skyfaller]

So I found a bug where colonists will take an inefficient, longer path with 3 autodoors just to avoid one single regular door -- even if that door is forced open. I will explain below, but first an annotated screenshot.



I've used the dining room as an example destination for a route path. The situation:
1. The door circled in red is a standard granite door, commanded to stay open.
2. Because the door stays open, colonists are not slowed down waiting for it to open. Colonists *should* be using the green path.
3. Colonists are actually using the yellow path in all cases - crossing 3 granite autodoors instead.
4. Solution: Replacing the regular door (red) fixes the pathfinding problem, and colonist use expected paths to their destinations again.

So the bug here is related to the force open command, I think? Does the pathfinding algorithm need to be updated to consider this?

I can provide a savegame demonstrating this issue, if you would like. The file is too big to attach to this post, but I will be happy to provide an alternative link if desired.

Hope this helps!

[Zhentar]

Please do share the save. The heuristic does consider held/left open doors to be zero cost - and even if it didn't, it should still consider opening the door to be faster than taking that long path.

[Rock5]

I always thought that when it zigzagged diagonally that that meant that it would take the same amount of time as going straight, ie. they go faster diagonally to compensate.

Because of this post I did a quick test and sure enough a pawn going straight takes a lot less time than one zigzagging diagonally.

Conclusion: This mod is a must.

[Oragepoilu]

In case someone would try to use it,

mod that add floor with hight speed (like the sensor panels from http://steamcommunity.com/sharedfiles/filedetails/?id=784370602, they give 162% speed) break this mod as an error pop up saying they search for over 160 000 cell, leaving your pawn stuck.

I didn't need more than about 10 modded tiles to have the error happen, so don't use it. (edit : I mean, don't use the tile, not this mod, it's a great one)

[Simulacrum0]

i'm seeing the 160000 search error as well on a 400x400 open area map that's mostly sand.

[Oragepoilu]

yeah, I can see why it would happen on big map. however, with the modded tile my guys can't even cross sometime more than 20 square distance, so there is something wrong with this.

[Zhentar]

Could you two test this and see if it resolves your issues? Better Pathfinding v1.3 RC

[Seinne]

love this mod btw, don't think I mentioned it before. Fixes an issue that drove me nuts playing this game.

[biship]

Better Pathfinding v1.3 RC seems to working for me. I hadn't seen any issues with the previous versions tho.

[KONO_DIO_DA]

Ran into an interesting issue between this mod and another.


As far as I can tell, Better Pathfinding is somehow speeding up the tickrate, which reduces the cooldown of SS13 Syndicate Mod's Syndicate Minibomb Grenade to effectively zero, allowing it to become a "cone of fuck " instead of a grenade. I can confirm this issue stopped once Better Pathfinding was disabled.