Dwarf Fortress Bug Tracker - Dwarf Fortress
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0001463Dwarf FortressPathfindingpublic2010-04-23 12:272014-01-21 18:04
Reporterronarscorruption 
Assigned To 
PrioritynormalSeverityminorReproducibilityalways
StatusnewResolutionopen 
PlatformOSOS Version
Product Version0.31.03 
Target VersionFixed in Version 
Summary0001463: Dwarves prioritize tasks oddly
DescriptionI've been watching dwarf behavior, and it's started to annoy me, so I'm reporting it as a bug, because it's bug-like.

Apparently, dwarves love the west. Why? No idea, but given two jobs of all other factors equal, I see dwarves always start with the job in the western-most location, be it mining, hauling, masonry...

Not so much of an issue on it;s own, but the problem is introduced with different Z-levels.

If a dwarf is free, they would rather run a dozen Z levels, and a thousand steps back and forth to a staircase to complete a job one X space further west. Inefficency at it's worst when you're trying to manage medium sized jobs across two or more levels at once. For instance, when mining. Same issue with Y coordinates. Z space, which should be prioritized first, is prioritized last.
Steps To ReproduceDig down several Z-levels to a space with solid stone. Dig a triangular space, then select one tile along the edge of each space.

Then, set any space near the dwarf, then the eastern point of the triangle. The dwarf will bypass the nearby space (so long as it's less west-ward) to go down howevermany levels and dig out triangle.
Additional Information
TagsIntentional/Expected?, pathfinding, pathing, tasks
Relationships
related to 0004367resolved Toady One Animals all try to graze from pasture's top left corner, starvation ensues 
parent of 0002901resolved Footkerchief Large floors use stone in inefficient order 
has duplicate 0002608resolved Logical2u Designate cut trees/plants/etc,, always starting from northwest corner 
has duplicate 0004000resolved Logical2u Dwarf Digging Priority ignores depth 
has duplicate 0004715resolved Logical2u Miners sometimes prefers to dig from a far side 
has duplicate 0005573resolved Logical2u When several are available, dwarves don't always choose the closest possible job tile 
Attached Files
Issue History
Date ModifiedUsernameFieldChange
2010-04-23 12:27ronarscorruptionNew Issue
2010-04-23 12:29ronarscorruptionNote Added: 0004754
2010-04-23 12:53FootkerchiefDescription Updatedbug_revision_view_page.php?rev_id=1637#r1637
2010-04-23 18:03Tyg13Note Added: 0004807
2010-04-23 18:03Tyg13Tag Attached: pathfinding
2010-04-24 00:15Khym ChanurIssue Monitored: Khym Chanur
2010-07-10 06:48Logical2uNote Added: 0009874
2010-07-10 06:48Logical2uDescription Updatedbug_revision_view_page.php?rev_id=3809#r3809
2010-07-10 06:48Logical2uRelationship addedhas duplicate 0002608
2010-07-10 08:15TomiTapioNote Added: 0009882
2010-07-10 08:15TomiTapioTag Attached: tasks
2010-07-10 08:16TomiTapioTag Attached: pathing
2010-07-10 09:52hyndisNote Added: 0009885
2010-07-10 12:17ChickenLipsNote Added: 0009886
2010-07-10 12:47smjjamesNote Added: 0009887
2010-07-10 15:03KumquatNote Added: 0009888
2010-07-10 15:26oliverNote Added: 0009890
2010-07-10 15:33oliverIssue Monitored: oliver
2010-07-10 23:12oliverNote Edited: 0009890bug_revision_view_page.php?bugnote_id=0009890#r3815
2010-07-15 14:49kwielandNote Added: 0010374
2010-07-15 14:49kwielandIssue Monitored: kwieland
2010-07-15 15:41FootkerchiefTag Attached: Intentional/Expected?
2010-07-30 16:35Logical2uRelationship addedparent of 0002901
2011-02-17 10:59Logical2uRelationship addedhas duplicate 0004000
2011-02-17 11:09idgaradNote Added: 0015195
2011-06-24 03:45JCUNote Added: 0018030
2011-06-24 05:47Logical2uRelationship addedhas duplicate 0004715
2011-06-28 09:40idgaradNote Added: 0018063
2011-06-28 09:40idgaradIssue Monitored: idgarad
2012-03-07 14:25Logical2uRelationship addedhas duplicate 0005573
2012-03-07 14:25Logical2uIssue Monitored: Edrin
2012-03-27 03:57StebIssue Monitored: Steb
2012-03-27 20:01cswigerNote Added: 0021808
2012-03-27 21:04arclanceIssue Monitored: arclance
2012-03-27 22:16krenshalaNote Added: 0021809
2012-06-19 04:18StebIssue End Monitor: Steb
2014-01-21 18:04FootkerchiefRelationship addedrelated to 0004367

Notes
(0004754)
ronarscorruption   
2010-04-23 12:29   
damn typo, I meant "one X space further west".
(0004807)
Tyg13   
2010-04-23 18:03   
This is how it's always been, it's just how dwarves prioritize pathfinding.
(0009874)
Logical2u   
2010-07-10 06:48   
I noticed in your description you said they start at the eastern location, but it seems like you mean Western, so I changed that.
(0009882)
TomiTapio   
2010-07-10 08:15   
Can you reproduce this with version 31.08?
(0009885)
hyndis   
2010-07-10 09:52   
Dwarves have always preferred to dig from the west.

Same thing with jobs. If you have many workshops and queue up a bunch of tasks from the job manager, the tasks will be assigned preferentially from the west. You can actually use this to your advantage. For example, I have training workshops that work like classrooms. They're on the eastern side of the map. Only if the workshops are idle do dwarves train.

With constructions they prefer the most recent construction over older ones. This means if you keep on laying out more and more walls or floors to be constructed it may take years for the first constructions to be completed, as dwarves will continue to work on the most recently designated constructions.
(0009886)
ChickenLips   
2010-07-10 12:17   
I understand the issue of tradition and it being how it has been, but I have to note that, from the perspective of someone coming new to the game as well, it is rather frustrating and counterintuitive to watch your dorfs do the behavior described.
(0009887)
smjjames   
2010-07-10 12:47   
I agree that its counterintuitive, but its going to require the pathing rewrite to change this.
(0009888)
Kumquat   
2010-07-10 15:03   
Not as much, really, only in respect of mining.

The mining picks out squares to mine in somewhat random manner, but it checks the adjacent squares for accessibility in a specific order. However since there usually are not really that many mining jobs happening all the time, the extra pathing cost would be negligible.

There could be also an 'see if there is an adjacent square I can mine next' mini-behavior for the miner to reduce pathing overall, but I don't know if the job system can handle things like that.
(0009890)
oliver   
2010-07-10 15:26   
(edited on: 2010-07-10 23:12)
I've noticed that mining digs out in 16x16 blocks preferentially, preferring to start in the most northwest block first, in north-south west-east order. i.e. if you have 9 16x16 blocks making up one world tile laid out like so:

ABC
DEF
GHI

Then they will be mined in the order ADGBEHCFI.

Within each individual block, the same sort of order is used.

You can see this very clearly by embarking on a flat area, then designating a large area for channeling.

A pathological case is if you have two long narrow east-west channels that are widely spaced in the north-south direction. Your miners will alternate between the two channels, digging 16 tiles then running to the other end of the map. (In the example above, the channels would run through ABC and GHI respectively).

This is very noticeable when digging a square moat!
(0010374)
kwieland   
2010-07-15 14:49   
This is also used for cutting down trees and harvesting plants. The other thing that can play a role is the different zones. I have seen (using your example above) a miner mine ADBECFGHI. I think the GHI is in a different zone. I remember Toady mentioning something about zones before.

A simple solution would be for the mining pathing to see if you can reach the designated square without moving. should save the "long walk around", but it wouldn't save the square moat problem.

The other digging issue I've seen is in channeling. say you have a 1 tile wide swath you are channeling.

JKLMNOPQRS

the miner will stand on K, mine J (this is correct)
Next (maybe thinks someone is standing on K?) stand on M and mine L.
Finally, stand on K and mine K which makes him fall and dazes him temporarily.

I don't remember what happens vertically.
(0015195)
idgarad   
2011-02-17 11:09   
This is minor in the fact that if we are trying to queue up (for instance using quickfort) a fortress it would be nice that the dwarves first complete the digging on the current level before going down.

Programatically it looks like they are running through a nested loop where it goes

for each y
  for each x
   for each z


to an extent. Where as doing
for each z
 for each x
  for each y

you resolve the cave in issue (simplification). Altering this may also resolved 3x3 stairwells which allow each level to be complete before descending the next level.

I never actually noticed this until .19 since I A: started building moats and B: starting using quickfort for build macros.

If the upper left corner is 0,0 then the whole West to East makes sense in the looping (build order weights aside.) It's frustrating when you want to dig a 2x2 or greater shaft or 2+ Z level deep moats as they also seem to dig down then back up when you stack Channels resulting in consistent cave-ins.

When coupled with build order you consistently end up with cave-ins when pre-designating multiple z-level channels.
(0018030)
JCU   
2011-06-24 03:45   
0.31.25 - same behaviour.

When dwarves are chopping trees within a large area, woodcutters are constantly moving vertically (in terms of screen, not z-levels). They ignore a tree within 3-5 tiles, preferring another one at opposing side of map, which sometimes takes about 90% (or more!) of their work time.

I think, there must be a search for a work on the same plane within something about 10 tiles away.
(0018063)
idgarad   
2011-06-28 09:40   
So a year later, any update on fixing the Z depth issue?
(0021808)
cswiger   
2012-03-27 20:01   
I was going to file a duplicate of this issue.

Clearly, if the unit can simply repeat the dig command against an adjacent square without moving, that avoids needing to do any pathfinding. For that matter, if a miner is next to a square to be dug, but some other miner has decided to do that job and is nowhere nearby, it would be better if the miner right there can decide to "take over" the job, and release the miner which is journeying from far away to take on some other task.

For the other aspect, I agree that jobs should be run against the highest Z-level until completion, before the jobs from a lower Z-level are allowed to run.
(0021809)
krenshala   
2012-03-27 22:16   
in my experience, the miners prefer to work from the bottom up, then from west to east, then from north to south. this results in them working the lowest, northernmost, westernmost tile first. this produces the vertical travel JCU notes, as they work north-south, moving slowly east, starting at the lowest level possible.

the part i'd like to see 'fixed' is the dwarves preferring to select a tile or object one z-level down over an object 2 tiles horizontally, when the actual path they take is 30 tiles over to the stairs/ramp down, 30 tiles back, pick up the object/dig the tile/what have you, then select the object 1 z-level up and repeat the process. very inefficient.