ONI's pathfinding : travelling from Paris to Berlin through Moscou

[OxCD]

Hi klei

Is there any chance to see a pathfinding better than this one... ?

Dups are sweeping stuff from the right to the left, they are jumping from each ladder to the next one, instead of taking the straight plastic floor... They are not taking the faster way, they are not even taking the shorter.

When I see this I'm worrying about general pathfinding. Do we have to clean every resilient ladder to make sure they always only have one path ? Sigh...

 

Have a nice day everyone

[KittenIsAGeek]

I generally clean up my dupe's paths on a regular basis.  If there's more than one choice, the dupes will frequently make the wrong choice.  Also, once you get to very large numbers of dupes, reducing the possible choices for any particular dupe will dramatically improve the performance of your base (not just FPS, but also Getting Stuff Done (tm)).

There's also a non-obvious way that tasks are completed.  For example, the way that sweeping currently works is that your storage locker doesn't set the task, the debris that will fit in it does.  So a debris that is close to your dupe basically says, "Hey! I have somewhere to go!  Who's available to pick me up?"  Then all the dupes check their current tasks and priorities and finally schedule priorities.  Multiple piles of debris are multiple tasks that get onto the queue.  They're decided based on where the dupe currently is, until the queue is full.  So the dupe will pick up a debris and run all the way across the map to its storage locker, put it away, then run ALL The way back to pick up the debris that was right beside that first pile, since that's close to where the dupe was when the tasks were originally organized.

Because we're human, we can easily see that this approach is not the best. Why doesn't Meep just pick up the debris right beside the locker, instead of running all the way across the base first?  Well, that's because the debris by the locker, since it was so far away from Meep, probably isn't even on his list of possible tasks.

[SharraShimada]

If you want a real challenge, code a pathfinding routine. If you manage to get a real complex one with thousands of possibilities without any error whatsoever, you got a high paid job in the IT-industry. Its one of the hardest tasks you may find. Especially when there is a dynamically changing set of possible paths. 

[Olleus]

2 hours ago, SharraShimada said:

If you want a real challenge, code a pathfinding routine. If you manage to get a real complex one with thousands of possibilities without any error whatsoever, you got a high paid job in the IT-industry. Its one of the hardest tasks you may find. Especially when there is a dynamically changing set of possible paths. 

Even coding something simple like A* is hard once you start worrying about efficiency. And, when it comes to path finding, efficiency is always a problem. There's a reason why the Travelling Salesman is a standard example of a very hard problem.

[KittenIsAGeek]

18 minutes ago, Olleus said:

There's a reason why the Travelling Salesman is a standard example of a very hard problem.

Yeah, Traveling Salesman is an example of a problem that is dead simple for humans and extremely complicated for computers.  Neural networks are doing a fairly good job, but I find it fascinating that any random kid can tell you which path is the shortest, but it takes a lot of very smart people a long time to teach a computer how to do the same thing.

[Olleus]

7 hours ago, KittenIsAGeek said:

Yeah, Traveling Salesman is an example of a problem that is dead simple for humans and extremely complicated for computers.  Neural networks are doing a fairly good job, but I find it fascinating that any random kid can tell you which path is the shortest, but it takes a lot of very smart people a long time to teach a computer how to do the same thing.

For simple problems humans can do it well, and computers can brute force it. But even for medium sized graphs both suck at finding the best solution. People find decent solutions fast, but then so can computers most of the time, although there are always pathological cases where those fail 

 

But the optimal solution (formally, knowing if there exists a path under a certain length) is just hard. It's NP-Complete, making it as hard as just about any practical problem in the world.

[Emeal]

I dont think its a problem with the AI of Dupes in the game.

I think its a problem of Logistics which is a problem for us to solve.

[OxCD]

14 hours ago, SharraShimada said:

If you want a real challenge, code a pathfinding routine. If you manage to get a real complex one with thousands of possibilities without any error whatsoever, you got a high paid job in the IT-industry. Its one of the hardest tasks you may find. Especially when there is a dynamically changing set of possible paths. 

While I'm fully convinced about this information you brought us, it doesn't mean the case I've provided isn't consistent.

If there's a way to improve pathfinding, my case is an argument which push on work needed.

And by the way, maybe I see this example as an isolated issue, and don't take account of dynamic environment, system processing, challenging coding, planets alignment and dup's shoe size, nevertheless the container where they go is few tiles below a ladder on the left, and the sweep order is few tiles straight on the right, this path doesn't seems complicated, so how to do not be worried about longer and more complex pathfinding when it fails on the most simple one ?

[Coolthulhu]

15 hours ago, SharraShimada said:

If you want a real challenge, code a pathfinding routine. If you manage to get a real complex one with thousands of possibilities without any error whatsoever, you got a high paid job in the IT-industry. Its one of the hardest tasks you may find. Especially when there is a dynamically changing set of possible paths. 

Incredibly misleading post.

Ability to differentiate between slower and faster paths has been done hundreds of times before. It's simply a matter of penalizing slow movements by treating them as if they involved longer paths. Klei already does it for climbing up poles.

@OxCD is not asking for something like Factorio's train route pathfinding. Nor for pathfinding with a large vehicle with momentum and direction. No portals, no time-dependent paths, no paths involving planning fuel usage. Just plain paths with extra weights. Like climbing up poles.

Depending on Klei's data structures, this problem is between easy and trivial to solve.

[Gurgel]

16 hours ago, SharraShimada said:

If you want a real challenge, code a pathfinding routine. If you manage to get a real complex one with thousands of possibilities without any error whatsoever, you got a high paid job in the IT-industry. Its one of the hardest tasks you may find. Especially when there is a dynamically changing set of possible paths. 

That one is actually pretty simple. Well, relatively speaking. (It already is very, very hard.) Now add resource-constraints and make it (soft) real-time. Good luck.

13 hours ago, KittenIsAGeek said:

Yeah, Traveling Salesman is an example of a problem that is dead simple for humans and extremely complicated for computers.  

It is actually dead simple for computers as well, and does not even require much code. If you have near infinite time, that is. Humans are pretty good at finding approximations by just looking at it, but that only works for small problem instances.

1 hour ago, OxCD said:

While I'm fully convinced about this information you brought us, it doesn't mean the case I've provided isn't consistent.

You have a consistent and repeatable artifact of the current algorithm used. The problem is that it likely requires coding in an exception or a second optimization pass to solve and that slows _everything_ down. Remember this is real-time planning.

Come to think of it, has anybody noticed dupes taking different paths based on game speed settings?

28 minutes ago, Coolthulhu said:

Depending on Klei's data structures, this problem is between easy and trivial to solve.

Yes, but how much does it cost in performance and memory footprint? Adding weights is costly and even more so when you take modern caching hierarchies into account. Poles are likely a hard-coded exception.

[Coolthulhu]

37 minutes ago, Gurgel said:

Yes, but how much does it cost in performance and memory footprint? Adding weights is costly and even more so when you take modern caching hierarchies into account. Poles are likely a hard-coded exception.

Performance: utterly negligible.

Memory: tens of mb at the worst. Possibly no change at all.

Poles may be a hardcoded exception, but unless it's a really ugly hack, the game should cache weights already. The case is probably handled on pathfinding cache building time, not on pathfinding algorithm execution, which needs to be fast and shouldn't handle weird cases on its side.

[KittenIsAGeek]

3 hours ago, Gurgel said:

It is actually dead simple for computers as well, and does not even require much code. If you have near infinite time, that is. Humans are pretty good at finding approximations by just looking at it, but that only works for small problem instances.

At its base, you're correct. Its simply a matter of iterating through possibilities and matching them up with distance/time constraints.

However, the problem is one of scale.  If you have only three possible paths, then its very simple to pick the shortest route.  The problem scales exponentially, however, as you include destinations and possible routes.  As humans, its easy for us to exclude routes immediately, so we only consider those that appear to be the best.  For computers, someone has to tell the computer which routes are not worth checking, otherwise it will analyze them along with the rest and add to the computing time requirement.

Google Maps pathfinding doesn't get it right quite a bit of the time in my area.  It often tries to direct people through the cement plant because on the map its a paved road while the alternative is dirt -- but the cement plant isn't an open public road.  There's also some routes that google will fail to give an option unless I chose a mid-point along the route I want.  

And the traveling salesman problem is even more complicated than the google maps pathfinding scenario, because the traveling salesman problem is: "There are X destinations that can be reached in any order, find the fastest route that goes through each of them, preferably without backtracking."  With multiple paths between each point, it isn't always a matter of just picking the next closest point.  The algorithm for a computer ends up being recursive, scaling exponentially with the potential paths and destinations: You pick a route through all destinations and calculate its weight, then you start again, picking a different route, and check its weight.  Do this for all possible paths and then sort for the shortest.  A person looking at the map would quickly say, "Well, we only need to check these three paths for the fastest," but a computer has to check all that aren't specifically excluded.

[Gurgel]

4 hours ago, Coolthulhu said:

Performance: utterly negligible.

Memory: tens of mb at the worst. Possibly no change at all.

Poles may be a hardcoded exception, but unless it's a really ugly hack, the game should cache weights already. The case is probably handled on pathfinding cache building time, not on pathfinding algorithm execution, which needs to be fast and shouldn't handle weird cases on its side.

You seem to overlook that a weighted algorithm has a massively larger cache, I/O and computation footprint. Have you ever added weights to an optimization algorithm for a not trivially sized task? Sure, if all is in 1st level cache, you will hardly notice, but the point is that this will not be the case here.

1 hour ago, KittenIsAGeek said:

At its base, you're correct. Its simply a matter of iterating through possibilities and matching them up with distance/time constraints.

Not even that. Enumerate all paths, remember the best one so far. If you find a better one, replace the remembered one. Yes, you can do that recursively, but you can also do it with a simple non-recursive depth-first search, a back-pointer and next-pointer in each node. This is PSPACE (actually linear space in the number of one-hop paths). As I wrote "if you have near infinite time", I think you can deduce I am well aware that the above approach is EXPTIME though.

It is definitely not difficult to implement, unless you actually care about execution time. Then it becomes exceptionally hard to even only find good approximations computationally. And ONI does not only care about execution time, it even needs (soft) real-time to keep the game flowing. It does not get much harder than that and I think the algorithm used in ONI performs pretty well given these constraints.

[KittenIsAGeek]

16 minutes ago, Gurgel said:

Yes, you can do that recursively, but you can also do it with a simple non-recursive depth-first search, a back-pointer and next-pointer in each node.

I remember going over this in one of my classes a few years back and the professor showed us several ways that this process actually fails to get the shortest path.  But, usually it does a pretty good job.  Anyway, we're both pretty much agreeing that pathfinding takes a lot of computational time.

[Gurgel]

14 minutes ago, KittenIsAGeek said:

I remember going over this in one of my classes a few years back and the professor showed us several ways that this process actually fails to get the shortest path.  

If you do a complete search, it will find it. But you never do that in practice as it may take longer than your remaining lifetime even for pretty small examples. Hence from a practical point of view you are correct as you always need to terminate early or do some other optimization. I was arguing from a point-of-view that in theory is practical but in practice is not   

14 minutes ago, KittenIsAGeek said:

 Anyway, we're both pretty much agreeing that pathfinding takes a lot of computational time.

That we certainly do. 

[Red Shark]

I actually worked on a pathfinder-y thing last year! I thought I had some sweet never-before-implemented idea to cut down on subsequent calls.So I implemented it, and it's pretty cool! It breaks big areas down into the minimum number of regions to reduce the # of pathfinding nodes. It looks like this:

Then I started to test it and found out it wasn't nearly so easy to handle partial-path caching while guaranteeing shortest path -- at least in the case where your data gets modified at run-time (as ONI's does).

Long story short: Pathfinding is hard.

My tangent aside, I'm inclined to agree with Coolthulhu.

7 hours ago, Coolthulhu said:

 

@OxCD is not asking for something like Factorio's train route pathfinding. Nor for pathfinding with a large vehicle with momentum and direction. No portals, no time-dependent paths, no paths involving planning fuel usage. Just plain paths with extra weights. Like climbing up poles.

This situation in particular looks like a failure of the path-cost analysis part of the pathfinder -- similar to how several versions back submerged dupes would prefer firepoles as a means of upwards traversal, despite the significant speed penalty for doing so.

[Coolthulhu]

10 hours ago, Gurgel said:

You seem to overlook that a weighted algorithm has a massively larger cache, I/O and computation footprint. Have you ever added weights to an optimization algorithm for a not trivially sized task? Sure, if all is in 1st level cache, you will hardly notice, but the point is that this will not be the case here.

The weights are there already in the cache. Poles.

If it was a special case hardcoded at the lowest level, it would be much worse for performance than switching the entire algorithm to weights.

[Gurgel]

13 minutes ago, Coolthulhu said:

The weights are there already in the cache. Poles.

If it was a special case hardcoded at the lowest level, it would be much worse for performance than switching the entire algorithm to weights.

Poles are a flag or an additional pass. They are not weights. They may even be implemented by giving ladders a length larger than 1 and poles a direction-dependent length, hence there would not even be a flag during path finding. So, have you ever added weights to some optimization algorithm? 

[Coolthulhu]

3 minutes ago, Gurgel said:

Poles are a flag or an additional pass. They are not weights.

How do you know that? Have you checked the actual algorithm or even just the cache building part of it?

How would an additional pass even work here? I already covered the flag option when talking about the performance penalty compared to weights.

How would "direction-dependent length" work without weights?

6 minutes ago, Gurgel said:

So, have you ever added weights to some optimization algorithm? 

What is that even supposed to mean? Pathfinding algorithms are weighted pretty much by definition.

[Gurgel]

4 hours ago, Coolthulhu said:

How do you know that? Have you checked the actual algorithm or even just the cache building part of it?

How would an additional pass even work here? I already covered the flag option when talking about the performance penalty compared to weights.

How would "direction-dependent length" work without weights?

What is that even supposed to mean? Pathfinding algorithms are weighted pretty much by definition.

I think I will stop now. There is no reaching some people...

[Coolthulhu]

5 minutes ago, Gurgel said:

I think I will stop now. There is no reaching some people...

Yeah, I noticed. No matter how much I try, all I get back is some vague concerns that would require very specific implementation that is incredibly unlikely to be a thing. All to excuse a hack that probably isn't even in the game.

Is it THAT hard to come up with an actual argument?

[0xFADE]

It doesn't seem like they have any weight when calculating travel.  Like traveling through liquid, or across a ladder instead of on top of it.  Even just going up and down a single tile(diagonal) should cost more.  Something as simple as adding in the movement speed should help.

[welepein]

14 hours ago, 0xFADE said:

It doesn't seem like they have any weight when calculating travel.  Like traveling through liquid, or across a ladder instead of on top of it.  Even just going up and down a single tile(diagonal) should cost more.  Something as simple as adding in the movement speed should help.

Thank you very much. Its really helped.

[Kiros]

I like to think of the terrible path finding as a feature to add challenge to the game, it feels like I'm playing Lemmings. I don't hate it.

[KittenIsAGeek]

35 minutes ago, Kiros said:

I like to think of the terrible path finding as a feature to add challenge to the game, it feels like I'm playing Lemmings. I don't hate it.

Lemmings was awesomely fun.  And the pathfinding is a challenge at times.

Although, Nails hasn't been built into a tile by Bubbles in a long time.  Hmm. I may have to try and force it to see if its still possible.