BSP dungeon generation

Game Engine Game Engine Support and Discussion
1

As many people might know I’ve been working on a personal project for some time now, a 3d roguelike.

Until now I’ve been using a rather primitive dungeon generation script which relies on brute force to place rooms and then uses an A star routine to link the rooms with corridors.

The code is something like this:

def place_a_room(array):
    room = get_random_room()
    
    corner = random_x_y_position()
    fits_check = check_and_place_room(room,corner,array)  
    
    if fits_check:
        return True
    else:
        return False                 

error = 0

array = get_array(min,max)

target_number_of_rooms = 20

number_of_rooms = 0
                
while number_of_rooms < target_number_of_rooms or error < 1000:
    try: 
        room_placement = place_a_room(array)   
        if room_placement:
            number_of_rooms +=1
        else:
            error +=1

Though I’ve simplified it and left out some of the functions.

This worked fine at first because I have a relatively small number of rooms with long snaking corridors. However, I’ve found that it leads to too many corridors and not really enough rooms, unless I set the error number really high, which in turn leads to a very long generation time. These maps can be a bit boring, as corridors are not that interesting.

I’ve been looking at binary space partition algorithms for dungeon generation and they produce a much more interesting dungeon, with lots more rooms and less corridor space. they can also be tweaked to give a result almost identical to my first dungeon generation script.

Here are some of the resources I used:
http://doryen.eptalys.net/articles/bsp-dungeon-generation/


http://eskerda.com/bsp-dungeon-generation/

I couldn’t find a python implementation of BSP trees however so I had to write my own. There was a java script version, but I couldn’t work out exactly what they’re doing.

I’ve muddled though and come up with something that seems to work (partially).
Here’s a couple of examples:

bsp_tree_1.jpg688×671 37.3 KB

Well it does some of what I want, I can get the room areas, and by putting in a bit of a cheat I can stop splitting of random rooms. The problem is that I can’t construct the tree structure. I only end up with the leaves at this point.

I could just continue with this version of the script, after all I’m using a burrowing algorithm to link my rooms, but it would be nice to work out how to preserve the tree structure, I could do some interesting things with it, like earmarking some areas to be not linked to the others (they would be reachable by stairs from above or below) or using different types of tilesets in different branches.

Here’s the blend file:
bsp_3.blend (440 KB)

Any ideas?
I’m thinking that something like python heaps could be the way to go, or a multilevel dictionary… Something that can preserve the hierarchical structure of the tree. (I’ve never successfully used heap before though…)

2

So you are going for a labyrinth style generator? I mean buildings usually have multiple paths through them. But I see this might be a bit to simple to solve.

I suggest you start with one room. When you split the room into two rooms, you add a doorway between them at a random location. When you continue to do so, you get your labyrinth. So splitting a room + adding a doorway between them. This guaranties all rooms are connected.

You can set the start and end position either before or after the generation. Just ensure they are not in the same room ;).

If you want several paths, you can add random doorways later or during splitting.

What do you think?

3

I really, really hate it when people post algorithms. It’s almost inevitable that I then spend an inordinate amount of time reading about them and creating my own implementation :wink:

I’ve written an implementation of a BSP tree here. You can change quite a number of parameters, such as the maximum dimension (which will then be split to reduce the extreme dimension) of the node, the smallest node size, the variance of the splitting position (using a random value centred at 0.5 ± a randomized range), the probability that nodes of a certain axis dimension (from the smallest dimension to a value larger than that (protected_size_threshold)) should not be split.

The closer the split variance is to 0.5, the more extreme split axis will occur.

This code could probably have an implementation error, but It seems solid enough. The next step of connecting tunnels is up to you :wink:

Also, each node stores its parent, and its child nodes, so you can easily traverse up or down the tree.

from random import Randomfrom itertools import product
from bge import logic




class Directions:
    vertical = "vertical"
    horizontal = "horizontal"


    @classmethod
    def reverse(cls, direction):
        """Return the alternative direction to given direction


        :param direction: axis direction
        """
        if direction == cls.vertical:
            return cls.horizontal


        return cls.vertical




class Dimensions:


    def __init__(self, right, left, top, bottom):
        self.left = left
        self.right = right
        self.top = top
        self.bottom = bottom


        self.width = right - left
        self.height = top - bottom


    def __eq__(self, other):
        assert isinstance(other, self.__class__)


        if self.left != other.left:
            return False


        if self.right != other.right:
            return False


        if self.top != other.top:
            return False


        if self.bottom != other.bottom:
            return False


        return True


    def __str__(self):
        return "Dimensions: Left: {:.3f}, Right: {:.3f}, Top: {:.3f}, Bottom: {:.3f}".format(self.left, self.right,
                                                                                             self.top, self.bottom)


    @classmethod
    def from_dict(cls, dict_):
        horizontal = dict_[Directions.horizontal]
        vertical = dict_[Directions.vertical]
        return cls(*(horizontal + vertical))


    def get_axis_size(self, axis_direction):
        """Return the size along a given axis


        :param axis_direction: direction of axis
        """
        if axis_direction == Directions.vertical:
            return self.height


        return self.width


    def get_axis_pair(self, axis_direction):
        """Return the maximum, minimum values for given axis


        :param axis_direction: direction of axis
        """


        if axis_direction == Directions.vertical:
            return self.top, self.bottom


        return self.right, self.left




class RandomNumberGenerator(Random):


    def random_bool(self, probability=0.5):
        """Return a random boolean value


        :param probability: likelihood of returning True
        """
        return self.random() <= probability


    def centered_random(self, median=0.5, range=0.5):
        """Return a weighted random value


        :param weight: the influence of the random
        """
        assert 0 <= (median - range) and (median + range) <= 1.0
        return self.uniform(median - range, median + range)




class BSPGenerator:


    def __init__(self, dimensions, maximum_dimension_ratio=1.25, smallest_partition_size=1, protected_partitions=0.1,
                 protection_size_threshold=None, split_variance=0.5, seed=None):
        self.dimensions = dimensions
        self.random_number_generator = RandomNumberGenerator(seed)
        self.maximum_dimension_ratio = maximum_dimension_ratio
        self.smallest_partition_size = smallest_partition_size
        self.protection_size_threshold = protection_size_threshold or (smallest_partition_size * 2.0)
        self.protected_partitions = protected_partitions
        self.split_variance = split_variance


    def create_tree(self):
        """Create a BSP tree.


        Returns the parent BSPNode instance
        """
        node = BSPNode(self, self.dimensions)
        node.partition()
        
        return node


    def should_split_node(self, partition_size):
        """Determine if we should split a node given a size along the partition axis


        :param partition_size: length along partition axis
        """
        smallest_partition_size = self.smallest_partition_size


        if smallest_partition_size < partition_size < self.protection_size_threshold:
            is_protected = self.random_number_generator.random_bool(self.protected_partitions)


            if is_protected:
                return False


        return partition_size > smallest_partition_size




class BSPNode:


    def __init__(self, bsp_generator, dimensions, parent=None):
        self.bsp_generator = bsp_generator
        self.dimensions = dimensions


        self.children = []
        self.parent = parent


    @property
    def leaves(self):
        """Find the leaf nodes of this node"""
        def _iter_leaves(node):
            if node.children:
                for child in node.children:
                    yield from _iter_leaves(child)


            else:
                yield node


        return _iter_leaves(self)


    @property
    def all_children(self):
        def _iter_children(node):
            for child in node.children:
                yield from _iter_children(child)


            yield node


        return _iter_children(self)


    def partition(self):
        """Split the node into two sub nodes"""
        dimensions = self.dimensions
        bsp_generator = self.bsp_generator


        maximum_dimension_ratio = bsp_generator.maximum_dimension_ratio
        random_number_generator = bsp_generator.random_number_generator


        width = dimensions.width
        height = dimensions.height


        # Prevent abnormal dimensions
        if (width / height) > maximum_dimension_ratio:
            # Split direction tangential to the actual split axis
            split_direction = Directions.horizontal


        elif (height / width) > maximum_dimension_ratio:
            split_direction = Directions.vertical


        else:
            split_direction = random_number_generator.choice((Directions.horizontal, Directions.vertical))


        other_direction = Directions.reverse(split_direction)


        split_bounds_max, split_bounds_min = dimensions.get_axis_pair(split_direction)
        other_bounds = dimensions.get_axis_pair(other_direction)


        split_length = dimensions.get_axis_size(split_direction)
        split_location = split_bounds_min + \
                         (random_number_generator.centered_random(range=bsp_generator.split_variance) * split_length)




        minimum_dict = {split_direction: (split_location, split_bounds_min), other_direction: other_bounds}
        minimum_child_dimensions = Dimensions.from_dict(minimum_dict)
        minimum_child = BSPNode(bsp_generator, minimum_child_dimensions, parent=self)


        maximum_dict = {split_direction: (split_bounds_max, split_location), other_direction: other_bounds}
        maximum_child_dimensions = Dimensions.from_dict(maximum_dict)
        maximum_child = BSPNode(bsp_generator, maximum_child_dimensions, parent=self)


        self.children.extend((minimum_child, maximum_child))


        if bsp_generator.should_split_node(split_location - split_bounds_min):
            minimum_child.partition()


        if bsp_generator.should_split_node(split_bounds_max - split_location):
            maximum_child.partition()




def bsp_builder(cont):
    own = cont.owner
    scene = own.scene
   
    dimensions = Dimensions(40, 0, 40, 0)
    generator = BSPGenerator(dimensions, smallest_partition_size=9, maximum_dimension_ratio=1.25, split_variance=0.3)


    tree = generator.create_tree()
    create_object = lambda: scene.addObject("ground_tile", own)


    nodes = list(tree.all_children if 0 else tree.leaves)


    for index, node in enumerate(nodes):
        draw_node(create_object, node, -index)




def draw_node(create_object, node, z_position):
    leaf_color = [node.bsp_generator.random_number_generator.random() for _ in range(4)]
    dimensions = node.dimensions    
    
    min_x = round(dimensions.left)
    max_x = round(dimensions.right)
    
    min_y = round(dimensions.bottom)
    max_y = round(dimensions.top)
    
    for x, y in product(range(min_x, max_x), range(min_y, max_y)):        
        room_tile = create_object()             
        room_tile.worldPosition = [x, y, z_position]
        room_tile.color = leaf_color
4

The original (author’s) link is dead but:


https://bmark.us/bmark/readable/9d95ad236c242f

5

That looks like an interesting generator, there’s lots of random dungeon types out there and all of them have advantages and disadvantages. BSP trees have the disadvantage of looking very square in overall outline. But they can have a nice mix of large and small rooms with simple corridors. Tunnelers have the advantage of creating very organic maps, but the disadvantage that they only reall look great when you have a huge map. Small tunneling maps often look very similar to each other.

I recently talked about prefabs, that is dungeon sections which are designed in advance, usually by hand and then slotted in to a gap in the dungeon. BSP trees can be great for accommodating prefabs, and with a good algorithm, prefabs can also be procedurally generated from smaller parts.

I think that’s the way I’m heading right now.

@ @Monster

So you are going for a labyrinth style generator? I mean buildings usually have multiple paths through them. But I see this might be a bit to simple to solve.

I suggest you start with one room. When you split the room into two rooms, you add a doorway between them at a random location. When you continue to do so, you get your labyrinth. So splitting a room + adding a doorway between them. This guaranties all rooms are connected.

You can set the start and end position either before or after the generation. Just ensure they are not in the same room ;).

If you want several paths, you can add random doorways later or during splitting.

What do you think?

The result in the picture above looks like a simple recursive subdivision labyrinth, but please check out the links, the end result has a very different style (because the rooms form only part of the total space assigned for them). Also I’m using a tunneling algorithm for the corridors, so conectivitiy is very different from standard BSP trees.

I do need the BSP tree structure though for doing other procedural generation actions, such as allocating multiple tilesets and monster spawn types in the same level. Like if branch A1 has the “filthy” tile set, all the daughter branches of that branch will also have it. If B2 is “magical” and B3 is “dark” some areas of the map will share that theme. I can also use it for allocating keys. For example, branch A is all unlocked, and you can find a “gold” key there. Branch B is locked and requires a gold key.

@ @agoose77
That algorithm looks amazing and has given me some good ideas.
But… There’s so much there I don’t understand I’d not be doing myself any favors if I used it in my project. For example even after reading about decorators I’m still confused about what they are and what they do.

I’m trying to teach myself so it’s important to know what something is doing and how it works before I use it. I learned a lot just reading through your code and doing some google searches, like I just learned about for _ in range from some questions on stack overflow, so that’s something good I got from it.

Anyway, I think I’m going to try and muddle through with what I know and see if i can get it to work. :slight_smile:

6

So what is your aim rooms or caves?

7

I want to create rooms, of various different sizes but that fit well in to a level with few gaps and fairly straight forward corridors.
My current method leaves the rooms too far spaced apart and requires long twisting corridors to link them up.

I’m not as much interested in realism as I am in creating interesting game play.

8

I think in this case a tunnel generating algorithm would not be the best idea.

Rooms are usually connected by doors.
Additionally rooms usually fill nearly all available space, leaving no gaps. I guess this is not that important if there are not that much doors as you seem to aim for.

Btw. you can make it more believable if you add “dummy doors” = locked doors to force the player to follow a long path. Or as a gimmick, the doors can be unlocked when both sides were visited = shortcut.

BTW. with decorator you mean some 3D elements or the decorator design pattern?

9 
@property

just fills my head with marshmallows when I try to read about what it’s doing. Probably because I still don’t properly understand classes.

In a house rooms are usually connected by doors, but in a dungeon or tunnel system rooms are usually connected by corridors. In medieval castles this was to create choke points which could be easily defended and to avoid undermining the castle above.

Mostly it’s a gameplay decision to have rooms connected by corridors. I want a mix of open areas and choke points. You have 4 characters in the game and not all of them will be dedicated to combat. The player will need to be able to position themselves so that a limited amount of enemies can attack them at one time. I don’t want the choke points to be actually at the doors because all too often that area is visually cluttered. It can be difficult to see what’s going on with your characters when walls and doors are in the way. The map has to be visually interesting and also interesting to play on.

10

The algorithm I posted is still a bsp tree, the main thing is writing it in a manner that it doesn’t need a game object to run, and can be reused.

The property decorator does what all decorators do, and ‘wraps’ the function after it in another object. It’s the same as writing ‘func=mydecorator(func)’
The object that it wraps it in makes use of the descriptor protocol. Essentially the descriptor protocol is a means of intercepting lookups on class attributes. You can find out when a user accesses an attribute before that value is returned. The property descriptor simply executed the function it wraps and returns the value whenever it is looked up on the class

11

Ah, ok in Python they are called decorators. I know them from Java as annotation. I think agoose77 described them pretty well.

The get an introduction, I suggest you look at the Python documentation. Search for property(). There is a whole section explaining how to define one, incl. the decorator option.

Regarding the corridors. A corridor is just a room. But with a special form.

The BSP method stays the same. To create a corridor, you do not split a room into two, but at least three rooms. Add doors from the middle room to both sides. You can even do that symmetrically. Ensure the corridor rooms are not to large or to small.

12

= all Greek to me. :slight_smile:

Don’t worry, I do “get” the code you posted, but I can’t get my head around the details. I’ve just about got the hang of dictionaries, loops, arrays and a lot of other things but some things are a little beyond me yet. I’m sure I’ll absorb them eventually, as I come to understand more about the tools I’m already using. I’ve never had any programming classes or any kind of education about coding (except some visual basic when I was in school, but that didn’t help) so what I know now is all knowledge that I’ve built up from experimentation and research.

13

I’ll post a reply nonetheless, because it might be useful for other interested users too. I know what you’re saying, we’ve all been there at some stage or another. I would recommend trying out new ideas, because it’s quite rewarding to learn the details, and interesting features of Python, and often gives you more tools to work with. Descriptors are probably the most useful thing I’ve discovered in Python, apart from (occasionally) metaclasses, and generator functions.

A little information on classes, and class instances
Classes and class instances are different things (but related, of course). Both classes and class instances have a “dictionary” which stores their individual data, which you can find with the .dict attribute.

When you create a class with the “class” statement, everything within the class body is run as python code. Any variable assignments inside the class body, such as


class Foo:
    bar = 1

are saved to the class dictionary.

When you create an instance of a class, writing an attribute to the instance will store it in the instance dictionary.

foo = Foo()
foo.bar = 12

How attributes are found
When you access an attribute of a class instance, it first looks for the attribute in the dictionary of the class instance (foo.dict) and then if it can’t find it, it looks in the class dictionary (Foo.dict).

This finding step is performed by the getattribute method of classes, and is run on the class instance when looking for class instance variables. (For class attributes, it is a little different (metaclass voodoo, see here https://docs.python.org/3.3/reference/datamodel.html#special-method-lookup)).

If our search fails, getattribute will call the class instance’s getattr method, which is a last-resort attempt to return some value. Users can override this when they might be adding some extra behaviour that knows the attribute will be missing. (overriding getattribute is a little more complex as everything calls that method, so you have to perform the lookup yourself with object._getattribute(self, name) which is a real pain!)

How descriptors come into play
Anyway, this is just a little bit of how-things-happen information. Now the important part. If getattribute finds the attribute, we don’t just return it. Often, the value will define some behaviour for when it is accessed, with the descriptor protocol. There is a useful overview here https://docs.python.org/3.3/howto/descriptor.html

The descriptor protocol is basically another means to intercepting read/write calls of attributes (and deletions too) from classes, and class instances. It has some benefits/reasons to use over changing the getattribute methods as before:

  • Sometimes you won’t want to change the behaviour of every attribute, so the descriptor protocol means that it happens on a per-attribute basis
  • The class doesn’t need to know about the attributes/attribute types in order to be able to provide this special behaviour, which makes the attributes more reusable.
  • Descriptors work for both class lookups (Foo.bar) and instance attributes (foo.bar) with the same methods.

So, instead of returning our attribute from the getattribute method, the class and class instance will first check if the attribute defines a “get” method. If it does, it calls it with some arguments, and returns the value of that method call. Otherwise, it just returns the attribute it found.

The property descriptor basically does the following:

  • “Wraps” (stores) the function that it was initialised with (you can either write prop_func = property(prop_func) or
@property
def prop_func(self):
    ....
  • Defines a get method which calls the property function and returns the value

So if we have an example class:


class Foo:
    
    @property
    def prop(self):
        return "hello world"

Then if you access the property of the class instance, it would return “hello world”


foo = Foo()
print(foo.prop)

# >> Hello World

We could also have written our class like this


class Foo:
    
    def prop_func(self):
        return "hello world"

    prop = property(prop_func)

The property decorator, and property descriptor
The reason for this is that writing @decorator basically does this:

  • Call the function “decorator” (in our case “property”) with the function defined after the @decorator line
  • Set the value of “prop” to the returned value of the decorator call (which for “property” is just a property descriptor, imagine that “property” is a class, we get a class instance.

The fact that we have used the terms descriptor and decorator is not because they are related to one another. They are very much separate, it’s just that decorators make things easier, as you can see with the second way of writing the class, which is more ugly (in my opinion!)

How our property is accessed
So, the entire sequence looks something like this:

  • Request foo.prop.
  • Find “foo”.
  • Run foo’s getattribute method (foo.getattribute), looking for a property called “prop”.
  • Try and find it in the instance dictionary (foo.dict).
  • We couldn’t find it there, because we defined prop on the class itself, not the class instance.
  • Try and find it in the class dictionary (Foo.dict).
  • Success! Read the “prop” value from the class instance dictionary.
  • We found a “property” instance.
  • Look for a get method on the property instance.
  • We found that too! Now call that get method, and give it some arguments.
  • It returned a value! Return that value to whoever asked for foo.prop!
14

So decorators are a way of making the code more tidy? You could write it the second way and it would still work the same?

I can see that it’s good to be able to get a property which has been run through a function.

If for example I want to get a character’s strength score (which is 5), but he is wearing a ring of strength which boosts the score by 5 for example (the class function in this case looks for any bonuses which could be applied by equipment or spells before returning the attribute), then the function could add the bonus before returning the attribute.

so:

character.strength

in that case would return 10. If he took off the ring later, the same call would return 5.

Am I right? That actually would be very useful to me if it’s the case.

15

As most things are with programming, it’s a means to an end. Properties are particularly useful for such tasks as:

  • Lazy evaluation - Some tasks might be quite expensive to calculate. Rather than calculating them, storing them, and recalling the saved value on the next call, API users just want a single point of call (see the example below)
  • Associated tasks - sometimes, you might provide an API which does more than the user expects, e.g reading a property on a “Database object” actually requires it to open the database, get the result, perform any authentication etc. The user doesn’t need to know about this in most cases, so hiding the setup machinery in a property function can be quite useful
  • Runtime-checks. This is your spell example. All of these examples can still be done in different ways, but sometimes properties offer a nice way to do something. You could alternatively have “addBooster” and “removeBooster” functions which modify the damage when you change the inventory. This is probably more efficient, but adds more code that can be made more user friendly with properties. You can also use this for input validation - checking that the user is writing a value in a certain range, for example.

Lazy evaluation


class Foo:

    def _do_something_slow(self):
        pass


    @property
    def bar(self):
        if not hasattr(self, "_result"):
            print("Once in a lifetime call!")
            self._result = self._do_something_slow()
        
        return self._result
16

Yes, the main benefit is that you can configure your code without touching it. This removes some strong dependencies from your code.

E.g. If the implementation of @property changes, your code does not need to change and will still work.

There is a wide use for them. A typical use case is to mark code as tests with a @test decorator. This way the test runner (which is and should never be a part of your code) knows to run this code as test.

No, you do not use decorators to do that. This is a different layer of the code.

Yes, if you mean @property.

e.g.


class MyDemoCharacter():
    def __init__(self, name, baseStrength = 100):
        self.name = name
        self.baseStrength = baseStrength
        self.strengthModifiers = []

    @property
    def strength(self):
         strength = self.baseStrength 
         for modifier in self.strengthModifiers:
            strength = modifier.calculateStrength(strength)
         return strength

    def dress(self, strengthModifier):
        self.strengthModifiers.append(strengthModifier)

    def undress(self, strengthModifier):
        self.strengthModifiers.remove(strengthModifier)

    def __str__(self):
        return "I'm {} and my base strength is {}. I wear {} modifiers that makes my strength {}".format(
                self.name, self.baseStrength, len(self.strengthModifiers), self.strength)

now you need a modifier to be dressed with

                
class RingOfAddingTenPercent():
    def calculateStrength(self, strength):
      return strength * 1.1

Now you have the blueprint of a ring “One Ring to rule them al…” :smiley:

This allows us to tell a


def littleStory():
    boy = MyDemoCharacter("Little boy", 15)
    print(boy)
    
    ring = RingOfAddingTenPercent()
    print( "hey I found a ring" )
    boy.dress(ring)
    print(boy)
    
    print()    
    knight = MyDemoCharacter("Blackadder")
    print(knight)
    
    print()
    print("Little boy give me the ring, I'm your Lord!")
    if boy.strength < knight.strength:
        print("Oh yes, here it is")
        boy.undress(ring)
        knight.dress(ring)
    else:
        print("No way, you are not stronger than me")
    print(knight)
    print(boy)

I hope you like it.

Hint:
Be aware if someone reads from a property (here strength) he expect is is a fast operation. So make sure, whatever you do to return an result, do not waste processing time. If you need more time better provide a function e.g. calculateStength(). An reader would expect it might take a while.

17

Following this, it’s up to you when to use methods vs properties. It is expected that properties are fast to access (though these days, I assume no such thing and always create local variables to prevent attribute lookups more often than absolutely necessary).

18

Thanks, that all makes for interesting reading. :slight_smile:

Do you like Blackadder too, Monster?
Did you hear poor old flashheart (Rik Mayall) died recently? It brought a tear to my eye. He was only 50(ish).

19

I just saw one or two episodes same years ago. It was not playing often in Germany or I just missed them. I really like Rowan Atkinson.

Looking for a knight stealing a ring from a boy, yes, blackadder popped into my mind ;).

Btw. This code was meabt to demonstrate how you can create a readonly property into your class using @property. It does not mean it is the best way to do it in this way. It is one way. Hopefully you know now how to read @property (notice there is no member variable called self.strength).

If you want you can check the Python documentation, how to add the setter for strength.

20

Thanks Monster. I’ll take a look.

I did some more work on this following some of the ideas in @agoose77’s script.
I used dictionaries rather than classes for now because that allowed me to get it clear in my head, once I’m sure it’s working correctly I’ll go back and try to improve it using some of the things talked about here.