Print

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

[Infiltrator]

The idea of this post is to gather as much data on DF pathfinding as possible. I hope to be able to have everything related to it in here, eventually. I would appreciate help in this. Feel free to provide links and/or data.

I will also be posting previous suggestions here, as well as summaries. Feel free to correct me if you believe I have misunderstood your suggestion.


Okay, well, having played DF a bit now (around a month or so), and lurking these forums, I see that pathfinding seems to be an issue.

Before making any kind of suggestions, though, I'd like to compile as much information on the matter as possible. (Other people also expressed the desire for such a compilation, and a search for "pathing" did not turn up any such repository.)

I'll try to make clean lists, with references where necessary.

Hopefully, I'll be able to compile all the information on pathing into here.


Reported problems with current system

• Z-level pathing difficulties. A dwarf would rather walk halfway around the map to get to a stone directly below him than one right next to him because it's "zero" steps away
  
  Spoiler (click to show/hide)

  when a dwarf looks for an item it doesnt count the steps taken to go around a long winding tunnel to grab an object, it goes by the direct distance to the object, up down or around<P>for instance
  i have a level of workshops above a huge strip mine
  the mason needs a stone
  to get that stone located 15 spaces north in a stockpile he skips that and takes 300 steps around a corner down the stairs and directly below his workshop making that stone 0 steps away but its really more like 350 steps away
  so slowing down his progress completely<P>similar problem with building floors walls and supports (buildings that use raw materials)
  i know there is no wood on a floor, and there are rocks just down the stairs in a stockpile whereas wood is located far away from my front door
  just above the front door i try to build a floor
  somehow miraculously it gives me the first option to build with a wood material which is 16 space away, although its about 30-40 steps away because he has to go 10 to stairs, down stairs, 10 to where he was, and 20 to where the wood stockpile is
  however there are stones withing 5 steps of him on a different z level<P>
  posting this as one of my masons went down 4 levels to grab a flawless stone fresh cut directly from beneath his workshop
  down 4 levels
  that requires literally 40 steps to the stairs on the level the stone is on, then 40 steps back to the stone directly below his workshop, then a total of 160 steps to make the round trip<P>but hey, atleast miners know what they are doing now
  
• Constant pathfinding eats CPU (doesn't really need a reference)
• Animals pathfind too much, combined with above
  
  Spoiler (click to show/hide)

  The size of the room actually doesn't matter. You can stick them in a room with a door and so long as the door is locked and there is no meeting area in the room, they won't path. I've had about 500 animals in a 48x48 room that was locked up with drawbridges and a locked door and it didn't affect my FPS. As soon as I unlock that door and have it tightly closed, FPS drops to some number near 0.
  
• Dwarves cannot dodge obstacles
  
  Spoiler (click to show/hide)

  I have noticed that dwarfs prefer to crawl under each other in order to take a straight path, even though they could dodge via two diagonal moves.
  It is possible that this only happens on workshops that are in use.
  In particular, I have a magma forge and two magma smelters in a row.  The smith makes a beeline for the far smelter, crawling under the furnace operator in the middle smelter.
  As lying down and standing up takes time, this is rather slower than dodging.<P>0x517A5D
  
• Up, down, can't go up again? UNCONFIRMED?
  
  Spoiler (click to show/hide)

  I've actually had this problem a dozen times in many different fortresses, and I'd assumed it's already been reported, but I didn't see it on the bug list nor in a forum search, and I've been hoping it would be fixed in the new release, so I'll do it now.
  
  When I have a path like
                  _____           ___Goal
  Start ____/         \_____/
  
  My dwarves can never figure out how to do it. My "Control Rooms" for Lava and Water almost always have setups like these so they can seal themselves off at will, and still control the fortresses water and magma distribution - this may be affecting the pathfinding somehow, as there are usually a number of other (inaccesible due to liquids, locked doors, etc.) paths to the Goal location, since it is connected to the fluid systems that runs through the entire fort. What it means is that in order to get someone in the room, I need to guide a soldier one step at a time, and then seal off the room (he can leave, but not return).
  
• Mining (of all forms, I believe) dwarves would rather take a long path to approach a tile from another direction than the one they're currently facing it at, because they prefer north
  
  Spoiler (click to show/hide)

  TA: Yeah, it's nice that they can solve an arbitrary labyrinth of your own design, and they'll pick the best possible path, generally. There are some exceptions, like mining where they can mine from multiple sides, and don't try them all.

  
  I still think this is solvable by running the A* with the designated to-be-dug tile made a "pathable-to" tile (within the scope of this particular path-searching attempt only, obviously), and the destination, rather than (as I understand it) accepting its status as a barrier when looking to see which cell one (choosing the first of N,S,W,E,NW,NE,SW,SE, in that order?) can ultimately accesible to dig from and then running A* with that as the destination, even if it means circumnavigating the mountain to approach from the north rather than staying in the same place and digging out from the SE.

  One tweak to the existing pathing that I think would help the sanity of miners is some variation on pretending the square to be mined is pathable and or pathing backwards from the square to be mined to the square the dwarf is in. Depending on the specifics of Toady's implementation either might allow the dwarf to find the nearest face to mine from.
  
  AWDBall
  
• Toady's comments from an interview found at http://www.gamasutra.com/view/feature/3549/interview_the_making_of_dwarf_.php?page=8
  
  Spoiler (click to show/hide)

  Anyway, let's move on to what I expect was one of the biggest challenges in developing the game: the amazing pathfinding.
  
  TA: Is it amazing? It's creaky and slow.
  Advertisement
  
  Well it looks amazing from my end, since there's a metric ton of characters all doing it at once.
  
  TA: The dwarves themselves mostly move around with A*, with the regular old street-distance heuristic. The tricky part is that it can't really call A* if they don't know they can get there in advance, or it'll end up flooding the map and killing the processor.
  
  Sometimes in commercial projects the developers do a bit of cheating, and predefine travel paths.
  
  TA: Yeah, that's the hard part. We can't really predefine areas beyond very basic notions because fluids can zip by and block them off, or they can mine a floor out. All it does now, and this isn't ideal, is keep connected component numbers. So if a dwarf is standing in "2", they know they can't get to "3" and don't bother trying. However, they assume they can get to any other "2", and will A* those paths. There are still a few failures, but it's fixable.
  
  There's a price to pay for that though, on a few levels. First, it's a pain to maintain. If a fluid occupies a square, it has to update. If a fluid flows through a passageway and cuts it in half, it has to reindex one or both sides. There are other ways to think about handling it, like keeping track of some sort of rectangles or something, and pathing on those, but the memory cost is too great.
  
  The memory cost here is large, and it's also a speed burden. There are probably a ton of better ways to do it, it's just a very hard problem.
  
  And all of this taking place over potentially many Z-levels too.
  
  TA: In a 480x480xZ map. Or even a 768x768xZ at max settings.
  
  And there's another huge downside to it that I have to cope with, and that's the mode of travel. A dwarf walks; a dwarf does not fly. For a flying creature, the path components are meaningless. So flying creatures are much dumber than dwarves, and dwarves are already kinda dumb.
  
  I still stand by the adjective "amazing" though, based on how watching a dwarf make his away around the world, then suddenly disappear because he took an unforeseen shortcut over a hillside, is a cool experience.
  
  TA: Yeah, it's nice that they can solve an arbitrary labyrinth of your own design, and they'll pick the best possible path, generally. There are some exceptions, like mining where they can mine from multiple sides, and don't try them all.

Resources

• The A* search algorithm at wikipedia: http://en.wikipedia.org/wiki/A*_search_algorithm
• A comparison on A* pathfinding: http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Previous suggestions

• Connectivity map 06/04/09 by Fieari
  Summary
  
  Spoiler (click to show/hide)

  Basically just update the current connectivity maps to include not just the walking type, but also other types of movement
  Full post
  
  Spoiler (click to show/hide)

  As well all know, DF's connectivity map works great for walkin dwarves, but not so great for flying or amphibious creatures.  This is because of the Connectivity Map, which determines whether the A* pathfinding system should be run at all.  If the spot can't be walked to, the game assumes it can't be reached, even if it could be reached via flying.
  
  This problem gets worse the more movement types you have, such as tunneling, or climbing.  Because you'd not only have to make a connectivity map for each movement type, but also for each COMBINATION of movement types, which is the harsh part.
  
  I'm not sure if Toady has considered methods by which multiple movement types could be implemented, but here's one.  It would likely require a couple days of coding, and more days optimizing, but it's a method, and I'd like to see what people think.
  
  Assume we have 8 different movement types requiring continuous movement (thus, removing teleportation).  We don't have eight right now, but maybe one day.  Let's say Walking, Swimming, Magma Swimming, Flying, Climbing, Jumping, Tunneling, and Demolishing.  Eight is convenient because it's one byte.  We can add more bytes too, for example "Trap Avoid" or some such.
  
  Step one utilizes the current system for making connectivity types, except this time we do it 8 times, a linear increase in processor requirement, so we're pretty safe.  Each tile is thus flagged with a number like 10011100, which means that if you can walk, fly, climb(aka crawl), or jump, you can move through the square.
  
  Then, the game must find all adjacent numbers, that is, all adjacent tiles with 10011100, and mark that as one continuous region.  From this region, create a nodal graph of the map.  This must be done once every time the map changes-- otherwise, you just need to keep the same map.  Remember, this is a linear increase in processor time, so it's expandable.
  
  Now, for connectivity checking, first the game sees whether you are within the same exact region, just like now.  If not, however, it then checks to see if there is a path utilizing all your movement types.  If each character is assigned a byte determining how they can move... such as 11000001 (for a troll perhaps), just do a Logical AND with each node of the connectivity map, then use a flood fill technique to see if it is possible to get to point A to point B.  After that, A* to your heart's content.
  
  Here's an example.
  
  Aribtrary Map:
  
  01101100 10110011 11111110
  11010100 11100111 00110110
  00111011 10101010 01010101
  
  Our creature's movement: 01001000
  
  AND map:
  
  01001000 00000000 01001000
  01000000 01000000 00000000
  00001000 00001000 01000000
  
  Truth map:
  
  101
  110
  111
  
  And there's our connectivity map!
  
  EDIT: If this is too slow, you could even cache such a map for each movement type possessed by a creature on the map.
  
• A new approach to path finding (nice pun ) on 09/11/08 by catpaw
  Summary
  
  Spoiler (click to show/hide)

  Ant-like behaviour, where dwarves drop and follow pheremones
  Full post
  Spoiler (click to show/hide)

  Recently I had an idea about path finding I want to write down, before it gets ultimativly lost to my weak memory.
  
  Okay. pathfinding is currently the single most framerate eater in DF beside hugh liquids in flow. How does it work currently, a dwarf is at position A, and needs to go to position B. The whole universe halts, the dwarf gets a mental represenation of the whole universe, and knows the ultimately most effecitve way to go from A to B. I think this does not only eat a lot CPU, its also unrealistic a dwarf suddendly knows about a door being closed miles away.
  
  How could this alternatively work, without having dwarf run around like crazy lost roboters (like the old follow the left wall algorithmn that will get you out of almost every maze) ... Lets look how ants do it! They have no mental presentation of the whole world around them, yet their pathfinding works pretty well. They do it by dropping chemicals hints along the way for other ants. A ant going from the nest puts pretty weak signals on the floor, its  actually a dotted line. If it returns with food it will orient itself on its weak line and make a thick line over it for other ants as hints. They walk over as well making the line stronger..
  
  How could this work with dwarves without making hugh memory requirements. Say a dwarf only sees a cube of 10 tiles in each direction. If the target is within the cube it will plot a path directly to target using the old algorithmn as long the path does not exceed the cube borders. If there isn't a direct path, or the target is out of the cube, it will plot the path taking him closest to the target (and additional corrected by dwarfes "pheromones" explained in a second). At the border he will plot a new cube... and so on. Unless there are some evil dead ends this should get a dwarf to his target with quite less CPU.
  
  Now suppose a dwarf runs into a dead end. What does he do now? He drops a negative pheromone point. Like a dwarf repellant. So other dwarfes wont run into the same dead end.... So next time they plan the path in the 10 tile cube, they try to get as close as possilbe to the targer. However corrected by getting points that are further to dwarf repellant pheromones. If a dwarf makes a sucessfull path at the target he drops a positive pheronome point on the last cube he came from.. if the next dwarf gets close to a positive pheromone he drops one as well. So soon you willl have a decent path. With only a few memory bytes needed for the dwarf pheromone points.
  
  There is come complication of course, since dwarves have more tasks to do than ants going outside of the nest. So while a craftdwarfs shop at the end of a large tunnel could be a dead end for most paths, its actually the right way if you want to go to this shop. So as solution every building needed its own pheromones... as as far I recall almost every dwarf path will always go from or to a building or stockpile. It takes some memory, but when you do this with pheromone points that signal at a radius, its not so bad IMHO. You don't need a per tile pheromone signal like ants do. This sure would be a memory explosion.
  
  Also this can be optimized for when a dwarf has to go to a building with none pheromone points it will take a building near that target as reference, and orient itself on its path points. Also sometimes a dwarf should do a bit of variance on the path, so when sucessfulll he would find possible a shorter, making new signal pheromone points.
  
  Well would need quite some simulation experiments to see how well it works really. I know in reality with ants it *does* work....
  
  Just imagine for example a main route of the dwarves gets blocked, and all the dwarves stand running around in panic trying to find a new way
• Route caching on 02/12/08 by Ogantai
  Summary
  
  Spoiler (click to show/hide)

  When you make a path, save it, so that it can be used again later without calculating it again
  Full post
  
  Spoiler (click to show/hide)

  Consider the following:
  
  1 dwarf with Item Hauling enabled at point A.
  Pile of 10 objects to be stored at B.
  Stockpile at C.
  
  The dwarf with Store item in stockpile job starts out at location A, paths A->B, then B->C, then must recalculate routes C->B and B->C 9 more times to complete the hauling.
  
  Considering that A* is O(nⁿ) in a worst-case scenario, the less pathfinding DF has to do the better. Instead, why not have the dwarf cache the precalculated B->C route, then instead of pathfinding C->B just reverse the route to arrive where he started, cache that, then repeat B->C and C->B from cache until done? That reduces the number of graph searches that must be done from 20 from 2. Perhaps store the last p routes in cache, let all dwarves share a common cache, and have then test if their prospective routes share endpoints within s squares (probably 1-2) of routes already in the cache. That reduces a potentially cpu-intensive 500 square long path calculation from the the armor stockpile to the xX(Pigtail Sock)Xx that Urist dropped to a much simpler calculation from the precached route's endpoint at xX(Pigtail Left Glove)Xx to the square adjacent to it.
  
  Obviously the values of s and p will have to be tweaked (just let us set them in the init file) but this would really reduce the strain DF places on lower-end computers with high pop fortresses.
  

Current development

• I'm going to need some help here. I'm not exactly sure what's being done right now regarding pathfinding.
  Preferably from ThreeToe or, if he has time, Toady.

*MY* Personal Issues (excluding those already diagnosed by psychiatrists)

Spoiler (click to show/hide)

• Telepathy and near-omniscience of dwarves and creatures. Self explanatory, really, I would say. Every creature seems to know exactly where every other creature and item is.
• An extension of the above, but only partially related to pathfinding, is that job items, such as stones, are "marked" for a job telepathically, and never used for anything else or moved out of the way, if something else is to be built on that tile.

[Fieari]

The problems are well known (other than the up-down-up-down thing... I don't even think that's true-- A* doesn't have limitations that would cause that, and neither does the connectivity map).  Do you have solutions to suggest?

The near-omniscience issue is partially solved next version anyway, with some temporary FOW implemented (Command & Conquer style, not starcraft style)

[Kilo24]

With telepathy, I can't imagine how it would be done without individual line-of-sight calculations for each dwarf with regards to pathfinding.  Though it already does the job cancellation when they encounter a hostile, the pathfinding (I think) is a separate beast entirely and would have to repeat those calculations.  Even if that's not the case, we'd be in a worse situation as we'd need separate mental maps for each creature and have to deal with transferring them to each-other somehow unless every dwarf needs to check that the river is now indeed empty.

Doing a separate mental map for each side would be better, but it would be painful to get the invading goblins to assault the fortress effectively.  Of course, if they traded with or tortured trading partners of you, they might be able to discover the traders' map of your place.  And it would give them a plausible excuse for knowing that your fortress exists and how to get to it.  And it would allow for you having an actually secret door, as well (without using levers or locking it yourself).  Another learning aid could be thieves just shadowing your dwarves to map out the place.

[Grendus]

Removing omniscience from dwarves would spike the lag. I'd leave it for right now. I lag already.

[Granite26]

Thanks for the hard work, Infiltrator.  It will be useful to point people to this thread in the future.

Consider linking (at the tail end) some of the CS level user discussions.

[Impaler[WrG]]

I think omniscience can be split into two broad categories, Omniscience of 'People' and Omniscience of 'Things'.  The former is the ability to home-in on someone (like the Mayor) and is rarely used because their are so few pre-determined interactions.  People have made good recommendations on the use of offices (one party goes to the office and waits for the other to arrive) to eliminate this weirdness. 

The later type of Omniscience is further sub-divided into 'Path' Omniscience and 'Item' Omniscience both rather self explanatory.  A system of pre-caching paths and giving individual dwarves some references to those paths might be able to create a reasonable approximation of personal memory, dwarves would not immediately take the newest shortest path and would try (and fail) to use an old path that's been blocked just as they do now if the map changes after they have started traveling.  Omniscience of Items is perhapse the trickiest thing to resolve because we really at some level must retain it if we expect to keep the fortress clean.  What we really want is a strong preference for items that are logically 'known' to a dwarf.  The most logically known items should be in stockpiles so dwarves should go to stockpiles preferentially when they want something.  On top of that dwarves could have some 'mental notes' on items outside of stockpiles.  Say for example you've mined out a large room any dwarf passing through that room notices the stone and gets a "un-stockpiled stone at coordinates x,y,z", these notes don't have to be any more detailed then that and would of course expire after a while (or a failed attempt to collect the thing in question).  Dwarves would use these mental notes either when stockpiles are exhausted or when they do hauling tasks (trying to fill stockpiles).  Dwarves could even exchange these notes when they are socializing or working so information can spread in a realistic manor.

[Infiltrator]

The problems are well known (other than the up-down-up-down thing... I don't even think that's true-- A* doesn't have limitations that would cause that, and neither does the connectivity map).  Do you have solutions to suggest?

I know that the problems are well known by SOME people. However, not everybody knows the whole story, certainly not me. And yes, I do have a suggestion, but I would like to collect as much data as possible to avoid making a suggestion that has already been rejected, that would not work, or would cause problems.

The near-omniscience issue is partially solved next version anyway, with some temporary FOW implemented (Command & Conquer style, not starcraft style)

Like I said, I'd like to collect as much data as possible.

With telepathy, I can't imagine how it would be done without individual line-of-sight calculations for each dwarf with regards to pathfinding.  Though it already does the job cancellation when they encounter a hostile, the pathfinding (I think) is a separate beast entirely and would have to repeat those calculations.  Even if that's not the case, we'd be in a worse situation as we'd need separate mental maps for each creature and have to deal with transferring them to each-other somehow unless every dwarf needs to check that the river is now indeed empty.

Doing a separate mental map for each side would be better, but it would be painful to get the invading goblins to assault the fortress effectively.  Of course, if they traded with or tortured trading partners of you, they might be able to discover the traders' map of your place.  And it would give them a plausible excuse for knowing that your fortress exists and how to get to it.  And it would allow for you having an actually secret door, as well (without using levers or locking it yourself).  Another learning aid could be thieves just shadowing your dwarves to map out the place.

Removing omniscience from dwarves would spike the lag. I'd leave it for right now. I lag already.

I think omniscience can be split into two broad categories, Omniscience of 'People' and Omniscience of 'Things'.  The former is the ability to home-in on someone (like the Mayor) and is rarely used because their are so few pre-determined interactions.  People have made good recommendations on the use of offices (one party goes to the office and waits for the other to arrive) to eliminate this weirdness. 

The later type of Omniscience is further sub-divided into 'Path' Omniscience and 'Item' Omniscience both rather self explanatory.  A system of pre-caching paths and giving individual dwarves some references to those paths might be able to create a reasonable approximation of personal memory, dwarves would not immediately take the newest shortest path and would try (and fail) to use an old path that's been blocked just as they do now if the map changes after they have started traveling.  Omniscience of Items is perhapse the trickiest thing to resolve because we really at some level must retain it if we expect to keep the fortress clean.  What we really want is a strong preference for items that are logically 'known' to a dwarf.  The most logically known items should be in stockpiles so dwarves should go to stockpiles preferentially when they want something.  On top of that dwarves could have some 'mental notes' on items outside of stockpiles.  Say for example you've mined out a large room any dwarf passing through that room notices the stone and gets a "un-stockpiled stone at coordinates x,y,z", these notes don't have to be any more detailed then that and would of course expire after a while (or a failed attempt to collect the thing in question).  Dwarves would use these mental notes either when stockpiles are exhausted or when they do hauling tasks (trying to fill stockpiles).  Dwarves could even exchange these notes when they are socializing or working so information can spread in a realistic manor.

I do have some ideas for this, that may actually reduce lag, but like I said, I'd like to collect as much data as possible lest I propose a solution that would not work.

Thanks for the hard work, Infiltrator.  It will be useful to point people to this thread in the future.

Consider linking (at the tail end) some of the CS level user discussions.

It would help if other people also helped me to compile this. Feel free to provide links/data.


PS, wow, how did the forum find out that I'm an escaped lunatic? That is pretty impressive.

[Starver]

TA: Yeah, it's nice that they can solve an arbitrary labyrinth of your own design, and they'll pick the best possible path, generally. There are some exceptions, like mining where they can mine from multiple sides, and don't try them all.

I still think this is solvable by running the A* with the designated to-be-dug tile made a "pathable-to" tile (within the scope of this particular path-searching attempt only, obviously), and the destination, rather than (as I understand it) accepting its status as a barrier when looking to see which cell one (choosing the first of N,S,W,E,NW,NE,SW,SE, in that order?) can ultimately accesible to dig from and then running A* with that as the destination, even if it means circumnavigating the mountain to approach from the north rather than staying in the same place and digging out from the SE.


As an addition to the discussion, the assignment of a more logical sequence (or resequencing/reassignment, on-the-fly) of digging/channelling/ramping jobs is a different issue, so I won't mention it, but it is related to what I think is the clincher in the pure domain of pathing: i.e. not taking account of currently active (e.g. digger being on the way) channelling, other barrier-building activities or floodgate/bridge operation along the path of a routing actor, or responding in a reasonable manner when said change occurs.

The impression of omniscience falls down a bit when a pathing dwarf (or creature of some other kind[1]) who has happily worked out a route from where they are to a previously unknown area located in a part of the map they have never been before, gets almost all the way there and then finds the way blocked by a change in map dynamics that occured almost immediately after it set off, and then heads back almost all the way to the original starting location to take the alternate route that left unblocked (at the risk of having to repeat if that is blocked off, and not immediately retrying the original route if re-opened just as they turn back).  I have no problems with the omniscience (it is less processor intensive than working out the background data to an "Artificial Ignorance" pathing algorithm that requires per-actor knowledge to be gained before each can successfully traverse the most efficient path) but at the risk of needing the reloading of connectivity zones perhaps initiate a "recalculate route" event whenever gaps/barriers are opened/closed.

Perhaps stagger the recalculations task for each actor, after a short semi-random delay, after each path-change event that restricts travel.  With similar but slightly less recalculation events for potential route openings (shorter routes being missed having less repurcussions than original routes needing to be diverted).  This way it does not all occur on the same tick and (like the generation of an incoming caravan or newborn child entity causes a noticable pause in the game, for me, while it calculates all the new data) but buries itself in the background a little and facilitates a more natural reaction than everyone suddenly reversing direction like some kind of dwarven Village Of The Damned reacting to a world change...

(On the other hand, these 'flaws' in the system do allow various Dwarf Computing dynamic setups to work.


[1] Actually, while my dwarfs tend to be stupid about this, I've had invaders start to enter a relatively short tunnel to the Depot, and then activated the drawbrige (tens of tiles away, definitely not yet reached by the hostile force) designed to force them to reassess and take another branch of tunnel once they hit this barrier.  But instead of advancing and then reassessing, they've immediately turned round, headed back outside and wandered around to the alternate external entrance that is (I freely admit) actually the shortest path given their insufficiently progressed, but would not be if they hadn't responded until meeting the new obstruction.  I can only assuming that as an aimless rabble with a generic "search out targets" algorithm, that they reassess their path far more often than a dwarf who tends to attempt a single targetted task until it comes up against an obstacle or realises that the item has dissappeared (e.g. been channeled under).  Not noting any appreciable hit in speed, I'm wondering how much extra power they are taking on, or whether it's mitigated by being a general search for "closest thing of interest" rather than "shortest path to specific target", and thus hits 'maximum depth' far sooner.  Noting that I might be misconceiving some aspect of the scenario.

[Infiltrator]

The impression of omniscience falls down a bit when a pathing dwarf (or creature of some other kind[1]) who has happily worked out a route from where they are to a previously unknown area located in a part of the map they have never been before, gets almost all the way there and then finds the way blocked by a change in map dynamics that occured almost immediately after it set off, and then heads back almost all the way to the original starting location to take the alternate route that left unblocked (at the risk of having to repeat if that is blocked off, and not immediately retrying the original route if re-opened just as they turn back).  I have no problems with the omniscience (it is less processor intensive than working out the background data to an "Artificial Ignorance" pathing algorithm that requires per-actor knowledge to be gained before each can successfully traverse the most efficient path) but at the risk of needing the reloading of connectivity zones perhaps initiate a "recalculate route" event whenever gaps/barriers are opened/closed.

Perhaps stagger the recalculations task for each actor, after a short semi-random delay, after each path-change event that restricts travel.  With similar but slightly less recalculation events for potential route openings (shorter routes being missed having less repurcussions than original routes needing to be diverted).  This way it does not all occur on the same tick and (like the generation of an incoming caravan or newborn child entity causes a noticable pause in the game, for me, while it calculates all the new data) but buries itself in the background a little and facilitates a more natural reaction than everyone suddenly reversing direction like some kind of dwarven Village Of The Damned reacting to a world change...

(On the other hand, these 'flaws' in the system do allow various Dwarf Computing dynamic setups to work.

I specifically put that unless a "my personal issues" heading for a reason.
However, I do have some ideas about it, that, at least to me, in my head, seem reasonable.

[Starver]

I specifically put that unless a "my personal issues" heading for a reason.

Oops, I'd missed that particular spoiler-expansion section, after going down and reading (or at least skimming!) the whole lot.

Plus I appear to be typing far too much, today, when just meaning to type basic points/responses, but that's not an issue restricted to this thread/forum. 

[Fieari]

I take back my earlier complaints, I didn't realize you were organizing a central megathread for all pathfinding issues.  I approve.  Good organization too!

[Granite26]

I take back my earlier complaints, I didn't realize you were organizing a central megathread for all pathfinding issues.  I approve.  Good organization too!

You're fortunate I'm over my quota for snide for the week :-p

[Rowanas]

Yeah, but I'm not!

[Infiltrator]

I take back my earlier complaints, I didn't realize you were organizing a central megathread for all pathfinding issues.  I approve.  Good organization too!

You're fortunate I'm over my quota for snide for the week :-p

Already?! It's only Tuesday!

Yeah, but I'm not!

You're not fortunate?

I take back my earlier complaints, I didn't realize you were organizing a central megathread for all pathfinding issues.  I approve.  Good organization too!

I'm glad.

And thanks for all the nice comments, but what would be much appreciated is provision of data and/or links.
Like I said, I'm a newcomer, I don't remember that thread with a funny name from a year ago that had some intricate details that needs to be referenced here.

I specifically put that unless a "my personal issues" heading for a reason.

Oops, I'd missed that particular spoiler-expansion section, after going down and reading (or at least skimming!) the whole lot.

Plus I appear to be typing far too much, today, when just meaning to type basic points/responses, but that's not an issue restricted to this thread/forum. 

You may have, yes. I am reorganising it as I go, and I didn't have it inside a spoiler section earlier, so you may not have seen the title before reading it.

And for this thread, lots of typing is probably good.
If anything's too long, it can always be summarised. Expanding is a lot harder.

[awdball]

One tweak to the existing pathing that I think would help the sanity of miners is some variation on pretending the square to be mined is pathable and or pathing backwards from the square to be mined to the square the dwarf is in. Depending on the specifics of Toady's implementation either might allow the dwarf to find the nearest face to mine from.

AWDBall