Print

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

[Elvenshae]

So, deadheading (also, sometimes, "repositioning").
 
In the transportation biz, it means the movement of people and equipment without performing useful tasks in order to perform a useful task.  Or, as an example, you're a truck driver and pick up a load in Boston and bring it down to DC.  Then, you drive out to West Virginia to pick up another load to bring to Buffalo.  The DC-to-West-Virginia leg of your trip is a deadhead, or a repositioning trip, as you will it.
 
Basically, it's movement that doesn't actually accomplish anything on its own other than to get you where you need to go to do your job.
 
DF is really bad at optimizing this (or, perhaps in better tems, it doesn't seem to care that much).  For instance, a dwarf will pick up a single stone craft at the workshop, walk it 5 steps over to the Finished Goods stockpile, and drop it off.  He will then walk 100 steps to the complete opposite side of the map, pick up a piece of ore, and carry it 20 steps to the ore stockpile.  He'll then walk 90 steps back to the craftsdwarfshop and move another single craft.  When you lather, rinse, and repeat this over the entirety of your fort, you end up with a large percentage of haulers spending a ridiculously large percentage of their time deadheading.  Ironically, the more optimized your input / output stockpile and workshop placement is, the greater percentage of the haulers' time is spent in deadheading.
 
Basically, you end up with forts thrashing.
 
Has Toady given any thought to ways to reduce the amount of deadheading?  Alternatively, has Toady outlined the manner in which dwarfs select their next task?  Obviously, workshop-based tasks get done with little-to-no deadheading (a dwarf will pick up a stone, make crafts, and upon completion largely immediately go and get the next stone, indicating that there seems to be at least some form of "Does my workshop have another task for me?" logic involved in the process).  It seems, then, that hauling tasks are done in a much more random fashion: possibly, hauling tasks are assigned in the order that they are generated, and the dwarf just picks the next one off the list.
 
Even a simple weighting towards a task which starts close to where the hauler has ended his last task (i.e., "What's the nearest hauling task to where I am now?") would reduce deadheading by quite a bit, allowing a smaller force of haulers to be more productive.
 
The burrows arc may do some work to alleviate this - a hauler will only haul intra-burrow, and the burrow only has a crafts workshop and a crafts finished goods pile, so the hauler will spend most of his time walking between the two - but it will likely have no effect on the inter-burrow haulers, who haul 1 object between burrows A and B, then run off across the fort to burrow Z to carry something to Q, before returning to A.
 
Tangentially, this also relates to items which are claimed for a task and then are released when that task is interrupted.  I've seen this most often with cage traps and smithing tasks.  A mechanic, for instance, will pick up a cage in the Animals stockpile, and carry it most of the way to the unloaded cage trap.  At this point, he'll get hungry, or thirsty, or decide to go on break, etc., and will drop the cage.  Inevitably, a dwarf will then walk out, pick up the cage, and bring it back to the stockpile, requiring that the mechanic, once he returns to duty, pick up the heavy cage and walk it all the way back out again.  Similarly, a dwarf will start working on, say, a golden statue, and will bring three bars to the smithy.  Before finishing the task, he'll get interrupted, and three haulers will step over to bring the bars back to the bar stockpile, requiring that the smith pick them up and bring them back to the smithy when he restarts his task, resulting in wasted effort on everyone's part.
 
Anything that can be done to alleviate this - perhaps, even though the "Load Cage Trap" task is interrupted, the cage itself is still associated with the task and is unavailable for general hauling - would be welcome.

[Granite26]

I also see this a lot with the mining... One miner will mine out a large area, leaving nothing but two blinking squares for the two miners following behind.  By the time they get there and mine out those two spaces, the fast miner has already dug out most of the next room, often across the map.  The slow miners will tag two squares in that room and walk over there.

In short some sort of 'I'm standing right here, I'm going to claim the job from you' kind of AI would be helpful.

[Fieari]

It may be tricky to reduce deadheading.  Toady has clarified that Dwarves don't choose their tasks, tasks choose dwarves.  If dwarves DID choose their tasks, it would simply be a matter of making the dwarves choose better.  But since it's the task that does the selecting, the issue gets a lot more complicated.

[Cthulhu]

Well maybe someone should punch the task in the face, and tell it to stop being so stupid.

[Drakale]

Remind me of an episode of futurama where a slave mine is reorganised to be so efficient that a single australian man do all the work :p He is not very happy about it if i recall...

[Mephansteras]

It may be tricky to reduce deadheading.  Toady has clarified that Dwarves don't choose their tasks, tasks choose dwarves.  If dwarves DID choose their tasks, it would simply be a matter of making the dwarves choose better.  But since it's the task that does the selecting, the issue gets a lot more complicated.

That does make it harder. Although if tasks don't already grab the closest acceptable dwarf, maybe they should? Hmmm...what about adding in a buffer for dwarf task assignments, so that a given dwarf can be qued up to do lots of tasks from a given area? Say, a workshop could find the closest dwarf with the appropriate job set and assign the top 5 jobs to that one dwarf. If that dwarf abandons the job to go eat or whatever, it could grab the next dwarf and queue them up? Might be a problem for hauling, though, where you'd rather have 20 nearby dwarves hauling stone then one poor dwarf set to run back and forth 20 times.

I wonder how hard it would be for Toady to redo that so it's the Dwarves who chose their tasks? I think that'll be necessary for the various Dwarf job prioritization schemes to work.

[Veroule]

If my analysis of the behavior and all the information Toady has been willing to reveil is combined correctly then the actually procedure looks something like this.

Code: [Select]

for each job in job list
 set best distance=really big number
 set selected dwarf=0
 for each idle dwarf
  if dwarf has needed labor
   calculate distance to dwarf
   if calculated distance <= best distance
    set best distance=calculated distance
    set selected dwarf=current dwarf
if selected dwarf not 0 then tag he's it (see the notes)The notes on when a dwarf gets a job are dependent on the job. For workshop jobs the next step is that the dwarf chooses an appropiate material and finds the closest to where he currently is.  For jobs produced through a designation there are zones that are worked, such that the top left is first, bottom left a bit later, top just off left, through to bottom right.

There is the further behavior for designation and workshop jobs that has the dwarf check at completetion for something else to do there.  Perhaps just extending that sort of check to stockpile jobs would be enough to reduce how often we notice these things.  The extension should be specific to the stockpile that an item was just delivered to, and the dwarf would look to take another job pending to that specific stockpile.

[Erk]

A small and micromanagy stopgap has occured to me:

Make stockpile AI handle tasks more like workshops. Dwarves taking jobs from one stockpile will keep taking jobs from that pile until there are none left. However, unlike a workshop, multiple dwarves can take tasks from one pile.

Under Stockpile Settings, allow the stockpile Profile to be set, so that 1) the number of dwarves working at the stockpile at once can be capped, and 2) the specific dwarves allowed to work at the stockpile can be set, so that Urist SeedHauler can be denied working at any stockpile but the one seed stockpile you want her to keep filling. It would be nice if you could hit a special toggle to enable a dwarf at that stockpile and simultaneously block them from all others...

with 2) you'd want to make it so that there were a few settings actually, more than a workshop.
-set a certain number of dwarves to work exclusively at this stockpile, no other, but other dwarves can still take jobs from the stockpile as well (so it has dedicated labour but can also take volunteers)
-set a certain number of dwarves to be the only workers at the stockpile (like a workshop does)

or both: a certain selection of dwarves are the only workers at the stockpile, and they will not work on any other stockpile (in other stockpile labour lists their names are specially marked, and either cannot be selected or their exclusivity will be removed if you select them; they should remain enabled at the stockpile they were on before of course, just no logner exclusive.) -- or maybe they could be ecxlusive at multiple stockpiles, they just wouldn't take jobs from stockpiles they were not designated labourers for.

It's micromanagy but it allows for extremely efficient labour force division.

[Draco18s]

Wow, I like that Erk.

[Erk]

Yeah, the more I think about it the more I do too

of course, exclusive stockpilericity would only affect hauling. Urist Seedhauler might be exclusive to the seed stockpile, but she would still be able to take jobs at any workshop she liked if she had crafting enabled.

[Elvenshae]

You're right, Erk, that's *very* micromanagery.
 
The problem with that is that stockpiles are pretty okay when you've got a small fortress; it's the larger fortresses that have significant issues with deadheading, which is where micromanagment is the worst.
 
On the other hand, it certainly has the added attraction of being workable - presumably with minor changes, especially when compared to the "jobs choose dwarfs" method that appears to be the current standard. 

[Corak]

Heavy on the micromanaging, as everyone is saying, but I think I like the first idea the best... that dwarves will continue drawing jobs from a given stockpile while they remain. Really this could apply to a large number of things (like mining).

I think this alone would greatly increase Dwarven efficiency, just by keeping them in one place. I hate when I have several mining jobs designated and they run back and forth between them across the map.

[korora]

I like the stockpile idea, just for micromanagement potential-- I like the idea of highly specialized haulers.  However, I think a better long-term solution is to rework things so dwarves choose jobs.  If Veroule's speculated psuedocode is correct, then it's pretty much the same time complexity either way, so it shouldn't be a processing hit.  Has Toady stated a reason why jobs choose dwarves and not vice versa?

[Sean Mirrsen]

I suspect because it's usually faster for a given job to cycle through available dwarves than for a given dwarf to cycle through available jobs - while dwarves usually max out at 200, even a medium sized fort can have thousands of rocks and various items for hauling, chopping, mining, crafting, etc,etc. I'm probably not entirely correct, but it's plausible.

[Granite26]

If you keep track of all the jobs in a couple of queued lists, you shouldn't need to process them all every time.  Job = Priority * Distance * I have that task, start at the top of the priority list, and grab the first job you can do.  At that point you have a min priority * distance,  At some point, the priorities will get low enough that even a job on the square you're standing on wouldn't be higher priority, so it can stop looking.

Hashing could be even more fun, but implementation details aren't me