Over-engineering dungeon generation

[buzzkill]

Rounded corners. Awesome!

[rdermyer]

That looks very slick!

[Pete Mack]

Waaaay back when I tried D&D, and soon realized that the easiest trap for a novice DM to fall into is to provide too many targets, or too many rooms.

A level should satisfy the following invariants:
1. Provide enough targets for reasonable advancement at corresponding cl (for Angband, this is cl=dl/2).
2. Not allow significant further character advancement without repeating levels
3. Provide a reasonable barrier to further progress into the dungeon, but not so much as to make progress tedious.

Some immediate corolaries include:
* Don't make too many rooms, as mapping quickly gets boring.
* Don't mMs too few rooms, as it makes powerdiving too easy. (there needs to be some risk in getting ti the next stairs down.)
* Keep your dungeon topology simple. If I want a maze, I'll find a cornfield somewhere.

The map you posted first is very cool, but as a player I'd rather stick to the angband default.
If you want to penalize diving, Unangband has some additional heuristics to make diving more dangerous, without adding more rooms or complexity to the map

[RogerN]

Originally Posted by Pete Mack

Waaaay back when I tried D&D, and soon realized that the easiest trap for a novice DM to fall into is to provide too many targets, or too many rooms.

I've definitely backed off from my original idea, which was to create one giant dungeon level with all the varying difficulty zones separated by gates. Three hundred rooms packed into a level certainly looked impressive, but it was a major hassle to explore even without being populated by monsters.

The most recent changes to dungeon generation have come about because of my switch to using 32x32 tiles. Screen real estate is now at a premium, so I've reduced the average size of most rooms to compensate. I don't think the larger rooms affected gameplay much anyway since players tend to do all their fighting in corridors.

Ultimately I'll probably end up with levels which are about the same size as Vanilla. Rooms tend to be more interconnected than Vanilla's, though, due to how corridors are generated.

[Pete Mack]

Originally Posted by RogerN

Ultimately I'll probably end up with levels which are about the same size as Vanilla. Rooms tend to be more interconnected than Vanilla's, though, due to how corridors are generated.

this sounds potentially good--higher connectivity means more monsters can chase you. One suggestion: make stairs down tend to be far away from the dungeon entry point.

[RogerN]

It's been a while since my last update, mostly due to the birth of my daughter. Coding time is scarce indeed, but work has resumed.

First of all, I've made changes to how doors are handled, both in terms of gameplay and dungeon generation. I decided that the lock-picking system and searching system of Vanilla are flawed, as evidenced by recent changes to searching. Why should this even be necessary? I don't think searching and lock-picking should be random. Either you're skilled enough or you're not - there should be no need spam the 's' key or repeatedly try to pick a lock.

Instead, I've decided that locked doors and secret doors will have a random difficulty associated with them. If your skill exceeds the difficulty then you succeed on the first attempt. Otherwise you will never be able to find the door or pick the lock, so you might as well stop trying - at least until your skill improves. I think this change will actually reduce player frustration.

As a consequence of the above, it's now necessary to ensure that an unobstructed path always exists from the level's starting point to the next staircase, as players could otherwise become stuck behind secret doors which are impossible for them to find. Thus we're finally back on topic: over-engineering dungeon generation!

In order to ensure connectivity and playability of each level, the following steps are taken:

- Instead of generating random door types to start with (open, closed, broken, secret, jammed, locked, etc...), all doors are created as normal, closed doors

- After rooms and tunnels have been created, doors are used to divide the dungeon into several walkable zones. The zones are assembled into a graph structure which tracks which zones are adjacent. Internal doors (i.e. doors inside vaults) are ignored for purposes of diving zones.

- A starting zone and a destination zone are randomly chosen, with preference given to locations which are far apart. These zones will eventually hold staircases to the previous/next level.

- Doors are then randomized. Dead-end zones have an increased chance to use secret doors. All potentially impassable doors (locked, secret) must pass a connectivity check, or the door must remain passable (open, broken, closed). The zone graph structure is used to ensure that a path still exists between the starting zone and the destination zone.

There is at least one other issue to consider. Teleportation effects (?Phase, ?Teleport, etc...) must never place the player in a section of the dungeon which is walled off by locked or secret doors.

A color-coded screenshot of how the zones are divided is attached.

[RogerN]

The previous screenshot was a little small, so I enlarged it.

[Nick]

Originally Posted by RogerN

It's been a while since my last update, mostly due to the birth of my daughter.

N:1:Firstborn child
G:t:w
I:110:1d4:4:2:40
W:0:3:0:0
B:CRY
B:DROOL
B:EAT_TIME
F:FEMALE | MOVE_BODY | FRIEND | TAKE_ITEM 
D:She looks gorgeous.

[ekolis]

Ooh, that looks very dungeony, as if it was built not entirely haphazardly as the Angband dungeons are, but not entirely planned as a single ginormous vault would be... your dungeon looks more like something where they dug one type of room, then realized they needed another, so they added it on, and so forth, much like a city would grow organically

[RogerN]

How *not* to make significant progress: get bogged down implementing a bunch of random tiles and decorations before the core gameplay is finished

There are three distinct room "styles" now: plain boring dungeon, dark brick dungeon, and wooden dungeon. There are random bits of moss, implemented as streamers, to add some atmosphere (seen in the top of the screenshot), and there are also occasional blood stains on the walls. Some of the doors are randomly generated as gates, which do not block LOS and allow arrows/bolts to pass through them.

There are also tiles for windows, fountains, statues, and columns, but the dungeon generator isn't placing any of these guys yet. I haven't come up with a satisfying method of placing those sorts of items yet. Suggestions are welcome!

The overhead map window is also functioning now, although it doesn't show monsters or items.

Screenshot