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.