Codezen

Fun with Roguelike Generators

gaming, programming, python

Jack

I may or may not be tooling around with a roguelike. Not because I think the genre is dead (it most certainly isn’t) but because some programming tasks are made fun just by their subject matter. I haven’t quite gotten to the point where I’m using “mana” and “damage” and etc. as variable names, but that’s not the first fun part. The first fun part is generating a rogue dungeon level.

Now, anybody that’s ever even thought about developing a roguelike should know about ASCII Dreams written by the developer of Unangband, Andrew Doull. I especially found his series on Unangband Dungeon Generation to provide a lot of insight into generating dungeons that are interesting a long with a lot of interesting history and philosophizing.

In the end, though, I wanted to try my own, naive, hand at the dungeon generation problem. I did take a few major things away from Andrew’s discussion however. Mostly that there are a lot of nice rooms that can be generating procedurally with simple tricks and, failing that, having a system for “vaults” (which are various, hand-designed rooms with interesting features) can be interspersed for extra flavor. Also, various features added to rooms, like water, lava, ice, minerals, rubble, etc. compel players to explore.

Most of this I’ll get to later, if ever, with my toy generator. The first problem is generating the topology of the dungeon itself.

My Approach

Now, one thing that I’ve found annoying about classic generation algorithms is that they tend to have a lot of really long tunnels. This is because rooms are generated at random across the static map and then, if they haven’t merged together, are connected by tunnels. This has never felt right to me. I understand that – in universe – a dungeon might not have the most sensible design, but having long winding tunnels are boring. Doing connectivity checks on the rooms is boring as well. While we’re at it, I don’t want to have a predefined playing field (array) to work with. I’ll put a limit on the area of the dungeon level, but if it’s a whole bunch of tiny rooms in a very long line, so be it. Unfortunately, I also want the level to be consistent (i.e. no physics violating overlapping inconsistent geometry) so it seems inevitable that the level will eventually be represented on a global grid, but at least that grid will be bounded and reasonably shaped to the level. If necessary, after the level is fully generated the excess grid could be eliminated just by noting where one room enters into another.

So, what I wanted to do was generate a dungeon level that is both tunnel free (for the most part), consistent and connected a priori. Interesting stuff like themed-features, rivers, lava flows, etc. could then be painted over the level geometry in broad strokes.

Problems vs. Classical

There are some troubles with this approach. The first of which is that it makes multiple level consistency really hard with multiple staircases. For a classical generator, you can randomly place down staircases on one level, and then replicate that pattern with up staircases on the next level and ensure that you have rooms to encompass them. This works when you’re going to manually connect all the rooms in the end, but it doesn’t work so well when you’re building a pre-connected level. As such, either there has to be only a single up and down staircase per level (not a bad idea, really) or you have to throw that level of consistency out the window and just match arbitrary up and down staircases. This means that you could have two down staircases right next to each other that would teleport you to different ends of the next level, but in a gametype that traditionally promotes save scumming (i.e. if you go down the same staircase twice, the level is different each time you descend) I think that’s acceptable.

Another problem is that, without tunnels, the dungeons are more likely to be dense. That’s a good thing in the fact that it gives a lot more interesting rooms close by and the player spends a lot of time in an environment. It’s also a dangerous thing because it means there’s a lot fewer twisty places to get out of sight of pursuing monsters. I think that’s acceptable as well, although it’ll be something to account for if I ever get around to generating monsters.

Implementation

I decided to bang out a proof of concept in an evening. Breaking down the logic, the easiest way to generate in this fashion is to generate one room, which will be the root. Then, generate another room. Connect these two rooms with a doorway, then that whole complex becomes the root “room”. Rinse and repeat until the dungeon is of a certain size.

In order to encompass this, I came up with a class for Space. A Space is any arbitrary portion of the dungeon level. It includes a 2-dimensional array geometry that describes what’s in that space. One Space’s geometry can be added to another Space’s geometry with a set overlapping point. A Room is just a space with a name and whose geometry is likely a single room, but is arbitrary. Then, special types of rooms, like one mentioned in Unangband as the core type, two overlapping rectangles (which results in single rooms, crosses, T-shapes, L-shapes, etc.) are just Rooms with special geometry generation.

Expand Code
#!/usr/bin/python

import random
import sys

def chance(c):
    if random.randint(1, 100) <= c:
        return True
    return False

def rand_element(l):
    return l[random.randint(0, len(l) - 1)]

def rand_block(max_x, max_y):
    return (random.randint(0, max_x), random.randint(0, max_y))

class Space(object):
    def __init__(self, geom = []):
        self.global_x = 0
        self.global_y = 0
        self.geometry = geom

    def point(self, x, y):
        return (self.global_x + x, self.global_y + y)

    def adjust_x(self, x):
        self.global_x = x

    def adjust_y(self, y):
        self.global_y = y

    def area(self):
        area = 0
        for row in self.geometry:
            for x in row:
                if x:
                    area += 1
        return area

    # Create an initialized array for a space with dimensions.  we can't just do
    # [[0] * x] * y because then the sublists are all just instances of the same
    # list.

    def space(self, x, y, val = 0):
        geom = []
        for y in range(0, y):
            geom.append([val] * x)
        return Space(geom)

    # Add space takes two arbitrary spaces and merges together, using points
    # s1p and s2p as the same points in the resulting form.

    # If kwargs["chicken"] is True, it will return False (i.e. fail), if any of s1's
    # points are overwritten by s2 except for the intersection point.

    def add_space(self, sq, s1p, s2p, **kwargs):

        chicken = False
        if "chicken" in kwargs and kwargs["chicken"]:
            chicken = True

        s1 = self.geometry
        s2 = sq.geometry

        s1_dim_y = len(s1)
        s1_dim_x = len(s1[0])

        s1_o_x, s1_o_y = s1p

        s2_dim_y = len(s2)
        s2_dim_x = len(s2[0])

        s2_o_x, s2_o_y = s2p

        g_max_x = s1_dim_x

        # Account for s2's width going farther to left
        if (s1_o_x < s2_o_x):
            s1_start_x = (s2_o_x - s1_o_x)
            s2_start_x = 0
            g_max_x += s1_start_x
        else:
            s1_start_x = 0
            s2_start_x = (s1_o_x - s2_o_x)

        # Account for s2's width going farther to right
        if [1]s1_dim_x - s1_o_x) < (s2_dim_x - s2_o_x:
            g_max_x += (s2_dim_x - s2_o_x) - (s1_dim_x - s1_o_x)

        g_max_y = s1_dim_y

        # Account for s2's height going higher
        if (s1_o_y < s2_o_y):
            s1_start_y = (s2_o_y - s1_o_y)
            g_max_y += s1_start_y
            s2_start_y = 0
        else:
            s1_start_y = 0
            s2_start_y = (s1_o_y - s2_o_y)

        # Account for s2's depth going lower
        if [2]s1_dim_y - s1_o_y) < (s2_dim_y - s2_o_y:
            g_max_y += (s2_dim_y - s2_o_y) - (s1_dim_y - s1_o_y)

        geom = self.space(g_max_x, g_max_y)

        # Draw both into geometry:

        for y in range(0, s1_dim_y):
            for x in range(0, s1_dim_x):
                geom.geometry[y + s1_start_y][x + s1_start_x] = s1[y][x]

        for y in range(0, s2_dim_y):
            for x in range(0, s2_dim_x):
                if s2[y][x]:
                    if chicken and (x, y) != s2p and\
                            geom.geometry[y + s2_start_y][x + s2_start_x]:
                        return False
                    geom.geometry[y + s2_start_y][x + s2_start_x] = s2[y][x]

        self.adjust_x(s1_start_x)
        sq.adjust_x(s2_start_x)

        self.adjust_y(s1_start_y)
        sq.adjust_y(s2_start_y)

        self.geometry = geom.geometry
        return True

    # Sort out surrounding used and unused coordinates.

    def _cardinal_sort(self, x, y):
        unused = []
        used = []
        pairs = [(-1, 0, 0),(0, -1, 3),(0, 1, 1),(1, 0, 2)]

        for off_y, off_x, direction in pairs:
            b = (x + off_x, y + off_y, direction)
            # Count out of bounds as unused.
            if (y + off_y) < 0 or\
               (y + off_y) >= len(self.geometry) or\
               (x + off_x) < 0 or\
               (x + off_x) >= len(self.geometry[y + off_y]) or\
               self.geometry[y + off_y][x + off_x] == 0:
                unused.append(b)
            else:
                used.append(b)

        return (used, unused)

    # Return a list of coordinates of used squares that have at least one
    # unused square (four-way) adjacent that, if used, would have no other used
    # neighbors but the first one. So, in summary

    # 1|
    # 2| <- all perimeter blocks
    # 3|
    #
    # 1|_  <-- neither are perimeter blocks
    #   2

    # The intent here is to find blocks where it's appropriate to attach a
    # doorway. For now, this only list blocks that are pressing against the
    # outside boundary of the geometry. There are some neat cases that could be
    # generated with finer granularity, but I'm not sure if that's better done
    # with specific generators.

    def connectable_coords(self):
        r = []
        for i, y in enumerate(self.geometry):
            for j, x in enumerate(y):

                # Skip unused blocks
                if not x:
                    continue

                used, unused = self._cardinal_sort(j, i)
                for s_x, s_y, s_d in unused:
                    sub_used, sub_unused = self._cardinal_sort(s_x, s_y)
                    if len(sub_used) == 1:
                        r.append[3]j, i, s_d
        return r

    def print_geom(self):
        for row in self.geometry:
            p = ""
            for x in row:
                if x:
                    p += ("%s" % (chr(x),))
                else:
                    p += " "
            print(p)

    def gen(self):
        pass


class Room(Space):
    def __init__(self):
        Space.__init__(self)
        self.name = ""

        self.name_prefixes = [ "Beautiful", "Evil", "Corrupted", "Pristine" ]
        self.name_suffixes = [ "of Doom", "of Dancing", "of Flowers", "of Blood" ]
        self.name_bases = [ "Room" ]

        self.name_prefix_chance = 25
        self.name_suffix_chance = 25
        
    def give_name(self):
        n = ""
        if chance(self.name_prefix_chance):
            n += rand_element(self.name_prefixes) + " "
        n += rand_element(self.name_bases)
        if chance(self.name_suffix_chance):
            n += " " + rand_element(self.name_suffixes)
        self.name = n

    def gen(self):
        self.give_name()

class SimpleRoom(Room):
    def gen(self, x, y, val):
        Room.gen(self)
        self.geometry = self.space(x, y, val).geometry

class SimpleAdditiveRoom(Room):
    def gen(self, min_x, max_x, min_y, max_y, val):
        Room.gen(self)

        # Get section 1 dimensions
        r1_dim_x = random.randint(min_x, max_x)
        r1_dim_y = random.randint(min_y, max_y)

        # Section 2 dimensions
        r2_dim_x = random.randint(min_x, max_x)
        r2_dim_y = random.randint(min_y, max_y)

        # Random overlapping points
        r1p = rand_block(r1_dim_x, r1_dim_y)
        r2p = rand_block(r2_dim_x, r2_dim_y)

        r1 = self.space(r1_dim_x, r1_dim_y, val)
        r2 = self.space(r2_dim_x, r2_dim_y, val)

        self.geometry = r1.geometry
        self.add_space(r2, r1p, r2p)

class Hallway(Space):
    def gen(self, x, y, val):
        Space.gen(self)
        self.geometry = self.space(x, y, val).geometry

if __name__ == "__main__":
    root = SimpleAdditiveRoom()
    root.gen(3, 10, 3, 10, ord('A'))

    val = ord('B')

    while root.area() < 2000:
        sr2 = SimpleAdditiveRoom()
        sr2.gen(3, 10, 3, 10, val)

        c1 = rand_element(root.connectable_coords())

        m = [ 2, 3, 0, 1 ]  
        c2 = rand_element([ x for x in sr2.connectable_coords() if x[2] == m[c1[2]]])

        hall = Hallway()

        if c1[2] == 0:
            hall.gen(1, 3, ord('+'))
            hall.add_space(root, hall.point(0,2), c1[:2])
            r = hall.add_space(sr2, hall.point(0,0), c2[:2], chicken = True)
        elif c1[2] == 2:
            hall.gen(1, 3, ord('+'))
            hall.add_space(root, hall.point(0,0), c1[:2])
            r = hall.add_space(sr2, hall.point(0,2), c2[:2], chicken = True)
        elif c1[2] == 1:
            hall.gen(3, 1, ord('+'))
            hall.add_space(root, hall.point(0,0), c1[:2])
            r = hall.add_space(sr2, hall.point(2,0), c2[:2], chicken = True)
        elif c1[2] == 3:
            hall.gen(3, 1, ord('+'))
            hall.add_space(root, hall.point(2,0), c1[:2])
            r = hall.add_space(sr2, hall.point(0,0), c2[:2], chicken = True)

        if r:
            root = hall
            val += 1

    root.print_geom()

I got a little lazy with the execution of __main__. There’s a cleaner way to deal with matching up the direction end-points (hell, just take a random one and rotate the entire room to match, really) but for an evening’s playing around I think the results are actually pretty nice.

Expand Example

        ]]]]]]                                                           
        ]]]]]]                                                           
        ]]]]]]]]]]]                                                      
        ]]]]]]]]]]]                                                      
        ]]]]]]]]]]]                                                      
        ]]]]]]]]]]]                                                      
        ]]]]]]]]]]]                                                      
        ]]]]]]]]]]]          UUUUUUUU                                    
        ]]]]]]               UUUUUUUU                                    
          +                UUUUUUUUUU                                    
         ZZZZ              UUUUUUUUUU                                    
         ZZZZ              UUUUUUUUUU                                    
         ZZZZ              UUUUUUUUUU                                    
         ZZZZ                UUUUUUUU MMMMMMMMM                          
         ZZZZZZZZ            UUUUUUUU+MMMMMMMMM                          
         ZZZZZZZZ            UUUUUUUU MMMMMMMMM                          
         ZZZZZZZZ            UUUUUUUU MMMMMMMMM                          
         ZZZZZZZZ                        MMMMMM                          
         ZZZZZZZZ                        MMMMMM                          
         ZZZZZZZZ                JJJJJJJ MMMMMM                          
         ZZZZZZZZ                JJJJJJJ MMMMMM                          
            +                    JJJJJJJ  +                              
          WWWWWWW                JJJJJJJJJJJJJJ                          
          WWWWWWWWWW NNNNNN      JJJJJJJJJJJJJJ                          
          WWWWWWWWWW NNNNNN      JJJJJJJJJJJJJJ                          
          WWWWWWWWWW+NNNNNN      JJJJJJJJJJJJJJ                          
          WWWWWWWWWW NNNNNN       +                                      
          WWWWWWWWWW NNNNNNBBBBBBBB                                      
          WWWWWWWWWW NNNNNNBBBBBBBBBB                                    
          WWWWWWWWWW NNNNNNBBBBBBBBBB                                    
             WWWWWWW  NNNN BBBBBBBBBB                                    
             WWWWWWW  NNNN BBBBBBBBBB                                    
            OOOOOOOOOONNNN       BBBB                                    
            OOOOOOOOOO   +       BBBB                                    
            OOOOOOOOOO FFFFFFF   BBBB                                    
            OOOOOOOOOO FFFFFFF   BBBB                                    
            OOOOOOOOOO FFFFFFF    +                                      
            OOOOOOOOOO FFFFFFF AAAAAAAAAAA                               
            OOOOOOOOOO FFFFFFF+AAAAAAAAAAA                               
            OOOOOOOOOO FFFFFFF AAAAAAAAAAA                               
            OOOOOOOOOO FFFFFFF AAAAA                                     
            OOOOOOOOOO+FFFFFFF AAAAA          PPPPPPPPP                  
             OOOOO     FFFFFFF AAAAA          PPPPPPPPP                  
             OOOOO LLL FFFFFFF AAAAA          PPPPPPPPP TTTT             
                   LLL +         +            PPPPPPPPP TTTT             
                  LLLLLLL        CCCCC        PPPPPPPPP+TTTT             
                  LLLLLLL        CCCCC        PPPP   +  TTTTT            
                  LLLLLLL        CCCCC      HHHHHHHHHH  TTTTT            
     [[[[[[[[[                   CCCCCCCCCC HHHHHHHHHH  TTTTT  XXXXXXXXXX
     [[[[[[[[[                   CCCCCCCCCC HHHHHHHHHHHHTTTTT XXXXXXXXXXX
     [[[[[[[[[ GGGGGGGGGG        CCCCCCCCCC HHHHHHHHHHHHTTTTT+XXXXXXXXXXX
     [[[[[[[[[ GGGGGGGGGG  EEEEE+CCCCCCCCCC HHHHHHHHHHHH      XXXXXXXXXX 
     [[[[[[[[[ GGGGGGGGGG  EEEEE CCCCCCCCCC+HHHHHHHHHH        XXXXXXXXXX 
     [[[[[[[[[ GGGGGGGGGG EEEEEE CCCCCCCCCC                   XXXXXXXXXX 
     [[[[[[[[[+GGGGGGGGGG EEEEEE CCCCCCCCCC                   XXXXXXXXXX 
   [[[[[[[[[[[ GGGGGGGGGG EEEEEE     +                        XXXXXXXXXX 
   [[[[[[[[[[[ GGGGGGGGGG EEE       DDD                                  
   [[[[[[[[[[[ GGGGGGGGGG+EEE       DDD                                  
   [[[[[[[[    GGGGGGGGGG EEE   III DDD                                  
   [[[[[[[[    GGGGGGGGGG EEE  IIII DDD                                  
   [[[[[[[[         +     EEE  IIII DDD                                  
   [[[[[[[[         KKK   EEE  IIII DDD                                  
                    KKK        IIII DDD                                  
                    KKK        IIII+DDDQQQQ                              
                    KKK        IIII QQQQQQQQQQ                           
                 KKKKKKK       IIII+QQQQQQQQQQ                           
                 KKKKKKK       IIII QQQQQQQQQQ                           
                 KKKKKKK       IIII QQQQQQQQQQ                           
                 KKKKKKK                    +                            
                 KKKKKKK                    SSS                          
\\\\\\\\\        KKKKKKK                SSSSSSSS                         
\\\\\\\\\        KKKKKKK                SSSSSSSS                         
\\\\\\\\\        KKKKKKK                SSSSSSSS                         
\\\\\\\\\        KKKKKKK                SSSSSSSS                         
\\\\\\\\\\\\\\   KKKKKKK                SSSSSSSS                         
\\\\\\\\\\\\\\     +                    SSSSSSSS                         
\\\\\\\\\\\\\\RRRRRRRRR                 SSSSSSSS                         
      \\\\\\\\RRRRRRRRR                     SSS                          
      \\\\\\\\RRRRRRRRR                                                  
      \\\\\\\\RRRRRRRRR                                                  
         +    RRRRRRRRR                                                  
        VVVVV RRRRRRRRR                                                  
      VVVVVVV RRRRRRRRR                                                  
      VVVVVVV+RRRRRRRRR                                                  
      VVVVVVV RRRRRRRRR                                                  
            + RRRRRRRRR                                                  
          YYYYY                                                          
          YYYYY                                                          
          YYYYY                                                          
          YYYYY                                                          
     YYYYYYYYYY                                                          
     YYYYYYYYYY                                                          
     YYYYYYYYYY                                                          
     YYYYYYYYYY                                               

Not many long tunnels, and a large number of rooms (which are indicated by different letters. Doorways are +s. There are still, of course, some places the geometry doesn’t make sense. Usually when two joined rooms have a doorway and also have adjacent open blocks (like P and H in the above). However, all in all, not bad for an evening’s screwing around.

Footnotes

1 s1_dim_x - s1_o_x) < (s2_dim_x - s2_o_x
2 s1_dim_y - s1_o_y) < (s2_dim_y - s2_o_y
3 j, i, s_d

Leave a Reply

Your email address will not be published. Required fields are marked *