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

[Jaridan]

Was able to obtain the savefile from said poster.
https://puu.sh/tD0a3/464e396b26.7z

[Rock5]

This ones really messed up. When I saw Arthur carrying Salt away from the base I thought "where's he going?. Maybe he's going through another door." What I saw was not expected.

Both Arthur and Emily are rescuing colonist and are both going that weird path. Not only do they go all the way back to this side of the wall but they don't even go through the closest door. They loop around and over the middle of the base.

I think this is the last straw. The funny little loops it sometimes does I can deal with but if it does crazy things like this it's time to uninstall this mod. Funny, I seem to remember it used to work better than this. I only seem to have this funny behavior in the latest version of the mod.

[attachment deleted by admin due to age]

[Rock5]

Time for another test.

With Better Pathfinding.

First half straight to edge of mountain - good. Second half detours to target - bad.

With Better Pathfinding returning.

First part straight to edge of moiuntain - good. Second half detours to target - bad.

With vanilla pathfinding.

First half detours to edge of mountain - bad. Second half straight to target - good.

With vanilla pathfinding returning.

First half straight to edge of mountain - good. Second half straight to target - good.

So overall it looks like vanilla is better, well for this scenario anyway.

[attachment deleted by admin due to age]

[Zhentar]

Could you post your mods list? There's nothing in Vanilla that should ever make it take that crazy long loop.

[Rock5]

Core
HugsLib
MineItAll
Zhentar's Vanilla Tweaks
Numbers
Medical Tab
JTReplaceWalls
JTZoneButtons
Trading Spot
AC-Enhanced Crafting
Area Unlocker
Blueprints
QualityBuilder
Haulpriority_lite
New Zone Tools
I Can Fix It
RimFridge
Industial Rollers
CaravanSpot
Mod List Backup
Refactored Work Priorities
Step Away From The Medicine
Crate
Fresh stockpile filter
Storage Search
Where is Potato soil
Where is rich soil
JTExport
Refugee Stats
Static Quality Plus
HuntersSpot
Realistic Darkness
ExtendedStorage
Follow Me

Wow I forgot about some of those. Must remember to use them.

[Rock5]

Ok I've been raking my brain trying to wrap my head around pathfinding for the last couple of days and I've come up with an idea. I don't really have the ability or drive to test it out so I thought I'd mention it here so better experts than me can pick it apart.

The main problem I see with A* is when you have dead end areas and it checks every square in that area before it exits it to continue on. The cause of this is the heuristics generally don't take into account the obstacle. There is also the problem of simitry but I'm not sure if it's an issue with variable weight terrains.

I came across Jump Point Search algorithm which looks like it's super fast compared to A*. The downside being that it assumes a uniform terrain. But I thought to myself, there has to be a way to use it's speed to improve A*. I thought to myself, "Improved heuristics can improve A*. Heuristics ignore terrain weight. JPS ignores terrain weight". So is it possible to use JPS somehow to make a grid of optimal paths quickly then have A*s heuristics use those JPS paths to come to a more accurate heuristic? If so, I would expect A* to pretty much follow the optimal path right off, saving a lot of time. This assumes that calculating the JPS paths would be faster than the time saved.

Then I thought of another variation of this idea. What if we used flood fill, I think it's called. If we can quickly make an array of of flood fill values from the destination (ignoring terrain weight of course) then use those values as the heuristics then again A* should follow the optimum path immediately instead of going in those dead end areas.

What do you think? Is it worth trying? Or am I just talking shit?

[Celestial]

Then I thought of another variation of this idea. What if we used flood fill, I think it's called. If we can quickly make an array of of flood fill values from the destination (ignoring terrain weight of course) then use those values as the heuristics then again A* should follow the optimum path immediately instead of going in those dead end areas.

Flood filling would cost even more. The problems with path finding isn't the actual finding, its the calculating distance part. Different algorithms are just methods of determining which cells I should check if I flood fill. How would you limit to what extent of the map I should flood fill? The entire map? or a certain radius?

[Rock5]

You don't calculate distances with flood fill. You just add 1 as you radiate out from the target. It assumes only horizontal and vertical movement though. To make it accurate it would have to add 1.4 diagonally. This makes things more complicated because the list wont remain in order just radiating out. You would want to avoid sorting but I think if you work out the right way to do it you could keep it in order without having to sort. I've been working on it. Here is my pseudo code. I'm using horizontal/vertical distance as 10 and diagonal as 14 because I assume using ints is better than using floats.

Code Select Expand

Starting with an open list of nodes, let's call it ol, with x,y and dist value                       
And closed list that is an array for easy reference cl[x,y]=dist                       
Assume ol has function add (int x, int y, int distance)       
               
ol.add (endNode.x, endNode.y, 0)                       
while ol. count != 0                       
    curDist = ol.getFirstItem.dist                   
    ' Do horizontal and vertical neighbors with dist values from curDist to curDist + 4                   
    for each node in ol do                   
        if node.dist <= curDist + 4 then               
            Get horizontal and vertical neighbours that are not on closed list or blocked           
            Add them to open list adding dist as curDist + 10           
        else               
            break           
        end if               
    end for                   
    ' Do diagonal neighbours for curDist only. Remove from open list as you do them.                   
    while ol.getFirstItem.dist = curDist                   
        Get diagonal neighbors that are not on closed list or blocked               
        Add them to open list adding dist as curDist + 14               
        remove first node from open list and add to closed list               
    end while                   
end while                       

I don't think there is anything there that is to complex so I'm hoping it wont take long to do the whole map. Then instead of using the Manhattan distance for the heuristics ie. abs(startNode.x-endNode.x) + abs(startNode.z-endNode.z) you can use the value in the closed list cl[endNode.x, endNode.y].

On another note I think I found in the vanilla pathfinding where it uses the Manhattan distance.

Code Select Expand

this.h = this.heuristicStrength * (Mathf.Abs((int)this.neighX - this.destinationX) + Mathf.Abs((int)this.neighZ - this.destinationZ));
Technically speaking the Manhattan distance assumes only vertical and horizontal movement. It should really be something like
x = abs(startNode.x-endNode.x)
y = abs(startNode.y-endNode.y)
max = Max(x, y)
min = Min (x, y)
heuristic = max - min + (min * 1.4)

It probably could be done more elegantly than that but I wonder what difference just this one change would make.

[Zhentar]

Making the vanilla pathfinder accurate is easy; switch from Manhattan distance to octile distance and remove the weight and you're done. But reducing the heuristic weight directly increases the performance cost.

I spent most of today looking at the pathfinder and figuring out why it was making poor choices in some cases. I figured out a somewhat better way to handle the heuristic weighting, and tie-breaker handling that significantly improved performance and also path quality in some cases.

It should do a fair bit better with your mountain test, but probably still not perfect. Doing better at requires reducing the weight of the heuristic, but that hurts performance when path costs aren't perfectly even with a straight path like that. One thought I've had to address that would be a heuristic weight heuristic, where it estimates how inconsistent terrain costs are and reduces/increases the weight accordingly.

[Rock5]

That's good to hear. I thought you were still tied up with the Extreme Desert Challenge.

Does changing from Manhattan to Octile really make that much of a difference to the performance?

I'm not quite sure what you mean by heuristic weight. Is that what you use to adjust the heuristic to balance the performance and accuracy? If so could you change to Octile while still using the weights?

[Zhentar]

For the vanilla pathfinder, switching to octile without otherwise adjusting the weight has a fairly small impact; mostly it will be slightly better about going around obstacles. My heuristic already uses octile distance.

The weight is indeed what balances performance and accuracy. The heuristic is an estimate of what the best possible path would cost, and the search will continue until it either finds a path that costs that much, or until it's proven that path doesn't exist. Since the heuristic almost always underestimates the actual optimal path cost, the search can spend a lot of extra time looking for alternate paths that aren't there. So when we "weight" the heuristic, we increase the estimate by some amount (I multiply it by between 1.05 and 1.2) and then the search will give up much earlier, but possibly miss a better path in the process.

I've posted an update. It includes an improvement to the heuristic that significantly improves path quality & performance on long diagonal paths, and a few small tweaks that make it better at travelling in straight lines (tie breaking logic, a small rounding change, and a simple check that corrects some inappropriate zig zags). I haven't rigorously tested the performance/optimized yet, but I think performance is on average at least slightly improved. Path quality (on easy paths where the heuristic was accurate) is much better; I still see a few quirks but they are fewer and smaller.

[Zhentar]

And another update. I discovered that two of the changes in 1.4.2 (one of them being particularly important) were broken.

Also, I did performance tests and verified that it has improved by a pretty decent margin in most of my test cases.

[dj84722]

The latest two updates for better pathfinding has broken compatibility with Sensor Panels(160% walk speed) from Pravus's Fences and floors  https://ludeon.com/forums/index.php?topic=26964.0

Both colonists and animals keep getting the ran out of cells to process error when trying to path with them, colonists have been stuck and unable to move anywhere even when drafted, my mod order for testing is
    <li>Core</li>
    <li>HugsLib</li>
    <li>ModListBackup</li>
    <li>Better Pathfinding</li>
    <li>PathAvoid</li>
    <li>Fences And Floors</li>

even when on a desert new colony i used god mode to create Sensor Panels around them and placed prefered paths with path avoid and the yellow error comes up straight away even when wandering

Husky11412 pathing from (127, 0, 112) to (129, 0, 117) ran out of cells to process.
Job:GotoWander A=(129, 0, 117)
Faction: PlayerColony

This will be the last message to avoid spam.
Verse.Log:Warning(String)
BetterPathfinding.NewPathFinder:FindPathInner(IntVec3, LocalTargetInfo, TraverseParms, PathEndMode, HeuristicMode)
BetterPathfinding.NewPathFinder:FindPath(IntVec3, LocalTargetInfo, TraverseParms, PathEndMode)
BetterPathfinding.PathFinderDetour:FindPath(PathFinder, IntVec3, LocalTargetInfo, TraverseParms, PathEndMode)
Verse.AI.PathFinder:FindPath(IntVec3, LocalTargetInfo, Pawn, PathEndMode)
Verse.AI.Pawn_PathFollower:GenerateNewPath()
Verse.AI.Pawn_PathFollower:TrySetNewPath()
Verse.AI.Pawn_PathFollower:TryEnterNextPathCell()
Verse.AI.Pawn_PathFollower:PatherTick()
Verse.Pawn:Tick()
Verse.TickList:Tick()
Verse.TickManager:DoSingleTick()
Verse.TickManager:TickManagerUpdate()
Verse.Game:Update()
Verse.Root_Play:Update()

Disabling better pathfinding fixed the problem straight away

[EldVarg]

Maybe all new floor types from mods does not work now. Could not play with the clutter mod and its new floors.

[tigg]

Got to say, I installed this mod in my game with the new hugslib and had lots of "standing", where I couldn't get my pawns to even do things eg. go to the toilet when they were busting (whole lot of errors to do with poo). This was the only new mod, so it was either this one or the new version of hugslib.