Dwarf Fortress Bug Tracker - Dwarf Fortress
View Issue Details
0010838Dwarf FortressPathfindingpublic2018-07-16 18:582022-09-24 03:55
eternaleye 
lethosor 
normalminoralways
acknowledgedopen 
x86_64Exherbo LinuxN/A
0.44.12 
 
0010838: Constructed floors and walls, as well as digging, break pathfinding on 16x16 embarks
On a 16x16 embark, any constructed wall or floor will cause its own tile and all directly adjacent tiles to become part of pathfinding group 1 (as tested with dfhack's gui/pathable). This isolates them from the rest of the map, breaking pathfinding.

In a likely-related issue, newly dug (d-d) tiles receive a unique pathfinding group ID per tile, though surrounding tiles are unaffected.

This occurs regardless of where in the embark the construction is performed (tested at the center and all four corners), where in the world map the embark is performed (tested two locations, one north-east-ish and one south-west-ish, on a 257x257 map), and does not occur on a 2x2 or 2x16 embark.

The broken pathfinding groups can be fixed by saving and loading, however the issue will recur with any subsequent construction or excavation.
1. Perform a 16x16 embark
2. Construct a large wooden floor
3. Watch dwarves get trapped; optionally use gui/pathable to inspect the floored tiles.
Many thanks to lethosor for helping me debug this on IRC
0.47.03, 0.47.04, 0.47.05
has duplicate 0010205resolved Loci Constructs break pathfinding on very large embarks 
has duplicate 0011158resolved Loci (Lazy Newb Pack 0.44.12 r2) My Dwarfs Pathing AI seemed to be a bit Confused. 
has duplicate 0011180resolved Loci Path not found in an open room 
Issue History
2018-07-16 18:58eternaleyeNew Issue
2018-07-16 19:00eternaleyeNote Added: 0038606
2018-07-16 19:05lethosorAssigned To => lethosor
2018-07-16 19:05lethosorStatusnew => acknowledged
2018-07-18 08:32eternaleyeNote Added: 0038612
2018-07-18 08:51eternaleyeNote Edited: 0038612bug_revision_view_page.php?bugnote_id=0038612#r15701
2018-07-18 09:11eternaleyeNote Edited: 0038612bug_revision_view_page.php?bugnote_id=0038612#r15702
2018-07-18 10:21eternaleyeNote Edited: 0038612bug_revision_view_page.php?bugnote_id=0038612#r15703
2018-07-18 15:41eternaleyeNote Edited: 0038612bug_revision_view_page.php?bugnote_id=0038612#r15704
2018-07-18 17:09eternaleyeNote Edited: 0038612bug_revision_view_page.php?bugnote_id=0038612#r15705
2018-07-18 17:38eternaleyeNote Edited: 0038612bug_revision_view_page.php?bugnote_id=0038612#r15706
2019-03-02 11:42LociRelationship addedhas duplicate 0010205
2019-10-07 13:52LociRelationship addedhas duplicate 0011158
2019-10-07 13:54LociNote Added: 0039535
2019-11-20 13:08LociRelationship addedhas duplicate 0011180
2020-02-28 05:22Sarmatian123Note Added: 0040250
2020-02-28 05:24Sarmatian123Tag Attached: 0.47.03
2020-02-28 05:26Sarmatian123Issue Monitored: Sarmatian123
2020-02-29 00:28Sarmatian123Note Added: 0040266
2020-02-29 04:19FantasticDorfNote Added: 0040267
2020-02-29 08:44Sarmatian123Note Added: 0040268
2020-03-01 03:02Sarmatian123Note Added: 0040274
2020-03-01 03:02Sarmatian123Tag Attached: 0.47.04
2020-03-01 04:19FantasticDorfNote Added: 0040276
2020-03-01 06:47Sarmatian123Note Added: 0040277
2020-03-01 07:47Sarmatian123Note Added: 0040279
2021-05-09 11:13SpikyNote Added: 0041049
2021-05-09 18:29SpikyTag Attached: 0.47.05
2022-09-24 03:55Man of LettersNote Added: 0041327
2022-09-24 03:56Man of LettersNote Edited: 0041327bug_revision_view_page.php?bugnote_id=0041327#r16841
2022-09-24 04:53Man of LettersNote Edited: 0041327bug_revision_view_page.php?bugnote_id=0041327#r16842

Notes
(0038606)
eternaleye   
2018-07-16 19:00   
Note - if gui/pathable is used, a single floored tile is sufficient to demonstrate the issue (as it's directly observable, rather than indirectly via trapped dwarves)
(0038612)
eternaleye   
2018-07-18 08:32   
(edited on: 2018-07-18 17:38)
Further testing has revealed that there's at least some influence from worldgen parameters. Attempting 17x17 and 257x257 worlds with otherwise baseline parameters using simple worldgen did not reproduce the issue, but using the same worldgen parameters as I originally encountered the issue in to generate a completely vanilla world (no tileset, no DFHack) did reproduce it. The worldgen parameters are at the bottom of this note; I'll continue trying to reduce the testcase.

EDIT: That was more text than expected; here are the _differences_ vs. LARGE REGION instead. Note that DF loads this as having random seeds, but the world was generated with the empty string as all seeds.

EDIT 2: The *_FREQUENCY, MINERAL_SCARCITY, {SEMI,}MEGABEAST_CAP, *_SQ_COUNTS, and PARTIAL_OCEAN_EDGE_MIN settings do not have any effect on this bug.

EDIT 3: The REGION_COUNTS:*, TOTAL_CIV_NUMBER, and *_RANGES settings do not have any effect on this bug.

EDIT 4: The seeds, BEAST_END_YEAR, POLE, and LEVELS_ABOVE_{GROUND,LAYER_1,LAYER_2} settings do not have any effect on this bug.

EDIT 5: A pocket region with [LEVELS_AT_BOTTOM:25] reproduces the issue; seeing where the tipping point is.

(0039535)
Loci   
2019-10-07 13:54   
D_Crypt posted an 8x9 embark that exhibits this problem in 0011158:

http://dffd.bay12games.com/file.php?id=14557 [^]
(0040250)
Sarmatian123   
2020-02-28 05:22   
The issue still exists on largest embarks in 0.47.03 with large surface bunker-construction. It applies both to constructing jobs and digging. Dwarves become idle standing for long time, despite need to sleep, drink or eat. Player is being spammed with "can't give water" and "item for eating is inaccessible".

The bug, in my game, starts after Human Caravan in summer of 3rd year old embark is packing and leaving the Trading Depot. So I suspect the caravan is the guilty party. It is sorrowfully repeatable. I am considering killing the caravan and starting war with humans, because this bug makes continuous building and continuous digging impossible without frenzy of reloads. Though, I could load an older game-save and simply block access to my Trade Depot for all caravans for ever.

My guess is, that the Dijkstra path-finding algorithm for sake of efficiency was badly optimized or is badly implemented for largest embarks. Floyd-Warshall parallel algorithm, for finding all points-pairs shortest distances, which is using GPU, solves the re-computing all paths issue under 1 second, when terrain changes for any whatsoever reason.
(0040266)
Sarmatian123   
2020-02-29 00:28   
http://dffd.bay12games.com/file.php?id=14875 [^]

Merchant caravan causes it. Load the save. Build a line of wall. It constructs fine. Wait for merchants to pack their stuff and leave trade depot. Repeat construction job. Watch Dwarves glued to positions next to the newly constructed wall. After a longer while, some Dwarves will try to break out by jumping over the new constructed wall. Wait for all human caravan to leave map. Save and load game a new. It removes the bug, but try to dig a channel 40x10. Dwarves stop digging after breaking out stone in the first line of the dig. To dig it clear, takes 40 game saves and reloads. Digging for magma is a digging job for 100 levels, so it will take 100 game reloads. This bug makes Dwarf Fortress totally unplayable.

Embark is created on DF 0.44.12.
Game is played from year 05 to year 08 on DF 0.47.03

The only odd thing with this human merchant caravan is, that one merchant animal sticks out of the trade depot, after arriving.No earlier Human, Dwarven or Elven trade caravans were causing this bug. This bug makes Dwarf Fortress unplayable.
(0040267)
FantasticDorf   
2020-02-29 04:19   
Reading through @Sarmartian123's comments, a recommendation would be to give caravan trade depots more internal space or surface area to work with, to see if it resolves the problem, i've personally seen large offering & profit swollen caravan convoys express the single animal or multiple animals poking out on smaller/default 4x4 size embarks without a obvious issue.

Other unhelpful pathing problems with merchants to make them difficult is that the animals & merchants are the only units to willingly lie down when not unconcious or injured/incapable in fort mode, the animals lie down when unloading/loading and both the merchants and animals also lie down when mentally stressed 0007619 , if lying down makes them chew up the algorithmn bandwidth then it'd be plausible.

@Samaritan123 i would recommend repeating the test in a previous/alternative save whilst the traders are still trading and deconstruct the depot underneath them to force them to leave with a empty inventory ending commitment to see if its specific to the loading & movement process.
(0040268)
Sarmatian123   
2020-02-29 08:44   
http://dffd.bay12games.com/file.php?id=14877 [^]

I reloaded game from a save taken before merchants arrive. No bug this time, when merchants left the Trade Depot. However there are still 3 caravan guards left on map, when this inaccessible terrain bug strikes again! IMHO Human merchant caravan somehow has to be causing it. They had plenty of cargo space on wagons, when they left. No animal was sticking out from Trade Depot this time. This is a bugged save. Loading it, will clear the bug temporarily. Digging and building floors/walls will cause it again. What a nasty bug.
(0040274)
Sarmatian123   
2020-03-01 03:02   
I dismantled Trade Depot. Human Wagons did not spawn. However 3 merchants with 3 escorts still spawned.

"The merchants need a trade depot to unload their goods."

Why? Why this *** still spawns on my embark?

At the end comes the long awaited message:

"The merchants from Gil Us have embarked on their journey."

Really? Why despite being just 1 tile away from map's edge these merchants still sit there for 14 more days? On 12th leaves one. On 14th leaves second. Last one still refuses to leave and guess what, the bug happens then and there all over again!

The bug wrecks construction and digging! Should I upload this bugged save too?

Constructing Dwarves get glued to their positions by the freshly constructed floors. Floors! Not even walls, but floors!

The miners can not approach the place of digging, because dug out places are marked "unreachable" and block further mining behind them.

Why there is no setting in noble menu for trader to turn this bloody trading off?

The only thing I didn't try is to kill Human Trading Caravan, but then next month is oh joy, the Dwarven Trading Caravan and Diplomat Diplomat too... Should I try to kill them all and check if that solves the bug?
(0040276)
FantasticDorf   
2020-03-01 04:19   
Thanks for testing that, it gives us more information to work with and no need to panic or be frustrated although those feelings might come naturally.

I booted up the save myself and noticed a lot of places where FPS rather than pathing can sink, maybe your user experience is different to mine (and im not dismissing your issue report, im just making a note of the lag). Infact i could barely run the save on my own hardware, it will be Autumn within the next month which creates a big cascade of leaves from the densely wooded area around your site which could throttle a impressive fortress like yours.

There is also a very large stairwell, two 11x3's and a regular 3x3 central staircase that is going to absolutely wreack havoc on your FPS and likely contribute to the problem when large numbers of dwarves are required on the surface moving between them, especially diagonally to get closer to their target site.

Talking back to pathing, other miscallenous notes about the plant-life is that you dont have a consistent road for the merchants to travel across meaning they have to navigate additional turns & weaving routes through the overgrowth rather than a direct route to map edge which might exacerbate it a little.

Im not being critical but its helpful to point these things out to see if this problem can be mitigated for you through active changes, like you described the length of time to do things before the merchants arrive is considerable.
(0040277)
Sarmatian123   
2020-03-01 06:47   
My desktop's CPU is quad I7 4GHz plus 16 Gb memory. Specially bought to enjoy Dwarf Fortress. :)

Screen is freezing for a while, but only sometimes. Nothing worrisome. The medium speed is still around 19-26 FPS, which is very good speed for an embark with constructed surface tower. The freezes happen only during some months. I guess, it has something to do with the river and land animals.

Actually, large radiant stairwells 11x3 speed up FPS. Calculated path between floors takes less time. It also offloads quite a lot of traffic from central 3x3 staircase. When you run Dijkstra algorithm from two points, then sooner those points meet, the sooner CPU is free. Without those large radiant stairs the floors will act essentially as big inhibiting walls. Walls cause lag. I did experiment with quite few tower designs. Radiant staircase 11x3 design is a particular success of mine on easing FPS lag tbh. Less walls = less lag.

Whatever I do in this game, the merchants leaving the map seems to be trigger for this bug.

Upon reloading, to remove the bug temporarily, I have consistently 2 error messages "Connected Component Overflow". However when I played the game for 3 years of embark, there were like 50 "Connected Component Overflow" error messages swapping with other 50 "removed erroneous unit occupancy flag" without any construction or dig site being bugged. Maybe upon reload "removed erroneous unit occupancy flag" is not done somewhere and this causes the bug to repeat? Just a guess.
(0040279)
Sarmatian123   
2020-03-01 07:47   
I also suggest following change for this bug description:

Severity: minor -> game breaking / game ending
(0041049)
Spiky   
2021-05-09 11:13   
I'm observing this in 0.47.05. My embark is a more reasonable size, and my fort only recently began exhibiting this behaviour - occasionally, usually (maybe always) next to new construction, cells will switch to pathing group 1 and become inaccessible to the main fort.

I'm using the x86-64 version on Debian stable. When I first noticed the bug, I had no active mods; however, some ingame years ago my compressed save got corrupted and I brute-forced it. (The script I used is here: https://spikycaterpillar.com/spiky_df_uncorruptor/ [^] ). This save is the one I made before adding dfhack.

To reproduce: Load this save. Follow Meng Sazirilash the surgeon. He's on his way to build a quartzite floor. After he completes the floor, both the new floor and the section he's standing on get reassigned to pathing group 1 and he can no longer find the rest of the fortress.
https://dffd.bay12games.com/file.php?id=15525 [^]

Construction tends to trigger the conversion of cells to pathing group 1; however, I don't think it always happens. Saving and reloading corrects the pathing groups, though new construction continues to put cells into pathing group 1. Occasionally I believe cells that were inaccessible have spontaneously become pathable again. Dwarves who are stuck in unpathable cells long enough will eventually start climbing towards normal parts of the fortress (which I believe is why the cavern pool is full of corpses, because they appear to have all decided that a locked trapdoor near the top of the cavern was MUCH more interesting than trying to get back to the wall-construction scaffold nearby.

I've had promising early results using dfhack to CHANGE the pathing group of afflicted cells - changing all group 1 cells that *have a dwarf in them* to group 34 will let the dwarves start walking, but so far I haven't managed to get a full workaround working.
(0041327)
Man of Letters   
2022-09-24 03:55   
(edited on: 2022-09-24 04:53)
I have a similar issue. Save available. Embark 11x11 or something like that. No special parameters anywhere. Very early in the game. No migrants nor caravan. Upon breaching the cavern with a staircase reaching the cavern floor, I construct an up staircase in place of an up-down staircase, one level above the caverns. Pathing group changes to 1 for that tile and one tile above. The caverns and the rest of the fortress share group 58. After reload, it gets back to normal and cavern is cut off, while all of the fortress, including the constructed up stairs, is in a single distinct pathing group. Looks like a bug in updating pathing information when stuff is constructed, in some special circumstances.

Probably irrelevant additional info: the stairs up is constructed when standing on it or perhaps also above it, but using a boulder from a position below (from the up-down staircase that touches cavern floor). Edit: and I'm on ancient Ubuntu Linux, running with self-compiled LNP package.