Please improve duplicant pathfinding

[Kasuha]

There are some things on duplicant pathfinding that make them spend unnecessary time while traveling to their destinations. Here are a few examples:

A duplicant can jump over single tile gap but if there's a ladder there, it jumps on the ladder and then jumps off.

When the ladder ends one tile lower, the duplicant jumps down that tile, then clibs back up.

When the ladder ends two tiles lower, the duplicant jumps down, then climbs up - this takes considerably longer than just jumping over that gap.

Last two are when there is a ledge just two tiles above the bottom of a ladder - instead of taking the ladder, the duplicant uses the ledge, both up and down.

The pathfinding should go the least travel time way, i.e. it should avoid unnecessary maneuvers if there's a faster path.

 

[mr_anderson]

i had a problem where my dupes ran to a piece of ladder, jumped for no reason and then returned , i had to block off the area so my dupes wouldnt waste time jumping for no reason. I eventually discovered that it was because of a water source below the ladder. So the AI sent  4 dupes to get water but only 1 dupe collected the water the rest simply went to the ladder leading down to the water source and jumped without doing anything.

[Kasuha]

Another, similar case: jumps off the ladder, then climbs on top of it. Also on entering the next ladder, jumps down instead of jumping straight on the ladder.

[Catus]

I've met some even worse case, here is an example:

If I don't build the two marked titles, the duplicant will be trapped on that place, that one will move left then move right because of pathfinding problems. (maybe it's difficult to choose one path?)

So I have to make one path unavailable to fix this problem.

[TopSloth]

I'm sure path finding will be worked on throughout development

[Ciderblock]

Optimal pathfinding is not practical in a real-time game, especially when the move speed depends on the local environment and the user can change the environment. All such games need to use heuristics to get approximately-optimal paths, which sometimes aren't even approximately optimal. Otherwise the performance quickly suffers.

 

That said, usually these problems arise with much longer paths. Short paths, like in several of the examples in this thread, should really work properly.

[azzaisme]

I had a dupe go across a ladder and then fall to his death. The fall didn't kill him. Drowning did

 

 

 

RIP Stinky

2017-2017

[vonVile]

Its really annoying when it comes to Dupes opening airlocks. Replace a lower tiles with a horizontal airlock and they'll hop down onto the airlock causing it to open followed by the Dupe hoping out.

I even had a weird one with a regular airlock. I was experimenting with having the doors being on top of 2 tiles to rooms with a ladder 1 square away. The Dupes would climb up the ladder, go to the airlock and then go back to the ladder.

[Cyberboy2000]

On 2017-04-06 at 0:03 AM, Ciderblock said:

Optimal pathfinding is not practical in a real-time game, especially when the move speed depends on the local environment and the user can change the environment. All such games need to use heuristics to get approximately-optimal paths, which sometimes aren't even approximately optimal. Otherwise the performance quickly suffers.

That shouldn't really be a problem though, you'd only need to recalculate every time your destination changes and when something in your path changes (path blocked, ladder broken etc) Plus, not being able to handle different speeds on different surfaces is one thing, but I can't imagine what kind of pathfinder would be used to get results where a path that's clearly longer than another is preferred (not just in terms of distance, but if the pathfinder works like the above images suggest number of nodes as well) 

[Ciderblock]

1 hour ago, Cyberboy2000 said:

That shouldn't really be a problem though, you'd only need to recalculate every time your destination changes and when something in your path changes (path blocked, ladder broken etc) Plus, not being able to handle different speeds on different surfaces is one thing, but I can't imagine what kind of pathfinder would be used to get results where a path that's clearly longer than another is preferred (not just in terms of distance, but if the pathfinder works like the above images suggest number of nodes as well) 

Again, it's really hard to do real-time pathfinding when your movement speed is environment-dependent. Hopping off the ladder and then back on it is not optimal, but with a faulty heuristic, it may look good to try to get your move speed up when possible. Altering the heuristic to fix that problem typically creates another one when dealing with more complicated paths.

That said, ONI's pathfinding does indeed need some serious work, but I would say the first issue is not bad path choices but rather infinite indecision issues (where the pathfinder finds two paths that it thinks are equally good and the dupe oscillates back and forth between them). Also, some of the pictures in the OP *really* make no sense, especially the third one.

[Kasuha]

12 minutes ago, Ciderblock said:

infinite indecision issues

Yeah that's more severe problem than suboptimal path choices but at cycle 600+ with my colony I only ran into that bug maybe once while my dupes have already wasted tons of time on those suboptimal paths. Especially with athletics skills on levels 70+ where my dupes are lightning fast on ladders or floors it's a pain to watch them "take the stairs" instead.

[Executive_Lurker]

I hate when they finish a liceloaf and instead of delivering it straight my priority 9 fridge right next to the musher they go do something else and then come all the way back :/

[n37runn3r]

"Where the pathfinder finds two paths that it thinks are equally good and the dupe oscillates back and forth between them" I have had tons of seriously aggravating deaths where they will sit there and spin in circles until they suffocate or drown instead of simply going left/right or up/down 1 or 2 tiles. Maybe a limiter on how many times it will calculate the path? It might mess up the responsiveness to change, but considering how often dupes will choose to strand or drown themselves while digging, I don't think the game would suffer.

[SmallMuffin11]

+1 on the thread !

[Firebee]

On 5/3/2017 at 8:02 PM, n37runn3r said:

I have had tons of seriously aggravating deaths where they will sit there and spin in circles until they suffocate or drown instead of simply going left/right or up/down 1 or 2 tiles

This happens to me a lot too and I really don't understand why. The path will be completely gree and clear but they'll just keep going back and forth till they die, or i notice and manually direct them out

[vonVile]

The worse one is Dupes taking a natural ladder instead of the much faster built ladder.