Pyrel dungeon generation

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • fizzix
    Prophet
    • Aug 2009
    • 3025

    #16
    Originally posted by Mikko Lehtinen
    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.
    Last edited by fizzix; October 10, 2012, 20:52.

    Comment

    • emulord
      Adept
      • Oct 2009
      • 207

      #17
      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.

      Comment

      • fizzix
        Prophet
        • Aug 2009
        • 3025

        #18
        Originally posted by 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.
        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).

        Comment

        • Mikko Lehtinen
          Veteran
          • Sep 2010
          • 1246

          #19
          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!)

          Comment

          • Nick
            Vanilla maintainer
            • Apr 2007
            • 9638

            #20
            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:

            Code:
              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.
            One for the Dark Lord on his dark throne
            In the Land of Mordor where the Shadows lie.

            Comment

            • fizzix
              Prophet
              • Aug 2009
              • 3025

              #21
              Originally posted by 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:

              Code:
                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).

              Comment

              • Scatha
                Swordsman
                • Jan 2012
                • 414

                #22
                Originally posted by fizzix
                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).

                Comment

                • fizzix
                  Prophet
                  • Aug 2009
                  • 3025

                  #23
                  Originally posted by Scatha
                  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.

                  Comment

                  • buzzkill
                    Prophet
                    • May 2008
                    • 2939

                    #24
                    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.
                    www.mediafire.com/buzzkill - Get your 32x32 tiles here. UT32 now compatible Ironband and Quickband 9/6/2012.
                    My banding life on Buzzkill's ladder.

                    Comment

                    • Derakon
                      Prophet
                      • Dec 2009
                      • 9022

                      #25
                      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.

                      Comment

                      • Nick
                        Vanilla maintainer
                        • Apr 2007
                        • 9638

                        #26
                        Originally posted by fizzix
                        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.
                        One for the Dark Lord on his dark throne
                        In the Land of Mordor where the Shadows lie.

                        Comment

                        • RogerN
                          Swordsman
                          • Jul 2008
                          • 308

                          #27
                          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.

                          Comment

                          • fizzix
                            Prophet
                            • Aug 2009
                            • 3025

                            #28
                            Originally posted by RogerN

                            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.

                            Comment

                            • Derakon
                              Prophet
                              • Dec 2009
                              • 9022

                              #29
                              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.

                              Comment

                              • RogerN
                                Swordsman
                                • Jul 2008
                                • 308

                                #30
                                Originally posted by Derakon
                                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.

                                Comment

                                Working...
                                😀
                                😂
                                🥰
                                😘
                                🤢
                                😎
                                😞
                                😡
                                👍
                                👎