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.
#!/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 ((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[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.
]]]]]]
]]]]]]
]]]]]]]]]]]
]]]]]]]]]]]
]]]]]]]]]]]
]]]]]]]]]]]
]]]]]]]]]]]
]]]]]]]]]]] 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.