Over-engineering dungeon generation

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

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

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

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

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

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

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]

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]

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