Draw a Room
We’re drawing a grid. Let’s try drawing a room.
Over on GeePaw’s code, the dungeon is being created by tiling with polyominos. Here, we have a simple flooding / search kind of thing. It’s fun to watch Hill’s version trying to place the ominos to file the plane. It may be less interesting to watch this Python program grow a room by accretion, and certainly if the point is to lay out a dungeon, viewing progress is a waste.
But it will probably be fun. So I think I’ll work to display things incrementally. We can always remove that capability if we want to.
Where Are We Now?
We have a Dungeon class that is so far unused:
class Dungeon:
def __init__(self):
self.rooms = []
@property
def number_of_rooms(self):
return len(self.rooms)
def add_room(self, room):
self.rooms.append(room)
Presumably, that’s a list of Rooms and presumably it will have some behavior someday. Certainly it will be able to iterate the rooms, if nothing else. So as we work today, we’ll build up a dungeon room by room.
We have a somewhat more capable Room class:
class Room:
def __init__(self):
self.cells:list[tuple[int, int]] = []
def add_cell(self, x, y):
self.cells.append((x,y))
def has_cell(self, x, y):
return (x,y) in self.cells
def grow(self, bank):
sx,sy = self.cells[0]
for nx, ny in [(-1,0), (0,1), (1,0), (0,-1)]:
check = (sx + nx, sy + ny)
if bank.has_cell(*check):
bank.take(*check)
self.add_cell(*check)
@staticmethod
def neighbors(self, pair):
x, y = pair
return [(x+dx,y+dy) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]]
def grow_randomly(self, bank):
for cell in sample(self.cells, len(self.cells)):
neighbors = self.neighbors(cell)
for x, y in sample(neighbors, len(neighbors)):
if bank.has_cell(x, y):
bank.take(x, y)
self.add_cell(x, y)
return
return
def cell_string(self):
return ", ".join([str(c) for c in sorted(self.cells)])
Seems likely that neighbors would be a method on a Cell class, if we had one, but we do not have one yet. We do have the CellBank:
class CellBank:
def __init__(self, max_x, max_y):
self.cells = set()
for x in range(max_x):
for y in range(max_y):
self.cells.add((x,y))
def has_cell(self, x, y):
return True if (x, y) in self.cells else False
def take(self, x, y):
self.cells.remove((x, y))
This is just a set containing pairs from zero to max_x, zero to max_y, max values not included. If a pair (x,y) is in the Bank, it is available and if not, not. The Room method grow_randomly uses the CellBank to decide how to grow:
class Room
def grow_randomly(self, bank):
for cell in sample(self.cells, len(self.cells)):
neighbors = self.neighbors(cell)
for x, y in sample(neighbors, len(neighbors)):
if bank.has_cell(x, y):
bank.take(x, y)
self.add_cell(x, y)
return
return
The Room finds a random cell in itself that has a neighbor that is still in the bank, and if it finds one, takes it from the bank and adds it to itself.
What Do We Want?
I think that what we want is something like this:
- Start at (0,0) (or perhaps a random location).
- Loop until the bank is empty:
- Build a room at the start location.
- Remember to remove that location from the bank.
- For a random size in some range that we will choose:
- Add a cell to the room if possible.
- End the loop with an available cell adjacent to the current room, or if none is available, a random available cell.
- Use that cell to start the next room.
- Repeat until there are no cells in the bank.
OK. This makes me want a method on Room that takes a starting cell and a size, that tries to build a room of that size, and that returns a cell for the next room (or None if there are none?).
Let’s try a test:
def test_build(self):
random.seed(234)
bank = CellBank(64, 56)
room = Room()
cell = room.build(bank, 100, (0,0))
assert len(room.cells) == 100
assert cell == (-1,-1)
We posit a new method build that will return a cell adjacent to the build. Write a stub to fail.
I went a bit beyond stub because PyCharm guessed what I wanted to do. Does it have some AI connected up? I’ll make a note to check that. Anyway this code fails the test on checking the cell:
def build(self, bank, length, start_cell):
bank.take(*start_cell)
self.add_cell(*start_cell)
for _ in range(length - 1):
self.grow_randomly(bank)
return tuple((-2, -2))
Pretty clear that (-2,-2) isn’t (-1,-1). Note that because we add the cell at the beginning, we only need length-1 more. I think I’d prefer this loop to be written like this:
def build(self, bank, length, start_cell):
new_cell = start_cell
for _ in range(length):
bank.take(*new_cell)
self.add_cell(*new_cell)
new_cell = self.find_adjacent_cell(bank)
return new_cell
def find_adjacent_cell(self, bank):
for cell in sample(self.cells, len(self.cells)):
neighbors = self.neighbors(cell)
for x, y in sample(neighbors, len(neighbors)):
if bank.has_cell(x, y):
return((x,y))
return bank.available_cell()
Now we always have a cell, either to use or return, given that CellBank had a method available_cell(), which we’ll provide:
class CellBank:
def available_cell(self):
return next(iter(self.cells), None)
That seems to be the Pythonic way to return the first element of the set if there is one, and that should work for us. Let’s see what our test says now.
Expected :(-1, -1)
Actual :(8, 7)
We check the length against 100. Let’s be sure there are no duplicates:
def test_build(self):
random.seed(234)
bank = CellBank(64, 56)
room = Room()
cell = room.build(bank, 100, (0,0))
assert len(set(room.cells)) == 100
assert cell == (8, 7)
Test passes. Commit: added Room build method.
What Have We Done?
I really want to see what we’ve done here. Let’s see about drawing the room in our main. We need to do the work in DungeonView. For now, I’ll just patch it in to see the room. We’ll figure out how to do it right after we see it.
class DungeonView:
def __init__(self):
pygame.init()
pygame.display.set_caption("Dungeon")
self.screen = pygame.display.set_mode(
(screen_width, screen_height))
self.clock = pygame.time.Clock()
# room display below
bank = CellBank(64, 56)
self.room = Room()
random.seed(234)
self.room.build(bank, 100, (0,0))
def main_loop(self):
running = True
moving = False
background = "gray33"
color = "darkblue"
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
self.screen.fill(background)
for x in range(screen_width//cell_size):
dx = (x+1)*cell_size
for y in range(screen_height//cell_size):
...
# added to draw room
for cell in self.room.cells:
dx = cell[0]*cell_size
dy = cell[1]*cell_size
pygame.draw.rect(self.screen, 'red',
(dx, dy, cell_size, cell_size))
self.clock.tick(60)
pygame.display.flip()
pygame.quit()
And this is what we get:
I take out the seed and make two more:
It’s interesting, though not surprising, that the first map has a unit hole in it. Since the algorithm grows from a randomly selected cell, there can easily be holes in the room. In the fullness of time, those will all be found and removed, since when we can’t find an adjacent cell, we find a random available cell, until there are no cells left.
Let’s sum up. There’s bacon to be eaten.
Summary
I think the build method and its helper find_adjacent_cell are actually pretty close to what we need. There are two other methods in Room, grow and grow_randomly that are no longer germane, although I did borrow some code from them to create the new two. We’ll adjust the tests and remove those later.
Despite the randomness, I am rather confident in this code and at this instant can’t think what else I’d like to test. Perhaps something about there not being enough cells, to check the end play.
I’m pretty sure, knowing myself as I do, that what we’ll do next is to build up an entire Dungeon and use it in the DungeonView to display a fully-allocated dungeon. Most likely I’ll work the code into the View and then extract it over to the Dungeon, mostly out of impatience. It might be better to build it in Dungeon and then view it. It would be better from a design perspective and might be a better approach. We’ll see what we do when we do it.
For now, I’ve seen some interesting rooms. Life is good. See you next time!
P.S.
A couple of 200-cell rooms in the middle of the space:
