Over-engineering dungeon generation

[RogerN]

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

[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.

[Pete Mack]

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]

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]

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

[rdermyer]

That looks very slick!

[buzzkill]

Rounded corners. Awesome!

[RogerN]

Work continues! I took some time off from boring tasks (status effects, UI stuff) to tackle a first-pass at town generation. None of the shops are functional yet, but the town looks pretty nice (by Angband standards I guess):

Town Screenshot - First Draft

Shops are generated in random locations, along with a couple of farm plots. All the shops are connected by dirt paths. Perlin noise is used to generate some forests. No water yet, but that's easily doable later.

[RogerN]

I have plans for secret doors If all goes according to plan, part of my dungeon creation routine will be connectivity analysis. The game will look for small dead-end rooms to use as treasure rooms, and the secret doors would occasionally be placed there. Of course, there might occasionally be an out-of-depth monster also.

Another idea I had was to have larger dungeons with varying levels of difficulty on single dungeon level, and special gates dividing the difficulty levels. Players would have to find the key (or pick the lock, or blast it with magic) in order to progress to the next area. That's not to say that the dungeon would be linear; there might be several paths from the level 1 area to the level 2 area, but all would be sectioned off by a gate which needs that key.

If I can't make it fun, though, I may have to throw that idea out. Large dungeon levels are tricky to balance IMO.

[buzzkill]

Maybe we could have secret doors and hidden doors. The difference being that secret were specifically constructed not to be found and must be searched for or detected. They would never be found without actively searching. These could lead to otherwise inaccessible portions of the dungeon. These otherwise inaccessible portions souls be shielded from other forms of detection and magic mapping.
Hidden doors would simply be hidden by debris, dust, years of non-use, and would function almost identically to the current implementation of secret doors, only they would be much easier to find.

[tynan]

If you are going to have secret doors, make sure there is a reason for them being there. I never liked the idea of a random secret door leading to nowhere? Basically if there is a feasible way to code an isolated room with secret door the only way in, and have minimum one piece of treasure there (with maybe a monster or two, the idea being there is something there worth keeping secret). And implement these isolated rooms into the random dungeon generation, so that when you use WoR scrolls/spells (or stairs up/down), you will never "accidentally" appear in one of these secret rooms.
Looks great so far, keep it up.

[RogerN]

The rendering code is all original. There's very little to it, actually. The GDI+ libraries included with C# already have support for blitting transparent bitmaps with good performance.

The rest of the code is a mix of original stuff and code ported from vanilla and Sangband.

[buzzkill]

Yea!!! We need more variants with good old fashioned 32x32 graphics. Did you borrow the code, or write it yourself?

[RogerN]

Not dead yet!

After almost a year of inactivity, I'm working on my (hopefully not doomed) variant again. Recent changes:

- Switched from text rendering to 32x32 graphical tiles
- Monsters! They can move, too.
- Items! Daggers and clubs, oh my!
- Saving / loading
- Looking around, examining your inventory
- Attacking monsters

There's a small glimmer of hope that I might release a playable game at some point...

[bpleshek]

I've written my own *band type game in VB6 and was porting it to VB.NET. I'm about 1/2 finished. But I had meant compiling vanilla with .NET.

Thanks anyway,

Brian

PS I can post my VB6 generation code if it would be useful to you. I think it works rather well and isn't too difficult to understand IMHO.