## Thursday, January 13

### Fun With Dungeon Generation

One of the more preinnal topics of roguelike game design, or general dungeon cralws is "How do I generate that funky dungeon procedurally?". There's an unbelievable number of algorithms, but this one is my favourite...

```import Numeric
import whrandom

class Burrower:
def __init__(self, x, y, lifetime = 0, dx = 0, dy = 0):
self.data = [ x, y, lifetime, dx, dy ]

return self.data == -1

def kill_burrower(self):
self.data = -1

def tick_burrower(self,b):
self.data = self.data + 1

def pick_random_motion(self, allow_diagonals):
motion = whrandom.randrange(0,3)
if motion == 0:
self.data =  - 1
if not allow_diagonals:
self.data = 0
elif motion == 1:
self.data = 1
if not allow_diagonals:
self.data = 0
elif motion == 2:
self.data = -1
if not allow_diagonals:
self.data = 0
elif motion == 3:
if not allow_diagonals:
self.data = 0
self.data = 1

# move the burrower one cell, carving as you go along
# to do  rather than randomly pick a direction, randomly *change* a direction (more control of twistiness, etc)
def move_burrower(self, minx, miny, maxx, maxy, changeprob, allow_diagonals):
if whrandom.random() < changeprob:
self.pick_random_motion(allow_diagonals)
# am i dead ? if so I should be concenrating on a nice firm rigor mortis
return
self.data = self.data + self.data
self.data = self.data + self.data
if self.data < minx:
self.data = 0
self.data = 1
if self.data < miny:
self.data = 0
self.data = 1
if self.data > maxx:
self.data = maxx
self.data = -1
if self.data > maxy:
self.data = maxy
self.data = -1
self.data = self.data + 1
return

class Dungeon:
TileIdNumber = { "granite" : 0 , "empty" : 1, "corridor" : 2 }

def __init__(self,  width, depth):
self.tiles = Numeric.zeros((width, depth))
self.width = width
self.depth = depth

# die, maybe, if lifetime expired, die with a whimper,
# else die with a bang and create a room
# returns count of rooms created so we can track them
# to do : probability of generating "special" rooms?
#
def burrower_death(self, b, bdeath_prob, lifetime, max_room_width, max_room_depth):
result = 0
# if out of time, just die quietly
b.kill_burrower()
# if random chance of death turns up, burst into a room
if whrandom.random() < bdeath_prob:
# we have a room
room_width = whrandom.randrange(max_room_width / 2) + 1
room_depth = whrandom.randrange(max_room_depth / 2) + 1
for x in range (b.data - room_width, b.data + room_width):
for y in range (b.data - room_depth, b.data + room_depth):
if (x >= 1) and (x < self.width-1) and (y >= 1) and (y < self.depth-1):
self.tiles[x][y] = Dungeon.TileIdNumber["empty"]
#           b.kill_burrower()
result = 1
return result

def burrower_birth(self,bbirth_prob):
return whrandom.random() < bbirth_prob

def baby_burrower(self, b):
return Burrower(b.data + whrandom.randrange(2), b.data + whrandom.randrange(2), 0, 0, 0)

def print_dungeon(self):
for y in range(0,self.depth):
s = ""
for x in range(0,self.width):
if self.tiles[x][y] == Dungeon.TileIdNumber["granite"]:
s = s + "#"
else:
s = s + " "
print s
#
# burrowers start on one side of the level, on each turn they can either split (birth prob),
# create a room (die), have a max lifetime, and the algo terminates when room_count is reached
#
def generate(self, burrower_total, room_total, birth_prob, death_prob, turn_prob, lifetime, max_room_width, max_room_depth, allow_diagonals):
# set up burrowers
burrowers = []
for i in range(0,burrower_total):
side = whrandom.randrange(0,4)
if side == 0:
burrower = Burrower( 0, whrandom.randrange(0, self.depth) , 0, 1, 0 )
elif side == 1:
burrower = Burrower( self.width-1, whrandom.randrange(0, self.depth) , -1, 0, 0 )
elif side == 2:
burrower = Burrower( whrandom.randrange(0,self.width), 0, 0, 0, 1 )
else:
burrower = Burrower( whrandom.randrange(0,self.width), self.depth-1 , 0, 0, -1 )
burrowers.append(burrower)
room_count = 0
burrower_alive = True
i = 0
while burrower_alive:
print "Generation " , i
print "Rooms # ", room_count
self.print_dungeon()
print
burrower_alive = False
birth_list = []
for b in burrowers:
burrower_alive = True
b.move_burrower(0, 0, self.width-1, self.depth-1, turn_prob, allow_diagonals)
if (self.tiles[b.data][b.data] == Dungeon.TileIdNumber["corridor"]):
b.kill_burrower()
self.tiles[b.data][b.data] = Dungeon.TileIdNumber["corridor"]
if self.burrower_birth(birth_prob):
birth_list.append(self.baby_burrower(b))
room_count = room_count + self.burrower_death(b, death_prob, lifetime, max_room_width, max_room_depth)
if birth_list:
burrowers.extend(birth_list)
if room_count == room_total:
birth_prob = 0
death_prob = 0
return

if __name__=="__main__":
dungeon = Dungeon(64,32)
dungeon.generate(16, 32, 0.01, 0.005, 0.05, 1024, 16, 16, False)
```