I needed to make a dungeon area for my game and didn't feel like making it by hand - enter procedural generation!

Binary space partitioning, if you read its Wikipedia page, is something super complicated and nerdy in actuality. What I've implemented should techically count as BSP, though!

My algorithm is basically:

• have an array of rectangles (size one to begin with)

• in that array, split each rectangle in 2 and add to a new array

• run the operation again on that new array

And then I can build room objects and walls after I have all that data set up.

I keep all rooms above a certain size threshold so that they don't get too small.

My implementation seems pretty fast too! The decoration phase is the slowest part that I have any control over. Sadly, the built-in Godot tilemap functions are really slow.

Greg greg greg Greg Greg