Print

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

[MugwumptheGrand]

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.

[Maximum Spin]

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.

[MugwumptheGrand]

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. 

[Maximum Spin]

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.

[MugwumptheGrand]

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.

[Ziusudra]

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.

[MugwumptheGrand]

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.

[PatrikLundell]

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.

[Maximum Spin]

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.

[Starver]

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.

[DontMineYellowSnow]

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.

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

[Putnam]

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.

[DontMineYellowSnow]

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.

[Putnam]

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.