Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[IndigoFenix]

An idea which could be applied to a wide variety of solutions and I don't think has been suggested yet (unless I missed it): move some processing time into in-game time.

That is, while the game is trying to figure out the optimal pathing solution between two points of interest, store the solution as it is being calculated in an in-game object and have dwarves use simpler, less-optimized solutions in the meantime, iterating the solution a few times each frame instead of trying to process the whole thing at once.  If this means dwarves will periodically run into walls, wander around in confusion, or get lost before everyone gets their bearings, that is pretty much exactly what you would expect after changing a major pathway, isn't it?  The more complex and maze-like the fortress is, the more time it will take before the dwarves all get their act together.

Calculated paths can even be stored as knowledge that is transmitted between allies, similar to rumors or knowledge of traps.  This would help avoid the all-seeing AI for invaders as well.

[ayy1337]

https://www.youtube.com/watch?v=RMBQn_sg7DA
This is a really interesting approach too, they don't actually use the mini regions or rooms for calculating a path, but just to check accessibility. This could really help if you have sections of fort that are inaccessible to some dwarves, they wouldn't even be considered as candidates for jobs in that area.

[Bumber]

https://www.youtube.com/watch?v=RMBQn_sg7DA
This is a really interesting approach too, they don't actually use the mini regions or rooms for calculating a path, but just to check accessibility. This could really help if you have sections of fort that are inaccessible to some dwarves, they wouldn't even be considered as candidates for jobs in that area.

DF does this already. IIRC, however, the regions are as large as possible, containing everything that is connected. If a dwarf is in a different region number than an item, it definitely cannot be reached (without climbing/swimming.)

I don't remember specifically how it handles flowing liquids blocking paths. There would be too many region recalculations, so it's definitely handled separately.

[ayy1337]

https://www.youtube.com/watch?v=RMBQn_sg7DA
This is a really interesting approach too, they don't actually use the mini regions or rooms for calculating a path, but just to check accessibility. This could really help if you have sections of fort that are inaccessible to some dwarves, they wouldn't even be considered as candidates for jobs in that area.

DF does this already. IIRC, however, the regions are as large as possible, containing everything that is connected. If a dwarf is in a different region number than an item, it definitely cannot be reached (without climbing/swimming.)

I don't remember specifically how it handles flowing liquids blocking paths. There would be too many region recalculations, so it's definitely handled separately.

Ahh I see. One advantage of the smaller regions mentioned in the rimworld video though is being able to do accessibility checks for different creatures, so locked doors are treated as impassable regions for animals - and I imagine you could do similar for flying creatures, ones that can swim, etc.
Plus it can be extended by precalculating paths between the mini regions.

But yes flowing liquids seem like a pretty big issue too come to think of it.

[☼Obsidian Short Sword☼]

+1

[Putnam]

Floyd-Warshall algorithm (all pairs shortest paths matrix), expanded with next-step matrix, on GPU runs at O(n) time.
To find path you check next-step matrix in O(n) time.

Thing is Toady is not using GPU or parallel programming. DF is old mill single thread program. You get 2 threads on 1 CPU these days. So Toady is using some improved or optimized version of Dijkstra algorithm running around O(n^3). At least so much I have been told on forums for last few years.

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Implementations

I could myself provide OpenCL implementation for Floyd-Warshall algorithm, if Toady wished me to.

Looking at the algorithm wikipedia page, it appears this algorithm is intended to run on graphs which can be weighted. How efficient it is for that purpose? I might have misunderstood, but I think to utilize this algorithm, it is first necessary to generate a graph on which the algorithm can work. What do you think, is it perhaps useful as it is?

You can modify the path weights on the weighted graph that is the pathable tiles in-game right now, so it's probably relevant.

An idea which could be applied to a wide variety of solutions and I don't think has been suggested yet (unless I missed it): move some processing time into in-game time.

That is, while the game is trying to figure out the optimal pathing solution between two points of interest, store the solution as it is being calculated in an in-game object and have dwarves use simpler, less-optimized solutions in the meantime, iterating the solution a few times each frame instead of trying to process the whole thing at once.  If this means dwarves will periodically run into walls, wander around in confusion, or get lost before everyone gets their bearings, that is pretty much exactly what you would expect after changing a major pathway, isn't it?  The more complex and maze-like the fortress is, the more time it will take before the dwarves all get their act together.

Calculated paths can even be stored as knowledge that is transmitted between allies, similar to rumors or knowledge of traps.  This would help avoid the all-seeing AI for invaders as well.

The game already sorta does this, at least in the sense that the dwarves only repath if something interrupts their path

[ayy1337]

On the Floyd-Warshall algorithm btw, I don't think it's gonna work.

If you have a 250 x 250 grid, that's 62500 points. So for each point you're storing the shortest path to each other point. So you need 62500^2 paths, which is ~4 billion paths.
Even if a path is only 2 bytes long on average - which would be a massive underestimation as distance between two points in a grid is i'd guess about half the diameter on average, with no obstacles to path around - that's 8GB. And that's just for 1 z-level. Generating this would take _ages_ even on a GPU.

[Putnam]

I did some profiling and it turns out pathfinding is simply not an important factor in performance, bar none. It happens far less often than people think (and thus is far slower than people think, but it doesn't matter that much).

Testing on a fortress that has no tightly-closed doors and no horrid connectivity edge cases (e.g. ongoing floods) gets me pathfinding taking up 6% of CPU time at most. The highest cause of CPU time has nothing to do with pathfinding, it's just units checking other units if they're in line-of-sight, alive, uncaged and needs reacted to, from the early game and getting slightly worse on (since this is O(n^2).

[ayy1337]

I imagine it would depend a lot on the size of the fort and the number of jobs being generated - and how far away the dwarves are to the jobs, since pathfinding cost would scale roughly cubically with that distance in the worst case.

Would be cool to see the profiling though if you're able to share more of the data, how do you do it?

[Putnam]

I imagine it would depend a lot on the size of the fort and the number of jobs being generated - and how far away the dwarves are to the jobs, since pathfinding cost would scale roughly cubically with that distance in the worst case.

Would be cool to see the profiling though if you're able to share more of the data, how do you do it?

I just attach Intel VTune to the Dwarf Fortress exe and analyze the disassembly to figure out what I'm looking at. Here's the profile results for a fortress that is, in fact, undergoing FPS death due to pathfinding (it was running at 3 FPS due to >20 tightly-closed doors)



That top function is pathfinding. This was a 60-second profile, so it's taking up nearly 92% of the CPU time (based on the caller/callee view); removing the issue (making all doors pet-passable) improved the FPS to ~55 or so.



This is a more typical fortress. That top one is some manner of unit processing function; the main line causing problems is a conditional jump on unit.flags1 & 0x2000002 being 0, i.e. on the unit being neither dead nor caged, but the function as a whole is only 28.2% of CPU time. The other 70% is everything else. Pathfinding is apparently 2.3%, about a quarter that of just checking if a unit is dead/caged, which is 9.7%. So yeah, profile.

[ayy1337]

That's actually pretty interesting. I wish toady would release some solid profiling data with actual function names so we could know for sure how long everything is taking.

[Putnam]

That's actually pretty interesting. I wish toady would release some solid profiling data with actual function names so we could know for sure how long everything is taking.

There's some unfortunate history with that. I haven't asked for such things, since I think that, considering what actually happened, being close to the hip about symbols like that isn't unreasonable.

[ayy1337]

I think just the profiling showing what takes how much time in different scenarios wouldn't be as useful for reverse engineering purposes as a copy of the game compiled with debugging information left in.. Plus I think the issue was as much those people being disrespectful and shit talking the game/Toady on his own forum in that case