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

[samuk190]

Zhentar, you're software developer right..
Try understand this poor brazilian-english suggestion.
You can add statistics
to look better the pathfinding? Example: I will go to the kitchen. Obviously I don't need see the map again to go to the kitchen in the second time.
Except if you modify any tiles around the kitchen..
This will make the game runs smoother with much more fps. Example: 50 colonists makes alot of CPU usage trying to look for a path..
if you have saved in statistics, they will just move to the saved route location instead of finding the location from zero.
Its like route system...
The performance logic:
http://prntscr.com/d91yk9 Look the pic.
You / vanilla logic.
http://prntscr.com/d91zmd
its like you did  in the montain, but with a improved statistics for more routes...
See the difference.
I'm not software developer, I just know some logic of C++.
In this logic, the only trouble is when you modify a tile that have much paths saved in statistics. This will cause a bit lag like the vanilla but only for 5 seconds to reorganize and rebuild the path statistics.

[Zhentar]

Caching paths is one of the approaches I considered. But ultimately, I rejected it because RimWorld isn't very well suited to it. There are a number of problems that reduce the effectiveness of it. There are different sets of rules that apply to different pawns, or the same pawns in different circumstances, so you would have to save half a dozen different types of paths, and even within a single group of pawns, the optimal path depends on the pawn's move speed (terrain adds a fixed number of ticks to the movement cost, rather than a percentage as the UI suggests, so for a luciferium enhanced bionic jogger it can be faster to take a much longer path across paved tiles, while it's faster for the stoned peg legged geezer with a bad back to cut through a swamp to move fewer tiles), and path costs are highly dynamic (holding open a door, dropping a stone chunk, etc., would affect optimal paths), so your path would be invalidated frequently. And on top of that, the most expensive paths are rarely taken; calculating the shortest path from the freezer to the dining room is easy so caching that doesn't help much.

[EldVarg]

What he means is that he is lazy? Jk :p

[skullywag]

Zhentar not sure its this or the mods in question but I get that same error I posted when using:

https://ludeon.com/forums/index.php?topic=27331
https://ludeon.com/forums/index.php?topic=26958

Its ALWAYS when roofs need constructing, now it could be it does it without those mods but I havent checked yet, i just get spammed with:

Exception ticking James: System.NullReferenceException: Object reference not set to an instance of an object
  at BetterPathfinding.RegionLinkDijkstra.RegionLinkPathCostInfo (Verse.Region region, Verse.RegionLink minLink, BetterPathfinding.RegionLinkPathCostInfo& result) [0x00000] in <filename unknown>:0
  at BetterPathfinding.RegionLinkDijkstra.GetNextRegionOverDistance (Verse.Region region, System.Nullable`1& secondBest) [0x00000] in <filename unknown>:0
  at BetterPathfinding.RegionPathCostHeuristic.GetPathCostToRegion (Int32 cellIndex) [0x00000] in <filename unknown>:0
  at BetterPathfinding.PathFinder.FindPathInner (IntVec3 start, TargetInfo dest, TraverseParms traverseParms, PathEndMode peMode, HeuristicMode mode) [0x00000] in <filename unknown>:0
  at BetterPathfinding.PathFinder._FindPath (IntVec3 start, TargetInfo dest, TraverseParms traverseParms, PathEndMode peMode) [0x00000] in <filename unknown>:0
  at Verse.AI.PathFinder.FindPath (IntVec3 start, TargetInfo dest, Verse.Pawn pawn, PathEndMode peMode) [0x00000] in <filename unknown>:0
  at Verse.AI.Pawn_PathFollower.GenerateNewPath () [0x00000] in <filename unknown>:0
  at Verse.AI.Pawn_PathFollower.TrySetNewPath () [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

Let me know if I can help with repro or anything.

[Canute]

Zhentar not sure its this or the mods in question but I get that same error I posted when using:

https://ludeon.com/forums/index.php?topic=27331
https://ludeon.com/forums/index.php?topic=26958

Its ALWAYS when roofs need constructing, now it could be it does it without those mods but I havent checked yet, i just get spammed with:

I think it might be an issue with [A15] Work Smarter, the 1. link, because i use Hauling hyst. and better path. too and don't got this problems.

[samuk190]

Caching paths is one of the approaches I considered. But ultimately, I rejected it because RimWorld isn't very well suited to it. There are a number of problems that reduce the effectiveness of it. There are different sets of rules that apply to different pawns, or the same pawns in different circumstances, so you would have to save half a dozen different types of paths, and even within a single group of pawns, the optimal path depends on the pawn's move speed (terrain adds a fixed number of ticks to the movement cost, rather than a percentage as the UI suggests, so for a luciferium enhanced bionic jogger it can be faster to take a much longer path across paved tiles, while it's faster for the stoned peg legged geezer with a bad back to cut through a swamp to move fewer tiles), and path costs are highly dynamic (holding open a door, dropping a stone chunk, etc., would affect optimal paths), so your path would be invalidated frequently. And on top of that, the most expensive paths are rarely taken; calculating the shortest path from the freezer to the dining room is easy so caching that doesn't help much.

Thanks for the answer... so there's a way to make the game run with more fps and taking it all circumstances? I have a fx 6350 and the game starts to be laggy after 25 colonists...

[skullywag]

Caching paths is one of the approaches I considered. But ultimately, I rejected it because RimWorld isn't very well suited to it. There are a number of problems that reduce the effectiveness of it. There are different sets of rules that apply to different pawns, or the same pawns in different circumstances, so you would have to save half a dozen different types of paths, and even within a single group of pawns, the optimal path depends on the pawn's move speed (terrain adds a fixed number of ticks to the movement cost, rather than a percentage as the UI suggests, so for a luciferium enhanced bionic jogger it can be faster to take a much longer path across paved tiles, while it's faster for the stoned peg legged geezer with a bad back to cut through a swamp to move fewer tiles), and path costs are highly dynamic (holding open a door, dropping a stone chunk, etc., would affect optimal paths), so your path would be invalidated frequently. And on top of that, the most expensive paths are rarely taken; calculating the shortest path from the freezer to the dining room is easy so caching that doesn't help much.

Thanks for the answer... so there's a way to make the game run with more fps and taking it all circumstances? I have a fx 6350 and the game starts to be laggy after 25 colonists...

I would suggest deleting all your worldpawns (dead and alive) from your save, leaving your faction leaders and anyone you care about(buried colonists etc) as these worldpawns eat ticks in late game colonies.
For example I found EVERY animal ive ever sold in there, that amounted to 100s of pigs...100s. All ticking...im looking into ways of automating this.

[hiepbg]

Caching paths is one of the approaches I considered. But ultimately, I rejected it because RimWorld isn't very well suited to it. There are a number of problems that reduce the effectiveness of it. There are different sets of rules that apply to different pawns, or the same pawns in different circumstances, so you would have to save half a dozen different types of paths, and even within a single group of pawns, the optimal path depends on the pawn's move speed (terrain adds a fixed number of ticks to the movement cost, rather than a percentage as the UI suggests, so for a luciferium enhanced bionic jogger it can be faster to take a much longer path across paved tiles, while it's faster for the stoned peg legged geezer with a bad back to cut through a swamp to move fewer tiles), and path costs are highly dynamic (holding open a door, dropping a stone chunk, etc., would affect optimal paths), so your path would be invalidated frequently. And on top of that, the most expensive paths are rarely taken; calculating the shortest path from the freezer to the dining room is easy so caching that doesn't help much.

Thanks for the answer... so there's a way to make the game run with more fps and taking it all circumstances? I have a fx 6350 and the game starts to be laggy after 25 colonists...

I would suggest deleting all your worldpawns (dead and alive) from your save, leaving your faction leaders and anyone you care about(buried colonists etc) as these worldpawns eat ticks in late game colonies.
For example I found EVERY animal ive ever sold in there, that amounted to 100s of pigs...100s. All ticking...im looking into ways of automating this.

How can i delete them from my save ?

Thanks,

[Alenerel]

I would suggest deleting all your worldpawns (dead and alive) from your save, leaving your faction leaders and anyone you care about(buried colonists etc) as these worldpawns eat ticks in late game colonies.
For example I found EVERY animal ive ever sold in there, that amounted to 100s of pigs...100s. All ticking...im looking into ways of automating this.

Thats awful. I can understand somehow the pawns, but the animals ticking? I think that this is something that should be addressed in the game. Both pawns and animals, since long saves with this are going to have speed problems.

[Thirite]

I got this error when a pawn was standing in an open door that was currently forbidden (click to enlarge)

[hoochy]

Caching paths is one of the approaches I considered. But ultimately, I rejected it because RimWorld isn't very well suited to it. There are a number of problems that reduce the effectiveness of it. There are different sets of rules that apply to different pawns, or the same pawns in different circumstances, so you would have to save half a dozen different types of paths, and even within a single group of pawns, the optimal path depends on the pawn's move speed (terrain adds a fixed number of ticks to the movement cost, rather than a percentage as the UI suggests, so for a luciferium enhanced bionic jogger it can be faster to take a much longer path across paved tiles, while it's faster for the stoned peg legged geezer with a bad back to cut through a swamp to move fewer tiles), and path costs are highly dynamic (holding open a door, dropping a stone chunk, etc., would affect optimal paths), so your path would be invalidated frequently. And on top of that, the most expensive paths are rarely taken; calculating the shortest path from the freezer to the dining room is easy so caching that doesn't help much.

Thanks for the answer... so there's a way to make the game run with more fps and taking it all circumstances? I have a fx 6350 and the game starts to be laggy after 25 colonists...

I would suggest deleting all your worldpawns (dead and alive) from your save, leaving your faction leaders and anyone you care about(buried colonists etc) as these worldpawns eat ticks in late game colonies.
For example I found EVERY animal ive ever sold in there, that amounted to 100s of pigs...100s. All ticking...im looking into ways of automating this.

I saw this too. As soon as the save gets big (due to history) the game lags a lot. Didn't know they were all ticking but it makes sense. Is this fixed in A16? A tool to do it would be great otherwise.

[pinguin42]

I'm using 30ish mods, but this one would seem the logical cause for this (rare) issue that I'm having. Sometimes my pawns freeze in place and will not move until I either double tap the R key or prioritize a new job to them. The game does not freeze at all, just a single pawn. Their job description will say they have a task, like "hauling granite blocks to granite wall (blueprint)", but they will not actually move at all. I've seen it happen with different tasks as well, hauling, building roof, building floor. This has happened 5 times in 2 years of game time now.

I'm running Rimworld on an old computer and have noticed the game needs a second or two when spawning large groups of visitors (Hospitality mod) or trade caravans, even though I'm on a 275x275 map with only 4 pawns and a very small base (and 9 pets). I have been unable to replicate this situation at all, reloading does not make it happen again, even from an autosave that was under an hour of ingame time before. Which is why I'm thinking it might be pathfinding related, pawns will end up in a slightly different spot at a different time and not get stuck because of it.

I have not tried to let the game run when it happens, so I have no clue whether a pawn will actually starve to death when getting stuck like this or that it will prioritize eating before finishing the task it got stuck on. Will try and remember to do that if it happens again.

Anyone care to guess at what's causing this?

P.S. If you want log files, mod lists or somesuch, please tell me where to find those and the easiest way to get those to you. I'm not that tech savvy 

[Zhentar]

That sounds like what happens when pathfinding fails, though it may not be the fault of this mod; I know there's at least one case where the core reachability check fails (reported & fixed for A16). The log file should show an error message if it's the mod's fault; you can find instructions on where to get the log file here: https://ludeon.com/forums/index.php?topic=513.0

[pinguin42]

Here's the log: http://pastebin.com/Sp3rhixK

[Zhentar]

Thanks. There's nothing pathfinding related in there, so I think it is a reachability issue (and therefore core, not this mod). I think for A16 I'll add in a bit more logging to help with tracking this sort of thing down.