Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 5 6 [7] 8 9 10

Author Topic: Stacking and Hauling Improvements (optimization)  (Read 18773 times)

Silverionmox

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #90 on: March 01, 2011, 04:22:32 pm »

Saying "A gives to B" or "B takes from A" will have the same effect... You're just allowing two links instead of one. Multiple links would be useful though. For example, if you want to supply a carpenter, an ashery and a siege workshop with their own stockpiles from a central wood stockpile.
Logged
Dwarf Fortress cured my savescumming.

Draco18s

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #91 on: March 01, 2011, 04:39:05 pm »

Saying "A gives to B" or "B takes from A" will have the same effect... You're just allowing two links instead of one.

Precisely.
Logged

Sowelu

  • Bay Watcher
  • I am offishially a penguin.
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #92 on: March 01, 2011, 05:47:12 pm »

Personally, I think that a major hauling improvement could be gained by letting dwarves poach jobs from other dwarves.  Once you're picking up five objects in one go, you start running into situations like the way that dwarves mine.  "I'll mine out all but one tile of this room, and leave it for the other dwarf who's hustling over from across the map!"

Let dwarves keep track of estimated time remaining that it will take to complete a goal.  If another dwarf is close enough that they can complete it a lot faster, let them poach it.  Hauling, mining, anything.
Logged
Some things were made for one thing, for me / that one thing is the sea~
His servers are going to be powered by goat blood and moonlight.
Oh, a biomass/24 hour solar facility. How green!

Granite26

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #93 on: March 01, 2011, 05:49:55 pm »

Personally, I think that a major hauling improvement could be gained by letting dwarves poach jobs from other dwarves.  Once you're picking up five objects in one go, you start running into situations like the way that dwarves mine.  "I'll mine out all but one tile of this room, and leave it for the other dwarf who's hustling over from across the map!"

Let dwarves keep track of estimated time remaining that it will take to complete a goal.  If another dwarf is close enough that they can complete it a lot faster, let them poach it.  Hauling, mining, anything.

You'd have to handle the serial theft case too.

Sowelu

  • Bay Watcher
  • I am offishially a penguin.
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #94 on: March 01, 2011, 06:30:10 pm »

Personally, I think that a major hauling improvement could be gained by letting dwarves poach jobs from other dwarves.  Once you're picking up five objects in one go, you start running into situations like the way that dwarves mine.  "I'll mine out all but one tile of this room, and leave it for the other dwarf who's hustling over from across the map!"

Let dwarves keep track of estimated time remaining that it will take to complete a goal.  If another dwarf is close enough that they can complete it a lot faster, let them poach it.  Hauling, mining, anything.

You'd have to handle the serial theft case too.

Seems easy enough.  Only take the job if you are significantly closer (say, will complete it in 50% the time), and don't take a job that's already far enough in progress (already holding item to be hauled, already mining the square, etc).
Logged
Some things were made for one thing, for me / that one thing is the sea~
His servers are going to be powered by goat blood and moonlight.
Oh, a biomass/24 hour solar facility. How green!

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #95 on: March 01, 2011, 06:50:14 pm »

There is but it's hard to think of an efficient algorithm to solve a problem we don't understand.  If we accept that the only use of minecarts (And related lifts, etc.) is to move things from one or two specific locations or stockpiles, to a few other specific locations, and we think manual control is tolerable, then that sets some fairly easy limits on what the algorithm is actually expected to cope with.  In this case we don't really have to change the algorithm at all, we just have a minecart that create store jobs like a stockpile.

Well, if we don't understand it, it's time to think about it more until we do.   :P

There shouldn't be any more manual control than absolutely necessary.

OK, let's think logically about how a minecart should probably operate... Unless you want to have the carts pushed around manually waiting at one point or another, then what we need to do is have a way for dwarves to know when it is fine to use a cart as a stockpile, and what areas that cart has connections to when you want to use it as a bulk transport. 

Without having to make your dwarves do a really complicated pathfinding check to see when it is acceptable to try to use a minecart, the only thing I can think of is to make a minecart track create its own zone upon creation.  Presumably, this will be connected to every other piece of track, lest it be useless, so it basically forms a long, snaking zone throughout the areas you have built those tracks, connecting everything together. 

This minecart zone would spread some arbitrary (possibly player-togglable) number of tiles out from the tracks, and when a dwarf tries to take up a job involving hauling, it will check to see if the item to be hauled is within the zone of the tracks, and if the destination is within the zone of the tracks.  Pathfinding along tracks, barring some really kooky behavior on the part of the player, should be very easy, so you could probably do a count of how many tiles it takes to get from start to finish fairly fast, but you could have either a pathfinding check to see what a straight walk would be, anyway, to see how many more tiles one would have to travel by foot, and compare that against the minecart's pathing if you want to be really accurate and save as much dwarf travel time as possible.  (Again, this is a matter of CPU efficiency vs. Dwarf motion efficiency.)  This would have to include the time/tiles it takes a cart-hauling dwarf to actually move the cart into position.

Before using a minecart even makes sense, however, you need to have a set number of items in the area to even make it more useful than just hauling everything by hand. 

This is a possible calculation, of course, it's just a very wierd one, since it means that you have to get the dwarf to calculate how many trips it would take the dwarf back and forth without using the cart vs. how many trips it takes with a cart, plus the amount of time you have to spend getting the cart into position, plus the amount of time it takes to get the dwarf to the cart to start pushing it... and these might have to be done by quick-and-dirty calculations to save on pathfinding time, and prevent a dwarf from just sitting there and making a dozen pathfinding calculations and then winding up just doing the simple pick up the earrings all by himself since it was only very light items type of solution. 

The player might have some sort of ability to interfere with how the zones are set up - letting the player exclude some areas from being in zones, and include larger areas than the cart would normally allow to be in zones, if need be.  It might just be a separate part of the zones menu, or some special cart extension of the zones menu. 

Cart zone tiles would theoretically also be able to include areas that are still walls as part of the zones, so that the yet-to-be mined portions of the mines would already be included in the cart zone... but that causes problems because you don't want zones that are on other sides of walls to be included.  The other solution is to make any tile that is made into a floor with no blocking wall tile take another check when the pathfinding connectivity map is running to see if any adjacent tile is already in a minecart zone, and if so, check for cart tracks within a finite number of steps (flood style) to see if it should be connected to the minecart zone.  This would mean that a tile that was recently mined would declare itself part of a minecart zone, and then tell the stone hauling job of the stone the wall became to become a potential minecart hauling job if its destination is part of the minecart zone's sphere of influence, as well. 

... OK, that's all that a first-blush look at how to make a minecart path will tell me... so could someone blow this idea up for me so I can try to think of a better way to rebuild it?



Gah.. so many people posting in this thread...  7 replies... I need to stop reading books in the middle of posts.
Logged
Personally, I like [DF] because after climbing the damned learning cliff, I'm too elitist to consider not liking it.
"And no Frankenstein-esque body part stitching?"
"Not yet"

Improved Farming
Class Warfare

Granite26

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #96 on: March 01, 2011, 07:05:42 pm »

Does the 'take from stockpile' command wait until there's a full bin?  That could be a very low hanging fruit

Silverionmox

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #97 on: March 02, 2011, 01:45:24 pm »

Personally, I think that a major hauling improvement could be gained by letting dwarves poach jobs from other dwarves.  Once you're picking up five objects in one go, you start running into situations like the way that dwarves mine.  "I'll mine out all but one tile of this room, and leave it for the other dwarf who's hustling over from across the map!"

Let dwarves keep track of estimated time remaining that it will take to complete a goal.  If another dwarf is close enough that they can complete it a lot faster, let them poach it.  Hauling, mining, anything.
That would possibly involve a lot of calculations to see whether and if a suitable dwarf is close, and then if he is close enough.

I think grouping jobs would be very useful: you'd have some parameters in the init, or an options screen in-game, that determines the size of the job groupings (eg. 250, 50, 5 or 1 (= free-for-all, like it is now)) for each type of job. Instead of a single job, a group of jobs would be assigned to a dwarf. Another dwarf can take over when the first is tired. (That would also serve as a kind of priority system: if the group sizes are large, there will be fewer dwarves working on them, and they'll take longer to be completed, keeping your other dwarves unoccupied.) All in all, it would reduce job assignment inefficiency, preventing logical job groupings to be splintered and dwarves run over to mine just a single square (which will reduce pathfinding needs as well, if the jobs of a particular dwarf are grouped in one place). Jobs are already sequentially grouped in workshops, so it's not far-fetched to apply it to other jobs, like hauling, woodcutting, dumping, mining etc. that are typically generated in large quantities at once.

Continuing in that vein, one could also group dwarves in teams much like and assign the job groups to them. That would also work nicely with a future apprentice system (they are all working on the same job, but use the skill of the master, while still allowing the apprentices to gain experience). It would be somewhat similar to squads, which is good because you'll want to determine their uniform/job clothing as well. Leather aprons for my smiths, helmets for my miners!
Logged
Dwarf Fortress cured my savescumming.

Granite26

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #98 on: March 02, 2011, 04:21:40 pm »

Personally, I think that a major hauling improvement could be gained by letting dwarves poach jobs from other dwarves.  Once you're picking up five objects in one go, you start running into situations like the way that dwarves mine.  "I'll mine out all but one tile of this room, and leave it for the other dwarf who's hustling over from across the map!"

Let dwarves keep track of estimated time remaining that it will take to complete a goal.  If another dwarf is close enough that they can complete it a lot faster, let them poach it.  Hauling, mining, anything.

You'd have to handle the serial theft case too.

Seems easy enough.  Only take the job if you are significantly closer (say, will complete it in 50% the time), and don't take a job that's already far enough in progress (already holding item to be hauled, already mining the square, etc).

What I mean is, take a 3x3 room and (d) all the walls.   If you have 2 miners, one might take the other miners job all the way around the room.

Draco18s

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #99 on: March 02, 2011, 04:28:50 pm »

What I mean is, take a 3x3 room and (d) all the walls.   If you have 2 miners, one might take the other miners job all the way around the room.

Explain further.

1) Why would miner 1 steal a job prior to his own being completed.
2) Why would miner 1 steal a job prior to completing every other available job in said 3x3 room.

E.g. prioritize untaken jobs that are at the same (or equivalent) distance.
Logged

Granite26

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #100 on: March 02, 2011, 04:55:37 pm »

I didn't mean it wouldn't work, just that it was a wrinkle.  Wrinkles are expensive.

Mike Mayday

  • Bay Watcher
  • gfx whr
    • View Profile
    • Goblinart
Re: Stacking and Hauling Improvements (optimization)
« Reply #101 on: April 01, 2012, 01:21:48 pm »

I asked Draco to link the ESV item to this discussion, so let me also post a link the other thread with hauling+stockpile suggestions (just in case).
http://www.bay12forums.com/smf/index.php?topic=104479.0

zwei

  • Bay Watcher
  • [ECHO][MENDING]
    • View Profile
    • Fate of Heroes
Re: Stacking and Hauling Improvements (optimization)
« Reply #102 on: April 01, 2012, 01:42:23 pm »

I think "naive" implementation would be rather painless to implement and very effective.

Naive is that while dwarf is carrying item to stockpile he checks whether each tile he steps on contains item that can be also put to same stockpile and is not tasked already, we will add it to carried bundle.

No extra pathing needed, only one check per item on each tile of path. Should be effective for batlefield clean up, field harvesting and gathering ores/stones. Anywhere where dwarf is likely to walk over objects of same type.

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #103 on: April 01, 2012, 03:01:05 pm »

I just modified a post from the first page of this discussion, since I have been thinking more and more about abstraction lately.

It's from the post on how to handle the data of items put into stacks:

Edit from a long time later:
Actually, you could track item wear or damage more abstractly, if you don't mind a loss of granularity over some types of items.  (If you are stacking them, anyway, then you shouldn't be all that concerned with granular details.)

Simply track an abstract "Average" wear or damage number, and then a "Standard Deviation" number, and bell-curve the results abstractly.  Hence, throwing a badly damaged item into a stack of reasonably well-maintained items will result in not just a drop in the average wear, but also a spike in the standard deviation, so the bell-curve will be spread out, and abstractly include plenty of low-wear items as well as a few outlier damaged items.

Dwarves could simply draw at random or puposefully pick the most damaged or most repaired ones as specified (so that if they are looking for socks in a sock pile, they would probably want to pick the least threadbare socks to own for themselves).

This would mean that a stack of socks would have its "threadbareness" data blurred between each other, but still keep some granularity as to whether or not some socks are more worn down than others.

It wouldn't be useful in terms of items where you absolutely want to keep track of how good of a repair an item is, like a named sword with a hundred kills, but those sorts of things are the types of things that probably just shouldn't stack at all, anyway.

For iron bolts or pig tail fiber socks, which don't need that sort of tracking data, it's good enough.
Logged
Personally, I like [DF] because after climbing the damned learning cliff, I'm too elitist to consider not liking it.
"And no Frankenstein-esque body part stitching?"
"Not yet"

Improved Farming
Class Warfare

Tirunus

  • Bay Watcher
  • Something witty here
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #104 on: April 01, 2012, 03:31:25 pm »

Tldr I am a rageing Sissy and want things to not be horribly inefficient.
Logged
My personal text is in itself a attempt to be witty, making fun of the fact that peoples personal text usually are trying to make a witty one liner. Possibly a reference to the game or just a generally humorous. You may also find that this signature is not used to regurgitate someone else's joke in a attempt to immortalize that they felt but instead have just joined a crowd of people who are to hung onto past feeling, but is used to better explain the personal text.
Pages: 1 ... 5 6 [7] 8 9 10