View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0002901 | Dwarf Fortress | Dwarf Mode -- Interface, Building Construction | public | 2010-07-30 15:07 | 2014-08-04 09:46 |
| Reporter | sparr | Assigned To | |||
| Priority | low | Severity | trivial | Reproducibility | always |
| Status | resolved | Resolution | no change required | ||
| Platform | PC | OS | Linux | OS Version | 2.6 |
| Product Version | 0.31.10 | ||||
| Summary | 0002901: Large floors use stone in inefficient order | ||||
| Description | When building a floor in a room that contains some stone of the type you are flooring with, the stone seems to be assigned to floor tiles starting in the top left, closest stone first. This leads to many canceled floor tiles that have to be uncanceled once some stone is rearranged. The desired behavior here is for tiles with stone of the appropriate type sitting on them to be assigned their 0-distance stone first (as if you had built many separate floors on just those tiles first), then other tiles to be assigned stones. | ||||
| Steps To Reproduce | Dig out a room. Build a floor in the room from the type of stone left sitting in the room during the digging. | ||||
| Tags | pathfinding, pathing | ||||
| child of | 0001463 | new | Dwarves prioritize tasks oddly |
|
|
That is how the pathing works atm, you'll see the same thing with any other large designation or task involving a large area. It'll require a pathing rewrite to fix this. |
|
|
Here's a way to lay out a block of N constructions that avoids the 0-distance problem. It doesn't require changes to pathing at all, only to how the stones are matched to constructions. * pick the closest N eligible stones to the construction centre; * sort the list of stones by ascending distance from the construction centre * for each stone in the list, assign it to the closest construction to the stone that does not yet have a stone assigned It is somewhat expensive complexity-wise (requires approx 0.5*N*N + N path distance calculations) but as N tends to be low (at most 121, IIRC) and it's a one-off cost when you place the floor not an ongoing cost, hopefully that's not too bad. If that cost is too high, then subdivide the construction area until the subareas are small enough to run the algorithm on them individually. (There might be some nasty edge-cases here that mean it doesn't quite work right, I haven't spent too much time working through examples; but I mostly wanted to respond to the assertion that "it'll require a pathing rewrite"..) |
|
|
oliver, your algorithm fails because the 'construction center' is a specific tile (the top left corner? the center?) of the overall construction. If you are building amid a large area of stone, the loose stone one tile northwest of your designation will be the 2nd stone on the list, and will be assigned to a designated tile that has stone sitting on top of it already (and that stone will get assigned somewhere else, and the problem will cascade). |
|
|
By construction center I mean the geometric center of the area designated. Because of the sorting step, in most cases all stone that overlaps the construction area will be handled before any stone outside the area. So in your example, the stone sitting on top of the designated tile will be processed (and assigned to the designated tile at 0 distance) first, before the "loose stone" is processed. This may not work in some pathological cases involving long thin areas with loose stone just outside the area's long side. It may be simpler to just have a special case for stone within the construction area. Split the list of stone into lists of "stone inside construction" and "stone outside construction area" (this should be very cheap as the area is rectangular); assign all stone in the inside-list first, then any remaining stone in the outside-list. Edit: That fails in some cases involving quantum stockpiles. Maybe the original suggestion is the simplest: do an initial pass over selected stone. For each stone, if there is a pending construction on the same tile as the stone that does not yet have a stone assigned, assign it. Once the initial pass is done, assign stones to the remaining constructions as currently happens. |
|
|
The proposed fixes seem to put this in Suggestions territory. |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2010-07-30 15:07 | sparr | New Issue | |
| 2010-07-30 15:24 | smjjames | Note Added: 0011306 | |
| 2010-07-30 15:25 | smjjames | Tag Attached: pathfinding | |
| 2010-07-30 15:25 | smjjames | Tag Attached: pathing | |
| 2010-07-30 16:35 | Logical2u | Relationship added | child of 0001463 |
| 2010-07-30 17:01 | oliver | Note Added: 0011307 | |
| 2010-07-30 17:05 | oliver | Note Edited: 0011307 | |
| 2010-07-30 17:06 | oliver | Note Edited: 0011307 | |
| 2010-07-30 17:12 | oliver | Note Edited: 0011307 | |
| 2010-07-31 01:05 | sparr | Note Added: 0011314 | |
| 2010-07-31 15:50 | oliver | Note Added: 0011340 | |
| 2010-07-31 16:14 | oliver | Note Edited: 0011340 | |
| 2014-08-04 09:46 |
|
Note Added: 0028283 | |
| 2014-08-04 09:46 |
|
Status | new => resolved |
| 2014-08-04 09:46 |
|
Resolution | open => no change required |
| 2014-08-04 09:46 |
|
Assigned To | => user6 |
