Intro

I am building a rogue like RPG, currently it is still a work in progress, but I would like to get an intermediate review of my Procedural map generation code.

I've chosen to use the Binary Space Partitioning algo, because it would make my life easier in the future when I will add corridors to the rooms.

There are some TODO's left,

• Creating random rooms within the leaves
• Adding corridors to connect the (random-sized) rooms

but they are not up for review.

Code

from queue import Queue
from random import choice, randint
from collections import namedtuple
from enum import Enum

Position = namedtuple("Position", ["y", "x"])

class Tile(Enum):
WALL = '#'
EMPTY = ' '
ROCK = '.'

class Split(Enum):
HORIZONTAL = 0
VERTICAL   = 1

class Room():
def __init__(self, lu, rd):
self.lu = lu
self.rd = rd

@property
def position_map(self):
return self._get_positions()

@property
def border_map(self):
return self._get_border()

@property
def width(self):
return self.rd.x - self.lu.x

@property
def height(self):
return self.rd.y - self.lu.y

def _get_positions(self):
return [
Position(row, col)
for col in range(self.lu.x + 1, self.rd.x)
for row in range(self.lu.y + 1, self.rd.y)
]

def _get_border(self):
return [Position(y, self.lu.x) for y in range(self.lu.y, self.rd.y)] + \
[Position(y, self.rd.x) for y in range(self.lu.y, self.rd.y)] + \
[Position(self.lu.y, x) for x in range(self.lu.x, self.rd.x)] + \
[Position(self.rd.y, x) for x in range(self.lu.x, self.rd.x + 1)]

class Leaf():
def __init__(self, lu, rd, parent, min_room_space):
self.lu = lu
self.rd = rd
self.parent = parent
self.min_room_space = min_room_space
self._children = None
self._sibling = None
self._room = None

@property
def children(self):
return self._children

@children.setter
def children(self, value):
self._children = value

@property
def sibling(self):
return self._sibling

@sibling.setter
def sibling(self, value):
self._sibling = value

@property
def room(self):
return self._room or self._generate_room()

@property
def width(self):
return self.rd.x - self.lu.x

@property
def height(self):
return self.rd.y - self.lu.y

def _generate_room(self):
#TODO create random sized room in the leaf
room = Room(self.lu, self.rd)
self._room = room
return room

class Map():
def __init__(self, width, height, min_room_space=10, split_threshold=1.25):
self.width = width
self.height = height
self.lu = Position(0, 0)
self.rd = Position(height-1, width-1)
self.min_room_space = min_room_space
self.split_threshold = split_threshold
self._leaves = None
self.board = [[Tile.ROCK.value] * (self.width) for _ in range(self.height)]

@property
def leaves(self):
return self._leaves

def generate(self):
# Reset the board
self.board = [[Tile.ROCK.value] * (self.width) for _ in range(self.height)]
self._generate_leaves()
for leaf in self.leaves:
for pos in leaf.room.position_map:
self.board[pos.y][pos.x] = Tile.EMPTY.value
for pos in leaf.room.border_map:
self.board[pos.y][pos.x] = Tile.WALL.value

#TODO Create corridors by adding corridors from the children up to the highest in the tree

def _generate_leaves(self):
splitable = Queue()
splitable.put(Leaf(self.lu, self.rd, None, self.min_room_space))
leaves = Queue()
while splitable.qsize() > 0:
leaf = splitable.get()
leaf_a, leaf_b = self._split(leaf)

if leaf_a is None and leaf_b is None:
leaves.put(leaf)
else:
leaf.children = (leaf_a, leaf_b)
leaf_a.sibling = leaf_b
leaf_b.sibling = leaf_a
splitable.put(leaf_a)
splitable.put(leaf_b)

self._leaves = list(leaves.queue)

def _split(self, leaf):
if leaf.width / leaf.height >= self.split_threshold:
return self._split_room(leaf, Split.HORIZONTAL)
elif leaf.height / leaf.width >= self.split_threshold:
return self._split_room(leaf, Split.VERTICAL)
else:
return self._split_room(leaf, choice([Split.VERTICAL, Split.HORIZONTAL]))

def _split_room(self, leaf, direction):
leaf_a = leaf_b = None
if direction == Split.VERTICAL:
if not leaf.height < self.min_room_space * 2:
random_split = randint(leaf.lu.y + self.min_room_space, leaf.rd.y - self.min_room_space)
leaf_a = Leaf(leaf.lu,
Position(random_split, leaf.rd.x),
leaf,
self.min_room_space)
leaf_b = Leaf(Position(random_split + 1, leaf.lu.x),
leaf.rd,
leaf,
self.min_room_space)
elif direction == Split.HORIZONTAL:
if not leaf.width < self.min_room_space * 2:
random_split = randint(leaf.lu.x + self.min_room_space, leaf.rd.x - self.min_room_space)
leaf_a = Leaf(leaf.lu,
Position(leaf.rd.y, random_split),
leaf,
self.min_room_space)
leaf_b = Leaf(Position(leaf.lu.y, random_split + 1),
leaf.rd,
leaf,
self.min_room_space)
return leaf_a, leaf_b

def __str__(self):
return "\n".join("".join(b) for b in self.board)

if __name__ == "__main__":
m = Map(50, 50, 10)
m.generate()
print(m)


Example Output

##################################################
#              ##        ##           ##         #
#              ##        ##           ##         #
#              ##        ##           ##         #
#              ##        ##           ##         #
#              ##        ##           ##         #
#              ##        ##           ##         #
#              ##        ##           ##         #
#              ##        ##           ##         #
#              ##        ##           ##         #
#              ##        ##           ##         #
#              ##        ##           ##         #
#              ##        ##           ############
#              ##        ##           ############
#              ##        ##           ##         #
#              ##        ##           ##         #
########################################         #
########################################         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ##         #
#          ##         ##              ############
#          ##         ##              ############
#          ##         ##              ##         #
#          ##         ##              ##         #
########################################         #
########################################         #
#           ##              ##        ##         #
#           ##              ##        ##         #
#           ##              ##        ##         #
#           ##              ##        ##         #
#           ##              ##        ##         #
#           ##              ##        ##         #
#           ##              ##        ##         #
#           ##              ##        ##         #
#           ##              ##        ##         #
#           ##              ##        ##         #
#           ##              ##        ##         #
#           ##              ##        ##         #
##################################################


• Would it be desirable to have rooms of different width within the same "column"? It looks a bit computer-generated with the equal width columns going down.
– maxb
Oct 31, 2018 at 10:57
• @maxb The width's are not always like this, it is random. By coincidence the rooms all have the same width in the example :) Oct 31, 2018 at 10:59
• @maxb I've added a better example output to avoid confusion. (It can happen because there is a minimal room space requirement, so it will stop splitting if the width or height is not big enough) Oct 31, 2018 at 11:01
• Ah, it looks better now!
– maxb
Oct 31, 2018 at 11:15
• Interesting question. Maybe it would be worth explaning the name "lu" and "rd". Nov 9, 2018 at 15:34

This is already nice-looking code. Some minor remarks

upper and lower

on both Leaf and Room, things would become more clear if you defined a left, right, up and down

@property
def down(self):
return self.rd.y

@property
def up(self):
return self.lu.y

@property
def left(self):
return self.lu.x

@property
def right(self):
return self.rd.x


and then you can search and replace all mentions of rd.x, rd.y, lu.x and lu.y. Now I have to make the translation in my head every time.

generators

Room._get_border and Room._get_positions return lists, while the code can be cleaner if they would return generators, using itertools' product and chain

def _get_positions(self):
for y, x in itertools.product(
range(self.left + 1, self.right), range(self.lower + 1, self.upper)
):
yield Position(y, x)

def _get_border(self):

left_wall = (Position(y, self.left) for y in range(self.upper, self.lower))
right_wall = (Position(y, self.right) for y in range(self.upper, self.lower))
upper_wall = (Position(self.upper, x) for x in range(self.left, self.right))
lower_wall = (Position(self.lower, x) for x in range(self.left, self.right + 1))
return itertools.chain(upper_wall, right_wall, lower_wall, left_wall)


enumerable

It's good you use an enumerable for Tile, but then really use it. Don't convert to .value immediately like in Map.init and Map.generate. The translation only needs to be done in __str__. If later you want to add other properties to the tile, like resistance speed, or damage per turn, or whatever, by using the .value in the Map, you won't be able to.

so change __str__ to:

def __str__(self):
return "\n".join("".join(tile.value for tile in b) for b in self.board)


and remove the .value from the other places in the code

Random seed

Allow for a random seed. This will help in testing, and later on if you want to generate the same game, you can easily do so.

All it needs, is a small change in Map.generate

def generate(self, random_seed=None):
random.seed(random_seed)
...


line split

If I need to split the arguments in a method call that is too long, I prefer to split immediately after the (, put the ) on a separate line, and add a , after the last argument., like I adapted in leaf_b

            leaf_a = Leaf(leaf.lu,
Position(leaf.down, random_split),
leaf,
self.min_room_space)
leaf_b = Leaf(
Position(leaf.up, random_split + 1),
leaf.rd,
leaf,
self.min_room_space,
)


And since recently, I don't even worry about line splits any more. I use the black formatter, which is uncompromising, but has very sane settings.

_split_room

The flows for a horizontal split and vertical split are completely separate, so I would make 2 separate functions out of it. Then you can drop the Split enumerable. You can pass functions variables, so _split can become:

def _split(self, leaf):
if leaf.width / leaf.height >= self.split_threshold:
split_func = self._split_room_horizontal
elif leaf.height / leaf.width >= self.split_threshold:
split_func = self._split_room_vertical
else:
split_func = random.choice(
(self._split_room_vertical, self._split_room_horizontal)
)
return split_func(leaf)


split success

at the moment, you convery whether a split was succesfull by leaving leaf_a and leaf_b to None. I'm always wary of using special return variables to signal the success of an operation. Another option here, would be to raise a NotSplittable Exception.

generate

So at this moment, you initialize a Map, and only afterwards generate() the board. Why do you do that? This leaves room open for users of your code to forget to do the generation. I would do an initial generation. And if you want an option to generate a new board with the same settings, you can create a regenerate function, which returns a new map (with or without a new random seed)

Tree

The Tree algorithm looks okay. I don't know what is the advantage of using queue.Queue instead of collections.deque.

The only thing I would change, would be to change the leaves property to into a tuple, and make it generate the leaves on the fly if they haven't been generated already.

@property
def leaves(self):
if self._leaves is None:
self._leaves = tuple(self._generate_leaves())
return self._leaves


Then instead of using the second queue leaves in _generate_leaves, you could do yield leave instead of leaves.put(leaf) and drop the self._leaves = list(leaves.queue)

properties

You make good use of properties, but sometimes you go overboard.

as they are implemented, Leaf.children and Leaf.siblings offer no advantages over using just an attribute

keyword-only parameters

If you have a longer parameter list, especially with some who are used only seldomly, it can be clearer to mark them as keyword-only. For example:

class Map:
def __init__(
self,
width,
height,
*,
min_room_space=10,
split_threshold=1.25,
):


Nothing about code review, I am here to explain my hypothesis that this is not a good algorithm for "Dungon Map" as it can't generate random enough rooms

def _split(self, leaf):
if leaf.width / leaf.height >= self.split_threshold:
return self._split_room(leaf, Split.HORIZONTAL)
elif leaf.height / leaf.width >= self.split_threshold:
return self._split_room(leaf, Split.VERTICAL)
else:
return self._split_room(leaf, choice([Split.VERTICAL, Split.HORIZONTAL]))

def _split_room(self, leaf, direction):
leaf_a = leaf_b = None
if direction == Split.VERTICAL:
if not leaf.height < self.min_room_space * 2:
...
elif direction == Split.HORIZONTAL:
if not leaf.width < self.min_room_space * 2:
...
return leaf_a, leaf_b


The split will stop when:

• leaf.height < self.min_room_space * 2 or leaf.width < self.min_room_space * 2

• And from random_split = randint(leaf.lu.y + self.min_room_space, leaf.rd.y - self.min_room_space) you've make sure that the room's width and heigh with at least self.min_room_space length

• self.split_threshold make sure width and height ratio, and whole space will be fully divided(no width/height longer than min_room_space * 2)

• and no extra space between rooms

So ultimately the whole space will be divided into rooms with width self.min_room_space to self.min_room_space * 2 and same for height.

So how will it looks like

Suppose I have room 1 and room 2 on the top now, looks like this and ready to add room 3, below room 1, on the top left of the whole space. And what's room 3's width, can only be the same as room 1

Because no matter when room 3 width larger or smaller than room 1, there is no possible to fill the "height gap" between room 1 and room 2, as the height difference between is smaller than min_room_space

You might also find, these small rooms always try to be a "big box" together

So these are rooms with not to much difference in width and height, (the difference be smaller with smaller min_room_space) and try to be "big box" together all the time, I think they are well organized rooms

• You are probably right that this may not be the best algo for it. Would you have any better suggestions? Nov 16, 2018 at 15:56
• simple improve, change the min_room_space to a range, instead of a single number. Nov 17, 2018 at 1:22