Print

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

[Arphahat]

My mason decided he had to go down to the deepest level of the fortress to retrieve flint, even though there was some right next to the shop.  I built a hatch and marked it forbidden on the stairs, and he would walk to the stairs and grab a rock from as far away as he could.

This doesn't seem to happen all the time.  I noticed this happen on a task set in the job manager for a larger number of items, something like 19 doors.

[Jintor]

IIRC didn't Material behaviour used to be 'get the 'newest' possible material for job'?

I might be totally wrong though. > >

[Overdose]

I guess the "Nearest Item" thing doesn't count for Z levels distance, and the path needed to be taken to get to them. So if you have a stone sitting below your workshop on another Z level (or above) and another next to the workshop, they will think the one on the other Z level is closer, then walk down the hall, around the corner, out the entrance, through the woods, around the goblin siege, past the bronze colossus, make a left at the Carp filled river, take the stairs down, get the rock below the workshop, then make their way back.

The best way to get around this (to me), is to have a stockpile directly above/below the workshop, and to have the workshop near a main stairwell of sorts, so the trip downstairs isn't a long one.

[i2amroy]

I guess the "Nearest Item" thing doesn't count for Z levels distance, and the path needed to be taken to get to them. So if you have a stone sitting below your workshop on another Z level (or above) and another next to the workshop, they will think the one on the other Z level is closer, then walk down the hall, around the corner, out the entrance, through the woods, around the goblin siege, past the bronze colossus, make a left at the Carp filled river, take the stairs down, get the rock below the workshop, then make their way back.

The best way to get around this (to me), is to have a stockpile directly above/below the workshop, and to have the workshop near a main stairwell of sorts, so the trip downstairs isn't a long one.

Correct. Z-level distance just counts as one square for each level, regardless of the actual distance that is required to walk to it. This bug has been around for forever.

[Draco18s]

Correct. Z-level distance just counts as one square for each level, regardless of the actual distance that is required to walk to it. This bug has been around for forever.

Incorrect.  Each Z-level counts for 0 distance (at least, last I checked).  You can verify by building a Depot over (z-levels above) a workshop or stockpile with goods.

[Emperor Bob]

Correct. Z-level distance just counts as one square for each level, regardless of the actual distance that is required to walk to it. This bug has been around for forever.

Incorrect.  Each Z-level counts for 0 distance (at least, last I checked).  You can verify by building a Depot over (z-levels above) a workshop or stockpile with goods.

That's kind of strange, when you think about it: if Dwarves pathfind using A*, then it's likely that Toady has an easy way of calculating straight line distances between two objects, especially if coordinates are treated as a 3-d vector. Now using A* for every object needed by a dwarf would make the game slow to a crawl. But there is a simple way to stop what to me seems to be the biggest problem with the current behavior, that of dwarves being willing to walk enormous distances to a rock below them, passing right by a whole lot of much closer ones.
Instead of treating all the floors at the same time, start with the dwarf's current floor only, and find both A) the closest rock (or other needed object) and B) the closest stair or ramp. Then if A<B the dwarf goes after that rock, else if B<A, the old algorithm takes over. This isn't perfect, but it would at least guarantee that if you give your dwarf a stockpile closer to his shop than any stairs are, then he wouldn't walk 15 z-levels down to take rocks that lie right next to his shop. And it might even make material seeking faster, because 3/4 of the time you could entirely ignore other Z-levels (depending on your fortress design)

[Keldor]

Correct. Z-level distance just counts as one square for each level, regardless of the actual distance that is required to walk to it. This bug has been around for forever.

Incorrect.  Each Z-level counts for 0 distance (at least, last I checked).  You can verify by building a Depot over (z-levels above) a workshop or stockpile with goods.

That's kind of strange, when you think about it: if Dwarves pathfind using A*, then it's likely that Toady has an easy way of calculating straight line distances between two objects, especially if coordinates are treated as a 3-d vector. Now using A* for every object needed by a dwarf would make the game slow to a crawl. But there is a simple way to stop what to me seems to be the biggest problem with the current behavior, that of dwarves being willing to walk enormous distances to a rock below them, passing right by a whole lot of much closer ones.
Instead of treating all the floors at the same time, start with the dwarf's current floor only, and find both A) the closest rock (or other needed object) and B) the closest stair or ramp. Then if A<B the dwarf goes after that rock, else if B<A, the old algorithm takes over. This isn't perfect, but it would at least guarantee that if you give your dwarf a stockpile closer to his shop than any stairs are, then he wouldn't walk 15 z-levels down to take rocks that lie right next to his shop. And it might even make material seeking faster, because 3/4 of the time you could entirely ignore other Z-levels (depending on your fortress design)

I think the easiest way to prevent them from going after the stones on the bottom of the map would be to just add some bias into the distance estimate.  e.g. Estimated Distance = x+y+10*z

Then suppose you had a rock on the same Z level, and 17 units to the left and 33 units north, and a second rock 2 units east, 1 unit north, but 13 z levels below you.

With a basic unbiased distance check, the first rock would be 50 units away, and the second 15 units away, making the dwarf think that the one way down on the bottom z level is actually easier to reach, which it most likely isn't!

With the improved guess, the rock on the same level is still estimated to be 50 units distant, but the one on the bottom is now estimated to be 133 units away.  Now the dwarf will go for the one on the same level.

Naturally, the actual value used to bias the z axis should be tweaked to get it as close to optimal as possible - my 10x multiplier is just a number I pulled out of thin air

Another interesting thing is that although my estimate x+y+k*z doesn't take into account diagonal directions, it may actually be MORE representative of true distance this way, AND faster to compute!  This is because every fort I can think of tends to have north-south and east-west access routes far more than other directions.  I mean, how many of us build everything based off of diagonal tunnels?

[numerobis]

Now using A* for every object needed by a dwarf would make the game slow to a crawl.

Why the hypothetical?  That's the current state of affairs.  First the no-job dwarf finds a job off the work queue.  Next, if it needs an unspecified object, it finds an object, apparently ignoring pathing (my bet: it uses BFS over all tiles of any kind, excavated or not).  Next, it does A* to find the path to the object.

It's not clear to me it would be slower to use Dijkstra's algorithm to find the nearest object and the path to it in one go.  As a bonus, it would fix this nuisance that frequently gets reported. 

And if I could have a cake to go with my pony, the dwarf would even go so far as to use Dijkstra's to find the closest job (currently, dwarves sometimes take jobs on the other side of the map even though there's one next door).

[Draco18s]

Next, it does A*

use Dijkstra's algorithm

Dijkstra's algorithm is the special case of A* where h(x) = 0 for all x.

[numerobis]

Right, which makes it probably pretty easy to implement the one-pass solution that works well as opposed to the two-pass one that doesn't work as you'd expect.

[Starver]

I imagine, BTW, that someone's already mentioned the far-from-rare tendency for miners just about to complete a new through-route to finish digging out the penultimate block, target the next block along (accessible from both sides) but wander around to the other side to do it?  As if the route-finder is working not on "square to be dug out", but "square to dig out from" (which is often not the one they've just cleared, which would be an ideal spot to stand and dig from, but the long-time open space all the way around the other side).

I'm sure it's been mentioned, so sure that I'm kicking myself for being too lazy to search for its specific mention, but then there's probably something (maybe it seizes at the pre-existing access point before it quite realises that the new access point is now available, due to route-caching or slightly pre-emptive Just-In-Time job planning) that makes this an inevitable occurrence, every now and then.

[King Doom]

There is something up with the pathfinding for getting resources. I have smelters, a stockpile for flux only, then a passage, a stockpile for obsidian then on the other side of that my masons workshops, so everything is next to the stockpile I want it to use and as far as possible from the ones I don't. They tend to gather stuff from the obsidian stockpile and use that, but randomly they will run across the area to the flux stockpile and use that. The obsidian was mined after the flux, and I've been mining more on and off, so it isn't about using 'fresh' materials that I can see. Thinking about it, it might have something to do with where the dwarf was when he went from drinking/eating/whatever back to working in the masons workshop. If he was under or next to the flux store, it might have been closest. I'll need to check that.

[Proteus]

IIRC didn't Material behaviour used to be 'get the 'newest' possible material for job'?

I might be totally wrong though. > >

At least in some situatioms this seems to be the case.
My newest dug out room was my underground arboretum (well, mycoretum would be a better descrption ) and, when I then started to build another story for my keep (which is filled with stone stockpiles) my hauler dwarves preferred to refill the stockpiles with stones from my arboretum despite the fact that other stones were much nearer

[Derakon]

I imagine, BTW, that someone's already mentioned the far-from-rare tendency for miners just about to complete a new through-route to finish digging out the penultimate block, target the next block along (accessible from both sides) but wander around to the other side to do it?  As if the route-finder is working not on "square to be dug out", but "square to dig out from" (which is often not the one they've just cleared, which would be an ideal spot to stand and dig from, but the long-time open space all the way around the other side).

Yep, this has been brought up before, and you're right - they pathfind to squares that are adjacent to the square they need to mine. But you can't pathfind to multiple squares simultaneously, so they do them in a fixed sequence: left, right, up, down, then the diagonals. The first one that comes up as accessible, regardless of the distance, is used. The dwarf never even realizes that there's a shorter path right in front of him.

People have suggested solutions of varying degrees of complexity, but it's not been a priority for Toady.

As for the "biased" distance algorithm that Keldor suggested, I'm not a fan of any algorithm that makes assumptions about how people lay out their forts. I know that I've seen people talking about digging out forts consisting entirely of up/down staircases, for example, which would mean that the cost for moving across Z-levels really would be equal to the cost of moving horizontally.

The suggestion to calculate both distance to the closest object on the current Z-level, and distance to the closest staircase, seems like a good compromise, since it still works nearly as well on a map that has lots of staircases. There's one extra distance calculation, but that's all.

[Starver]

I imagine, BTW, that someone's already mentioned the far-from-rare tendency for miners just about to complete a new through-route to finish digging out the penultimate block, target the next block along (accessible from both sides) but wander around to the other side to do it?  As if the route-finder is working not on "square to be dug out", but "square to dig out from" (which is often not the one they've just cleared, which would be an ideal spot to stand and dig from, but the long-time open space all the way around the other side).

Yep, this has been brought up before, and you're right - they pathfind to squares that are adjacent to the square they need to mine. But you can't pathfind to multiple squares simultaneously, so they do them in a fixed sequence: left, right, up, down, then the diagonals. The first one that comes up as accessible, regardless of the distance, is used. The dwarf never even realizes that there's a shorter path right in front of him.

People have suggested solutions of varying degrees of complexity, but it's not been a priority for Toady.

Perfectly understandable (it not being a priority).

For the record, my solution to (to remove the need to pathfind to the multiple adjacents), is to treat the to-be-mined square as a valid destination, run a single pathfind and extract the penultimate spot as the work-from.

Don't know what language Toady works with, whether it's OOP or not, supports overloading of functions/procedures or how it might be tweaked, but maybe as little as adding an analogue to...

Code: [Select]

function pathFromNextto(from,to): pathorfail
  markAsOpen(to)
  fullPath = pathFromTo(from,to)
  if fullPath = fail
   return fail
  else
    markAsWall(to) /* if this wasn't done locally and needs resetting */
    return partialPath(fullPath,-1)
end pathFromNextto

...if you can't just add some kind of "finalDestinationIsValidAsWall" flag recognition in the current "pathFromTo()" function call along with whatever handles the "dwarfAllowedOutside" sort of thing which allows the final step to be taken without such a restraint.

Whatever the case, mining (and smoothing and... does anything else that get so affected?) can be redirected to use pathFromNextto instead of pathFromTo (or the version that's at home to the last step being a wall under those circumstances).


Again, I don't know the code.  It seems easy enough to make a minor modification to (or modified copy of) the pathing procedure.  Keeping it transparent to all other users of the procedure which don't require that little extra functionality and merrily use it as they always have.  (Also, some solutions work well with unknown future changes to the pathing in-line with the suggestions here and elsewhere at improving the A* over Z-level displacement, if it isn't too spaghettiised in the first place.)   But then I know that there's plenty of space between theory and practice in such cases...

Never mind workload.  I bet amateurs like me suggest pseudocode fragments all the time.


(While we're here, how does wall-building work?  That probably targets the exact spot (which is currently open) for a route from the material pick-up point and checks that there is an orthogonal (not diagonal) space next door (where the builder can move into after hauling the material there) as a pre-validator before even considering assigning that job and making a standard route.  But if this goes ahead and the worker arrives, could it then be made to bias towards making the builder move off to the point of entry (or an adjacent square of it, if the last move was diagonal) where this is possible, as this would seem to be more a sensible generalisation that would negate the need to build additional 'spoiler' walls to pre-deny orthogonal access on what might be the wrong side of this last block of wall, i.e. enclosing an area with no other egress.  Nah, too many ideas in one post.  Ignore me.  )