Fun with Roguelike GeneratorsPosted by Jack on 2013-01-23 at 17:02
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.
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.
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 title="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 # [ * 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) s1_o_x, s1_o_y = s1p s2_dim_y = len(s2) s2_dim_x = len(s2) 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 ((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 ((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((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 == m[c1]]) hall = Hallway() if c1 == 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: 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 == 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 == 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 title="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.