Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 2 [3] 4 5 ... 10

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

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #30 on: February 27, 2011, 11:20:25 am »

OK, I can see that...

That's applying the same code to other tasks that have similar requirements, which can makes sense, provided the task is indeed similar.  A job from a furnace that requires coke and flux and iron to make some pig iron is something that can use the same code as what we are talking about, although you would have to do something like search for the coke first, then find the absolute nearest flux and absolute nearest iron from both the coke and flux items, and do that dirty salesman calculation to find the low-pathfinding quickest way to collect all three items and bring them to the forge in one trip.

You can just hold off on setting which stones are tasked for being built into a wall until a dwarf actually starts the decision tree to pick up stones to bring them to the wall.  Of course a "10 granite stones will be needed for this task, and there are only 15 granite stones are in the fort, so don't assign more than 5 more granite to any other tasks" type of message will need to be placed into the game's material-allocation logic in the meantime.

You would also need to make some sort of fancy extra step of temporary stockpile type of code, as well.  For example, the dwarf may pick up three stones that were nearby on his way to the wall he is going to build, and then set those three stones down in the places where they are going to be turned into their respective wall tiles, so that they are nearby and out of the way of the current building task.  If setting the stone down on the tile where the stone will be built into a wall is a problem for some reason, it has to be pretty fancy in choosing a "nearby" tile that isn't going to have a task on it (like another wall building), either.
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 #31 on: February 27, 2011, 11:26:28 am »

It is L*x, where L is length of path and x is maximum distance to find job (it is in fact BFS with found path as starting points with limited path length). It also will annihilate FPS.

So rather than countering the idea with a better idea all you did is tell me why it wouldn't be efficient enough.

And how efficient does the algorithm need to be in order to be good enough for you?
It's just a cost benefit thing.  Anticipated cost >> Anticipated benefit.

From my perspective, any change would need to pay for itself.  Since haulers are effectively free, doubling up would need to be at least as efficient (processor wise) as taking two trips.  Right now, I don't think it is (I mean sure, when they DO take two things, it's more efficient, but the overhead is added to ALL hauling jobs).

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #32 on: February 27, 2011, 11:56:20 am »

So rather than countering the idea with a better idea all you did is tell me why it wouldn't be efficient enough.

And how efficient does the algorithm need to be in order to be good enough for you?

It's just a cost benefit thing.  Anticipated cost >> Anticipated benefit.

From my perspective, any change would need to pay for itself.  Since haulers are effectively free, doubling up would need to be at least as efficient (processor wise) as taking two trips.  Right now, I don't think it is (I mean sure, when they DO take two things, it's more efficient, but the overhead is added to ALL hauling jobs).

Well, as an alternative, what about the "nearby" from only the specific site of the job, rather than the length of the pathfinding?  You could potentially alter the definition of "nearby" based upon a quick and dirty absolute length of the path to the stockpile or something, so that you could say that you will try harder to collect more items in a single trip if you know that the stockpile will be further away, and take longer pathfinding back.

That way, the amount of time you spend consolidating jobs by pathfinding just from one nearby item to the next nearby item, and then do the big and difficult pathfinding task of going from the last item to the stockpile all at once, saving in overall pathfinding time.
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 #33 on: February 27, 2011, 12:17:40 pm »

that makes a lot of sense.  What are the cases for massive amounts of A -> B hauling? 

1:  To/From Depot  (check)
2:  To stockpile from workshop (check)
3:  To stockpile from corpse (check)
4:  To workshop from stockpile (check), (think 'needs 5 steel bars)

Slightly more difficult:

4:  To stockpile from mining area
5:  To stockpile from battlefield

What other use cases for massive hauling are there?

I think wheelbarrows are still a mess, though.  Should I use one?  Where's the closest one?  How far do I actually have to go?  Do I pass close to one?

Kogut

  • Bay Watcher
  • Next account: Bulwersator
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #34 on: February 27, 2011, 12:49:40 pm »

It is L*x, where L is length of path and x is maximum distance to find job (it is in fact BFS with found path as starting points with limited path length). It also will annihilate FPS.
So rather than countering the idea with a better idea all you did is tell me why it wouldn't be efficient enough.

And how efficient does the algorithm need to be in order to be good enough for you?
I see that 'on your way' may be nice but I have no idea how to make efficient algorithm (n log n or better) to solve it.
Logged
The worst bug - 34.11 poll
Tired of going decades without goblin sieges? Try The Fortress Defense Mod
Kogut, the Bugfixes apostle of Bay12forum. Every posts he makes he preaches about the evil of Bugs.

Silverionmox

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #35 on: February 27, 2011, 01:01:48 pm »

If we do it that way, we can wind up "following a trail of breadcrumbs" away from a task we should be lumping in as a nearby task.  If there's a single item on the floor that by chance creates the first task on the job board, then there is another single item a single tile away to the north, but a pile of goods that needs to go to the stockpile two tiles to the south, and then when the flood search takes place from the single item that was to the north, it finds another item 2 more tiles to the north of that, then another item 4 more tiles to the north of that, then another 8 tiles to the north of that, then you've gone out of detection range for the whole pile of items to the south.
Hey, I like that. That's how children get lost in forests and stories start. I seriously think there is room for dumbness here. We want to save the player's time by improving processor usage, not save the hauler's time by improving his GPS.

It is just one hauling strategy: if there's a big pile of items, it should be grouped as one set of jobs and assigned to one or more dwarves). The items that are not eligible for that treatment because they are not concentrated enough will inevitably have to picked up that way.

I think wheelbarrows are still a mess, though.  Should I use one?  Where's the closest one?  How far do I actually have to go?  Do I pass close to one?

Another big problem with wheelbarrows: stairs. Giving each dwarf a backpack (or basket, bag, etc. depending on available materials and crafters) should be sufficient to do most hauling. Wheelbarrows can then be thought of as a tool to move heavy loads faster, rather than a container. Gravel, ore, sand, clay and other bulk goods should be put in bins for transport anyway: those can then be carried up the stairs as necessary.

Wheelbarrows would be the most useful for a group of identical jobs, eg. 35 pieces of bituminous coal to stockpile: the dwarf would fill a bin, put it on the wheelbarrow, deliver it to the stockpile, get a new bin and go back to fill it - keeping the wheelbarrow with him all the time. Otherwise the decision to get an empty wheelbarrow (probably somewhere near a stockpile) will be a calculation in itself (requiring pathfinding as well, wheels don't walk and the terrain needs to be checked).
Logged
Dwarf Fortress cured my savescumming.

Draco18s

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #36 on: February 27, 2011, 01:30:39 pm »

It is L*x, where L is length of path and x is maximum distance to find job (it is in fact BFS with found path as starting points with limited path length). It also will annihilate FPS.
So rather than countering the idea with a better idea all you did is tell me why it wouldn't be efficient enough.

And how efficient does the algorithm need to be in order to be good enough for you?
I see that 'on your way' may be nice but I have no idea how to make efficient algorithm (n log n or better) to solve it.

If you have no idea how efficient an algorithm is, then you can't comment on its efficiency.
Logged

Granite26

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #37 on: February 27, 2011, 02:07:18 pm »

It is L*x, where L is length of path and x is maximum distance to find job (it is in fact BFS with found path as starting points with limited path length). It also will annihilate FPS.
So rather than countering the idea with a better idea all you did is tell me why it wouldn't be efficient enough.

And how efficient does the algorithm need to be in order to be good enough for you?
I see that 'on your way' may be nice but I have no idea how to make efficient algorithm (n log n or better) to solve it.

If you have no idea how efficient an algorithm is, then you can't comment on its efficiency.

He said it wasn't n log n and he didn't know a way to make it n log n, not that he didn't know how efficient it was.

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #38 on: February 27, 2011, 04:53:05 pm »

Hey, I like that. That's how children get lost in forests and stories start. I seriously think there is room for dumbness here. We want to save the player's time by improving processor usage, not save the hauler's time by improving his GPS.

It is just one hauling strategy: if there's a big pile of items, it should be grouped as one set of jobs and assigned to one or more dwarves). The items that are not eligible for that treatment because they are not concentrated enough will inevitably have to picked up that way.

OK, fair enough, I guess having dumb dwarves as a flavor choice may be OK, so long as it isn't so stupid you pull your hair out or have to babysit them. 

Another big problem with wheelbarrows: stairs. Giving each dwarf a backpack (or basket, bag, etc. depending on available materials and crafters) should be sufficient to do most hauling. Wheelbarrows can then be thought of as a tool to move heavy loads faster, rather than a container. Gravel, ore, sand, clay and other bulk goods should be put in bins for transport anyway: those can then be carried up the stairs as necessary.

Wheelbarrows would be the most useful for a group of identical jobs, eg. 35 pieces of bituminous coal to stockpile: the dwarf would fill a bin, put it on the wheelbarrow, deliver it to the stockpile, get a new bin and go back to fill it - keeping the wheelbarrow with him all the time. Otherwise the decision to get an empty wheelbarrow (probably somewhere near a stockpile) will be a calculation in itself (requiring pathfinding as well, wheels don't walk and the terrain needs to be checked).

Well, cows can go up tight flights of stairs that apparently spin in place, so it might just be that for now, wheelbarrows go up stairs, too.  Alternately, wheelbarrows would have to be treated with code more similar to the caravan wagon code, which is massively problematic for Toady.  It would probably make ramps much more popular than stairs in fortress design, though.

Wheelbarrows are something I think might just become "hauler equipment" at a certain point just to make the game easier - a woodcutter grabs an axe so that he/she can cut down the trees, and a hauler might grab the first available wheelbarrow or backpack to be able to better haul goods, and just pathfinds and hauls as best they can with the equipment they have.  It might be wierd from the current game perspective, but if we cut down on the number of trips haulers have to do by giving them wheelbarrows, haulers shouldn't take up such a percentage of the fortress population.  Alternately, there might be some sort of toggle we can put on a flag in the labors menu that says they're a "wheelbarrower" labor acive that should be carrying around a wheelbarrow because we have determined they are performing hauling so frequently that they need a wheelbarrow, and it won't be wasted on them to push it.

There may need to be something in the job "relation" code that will make jobs try to group with each other and count how big a group of jobs they can make.  Wheelbarrowers and minecart pushers should try to go for the larger job groups, while backpackers might leave very large grouped jobs for wheelbarrowers and aim for mid-sized jobs as a priority, while standard haulers will go for individual outlier items that don't have many nearby items to group tasks.  (This means that the job order itself decides how to group themselves, before the dwarves even decide to take the job and try to pathfind.)

that makes a lot of sense.  What are the cases for massive amounts of A -> B hauling? 

1:  To/From Depot  (check)
2:  To stockpile from workshop (check)
3:  To stockpile from corpse (check)
4:  To workshop from stockpile (check), (think 'needs 5 steel bars)

Slightly more difficult:

4:  To stockpile from mining area
5:  To stockpile from battlefield

What other use cases for massive hauling are there?

Dump zones that are un-forbidden.  That can be a very large concentration of items.

Butcher's shops, too, but that's already a workshop to stockpile job. 

I actually think the "central distribution area" based upon minecarts would have to be the single most difficult decision tree to build.  Even if pathfinding is easy, since you have a set track to follow, you have a major set of decisions to make if you want this to be automated.

You have to decide when there are enough hauling jobs that a minecart is worth sending out, where to send it back, what to lump onto the cart, and what to haul by hand to stockpiles that are far enough away, when to haul back (if the only remaining items are "too far"), and then decide how to distribute the goods in the cart.

Plus, if we have draft animals pulling the minecart, we need jobs for attaching the mule or horse or ox to the cart, and then making sure to let it go before it starves to death.

A "central distribution area" that might look like some kind of Grand Central Station might be a good way of handling some of the "where does it go" coding.  It would also be amusingly bustling.  But a distribution area that has all your carts dump their cargo (maybe even keeping carts on a single track), and maybe load up their cargo to get shipped off to distant workshops or stockpiles, or else leaving the goods to be loaded from unloading bay to some of the nearby stockpiles.  This kind of setup would make industrial areas of the fortress much more centralized.

Oh, and what it you move the minecart up to the workshops?  Can you just haul a whole bunch or coal and flux and iron into a cart and shove it down to the furnaces?
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 #39 on: February 27, 2011, 05:18:14 pm »

I don't like the idea of institutionalizing the quantum dumps.

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #40 on: February 27, 2011, 05:24:08 pm »

I don't like the idea of institutionalizing the quantum dumps.

I'm not talking about institutionalizing quantum dumps, I was just talking about dump zones (which forbid items that go into them) that you unforbid.  There are reasons to use dump zones other than creating quantum stockpiles.  For example, dumping wood from the surface down a long pit to the magma forges, then unforbidding them at the bottom from time to time to save transit time on woodcutting.  (Besides, it's not a quantum stockpile if you're taking it to a real stockpile.)

More generally, any sort of mass-unforbid action will probably cause a big push to stockpile a huge number of items. 
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

Draco18s

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #41 on: February 27, 2011, 05:25:26 pm »

He said it wasn't n log n and he didn't know a way to make it n log n, not that he didn't know how efficient it was.

So because he doesn't know how to make it efficient, therefore its not efficient, therefore its bad?
Logged

Kogut

  • Bay Watcher
  • Next account: Bulwersator
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #42 on: February 27, 2011, 05:28:44 pm »

He said it wasn't n log n and he didn't know a way to make it n log n, not that he didn't know how efficient it was.
So because he doesn't know how to make it efficient, therefore its not efficient, therefore its bad?
I only said that I have absolutely no idea how to do it and that it is probably very hard to do it in FPS-friendly way (harder than normal pathfinding that is too slow already).
Logged
The worst bug - 34.11 poll
Tired of going decades without goblin sieges? Try The Fortress Defense Mod
Kogut, the Bugfixes apostle of Bay12forum. Every posts he makes he preaches about the evil of Bugs.

Granite26

  • Bay Watcher
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #43 on: February 27, 2011, 05:30:39 pm »

He said it wasn't n log n and he didn't know a way to make it n log n, not that he didn't know how efficient it was.

So because he doesn't know how to make it efficient, therefore its not efficient, therefore its bad?
Well, again speaking for me, bad to do unless a way to make it efficient is found.  It may not be possible.

Honestly, DF appears to be chasing Moore's Law for new features.  :)

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Stacking and Hauling Improvements (optimization)
« Reply #44 on: February 27, 2011, 05:46:54 pm »

Could we please stick to actually discussing the topic, instead of who's being unconstructive or not?

Is there any sort of response to how to most efficiently use wheelbarrows and backpacks, for example?  What about the minecarts and central distribution areas?
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
Pages: 1 2 [3] 4 5 ... 10