Right, so this topic is the single biggest winner of the ESV, and yet it doesn't have its own dedicated thread. I did a quick search of "stacking" and "hauling", and found only a couple of threads from two or three years ago, which mostly devolved into fighting, anyway, so I figure a new thread probably won't hurt.
This is a topic I'm extracting out of the
ESV thread, since this is straying pretty far off-topic to seriously discuss this one item in the ESV thread.
I'm not entirely sure this is going to be a "suggestion" so much as a discussion about what is and is not feasable, and how to make the coding as optimized as possible. But maybe we can put our heads together, and come up with some sort of way of handling all this code that Toady hasn't thought about, which would be great.
First up, the Devpage items we are talking about:
Hauling Improvements
- Being able to haul multiple small objects
- Having multiple dwarves involved with item hauling for a job
- Being able to move multiple objects with roughly the same destination at once
- Wheelbarrows to haul more objects than can be carried
- Minecarts
- Wooden, stone-carved and metal tracks
- Can be filled like stockpiles and moved between destinations
- Work animals to tow carts and haul objects
I don't think people really disagree with what needs to happen in the game - people want dwarves who can more rationally do things like pick up more than one object in the same tile that is going to the same stockpile. We want a dwarf to be able to see 5 plump helmets in a stockpile, and have a stack of 5 plump helmets in his/her hands, and figure that he/she can consolidate them together into a stack of 10 plump helmets, rather than having stacks that can only be divided, never consolidated back together again. In fact, people really, really agree on this, since it was the big winner of the ESV by a mile.
The problem here is the tradeoff of performance for dwarven sanity.
Thus, the conversation in progress:
It is not "the FPS drops by half", it is "the FPS drops to 1/n of old FPS" where n is quantify of dwarves. (or even "the FPS drops to 1/(n*n) of old FPS")
I'm going to have to ask you to explain where you came up with those numbers. The only way that sort of complexity would make sense is if the entire pathfinding routine would have to take place per every other pathfinding creature in the entire map, which makes absolutely no sense.
We have route from A to B. [for example single sock moved from A [battlefield] to B [trade depot]]
We want to detect routes likes A->X->Y->B, without huge additional cost.
To find routes like this it is required to make pathfinding A->B and A->X->Y->B for every possible pair of X->Y. [sock moved from X1 [battlefield] to Y1 [trade depot], sock moved from X2 [battlefield] to Y2 [trade depot], seed moved from X3 table to Y3 stockpile etc]
So with n jobs, single planned results in pathfinder running n times instead of one check.
Result: pathfinding running n^2 times for n jobs, instead of n times.
[I assumed that number of jobs is liner vs number of dwarves, but "where n is quantify of dwarves" can be changed to "where n is quantify of jobs"]
So, let's start...
To a certain extent, I think a part of this problem is that Stacking and Hauling constitute more than one topic and set of code, and what I really want to see (stacking) is something that should be not terribly difficult, at least for certain types of items.
StackingI did a little digging to find a Toady quote about how stacking works, as well...
Coins have their coin batch index (year for dwarves) and the material, but there's also ownership, contaminants, temperature, damage, age, storage information, maker id, flags based on if your fort owns/made it, melt/dump/forbid/hide designations, job information... and probably more. Some of it can be scrapped or otherwise dealt with, but it's not a triviality if you want to keep track of things. Even if it checks all of these things and consolidates equal stacks (which would be rare -- or with age+maker id, virtually impossible), seeing it happen in some cases and not others with identically named objects would lead to false bug reports, I think. Probably more profitable is addressing the main concerns in other ways -- getting dwarves to grab all the bolt stacks they need when they go to get a one bolt stack or making coins work in a sensible fashion don't really depend on stacking so much. Increased CPU drag from broken stacks is probably the main thing that can't be dodged without some direct handling, and I'm leaning toward not suppressing the information by using some extra objects (could use the same ones as the interface would I guess, though there are all sorts of ways to think about it).
Can't you just create a new "stack" container that would be created by stacking two objects of the same types (bolts, coins, ...) and destroyed when it contains only one object?
This is roughly what I meant by "extra objects", except for the "just" part. The main point is that it's not only an interface problem. If items are potentially contained in fake stack items, all the job handling needs to be revised to support that. It's a bit less of a pain if you restrict to only coins or bolts say, but there are still things to be considered. Take bolts for example. Your guy wants to equip some. First it needs to recognize the container as a valid ammo object. Depending on exactly what you choose to stack, some members might not be as eligible as others -- what if some in the stack were forbidden, or tasked for a job, prior to stack formation, for example? Those cases would need to be disallowed or handled. Then the equipment checker needs to realize he's got the bolts when he places the container in his quiver. Not so bad, possibly handled by current code, but something to check. Now he wants to fire a bolt -- shooting needs to be rewritten to support bolts in the fake objects. Sort of a piece of the quiver code already, maybe nothing needs to be touched at all, but takes some checking and testing. There are side issues like valuations and stocks screen stuff, which might be handled already, and other thises and thats (environmental functions would need to be taught about fake containers -- rain for example should get the bolts wet, but currently there's no mechanism for jumping through a container on the ground to get the inside stuff wet, I think, since containers are generally real -- not hard, but yet another issue), as well as any applicable storage jobs, which run into some of the first problems I mentioned. As you get to other objects, like food, you inherit more difficulties (vermin need to see and realize that they can eat food in stacks for free, etc. etc.). As far as I can tell, the problem is not super difficult, and a lot of the issues just need a nudge one way or the other, or no nudge at all, but there are a Lot of issues that turn this into a tedious and long haul. There's generally more to do and check than people expect.
Items like iron bars are not distinct from one another - you can stack as many iron bars in one location as you arbitrarily will decide the limit is for a given tile. You only have to keep wood distinct by the type of tree it came from. You can have as little as .1 liters of wood, (or whatever your smallest unit size is,) and up to 100 liters of wood, (or whatever the limit for volume in a given tile is,) and as long as dwarves just actively try to consolidate their items of the exact same type together, there's not really much problem in coding this, here. Basically, all you need is a "is this particular stack full?" check performed when a dwarf is trying to pathfind to the stockpiles. They already sort of do this in the form of a "is something on this tile?" check, and a check to put similar items into barrels, so you can't tell me that doing an additional check to see if there's a not-quite-full stack of identical material will cause a terrible strain in coding or FPS. (At least, this is assuming that iron bars and wooden logs don't have to carry around "maker data" or anything like that.)
As for other things...
Well, most of the detail could be exported to a single pointer on the actual coin, and if you rewrite stacks to be pointer counts, that helps. (Exported detail is everything on the coin when it's made, date manufacturer, material, etc)
The problem is contaminants...
Thing is, I think we could probably do some sort of bastardized system.
Some goods that are never going to be in stacks (statues, for example) can just continue being what they are.
This means that stackable manufactured items would need to have two data sections, a "manufacture data", and a "status data". Manufacture data is the data about what the stack actually is made of, who made it, when it was made, etc., all the stuff that doesn't change once the item has bene manufactured, unless it is consumed somehow. Status data is the information on contaminants, ownership, designations, job data, and other things that have to do with how something is being moved around and used.
For the stackable manufactured type of thing, a "stack" would just need a pointer to a master table of manufactured goods from your fortress for the "manufacture data", plus maybe something that gets imported to that list from the outside when the merchants are visiting, could work, similar to what Granite was talking about. It would need occasional garbage collection, as well, to see that the last of the 120 units in the masterwork quarry bush leaf roast stack had finally either been consumed or rotted, and that production data was not necessary any longer.
The rest of the "stack" would need to have status data on the specific items.
The "stack" would be what you see in the 'k' look menu, there, if you are looking specifically at a stack of cow bone bolts or something.
On top of this, we would want to have a more fungible "container" stack, where you could say that you grab 15 individual bone bolts that are all made at different times, but which you don't particularly care about the details, you just want a stack of 15 bone bolts.
To a certain extent, you don't really need to have individual status information on each bolt in the stack - if one bolt is spattered in mud, and you lump them all together in a container stack, it's not too big a deal if those lumped together bolts are now all spattered with mud, and all the same temperature, and all designated the same, since you want to treat those as a group of functionally similar items, anyway. Hence, container stacks can just have a list of pointers to that manufacture data, and then a single status data for everything in the "container" stack.
(Yes, this is the sort of thing that Toady said would take rewriting job data to get around, but... well, we're talking about rewriting how jobs get handled, anyway, so that's pretty much a sunk cost at this point, anyway.)
HaulingOK, here, we're talking about the problem where, let's say a dwarf or a goblin dies out in the battlefield on the surface of your fort. Now you have to go collect all those precious, precious socks. Thing is, each goblin or dwarf generates about 10-20 hauling jobs when he dies. Each individual piece of clothing needs to be individually hauled to the nearest stockpile that accepts the particular crap piece of clothing you're dealing with. This means it takes 10-20 trips from the battlefield to the stockpiles per dead dwarf or goblin. Typically, this means 10-20 haulers all swarm a single goblin at a time after a siege like some sort of bearded ant colony picking the meat from a set of dead critters. Since each trip only takes one stupid wooden ring at a time, it's frustratingly inefficient. In fact, most of the time, I just leave the non-iron crap out there for the kobolds and racoons to just take off my hands for me. (Oh no, the kobolds stole some worthless leather mittens and wooden rings from the goblin corpses!)
Now, this is where the job assignment for things like hauling needs to be much more sane. In the case of hauling clothing off of corpses, I think I can assume that what happens is that each item that isn't in a stockpile generates a "job" that says the item needs to go from where it is to the stockpile that it targets, and the item puts its job up into the job queue for dwarves who are idle and looking for a job with the hauling labor enabled to pick off the list.
What needs to happen in a rational sense is that jobs need to check for other jobs to get bundled into a complex job. In the case of a dead goblin with 20 articles of clothing, this should be fairly easy to do, because odds are, all the clothing items are all in the same tile, and need to go to the same stockpile as their task. Hence, if they are basically the same job repeated 20 times (carry item from point A to point B, and all of those point A are the same point A, and all those point B are the same point B), then there isn't going to be a problem in the "haul multiple items of different types" pathfinding task, because all you need to do is search for jobs that go from the same place to the same destination.
So long as we are dealing with same exact starting and ending points, then it's not going to be any problem at all to code this, the problem is when we are dealing with "nearby" tasks. This gets split into two ways of thinking about the task - "nearby" in terms of mutiple at least vaguely nearby starting points with only one destination stockpile, and "nearby" in terms of multiple densly nearby objects that have more than one destination.
After a miner has gone by and excavated a mining shaft, and there's a whole mess of stones just lying around for haulers to get around to doing something with. They're all in different tiles, but they all probably need to go to the same point. Either they're all getting dumped, or they're probably going to be slated for hauling jobs en masse to a large stockpile. This means that when the jobs are created, they're going to need to look in their own immediate vicinity for similar objects with a job to be hauled to the same spot that they need to be hauled. This way, they can line themselves up in a "related job set" or something so that hauler dwarves who have a wheelbarrow or something to carry that many stones can decide to declare they are taking more than one of these hauling jobs at the same time. I'll call this "Type A Nearby Hauling".
The other thing is if, in the goblin example, the iron breastplate and the elf leather socks need to go to different stockpiles. The iron breastplate, for example, needs to go to the stockpile near the furnaces to get melted down, while the socks are slated for dumping directly into the magma pit. Let's call this "Type B Nearby Hauling".
Now, here's the thing about how these get processed... It's the items themselves, in lining up the job queue that declares whether they are related to one another, not the dwarves who are taking the jobs, and it does this at the job task's creation. Dwarves who decide to take up the task will then have to declare how many of those jobs they can actually complete (based upon their hauling capacity), and then mark those jobs as "taken". The remaining jobs will then have to decide how to reform themselves on the jobs queue as priorities and how related they are to one another.
I'm not even really being specific in what "nearby" means, at that, since we don't want to call any more pathfinding than is really necessary. This means "nearby" can be a fairly problematic concept. We don't want to declare anything within 5 tiles to be "nearby", since maybe there's a wall in the way, and "nearby" will be declared to be something that actually takes 120 steps to even reach. The best thing I can say without actually declaring a real pathfinding search is that the game should be able to draw a direct line between all the objects without hitting an obstruction and without running a "real" pathfinding task to search from one to the other.
Even more problematic is that every time a task is created, it will then need to have to search for what other jobs are nearby.
One solution is searching the entire jobs list, and then looking at the "starting from" location to find the "nearby" ones. This causes problems when the jobs list becomes longer, because it means that every new job will have to make a search of every single job already put on the job queue to search its starting location. This basically has a complexity of O^2+O where O is the number of jobs being put into the jobs queue. (Subgeometric complexity growth with number of tasks.)
Alternately, it can actually look at the physical map around it, and search every tile for objects, then search those objects for jobs that take that object someplace, and then test to see if they are going the same place, and THEN search to see if they are actually "nearby" and don't have an obstruction between them. This causes problems to start with, since you have to search a lot of tiles for items to even start with, and then, if you have something horribly complex like a dump zone/quantum stockpile with 5,000 items in one of those tiles. Preventing quantum stockpiles or putting limits on the number of items that can physically enter a tile (meaning dumping an item into a pit which already has 100 items in it will simply create a "solid wall" that prevents more items from entering it) will put some sanity check into that, but it's still going to be a problem. This has a complexity of R^3 (O
p+O
q+O
d), where R is the radius of tiles around the object that you consider "nearby" (Alternately, you can only search for "nearby" as being on the same z-level - this means that objects on different portions of a ramp will never be tasked with one another, but it can cut out a lot of false positives where you assume that anything on another z-level is probably going to be very difficult to path a direct line to. This means you only need R^2 complexity.) while O
p are the number of items present in a given tile, O
q are the number of items with hauling jobs queued, and O
d are objects with nearby enough destinations.
I can't say with utter certainty which one would be the most efficient.
Ugh, for something that was just some idle side-conversation, this sure spun out of control into another big rant... Maybe I should stop thinking so much.
I probably forgot to complete a thought somewhere up there, but this is getting to the point where I just sort of want to post it and maybe revise it later...
Author
Topic: Stacking and Hauling Improvements (optimization) (Read 31535 times)