Print

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

[GavJ]

...well, easy to USE at least.


A 2 part solution

#1 is a UI/algorithm change: On the same screen as the UMHK when designating walls floors etc., have a 1-10 (using number keys) scale of priority you can choose as well for that block of designations. So I hit kkkkk and get a 6x1 line, and then also hit "1" and enter. Those will attempt to get built first, as if they were the only designations, and entirely completed before any designations are considered that were given a "2" or higher on the map.

Default is just "5" if you don't hit any number key, or something.

#2 is an under the hood only algorithm change: Whenever a dwarf is deciding in the code which designation order to complete first, they do the following:
1) Make a list of every construction designation that could currently be accessed (amongst those of the lowest priority assignments available, of course! See #1)
2) Amongst those, simulate building each one, and check whether doing so would prevent access to any of the others.
3) As soon as you find one where the answer is "no, it wouldn't," go ahead and choose that one to build. No need to continue checking the rest.
4) If there are no such options that don't already have a dwarf in the process of building them, then stop and check back later. No need to constantly calculate every tick if it's ready yet. It could wait until the next construction is completed on the map, to trip a flag for "okay ready to check again now everybody."




Combining the above two features would allow you to fairly easily designate huge constructions (many z levels of castle at once for instance) all at once, and have it correctly succeed in building them with no stranded dwarves or designations.  For example, let's say I want to build a 10x10x10 cube of walls.  EASY! Just U and K to make a 10x10 grid, hit priority 1, and designate the lowest floor. Then 10x10 grid hit priority 2 and designate the 2nd floor, etc. Then walk away and watch the dwarves build the whole cube with no further assistance, assuming they have stair access to all the levels. They might do it in very strange orders, but they will still do it, without getting trapped. Anything more than 10 high would require another round of designations, but come on, that's not a significant burden!

For more complicated things with, say, internal stairwalls, you may want to reserve some of the higher priorities for things like "build all the stairs first." You could also do this for a up to a 10x10x9 cube, if you reserve #1 for access stairs. The logic is pretty intuitive on how you would choose different patterns, and almost anything of a normal height can all be done in one single game pause.

The same system could also be extended to other designations like mining and channeling and deconstructing as well, of course.

[GavJ]

Addendums:

1) Actually the game should assign constructions to dwarfs, not the other way around, so it only calculates it all once. So like, check all of them 7 of the walls are reachable without blocking anything after building. Assign those 7 freely to dwarves.
2) You wouldn't re-check after each construction is finished. Only after the whole ROUND is finished. Otherwise, somebody nearby could finish another wall and block an in progress dwarf who is further away. So in the above example, all 7 have to be completed (or suspended) before it rechecks for another batch and starts assigning them.
3) The "will it block another wall" would have to take into consideration the other constructions already added to this round so far. See example below.
4) "Blocking" another tile doesn't mean blocking walking access. It means removing any adjacent-only path to it (so diagonals still allow walking but count as a "blocked path" for purposes of this algorithm.) This is usually a simple parameter option in A* path algorithms.

Example diagram. Let's say I am building a round tower like this one, in mid air above another level completed in the same shape:




Assuming all those stairways are accessible, and all these designations are currently at the highest priority level if t,he algorithm went in book-reading order, it would assign them in batches like so. Each batch complete = figure out the next batch.  You can see how #4 in the first image, for example, once chosen, stops the cell to the right of it being chosen, even though that cell wouldn't strictly block anything yet. I.e. it acts like the ones already chosen so far for that batch are built walls for purposes of deciding the next ones in the batch.

This should never result in a wall job being stranded. Dwarves being stranded could also be further improved potentially by using the information calculated by this same algorithm to determine the "not painting myself into a corner" direction to stand in.

[gritstone]

This is something I'd thought about a bit and believe it could do with some attention.  For the time being I'd be happy if dwarves stopped blocking their own construction by standing on the tile it's to be built on.

[FrankMcFuzz]

This is something I'd thought about a bit and believe it could do with some attention.  For the time being I'd be happy if dwarves stopped blocking their own construction by standing on the tile it's to be built on.

This, but I also would like to recommend some way to search for blocks to be used, to speed things up. In my current fort, I have 6 pages of building materials, and I only want the mica blocks. It's very hard to look through each page every 10 wall pieces.

But yeah, the 'Urist McMason has died of thirst: he walled himself in', 'Urist McMason canceled wall: Walled the wall in', and 'Urist McMason canceled wall: Is standing on the wall' are the biggest construction issues right now.

[GavJ]

This is something I'd thought about a bit and believe it could do with some attention.  For the time being I'd be happy if dwarves stopped blocking their own construction by standing on the tile it's to be built on.

This, but I also would like to recommend some way to search for blocks to be used, to speed things up. In my current fort, I have 6 pages of building materials, and I only want the mica blocks. It's very hard to look through each page every 10 wall pieces.

But yeah, the 'Urist McMason has died of thirst: he walled himself in', 'Urist McMason canceled wall: Walled the wall in', and 'Urist McMason canceled wall: Is standing on the wall' are the biggest construction issues right now.

Are you using the most up to date version of DF? In my version, when you choose mica blocks for a wall, the next wall you build will list mica blocks at the TOP of the materials selection screen, no matter how far away they are. It remembers what you chose last. Also, the memory is specific to each construction type (so it remembers I chose granite for down stairs but mica for walls). Yours does not do this?

[FrankMcFuzz]

This is something I'd thought about a bit and believe it could do with some attention.  For the time being I'd be happy if dwarves stopped blocking their own construction by standing on the tile it's to be built on.

This, but I also would like to recommend some way to search for blocks to be used, to speed things up. In my current fort, I have 6 pages of building materials, and I only want the mica blocks. It's very hard to look through each page every 10 wall pieces.

But yeah, the 'Urist McMason has died of thirst: he walled himself in', 'Urist McMason canceled wall: Walled the wall in', and 'Urist McMason canceled wall: Is standing on the wall' are the biggest construction issues right now.

Are you using the most up to date version of DF? In my version, when you choose mica blocks for a wall, the next wall you build will list mica blocks at the TOP of the materials selection screen, no matter how far away they are. It remembers what you chose last. Also, the memory is specific to each construction type (so it remembers I chose granite for down stairs but mica for walls). Yours does not do this?

I use the most recenty LNP. This does not happen.

[chris_strain]

Are you using the most up to date version of DF? In my version, when you choose mica blocks for a wall, the next wall you build will list mica blocks at the TOP of the materials selection screen, no matter how far away they are. It remembers what you chose last. Also, the memory is specific to each construction type (so it remembers I chose granite for down stairs but mica for walls). Yours does not do this?

I am 99.9% sure that's due to a dfhack plugin... a very, very handy plugin.

[GavJ]

OH okay yes that's definitely possible.  I don't remember activating any such plugin, though. Do some of them turn on by default?

Anyway, get dfhack then, and it will solve your woes =P

[gritstone]

Thinking about it again this has a lot going for it, though there are probably a few edge cases that might result in a massive pathfinding workload, or ridiculously inefficient paths if the algorithm isn't smart enough (or the user doesn't make it easier for the algorithm). 

Apparently I can't upload images.  Take your first image and imagine something similar with only the topmost access point.  The algorithm builds 1, 2, 3, 5, and 6 on the first round for example, but after that can only build one at a time and each one involves the longest possible route.  I'd bet someone would do the same thing with a square 150 blocks wide and wondering why the game stutters as it calculates 600 paths after each block is placed (if it's unlucky in its choices) and takes years to build.

Those are extremes though and I think on the whole it's a great idea.  Sorry if it seems like I'm always playing devil's advocate, but I can't seem to stop myself 

[GavJ]

Actually my algorithm would do 1,2,3, and 17 in the top image, if only the topmost stairs were available, since diagonal paths still count as "blocked" for the algorithm.

Thus, it would build two at a time per round wrapping left and right.  Which is AFAIK actually the fastest way to build it with only one stairwell! What would you do better as a human?

In the example I gave, it's not quite perfectly optimal, but it's only off by a round or two (12 roudns versus 10 maybe, or what have you), which I think 99.9% of people are going to be happy with as a cost of not having to micromanage. Make it a toggle option IN GAME to be safe, if you like.

I'd bet someone would do the same thing with a square 150 blocks wide and wondering why the game stutters as it calculates 600 paths after each block is placed (if it's unlucky in its choices) and takes years to build.

Surely if you have 1/10th of a brain in your skull, you'd see it sitting there building two blocks at a time, and would realize how and why it is restricted with a single staircase... That's just common sense, it's not anything weird or unexpected.

[gritstone]

Actually my algorithm would do 1,2,3, and 17 in the top image, if only the topmost stairs were available, since diagonal paths still count as "blocked" for the algorithm.

Can you explain to me how the algorithm chooses 17 over any other block?  There are dozens of combinations that don't block any paths... how is it that it just happens to choose the optimum combination first time?

Surely by the "3) As soon as you find one..." step, and going in book reading order, you would start with 1, 2, 3, 4 and the one to the right of 4, and after that you have to walk all the way round to get those the other side of 4.  Where am I going wrong?

[GavJ]

I'm sorry, you're right, actually. It would choose 1,2,3,4 and then wrap around almost entirely one-way. I confused myself for a bit.

However, you could add in another step to help it choose more optimally, by considering designations first that have the furthest city block distance from the point of access (not actual pathing, just literal distance "as the crow flies" since it's only a convenience heuristic). That'd be less than a millisecond extra calculation per round (several seconds at least realtime gameplay). Tile still has to qualify under the other conditions, but you just start far away and check based on that, instead of going in order of reading a book like in my example (which is a dumb method to use and I had it just as a placeholder).

That wouldn't always choose THE optimal tile (you can imagine weird serpentine wall shapes), but it would usually do well in the sorts of normal things people build. For example in my round tower it would indeed choose #17 then with little extra thinking.



Edit: I meant to say, "shortest as the crow flies distance from the material designated for that construction" So rank all the designations by their city block distances from their respective source materials. Just two algebraic calculations per designation based on grid coordinates, no biggie. Start checking them then beginning with the longest distance ones, as a slapdash, super cheap attempt to slightly optimize.  You can of course imagine a variety of other heuristics that could be used instead. Just an example.

[MeMyselfAndI]

Even just a high/normal/low priority would be great.

Currently I have to micromanage enabling and disabling my strip mine whenever I designate something else to be mined.

[Urist McGoombaBrother]

Are you using the most up to date version of DF? In my version, when you choose mica blocks for a wall, the next wall you build will list mica blocks at the TOP of the materials selection screen, no matter how far away they are. It remembers what you chose last. Also, the memory is specific to each construction type (so it remembers I chose granite for down stairs but mica for walls). Yours does not do this?

That's of course useful, but only to some extent. When using two, three or more specific building materials for a project, you have to constantly go through the whole ten pages of materials over and over again. Also when saving, reloading the fort, it is resetted. A possiblity to easily search for specific materials will be great - probably similar to various search options dfhack offers e.g. for stockpiles, trading, etc.

Even just a high/normal/low priority would be great.

Currently I have to micromanage enabling and disabling my strip mine whenever I designate something else to be mined.

I second this.