Pyrel dungeon generation

[fizzix]

I wouldn't worry too much about performance in dungeon generation. Even in the original comments in generate.c it is mentioned that clarity is much more important here than efficiency. Save the worries for things that happen multiple times every game turn!

I am not overly worried about performance for that exact reason. Nevertheless, it's probably a good idea to keep it to a reasonable speed (say under 5s for a normal computer) anymore than that and it becomes very annoying to wait.

The main performance kick to number 2 is determining whether you've intersected something (and possibly adjusting values so that you don't)

The methodology would be when creating a room, check every other (every third?) square one beyond the perimeter, making sure to check all convex corners. If nothing is on those squares, then you're good to go. Then check every third grid in a matrix inside the room to make sure you haven't completely covered up a room. (assume 3 blocks is the minimum size for a room feature.)

If checking is a major pain, some improvement can be made by first sorting by size and then you only need to check the center point and the perimeter.

An alternative would be to figure out how big a space any randomly chosen location can handle, but I think I'd rather start out picking the room first and then trying to place it.

[emulord]

Extra advantage for #3
Ensures the dungeon will be connected

Extra disadvantage for #3
If you end up with a tree structure, you may be blocked off by breeders / very strong monsters with no way to go around them short of digging or teleporting.
This was a problem in halls of mist sometimes.

[fizzix]

Extra advantage for #3
Ensures the dungeon will be connected

Extra disadvantage for #3
If you end up with a tree structure, you may be blocked off by breeders / very strong monsters with no way to go around them short of digging or teleporting.
This was a problem in halls of mist sometimes.

I'm not too worried about connectedness. The connectedness algorithm for Vanilla works fairly well and is not overly complicated. Plus it makes for an interesting tunnel pattern. (tunnels are not handled explicitly in option 3!)

If I understand the connection algorithm, you randomize all rooms and then connect each room to the next random one by starting a corridor from the room and heading in the general direction of the room you want to get to (with random twistinesses added in). You stop if you intersect another room or another corridor.

I think there's also a check to ensure you don't create a bipartite map, but I need to look at it. I know d_m worked on this.

I have no plans on making major alterations to this procedure (or the streamer placing routines for that matter).

[Mikko Lehtinen]

In my experience generating rooms is simple. Connecting them with tunnels is the tricky part. Choosing #3 might save you lots of work later on...

Angband doesn't have checks to make sure that all the rooms are connected. It relies on generating lots and lots of random tunnels between the rooms. It succeeds almost always, but the resulting dungeons always have that distinct "Angband feel". If you want to have levels with different styles, you need to come up with another method.

I changed the dungeon style in Halls of Mist and had big problems with unconnected rooms. I got some ideas from Un that helped me hack together a working system. It's very ugly because I wasn't able to understand everything about the Un system.

Basically, Unangband rooms have "sections". If two rooms get connected by a tunnel, their sections are joined. Connecting the rooms can stop when they all have the same section number. (IIRC.)

If you want to play around with the Angband dungeon generation to create levels with a different look, you may want to tweak the lottery where all rooms are randomly paired with each other for tunnel building purposes. You can keep rerolling the room pairs until some predefined conditions are satisfied. For instance, you can degree that the paired rooms cannot be too far from each other. Tweaking the numbers here enabled me to create dungeon levels that satisfied me aesthetically.

(Written before reading the last two posts!)

[Nick]

O has an approach 2 algorithm, with the added feature that there is a desired room type distribution for given depths (table indicates relative numbers), and a minimum depth certain types can occur:

  Depth:        0  10   20   30   40   50   60   70   80   90  100  min 

  Simple    {{  0,  0,   0,   0,   0,   0,   0,   0,   0,   0,   0},  0},
  Overlap   {{ 60, 80, 100, 120, 140, 165, 180, 200, 220, 240, 260},  1},
  Cross     {{  0  25,  50,  70,  85, 100, 110, 120, 130, 140, 150},  3},
  Large     {{  0, 25,  50,  70,  85, 100, 110, 120, 130, 140, 150},  3},
  Pit       {{  0,  5,  12,  25,  30,  35,  38,  40,  40,  40,  40},  5},
  Chambers  {{  0,  2,   6,  12,  15,  18,  19,  20,  20,  20,  20},  5},
  I.Room    {{ 50, 60,  70,  80,  80,  80,  80,  80,  80,  80,  80},  0},
  L.Vault   {{  0,  1,   4,   9,  16,  27,  40,  55,  70,  80,  90},  5},
  G.Vault   {{  0,  0,   1,   2,   3,   4,   6,   7,   8,  10,  12}, 20},
  Huge      {{  0,  0,   0,   0,   4,   4,   4,   4,   4,   4,   4}, 41}

IMHO it leads to really good dungeon levels.

[fizzix]

O has an approach 2 algorithm, with the added feature that there is a desired room type distribution for given depths (table indicates relative numbers), and a minimum depth certain types can occur:

  Depth:        0  10   20   30   40   50   60   70   80   90  100  min 

  Simple    {{  0,  0,   0,   0,   0,   0,   0,   0,   0,   0,   0},  0},
  Overlap   {{ 60, 80, 100, 120, 140, 165, 180, 200, 220, 240, 260},  1},
  Cross     {{  0  25,  50,  70,  85, 100, 110, 120, 130, 140, 150},  3},
  Large     {{  0, 25,  50,  70,  85, 100, 110, 120, 130, 140, 150},  3},
  Pit       {{  0,  5,  12,  25,  30,  35,  38,  40,  40,  40,  40},  5},
  Chambers  {{  0,  2,   6,  12,  15,  18,  19,  20,  20,  20,  20},  5},
  I.Room    {{ 50, 60,  70,  80,  80,  80,  80,  80,  80,  80,  80},  0},
  L.Vault   {{  0,  1,   4,   9,  16,  27,  40,  55,  70,  80,  90},  5},
  G.Vault   {{  0,  0,   1,   2,   3,   4,   6,   7,   8,  10,  12}, 20},
  Huge      {{  0,  0,   0,   0,   4,   4,   4,   4,   4,   4,   4}, 41}

IMHO it leads to really good dungeon levels.

Basically this approach is what I'm going to do. Except the allotment will go bottom up, so largest (and rarest) features get placed first. Continuing on to smaller features. The final bit will be bog standard rectangular rooms. I'm going to start with these first and then start adding the special rooms.

I haven't decided whether to make an allocation table like this or go with my original idea of power/rarity ratings. The nice thing about the allocation tables is that you can set features that are more common at shallower depths like garrisons (places filled with kobolds, orcs, ogres or trolls).

[Scatha]

I haven't decided whether to make an allocation table like this or go with my original idea of power/rarity ratings. The nice thing about the allocation tables is that you can set features that are more common at shallower depths like garrisons (places filled with kobolds, orcs, ogres or trolls).

If you want a general system, might it work to have more types of rating, to be specified by the user? These could be used to identify special kinds of feature, and then be specified at level generation (e.g. at depth X you ask for a 1/3 chance of a room with IsGarrison=1 being generated).

[fizzix]

If you want a general system, might it work to have more types of rating, to be specified by the user? These could be used to identify special kinds of feature, and then be specified at level generation (e.g. at depth X you ask for a 1/3 chance of a room with IsGarrison=1 being generated).

Yes, this might work best. In which case something like the allocation table would work fine. If I'm understanding the idea correctly the allocation table is used to choose what kind of special room you get once you've chosen to receive a special room.

The top-down approach first decides what special rooms to have and then places them. The choosing which rooms can be done with the allocation table also. Making this easy for the client (dev) is certainly high on the priority list.

[buzzkill]

I'd create as many different types of dungeon generation systems as possible. In Angband, just about every level feels the same. IMO it would be better if every level felt fresh/random. I think this would be much easier to accomplish using completely different systems, preferably written by different people with different methods. Yeah, the codebase will be larger but it'll be worth it. Great non-predictable dungeon generation would revolutionize Angband.

[Derakon]

I've mostly kept out of this because I have enough on my plate, thank-you very much. I do think, however, that it's worth considering having a two-tiered system:

Tier 1 decides how to place rooms (and connects them together)
Tier 2 places rooms.

Currently fizzix has one Tier-1 system planned, with Tier-2 systems being the code that makes vaults, pits, normal rooms, etc. But you could imagine various other potential Tier-1 systems that would invoke the Tier-2 systems in other ways:

* A generator that makes a bunch of rooms directly adjacent to each other, connected by doors (like in a real-life house)
* One that eschews corridors entirely in favor of a portal system
* Ones with varying levels of corridor complexity and interconnectedness
* ZAngband-style "arena" levels which are completely open except for the rooms (very dangerous!)

etc.

How different rooms relate to each other in an individual level goes a long way to determining how the level plays out. After all, the player's strategy cannot be limited to the scale of an individual room, or they're liable to be blindsided by some incoming threat.

[Nick]

Basically this approach is what I'm going to do. Except the allotment will go bottom up, so largest (and rarest) features get placed first. Continuing on to smaller features. The final bit will be bog standard rectangular rooms. I'm going to start with these first and then start adding the special rooms.

Mine was possibly the worst forum post anyone has ever made. For one thing O uses approach 1. For another, it does allocate bottom up.

In fact, the process is

1. Use the distribution (interpolating for levels not divisible by 10) to get numbers of rooms to attempt for each type
2. Build rooms, starting from the bottom of the table and going up
3. Connect rooms

More importantly, I love Derakon's idea. It could, for example, be combined with d_m's labyrinths, so that you have maze of rooms, and need to get from one end to the other.

[RogerN]

Sorry for thread necromancy here, but I thought I'd bring up another consideration thta I don't think has been mentioned yet: room placement can have a large impact on difficulty.

While developing one of my previous variants I departed from the standard 11x33 blocks approach used by Angband for room placement. My goal was to make room placement more efficient so that I could squeeze a larger number of interesting room shapes into the same level. It worked... but the unintended consequence was that players were far more likely to disturb monsters while exploring. Rooms were placed more "efficiently", so they were closer to each other on average and noises made by the player while walking around were far more likely to disturb monsters.

If you plan to support a variety of room placement algorithms then you must either enforce a monster "density" number (i.e. X number of monsters per Y walkable dungeon tiles) instead of a fixed number of encounters, or be prepared for cramped room placement algorithms to result in harder levels for stealth-focused characters.

[fizzix]

If you plan to support a variety of room placement algorithms then you must either enforce a monster "density" number (i.e. X number of monsters per Y walkable dungeon tiles) instead of a fixed number of encounters, or be prepared for cramped room placement algorithms to result in harder levels for stealth-focused characters.

That's useful feedback. Right now the planned approach is to select the number of rooms and then fit them in randomly. Some rooms will be allowed to be partially placed, and some will be allowed to overwrite previous areas.

The pyrel wiki page has information for the current plans. Currently, I'm working on connecting up the rooms.

I haven't thought much about monster placement at all yet.

[Derakon]

RogerN: I'm not familiar with monster awareness algorithms, but does sound travel equally well through all materials? It sounds like the problem was due to the player being closer to monsters a lot more of the time, even if there were walls in the way -- but if walls muffled sound strongly (and 10' of granite ought to be a heck of a sound barrier) then that would be less of an issue. A reasonably intelligent flow algorithm ought to be able to handle sound propagation through different materials so that the player can walk by close (as the Umber Hulk bores) to monsters without them ever noticing, even if that player is a dwarfish warrior wearing Boots of Noise.

[RogerN]

RogerN: I'm not familiar with monster awareness algorithms, but does sound travel equally well through all materials?

IIRC, yes. Noise decreases linearly with approximate distance between the player and the monster. It would be somewhat expensive to calculate effects of sound propagation through different materials.

Instead of using pure distance to calculate loudness, you could make use of the flows that Angband maintains after every step. I would try an average of the "actual" distance and the flow-path distance, so if the player isn't in the same room as a monster then sounds should be muffled somewhat.