Print

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

[Narmio]

I would really like to see dwarves choose crafting materials, dump sites, water sources, etc based on path distance instead of straight-line distance.  I think that dwarves choosing the garbage dump on the surface 20 levels up - through twisty turny passages - over the garbage dump at the magma pool 21 tiles to the side of them, with a clear path to it and all, qualifies as a bug.

I've been thinking about this, and I wonder if there's an algorithm to check for it that has an average-case performance not that much worse than the current one but will still work. Just speculating on an algorithm, so someone check my thought here.

OK, so, you begin by calculating the linear distance to each object and sorting them - the exact current procedure.  Then you use the following principle: Any object to which the linear distance from the current point is X will have a pathing distance to that object greater than X. 

So you check the closest object, call it Object A, by linear distance, and calculate a path to that, let's call the length of that path path(A) and the linear distance to that object dist(A).

Then you go down the ordered list of objects skipping over any objects that are in exactly the same place as A (because there's no point trying them - we'll pick A instead) until we find an object not in the same place as A, we'll call that Object B. We compare path(A) to dist(B), which we know already. If path(A) <= dist(B), we know for sure that A is the closest object by walking, since path(B) >= dist(B) and dist(everything else) > dist(B).

Alternatively, if the path to A is longer than the crow-flies distance to B, then we have to calculate path(B) and test whether it's shorter than path(A). If not, we go to the next object in the list that isn't in the same place as B, object C, and check if path(A) <= dist(C). If path(B) is shorter than path(A), we switch to that and then compare it to C.

This continues until we find reach object for which the linear distance to that object is GREATER than the shortest path distance we've calculated so far. At each object in the ordered list we've had to do one or two simple calculations - are they in the same position, then is their linear distance greater than the current shortest pathing distance.  We've also had to calculate a bunch of routes.

However, and here's the bit that I think might be a bit of a breakthrough - you really won't have to calculate that many paths in the vast, vast majority of cases, probably just a few. It will, at minimum, require the calculation of one path for each currently linear-distance using function. My sense is that that won't be a *huge* slowdown, the problem is having to calculate loads of paths, which should be very rare. Most of the time it will check paths to a few linearly close objects and find one for which the linear path and the actual path are very close, and then quickly stop.

The worst case scenario would be a workshop vertically adjacent to a stockpile with hundreds of usable objects in it, but no direct access to any of them. They're all going to be very close, so paths will be calculated for all of them (and all those paths will be very long) before the iterating pathing/distance function reaches an object with a shorter path - one on the same Z-level as the workshop, let's say - and then quickly stops soon after because it's found a very direct path. That could create loads of slowdown.  But that sort of thing should only happen due to bad layout design on behalf of the player, the average runtime of this algorithm should be much better than that.

Am I off base here? The way I see it, either this is a great idea (yay!), or there's an error in my algorithm, or the cost of calculating one or two paths for each job is so high that even this optimised solution would be too slow.

[Uristocrat]

I would really like to see dwarves choose crafting materials, dump sites, water sources, etc based on path distance instead of straight-line distance.  I think that dwarves choosing the garbage dump on the surface 20 levels up - through twisty turny passages - over the garbage dump at the magma pool 21 tiles to the side of them, with a clear path to it and all, qualifies as a bug.

I've been thinking about this, and I wonder if there's an algorithm to check for it that has an average-case performance not that much worse than the current one but will still work. Just speculating on an algorithm, so someone check my thought here.

OK, so, you begin by calculating the linear distance to each object and sorting them - the exact current procedure.  Then you use the following principle: Any object to which the linear distance from the current point is X will have a pathing distance to that object greater than X. 

So you check the closest object, call it Object A, by linear distance, and calculate a path to that, let's call the length of that path path(A) and the linear distance to that object dist(A).

The big problem is "what do you compare it to"?  I mean, it's true that you can measure "fast" in terms of "it takes X cycles on this CPU", but in general what matters to people is whether or not it's faster than the current algorithm.  So the thing is that the only way to get faster is to do less work.  Ideally, that means excluding most of the items in the fortress from consideration (and never even looking at them, let alone considering whether or not to path to them).

What I'm trying to say is that while these heuristics sound pretty reasonable, they're probably not going to be as fast as code which simply ignores most objects (even if it misses the closest one).  In that vein, Toady might get some mileage out of the secretary problem.  I mean, most players can live with it if the dwarf takes a stone that's 6 steps away instead of 5 steps, it's just when they head across the map for stone instead of using the that's right there that they get mad.

Of course, I've noticed that some people don't realize that the close stone they see the dwarves ignoring is either marked for dumping, reserved for another task, or possibly even marked as an economic stone, so it's not like we can discount human error.

[Narmio]

As this algorithm would be adding a feature - much smarter object selection by dwarves - it's not necessary that it be actually faster than the current solution, only that it not be deleteriously slow. There may, however, be a lot of options for using Marriage Problem (that's the term my algorithms teacher used to refer to the Secretary Problem, it's a much more poignant example! Nobody really cares if you get the *best* secretary, but the best spouse, that's a big deal!) type solutions, and for using clever approximation methods that don't result in a noticeable loss of precision. 

There are also undoubtedly caching solutions that have not been investigated by Toady, those would produce significant speed advantages at the cost of memory usage.  For example, I'm betting a dwarf at a workshop calculates the distances to all objects from the center of that workshop when making something, makes his pair of socks, then seconds later comes back and does all those calculations again.  Some objects may have been moved, added, destroyed, forbidden, used, or lost, but probably not the majority.  And the workshop hasn't moved, so the distances are going to be the same!  Simply caching a bunch of commonly used distances for each object will be quite a few Mb of data, but RAM is both plentiful and cheap! I'd bet that would speed things up a lot for the current object slowdown problem, and that's a solution that doesn't involve any approximation at all.

For most of these cases it's probably possible for Toady to read a book on optimisation and then spend some time restructuring low-level stuff.  But I can totally understand if it's not really a priority at the moment. Refactoring is slow, boring and usually annoyingly complex.

[Uristocrat]

There are also undoubtedly caching solutions that have not been investigated by Toady, those would produce significant speed advantages at the cost of memory usage.  For example, I'm betting a dwarf at a workshop calculates the distances to all objects from the center of that workshop when making something, makes his pair of socks, then seconds later comes back and does all those calculations again.

One of the best ideas I've heard was to allow stockpiles to be associated with a certain workshop.  If you have dedicated input and output stockpiles (and the dwarf isn't permitted to use anything else), it could reduce that sort of pathing by quite a bit and give us a feature to boot.  I wonder if there are other possibilities like that.

[Ves]

Isn't that what Burrows already do?

[Uristocrat]

Isn't that what Burrows already do?

Sort of, but you have to include a lot of things in addition to the stockpile and you have to assign dwarves to them, which can be pretty inflexible unless you make a dedicated set of workshops for each dwarf or something.

[Makbeth]

Isn't that what Burrows already do?

To some extent, but in my experience burrows can create their own pathing problems, even when no one is assigned to them.  Has that been fixed yet?  As soon as I realized that my unassigned burrows were the reason my furnacers were forgetting how to make steel, I stopped using them for anything but siege shelters, deleting them between each siege.  They just seem like more trouble than they're worth.

[Narmio]

I've not recently had any trouble with burrows. I use them for designating a Fortress burrow with all the safe bits attached to it so I can order civvies in there during sieges and the fort continues operating normally. I also assign a few high-value dwarves to that burrow permanently, so they don't take unsafe jobs.  I've also used burrows to separate newbie-miner and legendary-miner activities to preserve my precious veins.  All with no bugs/pathing/assignment problems.

Also, re: burrows and optimisation, I'm pretty sure burrows aren't helpful there currently.  Pathfinding doesn't respect burrow assignments, so it will perform A* on the entire map even when travelling within a burrow.  We know this is the case because dwarves can path outside a burrow to reach a target within a burrow - especially in the case of concave or complex burrows. So there's no optimisation there.  And I suspect for objects that the entire map worth of objects are measured, then the results are tested to see if they're in the correct burrows.  There certainly could be a lot done there, too. 

We can suggest things that might help, but really the only thing that will produce sustained, general performance increases is one or more releases dedicated to refactoring, in which Toady runs analysis tools to see what's causing slowdown and implements shortcuts in those areas. It seems like a lot of improvements could be made just with little tricks here and there, but it will take several months of development time in which no new features are introduced (although there may be new bugs!).  It's Toady's game, we can lobby for performance improvements, but Toady has to want them.

[Makbeth]

And since CPU manufacturers are now focusing more on multithreading than individual core performance, I suppose we can't even hope that it will run that much better on future computers.  Oh well.

[caknuck]

• Dungeon Master
• Bone decorations using up entire stacks

[Makbeth]

I was just trying to get around something that was fairly minor, but somewhat annoying.

You ever notice how immediately after things are made (anvils, tables, traction benches, etc) they are flagged for transport to a stockpile, even though it'll be a couple months before a dwarf actually begins the task of moving it?  All during that time, the item is unusable.  The only way to use it as soon as it is made is to forbid it and then assign it without unpausing.  Annoying but manageable for most objects, but when you need a lot of traction benches in a hurry and this is affecting your supply of tables, it's a big problem because you must unpause for some time before the mechanic will go get it, and it keeps getting reassigned to a hauling job that's several days/months away.

Of course, I'm playing 31.16, (took one look at the new embark geology interface and said "F that!") so it might have been fixed by now.  Hopefully it has been.

[Malibu Stacey]

And since CPU manufacturers are now focusing more on multithreading than individual core performance, I suppose we can't even hope that it will run that much better on future computers.  Oh well.

You couldn't be more wrong.

[Uristocrat]

I was just trying to get around something that was fairly minor, but somewhat annoying.

You ever notice how immediately after things are made (anvils, tables, traction benches, etc) they are flagged for transport to a stockpile, even though it'll be a couple months before a dwarf actually begins the task of moving it?  All during that time, the item is unusable.  The only way to use it as soon as it is made is to forbid it and then assign it without unpausing.  Annoying but manageable for most objects, but when you need a lot of traction benches in a hurry and this is affecting your supply of tables, it's a big problem because you must unpause for some time before the mechanic will go get it, and it keeps getting reassigned to a hauling job that's several days/months away.

Of course, I'm playing 31.16, (took one look at the new embark geology interface and said "F that!") so it might have been fixed by now.  Hopefully it has been.

You know, there *is* an option to allow you to up the minerals to .18 levels again.  I never have that big a problem with stockpiles, but then again, my masons make tables (and chairs, blocks, doors, etc.) on repeat so I rarely get low and I keep a large population, so haulers are abundant, too.

[Kogut]

• Clothing
• Dungeon Master & other "Baron" level nobles not appearing
• Some map generation things (high z-variance on a map causing the magma sea to drain into HFS, perfectly straight volcanoes, that sort of thing)
• Kobolds all dying of hunger 4 or 5 years into World Gen
• Bone decorations using up entire stacks
• All water in an embark being salty despite being several region tiles away from sea (affecting even water sources in mountains)
  

I added this to first post.

[ahonek]

And since CPU manufacturers are now focusing more on multithreading than individual core performance, I suppose we can't even hope that it will run that much better on future computers.  Oh well.

You couldn't be more wrong.

About what? It is the case that CPU manufacturers are choosing to increase processor power by adding cores rather than increasing clock speed, and it is the case that Toady has pretty clearly stated that he's not going to move significantly to multithreading any time soon.