Print

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

[PatrikLundell]

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).

[Putnam]

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) 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).

[PatrikLundell]

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.

[Starver]

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.)

[Putnam]

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.

[Starver]

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.

[MugwumptheGrand]

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.

[Putnam]

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 as a structure-of-arrays¹ series of x, y and z positions.

O(n²) is bad, but O(n) is also, quite often, bad in practice.

¹As opposed to array-of-structures

[MugwumptheGrand]

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.