Skip to content

Instantly share code, notes, and snippets.

@iskolbin
Created July 19, 2016 09:07
Show Gist options
  • Save iskolbin/502e93934779b5c4c0449cae0aedc8bd to your computer and use it in GitHub Desktop.
Save iskolbin/502e93934779b5c4c0449cae0aedc8bd to your computer and use it in GitHub Desktop.
Lua BSP room generation
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment