Creating Random Dungeon Using BSP

Monkey Forums/Monkey Programming/Creating Random Dungeon Using BSP

Why0Why(Posted 2013) [#1]
Hi all. I am working on dungeon creation and I would like to use the method described here:

http://7yrl.com/2009/04/10/7/

I have spent several hours working on it and am not really making much headway. The code has gotten long and I just can't seem to get it right. Does anyone have an example in Monkey or can give me a hand?

Thanks...


Gerry Quinn(Posted 2013) [#2]
Have a look at RogueBasin under Articles/Map. There's one on the BSP method. Not in Monkey but it goes through the algorithm step by step, with pictures.


Why0Why(Posted 2013) [#3]
I have looked at it. I just can't seem to get it. I have read pretty much everything I can find. Found code in Java and C++ too and just can't get it converted properly.

I split it and I stored the completed squares that were the right size in a different array. I guess I just can't get the continuing iteration and the links right.


Gerry Quinn(Posted 2013) [#4]
Go to bed and when you look at it tomorrow you will probably see your mistake!


Xaron(Posted 2013) [#5]
Hang on I can send you my code, you can check a running apk for Android here: http://www.codeknitters.com/dl/dungeon/dungeon_b32.apk

It looks like:



Why0Why(Posted 2013) [#6]
Hey Xaron, thanks! That is a good foundation. What method are you using? Looks like maybe a maze generator with rooms placed on top?


Raul(Posted 2013) [#7]
@Xaron: I am also interested in your example :)


zoqfotpik(Posted 2013) [#8]
One method I did for this years ago was I made two functions which called each other recursively, vrect and hrect. Each one took a rectangle as input, split it in two either horizontally or vertically, and then called the other function on the two sub-rects it had just created (hrect called vrect, vrect called hrect.) When the rectangle was below size limits the recursion bailed out.

The code for that was much, MUCH simpler than the BSP dungeon code linked above.


Why0Why(Posted 2013) [#9]
zoqfotpik, your way is a better way. Gerry provided me with some code that works the same way. I also found a java example that did it the way that you mentioned. I was making it too difficult.


zoqfotpik(Posted 2013) [#10]
Lots of people are scared of recursion but it's an incredibly powerful technique.

You could probably simplify it further but the way I did it is basically the oldstyle LISP way-- there is some code duplication but it's trivial and conceptually much easier.


Xaron(Posted 2013) [#11]
Hang on guys, still had a lot of family workload this weekend. lol

Will post it soon...


Gerry Quinn(Posted 2013) [#12]
I just posted a complete BSP-tree dungeon generator in the code forum.


impixi(Posted 2013) [#13]

Lots of people are scared of recursion but it's an incredibly powerful technique.



That's true, but you need to be wary of your stack's capacity, depending on the language, OS and hardware platform. It's nowhere near as problematic as the 'old days' (late 80s for me), though occasionally you hit a limit. My most recent 'stack overflow' barrier occurred a few years ago when implementing a recursive midpoint displacement algorithm in JavaScript. Sometimes you just have to use the iterative version of an algorithm (usually there is minimal performance penalty, sometimes even a gain).


Gerry Quinn(Posted 2013) [#14]
The only time recursion bit me recently was when I was creating puzzles for my game Detective Chess, which involves searching a tree of piece permutations. It wasn't especially deep, so memory wasn't an issue, but it could take up to 20 seconds on large puzzles. The problem was that Monkey is single-threaded, so I had to switch to what might be called an iterative method in order to jump out periodically and show a progress bar. Strictly speaking, I'd still call it recursive, but I was managing my own stacks and context switches, so from a naïve point of view you could argue that the algorithm was iterative.


zoqfotpik(Posted 2013) [#15]
This is why it's important to have a bailout value. For certain applications you could probably have an exception block to automatically bail out if the stack broke.