Dwarf Fortress Bug Tracker - Dwarf Fortress
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0002901Dwarf FortressDwarf Mode -- Interface, Building Constructionpublic2010-07-30 15:072014-08-04 09:46
Reportersparr 
Assigned ToFootkerchief 
PrioritylowSeveritytrivialReproducibilityalways
StatusresolvedResolutionno change required 
PlatformPCOSLinuxOS Version2.6
Product Version0.31.10 
Target VersionFixed in Version 
Summary0002901: Large floors use stone in inefficient order
DescriptionWhen 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 ReproduceDig out a room.
Build a floor in the room from the type of stone left sitting in the room during the digging.
Additional Information
Tagspathfinding, pathing
Relationships
child of 0001463new  Dwarves prioritize tasks oddly 
Attached Files
Issue History
Date ModifiedUsernameFieldChange
2010-07-30 15:07sparrNew Issue
2010-07-30 15:24smjjamesNote Added: 0011306
2010-07-30 15:25smjjamesTag Attached: pathfinding
2010-07-30 15:25smjjamesTag Attached: pathing
2010-07-30 16:35Logical2uRelationship addedchild of 0001463
2010-07-30 17:01oliverNote Added: 0011307
2010-07-30 17:05oliverNote Edited: 0011307bug_revision_view_page.php?bugnote_id=0011307#r4423
2010-07-30 17:06oliverNote Edited: 0011307bug_revision_view_page.php?bugnote_id=0011307#r4424
2010-07-30 17:12oliverNote Edited: 0011307bug_revision_view_page.php?bugnote_id=0011307#r4425
2010-07-31 01:05sparrNote Added: 0011314
2010-07-31 15:50oliverNote Added: 0011340
2010-07-31 15:50oliverIssue Monitored: oliver
2010-07-31 16:14oliverNote Edited: 0011340bug_revision_view_page.php?bugnote_id=0011340#r4446
2014-08-04 09:46FootkerchiefNote Added: 0028283
2014-08-04 09:46FootkerchiefStatusnew => resolved
2014-08-04 09:46FootkerchiefResolutionopen => no change required
2014-08-04 09:46FootkerchiefAssigned To => Footkerchief

Notes
(0011306)
smjjames   
2010-07-30 15:24   
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.
(0011307)
oliver   
2010-07-30 17:01   
(edited on: 2010-07-30 17:12)
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"..)
(0011314)
sparr   
2010-07-31 01:05   
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).
(0011340)
oliver   
2010-07-31 15:50   
(edited on: 2010-07-31 16:14)
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.
(0028283)
Footkerchief   
2014-08-04 09:46   
The proposed fixes seem to put this in Suggestions territory.