0002901: Large floors use stone in inefficient order

Notes
(0011306) smjjames (reporter) 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 (reporter) 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.5NN + 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 (reporter) 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 (reporter) 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 (manager) 2014-08-04 09:46	The proposed fixes seem to put this in Suggestions territory.

Issue History
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	View Revisions
2010-07-30 17:06	oliver	Note Edited: 0011307	View Revisions
2010-07-30 17:12	oliver	Note Edited: 0011307	View Revisions
2010-07-31 01:05	sparr	Note Added: 0011314
2010-07-31 15:50	oliver	Note Added: 0011340
2010-07-31 15:50	oliver	Issue Monitored: oliver
2010-07-31 16:14	oliver	Note Edited: 0011340	View Revisions
2014-08-04 09:46	Footkerchief	Note Added: 0028283
2014-08-04 09:46	Footkerchief	Status	new => resolved
2014-08-04 09:46	Footkerchief	Resolution	open => no change required
2014-08-04 09:46	Footkerchief	Assigned To	=> Footkerchief