Bay 12 Games Forum
Dwarf Fortress => DF Suggestions => Topic started by: MugwumptheGrand on October 01, 2020, 01:11:55 pm
-
Currently, Dwarf Fortress suffers considerable frame rate drops once a fort begins pushing past a population of ~100, running near 1/10th of its intended, default speed when the population nears 200 without using certain "features" such as atom smashing, tiny sized embarks, specially designed forts, and memory editors to help keep the load on the system down. However, one of the largest processor loads continues to be from dwarf pathfinding. A dwarf performs a pathfinding check to its final destination for every step it takes. This is extraordinarily inefficient, especially considering the workload increases exponentially with the distance to the destination.
What I propose is to attach an array to each job in the current jobs system. When a dwarf accepts the job and attaches their name to it, they will use the existing pathfinder to find the optimum path to their destination. When they do find the optimum path, they will store the coordinates of each step in the path into the associated array in the job. Then, they will use each coordinate in the array as their destination, only having to pathfind one tile away with each step. For example, if a dwarf at (21, 40, 81) wants to pathfind to collect a plump helmet spawn from a stockpile located at (11, 40, 81), they would first use the existing pathfinding to find their path to it. Then they would store each step along that path in the job (20, 40, 81), (19, 40, 81), (18, 40, 81), etc. Then the dwarf AI would, instead of pathfinding to the destination at (11,40,81) with every step, pathfind one tile at a time down the list until they reach the end. This is a massive improvement on the amount of processing power needed, as the dwarf is only checking the immediate >26 tiles around it for its next step instead of hundreds/thousands/tens of thousands of tiles every step along the majority of its journey.
The potential pro's of this method are massive. Currently, a significant amount of processor power goes to each dwarf checking thousands of tiles with every step along a 100 tile long path, leading to serious drops in fps. With this proposed array method, they would only make one large pathfinding decision when they accept a job and then a series of miniscule pathfinding decisions while following the array of coordinates. Another pro is this method, from what I can see, should be relatively easy to add to the existing AI without significant alterations to the AI decision loop.
Array pathing isn't ideal for jobs with mobile targets such as military dwarfs chasing a goblin or a hunter stalking an animal, so a flag or some other method would need to be included so the AI knows which jobs need to follow an array and which jobs don't and shouldn't generate one. The biggest foreseeable hurdle is modifying the current pathfinder to save coordinates of its discovered path into an array. The AI might need minor adjustments to its decision making loop if a tile it expected to be clear is now forbidden or blocked for some reason like flooding, fire, or a dwarf blocking a 1 tile wide passage. A likely solution would be to cancel the job, clear the array, and pathfind to the destination again which would bring the work load back to current levels temporarily.
The computer resource costs of implementing this should be minimal. Even hundreds of arrays with thousands of integers stored in them should only add several MB's to used RAM at most. Adding the creation of an array and saving coordinates to it slightly increases the processor load at the start of the pathfinding process, but using the stored coordinates as destinations should drastically reduce the amount of processing power being used overall. Pathfinding fps spikes should only occur when a large number of dwarfs suddenly take jobs at the same time, such as when they are let out of a burrow.
I also feel this would create some potentially interesting AI behavior if something along the path is modified while the dwarf is following the array. For example, if a door which was open becomes forbidden while the dwarf is pathfinding, they would continue following the array until they hit the forbidden door. It creates the illusion of the dwarf having to walk up to the door and test it to realize they need to find another path around instead of the current system of magically knowing the instant the door is forbidden even if they aren't nearby.
I'm making some assumptions with this post. Judging from the fact FPS stays consistently low and doesn't bob up and down, I'm assuming pathfinding is called frequently by dwarfs as they move around. And I'm assuming a method similar to this doesn't already exist in game.
Thank you for your consideration in reading this far.
-
Currently, Dwarf Fortress suffers considerable frame rate drops once a fort begins pushing past a population of ~100, running near 1/10th of its intended, default speed when the population nears 200 without using certain "features" such as atom smashing, tiny sized embarks, specially designed forts, and memory editors to help keep the load on the system down.
I don't have this problem (I use a high popcap and like large embarks), which makes me strongly suspect that this is a RAM-gated problem, not a CPU-gated problem (I have lots of RAM). If it's a RAM problem, the question of processor load is irrelevant: the slowdown is from hitting swap space which is orders of magnitude slower than RAM.
-
Must be nice being one of the few people with the golden game from Armok. For the rest of us, the game slows down considerably as the population of the fort increases, and it isn't due to RAM usage, which is extremely easy to check with any OS.
-
Must be nice being one of the few people with the golden game from Armok. For the rest of us, the game slows down considerably as the population of the fort increases, and it isn't due to RAM usage, which is extremely easy to check with any OS.
Are you sure about that? Total RAM usage doesn't have to be high before many OSes start swapping you, and DF's RAM usage pattern definitely looks like it would encounter that problem.
-
Well, while you are still wrong about more RAM being the solution, researching why you are wrong has led me to some interesting insights. The CPU is not the limiting factor in DF in most cases, nor is the amount of RAM the computer has beyond the minimum required. The limiting factor seems to be memory speed. DF makes such a colossal number of reads/writes (many of them misfires due to using an old compiler apparently) to memory that most RAM sticks and CPU caches can't keep up after a certain point.
I have no idea how array pathfinding would influence this at all, so I guess I'll just consider this suggestion debunked for now.
Also, OS's do not swap programs from RAM to hard drive unless explicitly told to do so or if the RAM runs out. A 2GB RAM user like DF is not going to cause that in most machines. Also DF is 32-bit. It is impossible for it to use more than 4 GB of memory no matter where it is stored due to its old architecture, so more RAM literally does nothing.
-
Also, OS's do not swap programs from RAM to hard drive unless explicitly told to do so or if the RAM runs out.
Depends on the OS, it's settings, and the amount of RAM.
Also DF is 32-bit.
DF comes in both 64 and 32 bit builds.
-
Also, OS's do not swap programs from RAM to hard drive unless explicitly told to do so or if the RAM runs out.
Depends on the OS, it's settings, and the amount of RAM.
I feel like you're arguing technicalities with me.
And thanks for correcting me on the bit format. Eventually we'll get to discussing the actual suggestion. I was going over the math, and even if the bottleneck is memory speed, reducing the calls to pathfinding would still improve the speed of DF. This is easily noticeable with the correct use of traffic designations and AI friendly fort design. A* involves a lot of reading and writing to memory as it constructs its pathfinding tree. I still feel adding arrays to dwarf jobs which allow them to only make a single pathfinding call per job is a substantial improvement which is relatively easy to implement.
-
Have you proven that your assumption about how DF goes about path finding is correct?
As far as I understand, the path to a target is calculated when the job is taken, and then stored in a path list in the unit (this list can be examined using DFHack). Each step the unit attempts to path to the next tile in that list, which usually succeeds. When it does not a somewhat stupid additional path finding to the next step is performed, leading e.g. to two dorfs meeting in a single tile corridor to both turn around and use the other, slightly longer, corridor, meet there, turn around...
You also get stupidities such as climbing on the wall (following the initial path) when a staircase has been removed, rather than path around the now non walking tile, extending the path by a one or two steps.
-
Also, OS's do not swap programs from RAM to hard drive unless explicitly told to do so or if the RAM runs out.
This is false: many do.
-
I suspect the slowdowns upon greater number of dwarves is mostly from all the rest of the 'calculation gunk' stuff that such a complex game accumulates (either by bad design, or from actual intended retentions of all the data and associated calculations that support this little civilisation-simulator).
(I'm pretty sure it is as Patrik says. Both from past discussions and emperical evidence. You can engineer quite interesting 'computers' with pressure-plates closing and opening doorways to force re-routing. Though I mostly used that behaviour, in the old days, to time-waste invaders back and forth along various winding tunnels. There's an omniscience[1] of "routes open right now" at the point of making a decision, but absolute ignorance of how this is changing (being blocked, shorter routes opening) while they're busy pathing. Only upon being blocked (or, possibly, being disturbed in various other ways to abandon and immediately reset their aims) do they gain an instantaneous (and newly-persistent) plan based on the most recent reconfiguration.)
[1] Save for semi-obstacles like actual traps, unless they're previously made aware of them.
-
Pathfinding is absolutely what cripples my DF forts and I've got a good system. Once you get to the 200-300 range its just inevitable. But I play with temperature and weather off because, well, those cripple it too. Anything, and I mean ANYTHING that could be done to fix it would be a huge win in my opinion and what would get me back to playing DF. I always wondered why some paths weren't just stored in memory until they needed to be recalculated for some reason.
-
Pathfinding is absolutely what cripples my DF forts and I've got a good system. Once you get to the 200-300 range its just inevitable. But I play with temperature and weather off because, well, those cripple it too. Anything, and I mean ANYTHING that could be done to fix it would be a huge win in my opinion and what would get me back to playing DF. I always wondered why some paths weren't just stored in memory until they needed to be recalculated for some reason.
How did you prove that your problems were caused by path finding, as opposed to any of the other possible causes, such as e.g. evaluation of which of the 10 million items Urist should path to, or anything else that comes with size and age (I've found that 30 years worth of webs in the caverns can cost up to 5 FPS when your rate is down under 20, for instance)?
To prove that Toady is wrong and that path finding is the big culprit you'd have to profile the program and verify that it's spending most of its time in the path finding code.
-
Dwarf Fortress objectively already does what you are suggesting and this is easily discernible through DFHack. You can even edit their cached path live. Fastdwarf teleports them to the end of the cached path.
-
Pathfinding is absolutely what cripples my DF forts and I've got a good system. Once you get to the 200-300 range its just inevitable. But I play with temperature and weather off because, well, those cripple it too. Anything, and I mean ANYTHING that could be done to fix it would be a huge win in my opinion and what would get me back to playing DF. I always wondered why some paths weren't just stored in memory until they needed to be recalculated for some reason.
How did you prove that your problems were caused by path finding, as opposed to any of the other possible causes, such as e.g. evaluation of which of the 10 million items Urist should path to, or anything else that comes with size and age (I've found that 30 years worth of webs in the caverns can cost up to 5 FPS when your rate is down under 20, for instance)?
To prove that Toady is wrong and that path finding is the big culprit you'd have to profile the program and verify that it's spending most of its time in the path finding code.
Anecdotal but:
1. When I send large numbers of dwarves out (as in when I send my army on a raid) the FPS death is massively reduced
2. When invading armies enter the map the FPS death is massively increased
3. When I send my miners on long-distance digs the FPS death is increased
4. When my dwarves aren't digging or hauling long distance and are just ambling around the inn, workshops, houses, etc. the FPS death is decreased
So, you're right, I haven't debugged a compiled computer program to make this determination. But the evidence overwhelmingly points to pathfinding operations as the culprit. Now, what part of pathfinding? Also unsure. But I can say with some confidence that its pathfinding.
-
The O(n) algorithm used to detect if the current cached path is valid, more than likely.
And I can also give overwhelming evidence towards cached paths using only in-game stuff, no DFHack knowledge: if you put a dwarf behind rapidly moving 3/4 depth water, such that they can occasionally path through but often can't, the game slows down massively, instantaneously, even if you have only 7 dwarves, because this one dwarf is pathfinding every 3 or 4 ticks. This is strong evidence that what the game is doing is faster than pathfinding every tick.
-
Pathfinding is absolutely what cripples my DF forts and I've got a good system. Once you get to the 200-300 range its just inevitable. But I play with temperature and weather off because, well, those cripple it too. Anything, and I mean ANYTHING that could be done to fix it would be a huge win in my opinion and what would get me back to playing DF. I always wondered why some paths weren't just stored in memory until they needed to be recalculated for some reason.
How did you prove that your problems were caused by path finding, as opposed to any of the other possible causes, such as e.g. evaluation of which of the 10 million items Urist should path to, or anything else that comes with size and age (I've found that 30 years worth of webs in the caverns can cost up to 5 FPS when your rate is down under 20, for instance)?
To prove that Toady is wrong and that path finding is the big culprit you'd have to profile the program and verify that it's spending most of its time in the path finding code.
Anecdotal but:
1. When I send large numbers of dwarves out (as in when I send my army on a raid) the FPS death is massively reduced
2. When invading armies enter the map the FPS death is massively increased
3. When I send my miners on long-distance digs the FPS death is increased
4. When my dwarves aren't digging or hauling long distance and are just ambling around the inn, workshops, houses, etc. the FPS death is decreased
So, you're right, I haven't debugged a compiled computer program to make this determination. But the evidence overwhelmingly points to path finding operations as the culprit. Now, what part of pathfinding? Also unsure. But I can say with some confidence that its path finding.
Not unless your "pathfinding" includes the part where object to path to determination is performed. Both that part and the path finding proper scales with the number of dorfs. In addition to that, I think the number of jobs posted from various categories scale with the number of eligible dorfs for some categories, which means the number of jobs dorfs have to evaluate when looking for a new task increases as the number of dorfs increases (you can see the unfiltered full set of jobs in the list for hauling stuff to the trade depot, and, I think, harvesting, and for a while in the past, books needed to be returned to a bookcase). I don't know if job selection evaluation is much of a factor, though.
It can be noted that invader path finding doesn't work the same as citizen path finding much of the time, which you can see from them often stopping to move towards your entrance when the drawbridge is raised, while migrants move up to the drawbridge and stand there stupidly until you crush them with the bridge if you don't provide alternative paths into the fortress.
In addition to that, invaders often engage is pursuit of whatever is available on the surface, and that, again, uses a path finding logic that keeps recalculating the target dynamically, rather than first move to the target's position at the time the pursuit began, then set a new point a the location the target is at at the time that point is reached, etc.
Another thing that scales with the number of dorfs is the number of clothing wear evaluations caused by wearing clothes, as well as the number of evaluations to determine if a new sock should be picked up. Uniforms might reduce that need a bit, depending on how DF determines when to look for better equipment and how that search is organized (a really poor implementation would be to look at every sock in the fortress to determine if if's of a better quality and free to claim at every job switch).
-
You've got job selection backwards, the jobs evaluate dwarves that might be able to do them, but the overall performance is the same anyway.
There's a few ways to improve performance on this. The most obvious way is to use a scheduler that simply interrupts the search process if it goes on for too long; this will keep the game running at 100 FPS, but will make job finding slower on a tick-by-tick basis, which might be undesirable behavior.
It's also possible to do these checks in multiple threads, e.g. by chunking the jobs list into largeish sets which are then iterated through, or by simply using std::foreach(std::execution::par_unseq,jobs.begin(),jobs.end(),&job.findWorker) (https://en.cppreference.com/w/cpp/algorithm/for_each) or similar. My experience with using C++17 parallel algorithms has actually been really good, for heavier work, though I should also note that if findWorker or a variation thereof modifies dwarf state then this is not really usable, since there's always a possibility that the dwarf is being assigned two jobs at once (this will simply make one of the jobs not have a worker when it expects to, which might cause incorrect state, which would be nasty).
-
Yes, it's true that technically jobs select dorfs to perform them as you say Putnam.
Also, as you say, if job selection would generate a worker each (or none) but not actually allocate them parallel evaluation should be good. That could then be followed by additional (parallel) passes to find replacement workers for the jobs that had their candidate snatched, or just have those allocations wait for the next cycle, but that might lead to low priority jobs being starved for extended periods of time. The downside with the iterative parallel evaluation process is that it will use more CPU overall, which laptops in particular are unhappy with, and in the worst case it's worse than sequential allocation (when each job's top candidate is the same on every pass, but there actually are enough dorfs to perform all the jobs, as you'd have to do as many passes as with the sequential allocation, plus handle the additional administration and memory bandwidth competition on top of that). That, in turn, might be countered by each job returning an ordered list of candidates, probably with a maximum length.
-
The most obvious way is to use a scheduler that simply interrupts the search process if it goes on for too long; this will keep the game running at 100 FPS, but will make job finding slower on a tick-by-tick basis, which might be undesirable behavior.
Not strictly related to this, and maybe happens elsewhere already, but this could spark odd bugs/strangenesses that are hard to diagnose/explain.
Person A has a slow machine, hits a 'search cap' quickly and gets "no route to <somewhere clearly routable>” errors. Uploads save for checking, Person B tries it on (marginally) better machine, cap not hit and issue not encountered.
Conversely, Person A has a very good machine but a genuine faulty code condition after a long-distance pathing legitimates a fateful interaction. Person B tries to run the same scenario but for them their own cap swerves them away from even encountering the condition as reported.
Not an argument against this approach, but I just want to raise the possibilities for future consideration. (Stepwise play at a key time might consistently avoid/reveal such awkward Heisenbug results, across all implementations, as it becomes obvious we're in this sort of territory.)
-
The most obvious way is to use a scheduler that simply interrupts the search process if it goes on for too long; this will keep the game running at 100 FPS, but will make job finding slower on a tick-by-tick basis, which might be undesirable behavior.
Not strictly related to this, and maybe happens elsewhere already, but this could spark odd bugs/strangenesses that are hard to diagnose/explain.
Person A has a slow machine, hits a 'search cap' quickly and gets "no route to <somewhere clearly routable>” errors.
Not "stopping pathfinding halfway", "stopping job searches halfway". It would finish the current job, check if it has time to do another job check, then return if it doesn't.
-
Same general thing, different details. Whether "the search process" is within an A* search or between them.
If the job "goes idle" until the next slot then it won't complain about no route but it will go unfulfilled in one simulation where it might in another, with no in-game reason.
It might be serviced the next time there's an attempt to run through job-associations. Does it get priority next 'tick' as remnants of the old tick queue, ahead of anything new/renewed, or is it still at the same possible unreachable end of the rebuilt queue? Depends on how it's coded[1] by the coder or his chosen library functions, but there's possible differing handling that could confound all existing expectations on rare occasions.
Just mentioned for the potential curiosity. Increasingly not part of the root of this discussion, I know, just a (risingly convoluted) trivial aside.
[1] Assuming that the effort to check each job averages significantly more than the "choosing" code needed to implement this, I'd probably consider something like pre-weighting/grouping candidates with priority values and checking 'N priority-N' jobs for N=N.max downto 0 (within a wider loop that continues until all jobs or time available to assess jobs become depleted), and within each "N jobs" bit randomly pick the (up to) N jobs to try in this particular pass. Could just be random-plucking without the weight-groupings (which could also be dealt with by something like "N² priority-Ns" if you wish) but I'm imagining there's good reason to (e.g.) set "Trying to Moodcraft" as more urgent than some other jobs I could mention (for the game, whatever the player's thoughts are about the relative needs of Dumping, Smoothing, Deconstructing, etc, though "Do This Now!" tasks could be given something like an N+=10 adjustment on behalf of the clearly frustrated player) the basic idea is that the overall chances of non-choosing go down each time it slips through each instance of choosing made, just by statistics, without ever having an 'untouchable' class of jobs either. It just smooths out the 'bad luck'. It's also very unlikely to consistently hit/not-hit the problem I was describing as the Heisenbug on the same machine, which might still be awkward, but not in the way I originally described.
-
The O(n) algorithm used to detect if the current cached path is valid, more than likely.
And I can also give overwhelming evidence towards cached paths using only in-game stuff, no DFHack knowledge: if you put a dwarf behind rapidly moving 3/4 depth water, such that they can occasionally path through but often can't, the game slows down massively, instantaneously, even if you have only 7 dwarves, because this one dwarf is pathfinding every 3 or 4 ticks. This is strong evidence that what the game is doing is faster than pathfinding every tick.
The dwarfs are still constantly rechecking their path, likely looking for changes and hazards. Want to know how I know? Start playing with traffic designations. If the dwarfs were using stored paths, the FPS would take 20-30 seconds to increase and the increase would be very minor as dwarfs finish their jobs and create new paths for the next. However, if you change a traffic designation in the current version of DF, the FPS literally changes over the course of seconds and by 10-12 frames with good traffic designation. This means they are frequently calling pathfinding and are not using their stored path like they should for efficiency. If Toady is worried about them blundering into a hazard, he could do infrequent (once every five dwarf steps or so) path finding checks to the destination nine spots ahead in the array (if it exists, otherwise don't) to make sure the path is open without the dwarf walking directly adjacent to a raging fire and without the massive workload of checking if the entire path to the destination is open every few steps. The best way to cost effective pathfinding is to find ways to shorten the distance it performs pathing checks as much as possible due to its exponential increase in cost with distance.
-
It's a quadratic cost increase with distance, actually, and also, what you've shown is that they're constantly rechecking their current path, which is, again, with 100% certainty known to be stored in a unit (https://github.com/DFHack/df-structures/blob/00549aca0640ca121c20734df667f79b247c93b4/df.units.xml#L618) as a structure-of-arrays1 series of x, y and z positions. (https://github.com/DFHack/df-structures/blob/00549aca0640ca121c20734df667f79b247c93b4/df.map.xml#L44)
O(n2) is bad, but O(n) is also, quite often, bad in practice.
1As opposed to array-of-structures (https://en.wikipedia.org/wiki/AoS_and_SoA)
-
A* has the potential to be a combination of linear (unobstructed path between A and B), quadratic
(same z-level with obstructions), or exponential (different z-levels) depending on how complex the path is. In most cases, a fort will have multiple z-levels which immediately makes it take a linear/quadratic increase as the pathfinder moves to the point above/below the desired location, then an exponential increase as it begins fanning out in all directions to find a path down/up (8^x or 16^x if it's looking for ways to climb or leap up/down), and finally back to linear/quadratic once it's on the same z-level.
Sleep deprivation and math is fun.
Either way, it seems the recommendation has become to lessen the distance the dwarf does its path rechecks since arrays are already implemented. Only checking ten steps ahead in the array vs current pos to destination pos would have a noticeable impact on FPS if experiments with traffic designations and different fort designs are any indicator. It would be interesting to base how far something checks ahead in the array based on a character's perception, so more perceptive characters would see a hazard from further away and change their path. But for now I'd be happy with optimizing the path checking.