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