Print

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

[idgarad]

Cutting to the Specifics:

Rather then Define a stockpile as a region of map space build it as a workshop-like entity.

When objects are placed into the stockpile they are in effect destroyed. The stockpile object itself maintains a list of quantities in it's place.

e.g.

300 units of Obsidian are delivered to the stockpile: The stockpile workshop in effect destroys the 300 objects and simply stores a value of:

Obsidian:300 as a value. In the event the stockpile is destroyed or move the stockpile object effectively drops it's contents on the follow (no more or less cheaty then quantum storage.) There would be some lag I assume during the dump (Creating all the objects that were stored.)

Dwarves could then go to a stockpile workshop and retrieve an item out of the stockpile workshop. This could drastically cut down on the memory usage as objects stored in a stockpile\bank are a single object with quantities rather then individual objects for each.

[JanusTwoface]

That would probably work fine for stones and other raw materials, but how would it work for any manufactured item--items with an associated quality or subcomponents like meals?

I think optimizing how the items are stored and accessed--so that the program doesn't have to go through the entire list of items for a variety of tasks as it appears to do now--would be more beneficial.

[idgarad]

That would probably work fine for stones and other raw materials, but how would it work for any manufactured item--items with an associated quality or subcomponents like meals?

I think optimizing how the items are stored and accessed--so that the program doesn't have to go through the entire list of items for a variety of tasks as it appears to do now--would be more beneficial.

The process is actually quite simple in that regard, since we can take any arbitrary meta-data and store it. We just add it on the fly. Since the object already exists as a single entity there is not much in the way of overhead since the object already exists. So for 1-off items we aren't losing or gaining anything but even at 2 of an item we've cut at least 1 single instance of the object. The hardest part that I can see if modify dwarf logic to take from a stockpile workshop versus the current method. Storing objects should be easy in contrast.

[rampaging-poet]

Let me see if I've got this right: The master item list remains the same. When an item is placed in a stockpile, it is removed from the master item list and placed in the stockpile's list.  When dwarves try to find materials, they search the applicable stockpile lists before checking the master list, ensuring that they check to see if the ~200 stone in your stockpiles will work before checking the distance to all 50,000 boulders on the map.

You'd definitely want the individual stockpile lists to be in the same format as the master list.  That would make transferring items between lists much easier, and actually using the stockpile lists would just be a matter of selecting which list to pass to the existing logic.

Most mass-quantity tasks like masonry, mechanics, and smelting would probably see significant speed increases from this. Evening hauling would improve slightly because items that are already stockpiled wouldn't be repeatedly checked for hauling again.  However, I see three possible problems with this setup.

One: this might slow down anything affecting items in a specific square like magma floods and blood splatter.  The savings of not checking for stockpiled items in the middle of nowhere are probably more than eaten up by checking each square to see whether or not it's a stockpile in the first place.

Two: dwarves will presumably be carrying items in and out of stockpiles quite frequently.  While it's unlikely to be less efficient than iterating over all 50,000 boulders (and socks, and bolts, and...) every time you make a table, moving items between stockpile lists and the master list isn't free.

Three: if checking whether or not to add an item to a stockpile's list isn't efficient enough, we're right back where we started.  It's probably only a problem when units with a lot of blood-splattered equipment are torn limb from limb, causing the game to check to see if each and every item/body part is in a stockpile, but we still wouldn't want the game to lag every time Urist McChampion decides to get poisoned and explode in a shower of gore.

Still, if the savings in the average case are good enough and it's not too difficult to be worth the time, this is a good idea.

[janglur]

Actually, you can recreate this fairly well.  I get a fair FPS boost by 'd'umping everything onto a square adjacent to it's relevent workshop, most noteably metals, wood, and stone.  This cuts pathfinding drastically and if they don't path too close to the pile when travelling, it reduces various observational calculations as well.

[idgarad]

Let me see if I've got this right: The master item list remains the same. When an item is placed in a stockpile, it is removed from the master item list and placed in the stockpile's list.  When dwarves try to find materials, they search the applicable stockpile lists before checking the master list, ensuring that they check to see if the ~200 stone in your stockpiles will work before checking the distance to all 50,000 boulders on the map.

You'd definitely want the individual stockpile lists to be in the same format as the master list.  That would make transferring items between lists much easier, and actually using the stockpile lists would just be a matter of selecting which list to pass to the existing logic.

Most mass-quantity tasks like masonry, mechanics, and smelting would probably see significant speed increases from this. Evening hauling would improve slightly because items that are already stockpiled wouldn't be repeatedly checked for hauling again.  However, I see three possible problems with this setup.

One: this might slow down anything affecting items in a specific square like magma floods and blood splatter.  The savings of not checking for stockpiled items in the middle of nowhere are probably more than eaten up by checking each square to see whether or not it's a stockpile in the first place.

Two: dwarves will presumably be carrying items in and out of stockpiles quite frequently.  While it's unlikely to be less efficient than iterating over all 50,000 boulders (and socks, and bolts, and...) every time you make a table, moving items between stockpile lists and the master list isn't free.

Three: if checking whether or not to add an item to a stockpile's list isn't efficient enough, we're right back where we started.  It's probably only a problem when units with a lot of blood-splattered equipment are torn limb from limb, causing the game to check to see if each and every item/body part is in a stockpile, but we still wouldn't want the game to lag every time Urist McChampion decides to get poisoned and explode in a shower of gore.

Still, if the savings in the average case are good enough and it's not too difficult to be worth the time, this is a good idea.

One thing is we don't need to allow everything in the stockpile workshop. We could also just call it a Bank for instance and only allow certain items to be put in the vault (call them vaults then... whatever)....

Now the rebuttal:

One: Since the stockpile is a single workshop with it's own list it would be treated really no differently then any other workshop (carpenter, kitchen, etc.) with the exception that if it is destroyed or deconstructed we would have to take the contents and transfer it to the master list as you say. Not saying it wouldn't be a lag inducer but momentary lag when destroying or deconstructing a vault would seem to be an acceptable trade-off. Destroy the workshop and leave a pile of the crap no different then a garbage pit and move on from there. Yes potential for a big lag-spike, on the plus side we could also make items in the workshop non-tossable in the event of an abandon\reclaim but that should be an init option if you ask me...


Two: The transaction should be the same, you still need to update the dwarf's inventory such that he is hauling stuff, so there should be a hook in the core game logic to stitch it into. It's a decrement and create transaction (or increment and delete in the case of a deposit)

On Drop Off
 Begin Transaction
  If Item Exists in List of Stockpile Goods
   Increment Else Add Item and Increment
  Delete Item From Hauler's Inventory
  Set Dwarf to Idle
 END Transaction

(To my best guess at the logic)

Where as the current is likely

 On Drop Off
   Begin Transaction
   Object Location = Dwarf Location
   Remove Object from Dwarf Inventory
   End Transaction

The only thing we are really adding is incrementing an element in a linked list (or array table) and a delete operation. The overhead seems marginal in contrast to the fact we could be reducing the object count on a map by MASSIVE amounts (Just think of all the times we use Quantum Storage and converting that 800 stone into 1 stone(quantity=800) instead. Again, think of all those damn pair of Giant Cave Spider Silk Socks (all 900 of them) and turning those into a single Stockpile location with 1, just 1 path finding check needed....

Three:
Is should be vastly quicker, even in the case of a linked list setup for the master object array we are effectively changing the following logic:

Rather then an individual objects we are having a list of singular objects

Giant Cave Spider Sock
   Location(x,y,z)

and changing it to
Giant Cave Spider Sock
   Stockpile(uid)
    Quantity(int)

So even it we wanted to keep the info in the master list we would only be adding two INTs (hell you can use short ints and limit the quantities to 255 each stockpile even).

If that is the case (assuming short ints for the xyz) we are looking at 24 bits versus 16 bits for whereIExist information. If it is written in C++ or anything that handles typical OOP then you can have location(x,y,z) for on-map objects and stockpile(uid) for items in the stockpiles and still come out on average with at least 8 bits of savings per object and I'm just talking the location data. This is classical de-duplication programming is all wrapped in a new workshop

The check should only be made at drop off. The gore pieces are still on the master list until some dwarf takes them to a stockpile. The stockpile list in this case would be cage-space with no time inside so no need to check anything except at check-in and check-out. The check in this case (as far as I follow) would be no different then checking stockpiles on the ground, again the advantage is only 1 square in size for path finding and since we can control the new stockpile list using a simple branching tree should make a search easy and efficient.


I'm thinking based on scanning my fortresses stockpiles we are talking about reducing the memory footprint and object counts by at least 1/2 if not more with this method. Even if it is slightly more inefficent code wise I'd take a 5% increased overhead per object if I can reduce the objects needed by 1/2 if not more..