Game Design: Level Generation Using Binary Space Partitioning
Binary Space Partitioning is a simple technique used to create 2D maps for puzzle games and platformers. We use BSP to generate “solvable” levels in BentoBlox:
How exactly do we use BSP? In BentoBlox, we recursively divide a grid into sub-grids no smaller than a minimum size. That’s the essence of BSP in this context. Abstractly, we’re just taking a rectangle and bisecting repeatedly until we have a grid of smaller rectangles:
Here’s how we do it:
We start with a Grid
struct (note: all code is Swift):
Next we extend our Grid
with a function that divides it (horizontally or vertically) into 2 sub-grids:
With our Grid
extended in this way, we can call our function recursively to generate a collection of sub-grids that fit inside our initial grid and don’t overlap.
But there’s something we need to watch out for. What’s to prevent us from generating sub-grids that are too small? A sub-grid of area 0 wouldn’t be very useful. To avoid this outcome we can tell our calling function to return once it generates a sub-grid below certain minimum size:
And that’s really all we need. Now we can generate a “solvable” level with a single function call:
Which yields a level containing 4 rectangles of varying sizes:
You’ll discover more neat things like this in BentoBlox — check out the game here on the App Store.