Pyrel dungeon generation

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

    Pyrel dungeon generation

    I've been thinking a lot on how to best write the dungeon generation for pyrel. In keeping with the spirit, the goal would be to improve on how the generation algorithm handles certain things so that the client (i.e. programmer) has more flexibility in determining the dungeon style.

    My basic ideas is that each dungeon feature should have an associated power rating and an associated rarity (or strangeness) rating. A greater vault would have both a high power and rarity rating, while a bizarre empty room might have a large rarity rating but a low power. Conversely, a OoD monster or a unique could have a high power but a low rarity. Bog-standard features like normal rooms, corridors and doors have 0 for both.

    At the beginning of each level, the RNG rolls for both rarity and power and those rolls determine the features. This gives the client the capability of tweaking the dungeon in fundamental ways with very simple changes. I envision the power rating to be very highly tied to dungeon levels and the rarity rating to have a much weaker dependence. I could also envision the capability of gradually reducing the power of a level each time it's visited to encourage deeper exploration, but that's an entirely different conversation. The point is that the capability would be there.

    The basic algorithm goes like this.
    1. Choose dungeon template (see below)
    2. Roll for power/rarity
    3. Place large features (GVs, labyrinths, caverns) if justified by rolls.
    4. Place smaller features (MVs, LVs, pits nests) if justified by rolls.
    5. Fill up remaining allotment for strangeness with abnormal rooms.
    6. Fill up remaining allotment for power with OoD monsters and items.
    7. Make remaining normal rooms
    8. Make corridors for connection, magma and quartz streamers.
    9. Place random monsters and items


    For 1. currently the dungeon templates are town, normal, cavern and labyrinth. I plan to subsume caverns and labyrinths as large scale sub-features of a level as opposed to their own type. However, this step is useful for differentiating the town from the dungeon in V and for differentiating different types of dungeon maps (overland, mountain, different dungeons) in variants. Since the rarity rolls could conceivably depend on dungeon templates, I move the rolls to the second step.

    2 has been explained already.

    One of the current drawbacks of dungeon generation is that features are often limited by whether or not they fit. In step 3 we place the largest features as the first features in the dungeon. This way we can ensure that you get a GV if one is called for. The main advantage is not to make GVs more common, but to give the client the capability of setting their frequency in a very transparent manner. I'm envisioning High rarity, low power levels to get a cavern. High rarity, medium power levels to get a labyrinth and High rarity, high power levels to get a GV.

    For 4, I lumped a lot of thing together but you can imagine further stratification. You can first check for MVs, then LVs, then pits and nests if you want. I'm not sure this stratification is necessary right now, but it would be useful if you have some features that are much larger than others.

    5 is how you get somewhat interesting dungeons with low power levels. This way the first 10 levels can still have interesting features instead of the current boring situation. These would be the rooms in room_template.txt as well as the moated rooms, the cross rooms, the circle rooms, the double rooms, the pillared rooms and all the other non-standard rooms.

    6 is how you satisfy a high power low rarity dungeon. Basically this looks like a normal dungeon except it's chock full of dangerous monsters and awesome loot.

    7,8,9 finish out dungeon generation similar to what's done in V.

    I was going to go into more details about how to pick features based on the rolls, but my lunch break is over. Maybe later tonight.
  • Patashu
    Knight
    • Jan 2008
    • 528

    #2
    If you want a case study, Dungeon Crawl: Stone Soup has a LUA interface and plugins for (most? all?) of its dungeon building styles, and it has its own file format for 'vaults', special rooms that have their own defined layout (which can have elements of randomness, subvaults, randomized subvaults, arbitrary embedded LUA, etc)
    My Chiptune music, made in Famitracker: http://soundcloud.com/patashu

    Comment

    • ekolis
      Knight
      • Apr 2007
      • 921

      #3
      Heh, Crawl actually has Lua? I must have missed that - wasn't Lua actually removed from Angband around 3.1.0 or so?
      You read the scroll labeled NOBIMUS UPSCOTI...
      You are surrounded by a stasis field!
      The tengu tries to teleport, but fails!

      Comment

      • Patashu
        Knight
        • Jan 2008
        • 528

        #4
        Originally posted by ekolis
        Heh, Crawl actually has Lua? I must have missed that - wasn't Lua actually removed from Angband around 3.1.0 or so?
        Crawl has LUA for a lot of things - you can put LUA in your configuration file to define macros, scripts and so on. There is at least one bot written entirely in client-side LUA.
        My Chiptune music, made in Famitracker: http://soundcloud.com/patashu

        Comment

        • Antoine
          Ironband/Quickband Maintainer
          • Nov 2007
          • 1010

          #5
          I must be confused - I thought pyrel was intended to be a port of Angband - do I have that wrong??? (Could I be thinking of pyAngband?)

          A.
          Ironband - http://angband.oook.cz/ironband/

          Comment

          • Derakon
            Prophet
            • Dec 2009
            • 9022

            #6
            Pyrel is a port of Angband (or will be when it's done!). I believe Patashu was simply suggesting that we check out Crawl for inspiration as to implementation mechanisms, if not content.

            (Of course, how much Pyrel will resemble Angband when it actually starts being playable is an open question. Devs like to meddle.)

            Comment

            • fizzix
              Prophet
              • Aug 2009
              • 3025

              #7
              Here are what I envision to be the changes to the "final product" of dungeon generation.

              1) Labyrinths and Caverns will become features on a level instead of their own level. This was actually a design goal for a while, so it's well in the intended spirit.

              2) Angband splits up the dungeon into smaller sub-blocks and then creates rooms contained entirely in those blocks. Vaults can span multiple blocks. I think the original idea was to prevent rooms from spanning across a window boundary (this is prior to window resizing and center on player). I'm not sure there's another good reason to split the dungeon this way anymore, so I have a feeling rooms will be placed more or less randomly in the pyrel generation script.

              3) Frequencies of various features may change. This is probably for the better, since the current allotment is far from ideal (every level in the 90s is almost guaranteed a demon, ainu, undead or if you're lucky dragon pit).

              I have lots of other ideas for improvement including making pits variably sized, making sections immune to item/feature detection and mapping, and creating sections where certain monster types are prevalent. But I'm not even sure I'll be able to get generation working given the poor state of my python abilities. So these extra things may not happen.

              Comment

              • Antoine
                Ironband/Quickband Maintainer
                • Nov 2007
                • 1010

                #8
                Originally posted by Derakon
                How much Pyrel will resemble Angband when it actually starts being playable is an open question. Devs like to meddle.
                So they do. Then, as I always anticipated, this will be a variant in another programming language, rather than a port.

                A.
                Ironband - http://angband.oook.cz/ironband/

                Comment

                • Magnate
                  Angband Devteam member
                  • May 2007
                  • 5110

                  #9
                  Originally posted by Antoine
                  So they do. Then, as I always anticipated, this will be a variant in another programming language, rather than a port.
                  No, it'll be a 100% faithful port of Vanilla Angband, because YOU, along with Timo and and everybody else who likes to carp from the sidelines, will step up and contribute to make sure it is.

                  And if you don't, you'll stop bitching about the difference between a faithful port and a variant rewrite, won't you?
                  "Been away so long I hardly knew the place, gee it's good to be back home" - The Beatles

                  Comment

                  • Antoine
                    Ironband/Quickband Maintainer
                    • Nov 2007
                    • 1010

                    #10
                    Originally posted by Magnate
                    No, it'll be a 100% faithful port of Vanilla Angband, because YOU, along with Timo and and everybody else who likes to carp from the sidelines, will step up and contribute to make sure it is.

                    And if you don't, you'll stop bitching about the difference between a faithful port and a variant rewrite, won't you?
                    ha! surely you jest sir. the more people were involved, the less likely it would be to be a faithful port.

                    let me be the first to welcome this fine new variant!

                    a.
                    Ironband - http://angband.oook.cz/ironband/

                    Comment

                    • Nick
                      Vanilla maintainer
                      • Apr 2007
                      • 9634

                      #11
                      I would just say the Angband is at a most interesting stage in its development. As usual.
                      One for the Dark Lord on his dark throne
                      In the Land of Mordor where the Shadows lie.

                      Comment

                      • fizzix
                        Prophet
                        • Aug 2009
                        • 3025

                        #12
                        Basic room allotment algorithm

                        The algorithm for deciding where rooms are and whether they fit is probably the first area to focus. I've come up with several ways to do this. It's good to figure this out first because it will have some considerable impact on how the dungeon looks. The goal is to place rooms assuming the existence of off-limits areas (vaults and already placed rooms)

                        For all possible approaches it may be best to pre-select room sizes and try to place larger or more awkward rooms first and then fill the rest with the easier smaller and rectangular rooms.

                        Approach 1 - dungeon block approach
                        ------------------------------------------------------

                        This is the method currently use in Angband and the several variants I looked at. (Thanks Nick for the github variant repository, it has been helpful here!) The basic idea is to split up the dungeon into smaller blocks, 11x11 is the size used in Angband but the value is arbitrary.

                        You cycle through all the blocks picking a random one each time. After selecting a dungeon block you try to place a room and check if it fits by seeing if the room only uses unused blocks. If the room fits, you mark off all the blocks that it touches as "used" blocks.

                        There's some logic to try to move rooms around to fit them in as few blocks as possible, but I haven't really looked into it too much.

                        Positives for this approach:
                        It is simple and essentially already coded. I would just need to port it over.
                        It does a decent job of keeping the levels mostly filled up.
                        It can be used to prevent rooms from spanning window boundaries (part of the original reason)

                        Negatives for this approach:
                        It handles non-rectangular rooms (crosses, double rooms, etc.) inefficiently.
                        It can lead to blocky looking dungeons with stacked rooms vertically.

                        Approach 2: Random room location approach
                        --------------------------------------------------------------

                        This is probably the easiest conceptual approach. You pick a random location, place a room (if it fits) then pick another and repeat until you've placed enough rooms or failed enough times. This is kind of the standard angband way of doing things like this, pick a bunch of random points and throw away the ones that don't fit your criteria.

                        Positives:
                        Extremely simple to code.
                        Dungeon room layout is randomized (no blocky effects)
                        Has the potential to densely pack odd shaped rooms.

                        Negatives:
                        Room intersection finding is much more difficult, instead of checking if blocks are occupied, you have to check if most of the squares are already used.
                        Dungeon has a chance to be very sparsely populated (unlucky RNG location selection) or over-dense.
                        Probably more inefficient than the blocky approach

                        Approach 3: Network
                        ------------------------------
                        The idea here is to start with a random point and place a room. Then select another room size and travel some random amount in a direction so that the room fits and place it (room 2) Repeat n times for room 1 (probably 3 or so) and then do the same thing for room 2 etc. Eventually you get a network of rooms that grows somewhat organically from the starting location.

                        This probably needs a reasonably sophisticated graph-theory routine, and I'm not sure I'm up for it, nevertheless it's worth thinking about.

                        Positives:
                        Capable of creating highly dense or highly sparse grids very easily.
                        Can be the most efficient method (but with significantly more code).

                        Negatives:
                        I'm not sure I can actually do this one.
                        Room intersection checking is just as hard as in version 2 (you probably still want to place the vaults/caverns/labyrinths first)

                        ------------------------------------------------------

                        I'm leaning towards 1 for ease of writing, but there are good arguments for 2 if someone wants to convince me. 3 could be cool but it's a tough algorithm and may not be transparent.

                        There are possibly other approaches that are used in different roguelikes, so if anyone knows one with interesting dungeon characteristics, I'll check it out.

                        Comment

                        • Mikko Lehtinen
                          Veteran
                          • Sep 2010
                          • 1246

                          #13
                          Just a little idea I tried in Mist: after all the rooms have been generated and connected with tunnels, and all the stairs are in place, create some extra rooms (teleport-proof) and tunnels. Then you can have truly challenging locks, stuck doors, and other puzzles that not every character can pass. The locks in Angband are absolutely boring.

                          Comment

                          • Magnate
                            Angband Devteam member
                            • May 2007
                            • 5110

                            #14
                            I think #2 is probably the best compromise, though I worry about the performance given recent IRC debate. (But I worry about that whichever method we choose, so it doesn't influence the choice.)

                            I am not really sure that #3 will provide sufficient gain to make it worth the significant additional coding effort (though I like the straightforward relationship between config variables and dungeon level sparseness/denseness). By contrast, I think #2 provides a great deal that #1 doesn't, in terms of the handling of different room shapes and generally improved randomness of dungeon level layout.

                            So my recommendation is to code up #2 and see how dog slow it turns out to be. If we can't optimise it to a good enough level of performance, we can always try something else.
                            "Been away so long I hardly knew the place, gee it's good to be back home" - The Beatles

                            Comment

                            • Mikko Lehtinen
                              Veteran
                              • Sep 2010
                              • 1246

                              #15
                              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!

                              Comment

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