Is this a BSP tree? Am I missing something?

I've been practicing using BSP trees as I hear they are a good start to create procedural spaces such as houses.

For ease-of-deployment purposes, I've tested this code in Lua and it seems to work. However, I want to confirm if I did what I needed to do instead of something else. When I am sure this works I will properly implement it in C.

This would be the code:

```
MAX_RECURSION = 3
TL = 1
BL = 2
BR = 3
TR = 4

grid = {}
grid.w = 60;
grid.h = 12;
grid.max = grid.w * grid.h
grid.pos = function (self, x, y) return (x * self.w + y)+1 end
grid.get = function (self, x, y) return self.data[self:pos(x, y)] end
grid.set = function (self, x, y, d) self.data[self:pos(x,y)] = d end
grid.data = {}
for i = 1, grid.max do grid.data[i] = " " end

rooms = 1

function node_c(parent, rect)
n = {}
n.child1 = nil
n.child2 = nil
n.parent = parent
n.rect = rect
n.w = rect[TR].x-rect[TL].x
n.h = rect[BL].y-rect[TL].y if n.h node.w - 2 then return nil else return node.rect[TL].x + r end
else
local r = math.floor(((math.random(20, 80)/100) * node.h))
if r node.h - 2 then return nil else return node.rect[TL].y + r end
end
end

function print_rect(rect)
return "TL:"..rect[TL].x..","..rect[TL].y.." BL:"..rect[BL].x..","..rect[BL].y.." BR:"..rect[BR].x..","..rect[BR].y.." TR:"..rect[TR].x..","..rect[TR].y
end

function node_rects(node, split)
local rect1, rect2
local t
t = node.rect
if node.vertical then
rect1 = {[TL] = t[TL], [BL] = t[BL], [TR] = {x=split,y=t[TR].y}, [BR] = {x=split,y=t[BR].y}}
rect2 = {[TL] = {x=split,y=t[TL].y}, [BL] = {x=split,y=t[BL].y}, [TR] = t[TR], [BR] = t[BR]}
return rect1,rect2
else
rect1 = {[TL]=t[TL],[TR] = t[TR],[BL]={x=t[BL].x,y=split}, [BR]={x=t[BR].x,y=split}}
rect2 = {[TL]={x=t[TL].x,y=split},[TR]={x=t[TR].x,y=split},[BL]=t[BL],[BR] = t[BR]}
return rect1,rect2
end
end

function bsp_it(g)
local rect = { --Counter clockwise

Your principal algorithm is a correctly implemented BSP, so yes. You are creating a Binary Space Partitioning tree.

Also, FWIW: You only need two points on opposing corners to define an axis aligned rectangle which you seem to be using here. So you could simplify.

Edit: Just noticed your question about connectivity:

Just checking the immediate parent will give you a subset of the possible connection information. Since your BSP is axis aligned and 2 dimensional each node can have 1 to 4 neighboring nodes (depending on if it's positioned along the edges or not) or 0 for the root but lets ignore the root because it's not interesting.

If you're interested in the full connectivity you can either traverse the tree top down and keep track of all edges and in that way find which rooms are neighboring. Or you can keep track of north,west,east,south neighbor of a node during tree generation and use this information to determine connectivity.

If you only look at the immediate parent, you only get one connecting node (out of possibly 4). I do not know how you intend to use this connectivity information so this may be enough for you.

StackExchange Code Review Q#4334, answer score: 7