Help using BSP tree for dungeon generation

I’ve been trying to set up a BSP tree dungeon generator like this for hours now and I can’t figure it out. :sweat: Like I get the basic idea, split rectangles, but translating this to Lua is really going over my head, especially with trying to keep track of all the rooms and their leaves so that I can do corridors. :sweat_smile: Some help would be much appreciated.

This isn’t too simple to do, however I can try to give you some guidance to get started. You’ll want to use a tree data structure something like this:

z = {left = nil, right = nil}

z.left = {x = 0, y = 0, x2 = 20, y2 = 40, sub_trees = {}}
z.right = {x = 20, y = 0, x2 = 40, y2 = 40, sub_trees = {}}

Except instead of using hard-coded values you’ll want a function to assess a section’s boundaries and then randomly choose values to split it (horizontally or vertically.)

This however, only splits the dungeon one time. You’ll need to figure out a way to recursively delve into the tree node and perform more splits, while storing the pathway taken down the tree in a stack data structure. Then you can simply push the nodes onto the path and pop them off to return up the tree once the area of the boundaries split into become small enough (perhaps add some randomness here as well.)

You can likely generate the rooms while doing this splitting process but the corridors seems like it will be more complex to do. Likely you will need to do a separate traversal after just to handle corridor creation to avoid trying to connect to an non-generated room.

EDIT: This link shows code and animations which may be more helpful than the link shown: