Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
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.
TagsIntentional/Expected?, pathfinding, pathing, tasks
Attached Files

- Relationships
related to 0004367resolvedToady One Animals all try to graze from pasture's top left corner, starvation ensues 
parent of 0002901resolvedFootkerchief Large floors use stone in inefficient order 
has duplicate 0002608resolvedLogical2u Designate cut trees/plants/etc,, always starting from northwest corner 
has duplicate 0004000resolvedLogical2u Dwarf Digging Priority ignores depth 
has duplicate 0004715resolvedLogical2u Miners sometimes prefers to dig from a far side 
has duplicate 0005573resolvedLogical2u When several are available, dwarves don't always choose the closest possible job tile 

-  Notes
(0004754)
ronarscorruption (reporter)
2010-04-23 12:29

damn typo, I meant "one X space further west".
(0004807)
Tyg13 (reporter)
2010-04-23 18:03

This is how it's always been, it's just how dwarves prioritize pathfinding.
(0009874)
Logical2u (manager)
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 (reporter)
2010-07-10 08:15

Can you reproduce this with version 31.08?
(0009885)
hyndis (reporter)
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 (reporter)
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 (reporter)
2010-07-10 12:47

I agree that its counterintuitive, but its going to require the pathing rewrite to change this.
(0009888)
Kumquat (reporter)
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 (reporter)
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 (reporter)
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 (reporter)
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 (reporter)
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 (reporter)
2011-06-28 09:40

So a year later, any update on fixing the Z depth issue?
(0021808)
cswiger (reporter)
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 (reporter)
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.

- Issue History
Date Modified Username Field Change
2010-04-23 12:27 ronarscorruption New Issue
2010-04-23 12:29 ronarscorruption Note Added: 0004754
2010-04-23 12:53 Footkerchief Description Updated View Revisions
2010-04-23 18:03 Tyg13 Note Added: 0004807
2010-04-23 18:03 Tyg13 Tag Attached: pathfinding
2010-04-24 00:15 Khym Chanur Issue Monitored: Khym Chanur
2010-07-10 06:48 Logical2u Note Added: 0009874
2010-07-10 06:48 Logical2u Description Updated View Revisions
2010-07-10 06:48 Logical2u Relationship added has duplicate 0002608
2010-07-10 08:15 TomiTapio Note Added: 0009882
2010-07-10 08:15 TomiTapio Tag Attached: tasks
2010-07-10 08:16 TomiTapio Tag Attached: pathing
2010-07-10 09:52 hyndis Note Added: 0009885
2010-07-10 12:17 ChickenLips Note Added: 0009886
2010-07-10 12:47 smjjames Note Added: 0009887
2010-07-10 15:03 Kumquat Note Added: 0009888
2010-07-10 15:26 oliver Note Added: 0009890
2010-07-10 15:33 oliver Issue Monitored: oliver
2010-07-10 23:12 oliver Note Edited: 0009890 View Revisions
2010-07-15 14:49 kwieland Note Added: 0010374
2010-07-15 14:49 kwieland Issue Monitored: kwieland
2010-07-15 15:41 Footkerchief Tag Attached: Intentional/Expected?
2010-07-30 16:35 Logical2u Relationship added parent of 0002901
2011-02-17 10:59 Logical2u Relationship added has duplicate 0004000
2011-02-17 11:09 idgarad Note Added: 0015195
2011-06-24 03:45 JCU Note Added: 0018030
2011-06-24 05:47 Logical2u Relationship added has duplicate 0004715
2011-06-28 09:40 idgarad Note Added: 0018063
2011-06-28 09:40 idgarad Issue Monitored: idgarad
2012-03-07 14:25 Logical2u Relationship added has duplicate 0005573
2012-03-07 14:25 Logical2u Issue Monitored: Edrin
2012-03-27 03:57 Steb Issue Monitored: Steb
2012-03-27 20:01 cswiger Note Added: 0021808
2012-03-27 21:04 arclance Issue Monitored: arclance
2012-03-27 22:16 krenshala Note Added: 0021809
2012-06-19 04:18 Steb Issue End Monitor: Steb
2014-01-21 18:04 Footkerchief Relationship added related to 0004367


Copyright © 2000 - 2010 MantisBT Group
Powered by Mantis Bugtracker