creating procedural generated RPG Dungeon maps

Question

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

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

Please critique any and all

Answer 1

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,
    ):

Answer 2

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

So from your algo

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