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 = 3TL = 1BL = 2BR = 3TR = 4grid = {}grid.w = 60;grid.h = 12;grid.max = grid.w * grid.hgrid.pos = function (self, x, y) return (x * self.w + y)+1 endgrid.get = function (self, x, y) return self.data[self:pos(x, y)] endgrid.set = function (self, x, y, d) self.data[self:pos(x,y)] = d endgrid.data = {}for i = 1, grid.max do grid.data[i] =   endrooms = 1function 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 < 0 then n.h = 0 end    n.level = parent.level + 1    n.id = 0    n.vertical = direction_get(n)    node_draw(n)    return nendfunction rootnode(rect)    n = {}    n.child1 = nil    n.child2 = nil    n.rect = rect    n.parent = nil    n.w = rect[TR].x-rect[TL].x    n.h = rect[BL].y-rect[TL].y    n.level = 0    n.id = 0    n.vertical = direction_get(n)    node_draw(n)    return nendfunction node_draw(node)    local x, y    local rect = node.rect    for y = rect[TL].y, rect[BL].y do        for x = rect[TL].x, rect[TR].x do            if x==rect[TL].x or x==rect[TR].x or y==rect[TL].y or y==rect[BR].y then                grid:set(x, y, #)            else                grid:set(x, y, .)            end        end    endendfunction node_split(node)    if not node or not (node.level < MAX_RECURSION) then        node.id = rooms        rooms = rooms + 1        return    else        local p        if node.vertical then p = X else p = Y end        local split = node_splitfrom(node)        if split == nil then return end        local c1, c2, r1, r2        r1,r2 = node_rects(node, split)        node.child1 = node_c(node, r1)        node.child2 = node_c(node, r2)        --draw_it(grid)        node_split(node.child1)        node_split(node.child2)    endendfunction direction_get(node)    if math.random(0, 1) == 0 then return true else return false endendfunction node_splitfrom(node)    local result    if node.vertical then        local r = math.floor(((math.random(20, 80)/100) * node.w))        if r < 2 or r > 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 < 2 or r > node.h - 2 then return nil else return node.rect[TL].y + r end    endendfunction 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].yendfunction 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    endendfunction bsp_it(g)    local rect = { --Counter clockwise        [TL] = {x=0,y=0},        [BL] = {x=0,y=g.h},        [BR] = {x=g.w,y=g.h},        [TR] = {x=g.w,y=0}    }    local root = rootnode(rect)    node_split(root)    return rootendfunction print_it(t)    if(t) then        local spaces = (t.level * 2)        local i        local space =         for i = 0, spaces do space = space..  end        if not t.parent then print(space..#..(%X):format(t.id)) else print(space..\\..(%X):format(t.id)) end        print_it(t.child1) print_it(t.child2)    endendfunction draw_it(grid)    local line =     local x,y    for y = 0, grid.h do        for x = 0, grid.w do            line = ..line..(grid.data[grid:pos(x,y)] or 0)        end        print(line)        line =     endendmath.randomseed(os.time())test = bsp_it(grid, 3)print_it(test)draw_it(grid)This is a very naive approach. I don't check for size ratio or anything to make it look good and I am not connecting the rooms yet (I will deal with it later. A table recursively collecting the nodes should do the work). So the question is if this is actually a BSP tree, and if I am missing something important in here.Additionally, having this data, how should I check for connectivity among individual rooms? Picking a node, check parent and connect all nodes inside parent, perhaps?
Is this a BSP tree? Am I missing something?
tree;lua;computational geometry;clustering