Lua BSP room generation

luabsp.lua

local unpack, floor, random = table.unpack or unpack, math.floor, math.random

local Bsp = {}

function Bsp.splitTree( x, y, w, h, l, kwargs )
	local maxlevel = kwargs.maxlevel or 4
	local deviation = kwargs.leafdeviation or 0.1
	if w < 4 or h < 4 or l > maxlevel then
		return {x,y,w,h}
	else
		local xsplit
		if kwargs.split == 'random' then xsplit = random() > 0.5
		elseif kwargs.split == 'random2' then xsplit = random() > 0.5 * h/w 
		elseif kwargs.split == 'optimal' or kwargs.split == nil then xsplit = w > h
		elseif type( kwargs.split ) == 'function' then xsplit = kwargs.split( x, y, w, h, l, args )
		else error( 'Unrecognized .split type: ' .. tostring( kwargs.split ))
		end
		
		if xsplit then
			local x_ = random( floor((0.5-deviation)*w), floor((0.5+deviation)*w ))
			return {x,y,w,h, l = Bsp.splitTree( x, y, x_, h, l+1, kwargs ), r = Bsp.splitTree( x+x_+1, y, w-x_-1, h, l+1, kwargs )}
		else
			local y_ = random( floor((0.5-deviation)*h), floor((0.5+deviation)*h ))
			return {x,y,w,h, l = Bsp.splitTree( x, y, w, y_, l+1, kwargs ), r = Bsp.splitTree( x, y+y_+1, w, h-y_-1, l+1, kwargs )}
		end
	end
end

local function defaultFill( f )
	return function( self, x, y, v )
		return f
	end
end

function Bsp.fillRects( bsp, grid, fill, kwargs )
	if type( fill ) ~= 'function' then
		fill = defaultFill( fill )
	end

	if not bsp.l then
		local deviation = kwargs.rectdeviation or 0.2
		local margin = kwargs.rectmargin or 1
		local w, h = bsp[3]-margin-margin, bsp[4]-margin-margin
		local x1, x2 = floor( bsp[1]+margin+random()*deviation*w), floor(bsp[1]+bsp[3]-margin-random()*deviation*w)
		local y1, y2 = floor( bsp[2]+margin+random()*deviation*h), floor(bsp[2]+bsp[4]-margin-random()*deviation*h)
		for x = x1, x2 do
			for y = y1, y2 do
				grid[x][y] = fill( grid, x, y, grid[x][y] )
			end
		end
	else
		Bsp.fillRects( bsp.l, grid, fill, kwargs )
		Bsp.fillRects( bsp.r, grid, fill, kwargs )
	end
end

function Bsp.connectRects( bsp, grid, fill, kwargs )
	if type( fill ) ~= 'function' then
		fill = defaultFill( fill )
	end
	
	local x1, y1, w1, h1 = unpack( bsp.l )
	local x2, y2, w2, h2 = unpack( bsp.r )

	local left,right,top,bottom = x2 > x1+w1, x1 > x2+w2, y2 > y1+h1, y1 > y2+h2

	if left then
		local y = math.floor( y1 + h1/2 )
		for x = math.floor(x1+0.5*w1), math.floor(x2 + 0.5*w2) do
			grid[x][y] = fill( grid, x, y, grid[x][y] )
		end
	elseif right then
		local y = math.floor( y2 + h2/2 )
		for x = math.floor(x2+0.5*w2), math.floor(x1 + 0.5*w1) do
			grid[x][y] = fill( grid, x, y, grid[x][y] )
		end
	elseif top then
		local x = math.floor( x1 + w1/2 )
		for y = math.floor(y1+0.5*h1), math.floor(y2 + 0.5*h2) do
			grid[x][y] = fill( grid, x, y, grid[x][y] )
		end
	elseif bottom then
		local x = math.floor( x2 + w2/2 )
		for y = math.floor(y2+0.5*h2), math.floor(y1 + 0.5*h1) do
			grid[x][y] = fill( grid, x, y, grid[x][y] )
		end
	end
	if bsp.l.l then
		Bsp.connectRects( bsp.l, grid, fill, kwargs )
		Bsp.connectRects( bsp.r, grid, fill, kwargs )
	end
end

function Bsp.generate( grid, kwargs )
	kwargs = kwargs or {}
	local w, h = #grid, #grid[1]
	local minx, miny, maxx, maxy = kwargs.minx or 2, kwargs.miny or 2, kwargs.maxx or w-1, kwargs.maxy or h-1
	local minw, minh = kwargs.minw or 4, kwargs.minh or 4
	local tree = Bsp.splitTree( minx, miny, maxx-minx+1, maxy-miny+1, 0, kwargs )
	Bsp.fillRects( tree, grid, kwargs.fill or '.', kwargs )
	Bsp.connectRects( tree, grid, kwargs.fill or '.', kwargs )
	return grid
end

return Bsp