Make pathfinding based on travel time

[x4550]

Something is wrong when horizontal ladders are always the preferred route.

 

[Ciderblock]

It IS based on travel time. That's why the weirder problems happen in the first place. Pure distance pathfinding would be much simpler and more predictable.

The problem, as I've mentioned in another thread on this subject, is that you generally can't do full optimization in a real time game, especially one with variable environments. So you have to use some heuristics at some stage of the calculation. Sometimes these heuristics give results that are far from optimal. The heuristics in ONI still need work, but that doesn't mean the pathfinding isn't even based in travel time.

[Kasuha]

3 hours ago, Ciderblock said:

It IS based on travel time. That's why the weirder problems happen in the first place. Pure distance pathfinding would be much simpler and more predictable.

It is not based on travel time. Most of pathfinding is based on number of "steps" where each step counts for "1" added measure. There are exceptions, for instance climbing ledges had apparently its weight raised so duplicants don't prefer that over climbing ladders anymore, but most of other kinds of step still count as 1 and in some cases it leads to funny effects.

3 hours ago, Ciderblock said:

The problem, as I've mentioned in another thread on this subject, is that you generally can't do full optimization in a real time game, especially one with variable environments.

For the purpose of current path selection, you can consider the environment stable. Yes it may change over time but it's not very likely and you don't have to re-evaluate the path with every step, you can select the path and only check periodically if the path is still valid, running new pathfinding only if the path gets broken. You can even let the dupe run all the way to the place where the path broke (that's what people would do anyway). In such situation you can technically account for all effects such as length of climbing or jumping animation, or the acceleration on long strikes of floors or ladders due to the Athletics skill level without serious performance impact.

It seems to me, though, that the current implementation really re-evaluates the path after each step. That might be behind the problems where a suffocating dupe would periodically switch paths after each step, or it might be behind serious performance problems with large maps and large duplicant counts. It looks like the most robust approach for changing environment but it also has the worst performance impact which is even emphasized if you try to account for subtle effects like animation lengths or skill levels in it.