Disconnected dungeon generation

[Hariolor]

I am intrigued by the novel idea of cordoned-off areas requiring tunnels to escape. Makes picks of digging seem remotely useful, and stone-to-mud good for something other than building ASCs.

FWIW, I'd say to make the starting room be guaranteed a path to >, and maybe even make disconnected rooms/vaults more likely...

[Zikke]

Disconnected vaults off in the middle of the rock make a lot of sense and would be a really fun addition. Random disconnected rooms not so much; it seems like a vault (like a tomb) wouldn't have a nice logical path to it all the time.

[Pete Mack]

Disconnected vaults off in the middle of the rock make a lot of sense and would be a really fun addition.

LOL!
You are so right, that would be a great "addition" to the game.

[andrewdoull]

Qualifies as bug. That shouldn't happen.

Doesn't qualify as a bug as there is nothing in the dungeon generation routine to prevent it from happening.

Andrew

[Nick]

FA does this all the time, I kinda like it.

Really ?

[buzzkill]

Really ?

Yep, maybe not entire rooms, but often little nooks get cut off from the little dungeon forested areas. Sometimes bigger chunks, sometimes containing items. I'm not sure about standard rooms being disconnected.

Also, stairs from the wilderness into the dungeon used to appear imprisoned in rock, but you probably already fixed that.

[RogerN]

It looks like the tunneling code had a difficult time connecting those two rooms because of the adjacent outer walls. The algorithm avoids tunneling through two adjacent outer walls in order to prevent tunnels from entering a room at a corner.

There are other ways that a tunnel could have potentially connected the rooms, but since the algorithm is a semi-directed random walk rather than a true pathfinder, it does not exhaust all possibilities.

This case is rare enough that's probably not worth fixing. The only 100% certain way to fix something like this is the change the tunneling algorithm to use a real pathfinder (such as Cryptband uses) and to ensure a minimum 1-tile gap when placing rooms next to each other. The drawbacks, which are additional code complexity and performance hits during dungeon generation, outweigh the benefits since Vanilla doesn't require connectivity.

[fizzix]

This case is rare enough that's probably not worth fixing.

Yay for thread necromancy:

I now have an answer to how rare.

There are two ways for the dungeon to be disconnected from a wandering, non-digging (except through rubble and stuck doors) character. By far the most common disconnects are caused by GVs without a passable outer moat. Even these are fairly rare. Total disconnects come in between 0.1 and 1 % at dlevel 98. Of these disconnects, about 5% leave the player isolated from any downstairs based on his randomized starting position. Hopefully a player will have some escape or teleporting option by the time they are hitting GVs...

Now these dungeons aren't the fault of the generating algorithm. If anything they are the fault of vault designs that do not have moats. More interesting, are cases where the dungeon has a single room or a group of rooms disonnected from the rest of the dungeon. We can examine these cases by simulating dlevel 1, where GV cases are likely to be rare.

All numbers quoted below are in occurances per million. Warning: stats below!

at dlevel 1:

173 levels that had a disconnected region.
7 levels that started the player disconnected from any down stairs. (only down stairs were considered because this simulates the ironman perspective).

7 in a million...pretty long odds indeed.

Looking at dlevel 10 where GVs are rare but not unheard of, but a player may still not be in possession of teleport, we see:

949 levels had a disconnected region.
34 levels had the player disconnected from any down stairs.

at dlevel 98 where GVs are common
74526 levels had disconnected areas
4974 had the player isolated from the stairs.

at dlevel 98 where all vaults were turned off (but special rooms still allowed)
4278 levels had disconnected areas
159 had players isolated from stairs

It looks like that special rooms are something like a factor of 10 more likely to be disconnected than normal rooms. Still nothing compared to what vaults can do.

[Magnate]

Yay for thread necromancy:

I now have an answer to how rare.

There are two ways for the dungeon to be disconnected from a wandering, non-digging (except through rubble and stuck doors) character. By far the most common disconnects are caused by GVs without a passable outer moat. Even these are fairly rare. Total disconnects come in between 0.1 and 1 % at dlevel 98. Of these disconnects, about 5% leave the player isolated from any downstairs based on his randomized starting position. Hopefully a player will have some escape or teleporting option by the time they are hitting GVs...

Now these dungeons aren't the fault of the generating algorithm. If anything they are the fault of vault designs that do not have moats. More interesting, are cases where the dungeon has a single room or a group of rooms disonnected from the rest of the dungeon. We can examine these cases by simulating dlevel 1, where GV cases are likely to be rare.

All numbers quoted below are in occurances per million. Warning: stats below!

at dlevel 1:

173 levels that had a disconnected region.
7 levels that started the player disconnected from any down stairs. (only down stairs were considered because this simulates the ironman perspective).

7 in a million...pretty long odds indeed.

Looking at dlevel 10 where GVs are rare but not unheard of, but a player may still not be in possession of teleport, we see:

949 levels had a disconnected region.
34 levels had the player disconnected from any down stairs.

at dlevel 98 where GVs are common
74526 levels had disconnected areas
4974 had the player isolated from the stairs.

at dlevel 98 where all vaults were turned off (but special rooms still allowed)
4278 levels had disconnected areas
159 had players isolated from stairs

It looks like that special rooms are something like a factor of 10 more likely to be disconnected than normal rooms. Still nothing compared to what vaults can do.

Very interesting stats. I wonder why there is a 5x jump between levels 1 and 10. It seems clear that GVs account for about 90% of cases of disconnectedness.

Presumably, now you have coded the test for disconnectedness (i.e. starting location not connected to down stairs), we can include it in generate.c and ensure that those seven in a million ironmen can still reach the stairs ...

[Derakon]

Thanks, Fizzix. It's neat to see this information.

Given that the last time I saw a disconnected dungeon, the disconnected portion consisted of a troll pit, it's pretty clear that special rooms can occasionally break connectivity, as you discovered with the "no vaults" test. This might well be worth trying to fix. I'm not so worried about the moatless greater vaults, though; Great Checkerboard Vaults just wouldn't be the same if you didn't have to tunnel to get to them.

[fizzix]

Very interesting stats. I wonder why there is a 5x jump between levels 1 and 10. It seems clear that GVs account for about 90% of cases of disconnectedness.

Presumably, now you have coded the test for disconnectedness (i.e. starting location not connected to down stairs), we can include it in generate.c and ensure that those seven in a million ironmen can still reach the stairs ...

What should be done is check for connectivity to down stairs. If none are accessible, move the player to a new location. The check for connectivity is quicker than new dungeon generation. This can be adapted immediately, and I could add it to generate.c (instead of having it stuck in my wiz-stats file.) without too much trouble.

But since this is a 1 in 100000 problem, it might be worthwhile to consider updating cave->flow to an int that encompasses the entire accessible region of the dungeon. What I now have is a dungeon sized array that tracks how many movements it takes @ to reach it. (I think this is what cave->flow is for, but honestly, I couldn't understand the code) We should then be able to use an updated cave->flow to check for connectivity, and do other things as well. Monsters already use cave->flow to move, but it doesn't seem to be working properly, this can be improved:

Monsters like Sauron can track @ down across the entire dungeon.
You can track monster awareness, not by raw distance to player, but by the value of the square it is on.
Following up on the above. A monster that is more than max-movable-squares away will not wake up, even if they are on the opposite side of a granite wall.
Monsters that are awake but are too far away from the player (like TOed monsters) can do random motions, perhaps vaguely in the direction of the player)
You can put bounds checks for pass/eat wall monsters, or improve their algorithm for dealing with permanent walls. (A secondary cave->flow that only considers permanent walls as barriers.)
Detections can be gerrymandered to fit the dungeon instead of some arbitrary region of space. (You detect all monsters within 50 walkable squares from your current location.)
ESP can be the same. (pass wall monsters become brutal)

Really the fact that we're not using cave->flow more than we are is kind of mysterious... I'm guessing it's because most people don't know it's there, or like me, couldn't figure out what exactly it was doing.

One of the big obstacles to all this is....rubble. Goddamn rubble. An impossible barrier to monsters, but really not much of a barrier to players. (well, closed doors to monsters without open/bash doors, but I'm not worried about them having shitty pathfinding)

[PowerDiver]

One of the big obstacles to all this is....rubble. Goddamn rubble. An impossible barrier to monsters, but really not much of a barrier to players. (well, closed doors to monsters without open/bash doors, but I'm not worried about them having shitty pathfinding)

That's so funny. I think rubble is the solution rather than the problem. Some day I plan to add a phase to dungeon generation that connects everything, including vault chambers, by converting walls into rubble. This seems like a necessary first step before implementing the radical approach of eliminating diggers and stone-to-mud.

[fizzix]

That's so funny. I think rubble is the solution rather than the problem. Some day I plan to add a phase to dungeon generation that connects everything, including vault chambers, by converting walls into rubble. This seems like a necessary first step before implementing the radical approach of eliminating diggers and stone-to-mud.

It's a problem only in that it makes paths asymmetrical from player and monster perspectives. So it's a problem only for calculation of paths and using them for both sound/wakening/detection and monster pathfinding. For gameplay purposes, I agree that rubble paths should be made to vault entrances, and all granite walls (that you're supposed to dig through) should be rubble. But I don't feel strongly enough about it to make the change.

If you wanted proper pathfinding you would need 4 different connectivity charts.

1: only permanent walls are boundaries (path chart for pass-wall monsters)
2: permanents walls, granite walls, magma, quartz are boundaries (path chart for player)
3: all walls and rubble are boundaries (path chart for non pass-wall monsters)
4: all walls, rubble and close doors are boundaries (path chart for monsters without open-door)

Calculating all 4 of these on every player move or terrain change may be burdensome time-wise. I'd go for just calculating No. 2 on every move, and calculating No. 1 only if there's a pass wall monster in the vicinity. And let monsters have their path-finding algorithms get screwed by rubble.

Now if earthquakes/destruction were modified to produce lots of rubble, then we'd need 3 also. Right now, rubble is rare enough that it doesn't matter.

[Magnate]

It's a problem only in that it makes paths asymmetrical from player and monster perspectives. So it's a problem only for calculation of paths and using them for both sound/wakening/detection and monster pathfinding. For gameplay purposes, I agree that rubble paths should be made to vault entrances, and all granite walls (that you're supposed to dig through) should be rubble. But I don't feel strongly enough about it to make the change.

If you wanted proper pathfinding you would need 4 different connectivity charts.

1: only permanent walls are boundaries (path chart for pass-wall monsters)
2: permanents walls, granite walls, magma, quartz are boundaries (path chart for player)
3: all walls and rubble are boundaries (path chart for non pass-wall monsters)
4: all walls, rubble and close doors are boundaries (path chart for monsters without open-door)

Calculating all 4 of these on every player move or terrain change may be burdensome time-wise. I'd go for just calculating No. 2 on every move, and calculating No. 1 only if there's a pass wall monster in the vicinity. And let monsters have their path-finding algorithms get screwed by rubble.

Now if earthquakes/destruction were modified to produce lots of rubble, then we'd need 3 also. Right now, rubble is rare enough that it doesn't matter.

Surely the solution is to let all monsters ignore rubble?? Then it simply blocks LOS but not movement.

[fizzix]

Surely the solution is to let all monsters ignore rubble?? Then it simply blocks LOS but not movement.

I'm not opposed to that at all. Or do like DJA does and allow monsters (and players) to climb over rubble.