Part 3 - Generating a dungeon
Welcome back to the Roguelike Tutorial Revised! In this tutorial, we’ll be taking a very important step towards having a real, functioning game: Creating a procedurally generated dungeon!
Remember that little wall we created for demonstration purposes in the last tutorial? We don’t need it anymore, so let’s take it out.
- tiles[30][22].blocked = True
- tiles[30][22].block_sight = True
- tiles[31][22].blocked = True
- tiles[31][22].block_sight = True
- tiles[32][22].blocked = True
- tiles[32][22].block_sight = True
tiles[30][22].blocked = True tiles[30][22].block_sight = True tiles[31][22].blocked = True tiles[31][22].block_sight = True tiles[32][22].blocked = True tiles[32][22].block_sight = True
We also need to make a slight change to the list comprehension that created our Tiles.
- tiles = [[Tile(False) for y in range(self.height)] for x in range(self.width)]
+ tiles = [[Tile(True) for y in range(self.height)] for x in range(self.width)]
tiles = [[Tile(False) for y in range(self.height)] for x in range(self.width)] tiles = [[Tile(True) for y in range(self.height)] for x in range(self.width)]
Why are we changing the False to True? Before, we were setting every
Tile to be walk-able by default, so that we could move around easily.
Hence, we passed False to the Tile class, so that the blocked
attribute would be False.
However, our dungeon generation algorithm works the opposite way: We start with a completely walled off room, and start “digging” out sections as we go along. Therefore, we initialize all our tiles to be blocked by default. For the record: every dungeon generation algorithm I’ve seen does this in some way.
One more thing we’ll want to do before getting to our dungeon algorithm
is defining a helper class for our “rooms”. This will be a basic class
that holds some information about dimensions, which we’ll call Rect
(short for rectangle). Create a new file in the map_objects folder,
and name it rectangle.py. Enter the following code into it:
class Rect:
def __init__(self, x, y, w, h):
self.x1 = x
self.y1 = y
self.x2 = x + w
self.y2 = y + hThe __init__ function takes the x and y coordinates of the top left
corner, and computes the bottom right corner based on the w and h
parameters (width and height). We’ll be adding more to this class
shortly, but to get us started, that’s all we need.
Now, if we’re going to be “carving out” a bunch of rooms to create our
dungeon, we’ll want a function to create a room. This function should
take an argument, which we’ll call room, and that argument should be
of the Rect class we just created. From x1 to x2, and y1 to y2, we’ll
want to set each tile in the Rect to be not blocked, so the player can
move around in it. We can put this function in the GameMap class,
since it will be manipulating the map’s list of tiles.
What we end up with is this function:
def initialize_tiles(self):
...
+ def create_room(self, room):
+ # go through the tiles in the rectangle and make them passable
+ for x in range(room.x1 + 1, room.x2):
+ for y in range(room.y1 + 1, room.y2):
+ self.tiles[x][y].blocked = False
+ self.tiles[x][y].block_sight = False
def is_blocked(self, x, y):
...
def initialize_tiles(self):
...
def create_room(self, room):
# go through the tiles in the rectangle and make them passable
for x in range(room.x1 + 1, room.x2):
for y in range(room.y1 + 1, room.y2):
self.tiles[x][y].blocked = False
self.tiles[x][y].block_sight = False
def is_blocked(self, x, y):
...
* Note: initialize_tiles and is_blocked shortened for the sake of
brevity.
What’s with the + 1 on room.x1 and room.y1? Think about what we’re saying when we tell our program that we want a room at coordinates (1,
- that goes to (6, 6). You might assume that would carve out a room like this one (remember that lists are 0-indexed, so (0, 0) is a wall in this case):
0 1 2 3 4 5 6 7
0 # # # # # # # #
1 # . . . . . . #
2 # . . . . . . #
3 # . . . . . . #
4 # . . . . . . #
5 # . . . . . . #
6 # . . . . . . #
7 # # # # # # # #
That’s all fine and good, but what happens if we put a room right next to it? Let’s say this room starts at (7, 1) and goes to (9, 6)
0 1 2 3 4 5 6 7 8 9 10
0 # # # # # # # # # # #
1 # . . . . . . . . . #
2 # . . . . . . . . . #
3 # . . . . . . . . . #
4 # . . . . . . . . . #
5 # . . . . . . . . . #
6 # . . . . . . . . . #
7 # # # # # # # # # # #
There’s no wall separating the two! That means that if two rooms are one right next to the other, then there won’t be a wall between them! So long story short, our function needs to take the walls into account when digging out a room. So if we have a rectangle with coordinates x1 = 1, x2 = 6, y1 = 1, and y2 = 6, then the room should actually look like this:
0 1 2 3 4 5 6 7
0 # # # # # # # #
1 # # # # # # # #
2 # # . . . . # #
3 # # . . . . # #
4 # # . . . . # #
5 # # . . . . # #
6 # # # # # # # #
7 # # # # # # # #
This ensures that we’ll always have at least a one tile wide wall between our rooms, unless we choose to create overlapping rooms. In order to accomplish this, we add + 1 to x1 and y1.
* Note: In case you’re wondering, we don’t subtract 1 from x2 and y2 because Python’s range function does not include the ’end’ value in its range. For example, range(0, 10) would give us [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].
Let’s make some rooms! We’ll need a function in GameMap to generate
our map, so let’s add one:
def initialize_tiles(self):
...
+ def make_map(self):
+ # Create two rooms for demonstration purposes
+ room1 = Rect(20, 15, 10, 15)
+ room2 = Rect(35, 15, 10, 15)
+
+ self.create_room(room1)
+ self.create_room(room2)
def create_room(self, room):
...
def initialize_tiles(self):
...
def make_map(self):
# Create two rooms for demonstration purposes
room1 = Rect(20, 15, 10, 15)
room2 = Rect(35, 15, 10, 15)
self.create_room(room1)
self.create_room(room2)
def create_room(self, room):
...
We need to import the Rect class into the game_map file in order for
this to work. At the top of the file, modify your import section:
+from map_objects.rectangle import Rect
from map_objects.tile import Tile
from map_objects.rectangle import Rect
from map_objects.tile import Tile
Finally, modify engine.py to actually call the new make_map
function.
game_map = GameMap(map_width, map_height)
+ game_map.make_map()
game_map = GameMap(map_width, map_height)
game_map.make_map()
Now is a good time to run your code and make sure everything works as expected. The changes we’ve made puts two sample rooms on the map, with our player in one of them (our poor NPC is stuck in a wall though).
I’m sure you’ve noticed already, but the rooms are not connected. What’s
the use of creating a dungeon if we’re stuck in one room? Not to worry,
let’s write some code to generate tunnels from one room to another. Add
the following methods to GameMap:
def create_room(self, room):
...
+ def create_h_tunnel(self, x1, x2, y):
+ for x in range(min(x1, x2), max(x1, x2) + 1):
+ self.tiles[x][y].blocked = False
+ self.tiles[x][y].block_sight = False
+
+ def create_v_tunnel(self, y1, y2, x):
+ for y in range(min(y1, y2), max(y1, y2) + 1):
+ self.tiles[x][y].blocked = False
+ self.tiles[x][y].block_sight = False
def is_blocked(self, x, y):
...
def create_room(self, room):
...
def create_h_tunnel(self, x1, x2, y):
for x in range(min(x1, x2), max(x1, x2) + 1):
self.tiles[x][y].blocked = False
self.tiles[x][y].block_sight = False
def create_v_tunnel(self, y1, y2, x):
for y in range(min(y1, y2), max(y1, y2) + 1):
self.tiles[x][y].blocked = False
self.tiles[x][y].block_sight = False
def is_blocked(self, x, y):
...
Let’s put this code to use by drawing a tunnel between our two rooms.
...
self.create_room(room2)
+ self.create_h_tunnel(25, 40, 23)
...
self.create_room(room2)
self.create_h_tunnel(25, 40, 23)
Now that we’ve demonstrated to ourselves that our room and tunnel functions work as intended, it’s time to move on to an actual dungeon generation algorithm. Ours will be fairly simple; we’ll place rooms one at a time, making sure they don’t overlap, and connect them with tunnels.
We’ll need two additional functions in the Rect class to ensure that
two rectangles (rooms) don’t overlap. Enter the following methods into
the Rect class:
class Rect:
def __init__(self, x, y, w, h):
self.x1 = x
self.y1 = y
self.x2 = x + w
self.y2 = y + h
+ def center(self):
+ center_x = int((self.x1 + self.x2) / 2)
+ center_y = int((self.y1 + self.y2) / 2)
+ return (center_x, center_y)
+
+ def intersect(self, other):
+ # returns true if this rectangle intersects with another one
+ return (self.x1 <= other.x2 and self.x2 >= other.x1 and
+ self.y1 <= other.y2 and self.y2 >= other.y1)
class Rect:
def __init__(self, x, y, w, h):
self.x1 = x
self.y1 = y
self.x2 = x + w
self.y2 = y + h
def center(self):
center_x = int((self.x1 + self.x2) / 2)
center_y = int((self.y1 + self.y2) / 2)
return (center_x, center_y)
def intersect(self, other):
# returns true if this rectangle intersects with another one
return (self.x1 <= other.x2 and self.x2 >= other.x1 and
self.y1 <= other.y2 and self.y2 >= other.y1)
Don’t worry too much about the specifics here. Just know that the ‘center’ method gives us the center point of a rectangle, and that ‘intersect’ tells us if two rectangles overlap.
We’re going to need a few variables to set the maximum and minimum size
of the rooms, along with the maximum number of rooms one floor can have.
Add the following to engine.py
...
map_height = 45
+ room_max_size = 10
+ room_min_size = 6
+ max_rooms = 30
colors = {
...
...
map_height = 45
room_max_size = 10
room_min_size = 6
max_rooms = 30
colors = {
...
At long last, it’s time to modify make_map to generate our dungeon!
You can completely remove our old implementation and replace it with the
following:
- def make_map(self):
+ def make_map(self, max_rooms, room_min_size, room_max_size, map_width, map_height, player):
- room1 = Rect(20, 15, 10, 15)
- room2 = Rect(35, 15, 10, 15)
- self.create_room(room1)
- self.create_room(room2)
- self.create_h_tunnel(25, 40, 23)
+ rooms = []
+ num_rooms = 0
+
+ for r in range(max_rooms):
+ # random width and height
+ w = randint(room_min_size, room_max_size)
+ h = randint(room_min_size, room_max_size)
+ # random position without going out of the boundaries of the map
+ x = randint(0, map_width - w - 1)
+ y = randint(0, map_height - h - 1)
def make_map(self): def make_map(self, max_rooms, room_min_size, room_max_size, map_width, map_height, player): room1 = Rect(20, 15, 10, 15) room2 = Rect(35, 15, 10, 15) self.create_room(room1) self.create_room(room2) self.create_h_tunnel(25, 40, 23) rooms = [] num_rooms = 0 for r in range(max_rooms): # random width and height w = randint(room_min_size, room_max_size) h = randint(room_min_size, room_max_size) # random position without going out of the boundaries of the map x = randint(0, map_width - w - 1) y = randint(0, map_height - h - 1)
The variables we’re creating here will be what we use to create our
rooms momentarily. randint gives us a random integer between the
values we specify. In this case, we want our width and height to be
between our given minimums and maximums, and our x and y should be
within the boundaries of the map.
We also need to import randint from random at the top of the file.
Your import section for game_map.py should now look something like
this:
from random import randint
from map_objects.rectangle import Rect
from map_objects.tile import TileLast thing before we proceed: We need to update the call to make_map
in engine.py, because now we’re asking for a bunch of variables that
we weren’t before. Modify it to look like this:
...
game_map = GameMap(map_width, map_height)
- game_map.make_map()
+ game_map.make_map(max_rooms, room_min_size, room_max_size, map_width, map_height, player)
...
game_map = GameMap(map_width, map_height)
game_map.make_map()
game_map.make_map(max_rooms, room_min_size, room_max_size, map_width, map_height, player)
Now we’ll put our Rect class to use, by passing it the variables we
just created. Then, we can check if it intersects with any other rooms.
If it does, we don’t want to add it to our rooms, and we simply toss it
out.
...
y = randint(0, map_height - h - 1)
+ # "Rect" class makes rectangles easier to work with
+ new_room = Rect(x, y, w, h)
+
+ # run through the other rooms and see if they intersect with this one
+ for other_room in rooms:
+ if new_room.intersect(other_room):
+ break
...
y = randint(0, map_height - h - 1)
# "Rect" class makes rectangles easier to work with
new_room = Rect(x, y, w, h)
# run through the other rooms and see if they intersect with this one
for other_room in rooms:
if new_room.intersect(other_room):
break
If the room does not intersect any others, then we’ll need to create it. Rather than introducing a boolean (True/False value) to keep track of whether or not we intersected, we can simply use a for-else statement! This is a unique, lesser known Python technique, which basically says “if the for loop did not ‘break’, then do this”. We’ll put our room placement code in this ’else’ statement right after the for-loop.
...
for other_room in rooms:
if new_room.intersect(other_room):
break
+ else:
+ # this means there are no intersections, so this room is valid
+
+ # "paint" it to the map's tiles
+ self.create_room(new_room)
+
+ # center coordinates of new room, will be useful later
+ (new_x, new_y) = new_room.center()
+
+ if num_rooms == 0:
+ # this is the first room, where the player starts at
+ player.x = new_x
+ player.y = new_y
...
for other_room in rooms:
if new_room.intersect(other_room):
break
else:
# this means there are no intersections, so this room is valid
# "paint" it to the map's tiles
self.create_room(new_room)
# center coordinates of new room, will be useful later
(new_x, new_y) = new_room.center()
if num_rooms == 0:
# this is the first room, where the player starts at
player.x = new_x
player.y = new_y
We’re creating our room, and saving the coordinates of its “center”. If it’s the first room we’ve created, then we place the player right in the middle of it. We’ll also put these center coordinates to use in just a moment to create our tunnels.
...
if num_rooms == 0:
# this is the first room, where the player starts at
player.x = new_x
player.y = new_y
+ else:
+ # all rooms after the first:
+ # connect it to the previous room with a tunnel
+
+ # center coordinates of previous room
+ (prev_x, prev_y) = rooms[num_rooms - 1].center()
+
+ # flip a coin (random number that is either 0 or 1)
+ if randint(0, 1) == 1:
+ # first move horizontally, then vertically
+ self.create_h_tunnel(prev_x, new_x, prev_y)
+ self.create_v_tunnel(prev_y, new_y, new_x)
+ else:
+ # first move vertically, then horizontally
+ self.create_v_tunnel(prev_y, new_y, prev_x)
+ self.create_h_tunnel(prev_x, new_x, new_y)
+
+ # finally, append the new room to the list
+ rooms.append(new_room)
+ num_rooms += 1
...
if num_rooms == 0:
# this is the first room, where the player starts at
player.x = new_x
player.y = new_y
else:
# all rooms after the first:
# connect it to the previous room with a tunnel
# center coordinates of previous room
(prev_x, prev_y) = rooms[num_rooms - 1].center()
# flip a coin (random number that is either 0 or 1)
if randint(0, 1) == 1:
# first move horizontally, then vertically
self.create_h_tunnel(prev_x, new_x, prev_y)
self.create_v_tunnel(prev_y, new_y, new_x)
else:
# first move vertically, then horizontally
self.create_v_tunnel(prev_y, new_y, prev_x)
self.create_h_tunnel(prev_x, new_x, new_y)
# finally, append the new room to the list
rooms.append(new_room)
num_rooms += 1
This ’else’ statement covers all cases where we’ve already placed at least one room. In order for our dungeon to be navigable, we need to ensure connectivity by creating tunnels. We get the center of the previous room, and then, based on a random choice (between one or zero, or a coin toss if you prefer to think of it that way), we carve our tunnels, either vertically then horizontally or vice versa. After all that, we append the room to our ‘rooms’ list, and increment the number of rooms.
And that’s it! There’s our functioning, albeit basic, dungeon generation algorithm. Run the project now and you should be placed in a procedurally generated dungeon! Note that our NPC isn’t being placed intelligently here, so it may or may not be stuck in a wall.
If you want to see the code so far in its entirety, click here.