improved bsp dungeon algorithm

gistfile1.lua

map = {}
map.width = 100
map.height = 40

areas = {}

function initMap()
	for i = 1, map.width do
		map[i] = {}
		for j = 1, map.height do
			map[i][j] = "#"
		end
	end
end

function isLegal( x, y )
	return x >= 1 and y >= 1 and x <= map.width and y <= map.height
end

function showMap()
	for j = 1, map.height do
		for i = 1, map.width do
			io.write( map[i][j] )
		end
		io.write( "\n" )
	end
end

function makeRoom( x, y, w, h )
	for i = x+1, x+w-2 do
		for j = y+1, y+h-2 do
			if isLegal( i, j ) then
				map[i][j] = "."
			end
		end
	end
end

function bsp( n )
	local mainArea = {
		x = 1,
		y = 1,
		w = map.width,
		h = map.height
	}

	table.insert( areas, mainArea )

	local tries = 0

	for i = 1, n do
		-- find random area to divide
		local r = 0
		
		while true do
			r = math.random( #areas )

			tries = tries + 1

			if areas[r].w > map.width / 6 and areas[r].h > map.width / 6 then
				break
			end

			if tries > 9999 then
				return
			end
		end

		tries = 0

		if math.random( 2 ) == 1 then
			-- divide vertically
			local rx = math.random( math.floor( areas[r].w / 4 ), math.floor( areas[r].w * 3 / 4 ) )
			local ta = {
				x = areas[r].x,
				y = areas[r].y,
				w = rx + 1,
				h = areas[r].h
			}
			local tb = {
				x = areas[r].x + rx,
				y = areas[r].y,
				w = areas[r].w - rx,
				h = areas[r].h
			}
			table.remove( areas, r )
			table.insert( areas, ta )
			table.insert( areas, tb )
		else
			-- divide horizontally
			local ry = math.random( math.floor( areas[r].h / 4 ), math.floor( areas[r].h * 3 / 4 ) )
			local ta = {
				x = areas[r].x,
				y = areas[r].y,
				w = areas[r].w,
				h = ry + 1
			}
			local tb = {
				x = areas[r].x,
				y = areas[r].y + ry,
				w = areas[r].w,
				h = areas[r].h - ry
			}
			table.remove( areas, r )
			table.insert( areas, ta )
			table.insert( areas, tb )
		end
	end
end

function fillAreas()
	for i = 1, #areas do
		makeRoom( areas[i].x, areas[i].y, areas[i].w, areas[i].h )
	end
end

function main()
	initMap()
	math.randomseed( os.time() )
	bsp( 1000 )

	fillAreas()

	showMap()

	for i = 1, #areas do
		print( areas[i].x, areas[i].y, areas[i].w, areas[i].h )
	end
end

main()