Bay 12 Games Forum

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.

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.

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.