A maze generation algorithm written in lua.

maze.lua

-------------------------------------
-- Maze generation script
-------------------------------------
-- A test by @Starbeamrainbowlabs

---------------------------------------------
-- Intelligent table printing function
---------------------------------------------
-- From http://coronalabs.com/blog/2014/09/02/tutorial-printing-table-contents/

function print_r ( t )  
    local print_r_cache={}
    local function sub_print_r(t,indent)
        if (print_r_cache[tostring(t)]) then
            print(indent.."*"..tostring(t))
        else
            print_r_cache[tostring(t)]=true
            if (type(t)=="table") then
                for pos,val in pairs(t) do
                    if (type(val)=="table") then
                        print(indent.."["..pos.."] => "..tostring(t).." {")
                        sub_print_r(val,indent..string.rep(" ",string.len(pos)+8))
                        print(indent..string.rep(" ",string.len(pos)+6).."}")
                    elseif (type(val)=="string") then
                        print(indent.."["..pos..'] => "'..val..'"')
                    else
                        print(indent.."["..pos.."] => "..tostring(val))
                    end
                end
            else
                print(indent..tostring(t))
            end
        end
    end
    if (type(t)=="table") then
        print(tostring(t).." {")
        sub_print_r(t,"  ")
        print("}")
    else
        sub_print_r(t,"  ")
    end
    print()
end

if arg[1] ~= nil then
	width = tonumber(arg[1])
else
	width = 36
end
if arg[2] ~= nil then
	height = tonumber(arg[2])
else
	height = 16
end

----------------------------------
-- function to print out the world
----------------------------------
function printspace(space, w, h)
	for y = 0, h, 1 do
		local line = ""
		for x = 0, w, 1 do
			line = line .. space[y][x]
		end
		print(line)
	end
end

-- Initialise the world
start_time = os.clock()
math.randomseed(os.time()) -- seed the random number generator with the system clock
world = {}
for y = 0, height, 1 do
	world[y] = {}
	for x = 0, width, 1 do
		world[y][x] = "#"
	end
end

-- do a random walk to create pathways
nodes = {} -- the nodes left that we haven't investigated
curnode = 1 -- the node we are currently operating on
cx, cy = 1, 1 -- our current position
table.insert(nodes, { x = cx, y = cy })

world[cy][cx] = " "
while #nodes > 0 do
	io.write("Nodes left: " .. curnode .. "\r")
	--print("Nodes left: " .. #nodes)
	--print("Currently at (" .. cx .. ", " .. cy .. ")")
	
	local directions = "" -- the different directions we can move
	if cy - 2 > 0 and world[cy - 2][cx] == "#" then
		directions = directions .. "u"
	end
	if cy + 2 < height and world[cy + 2][cx] == "#" then
		directions = directions .. "d"
	end
	if cx - 2 > 0 and world[cy][cx - 2] == "#" then
		directions = directions .. "l"
	end
	if cx + 2 < width and world[cy][cx + 2] == "#" then
		directions = directions .. "r"
	end
	--print("radar output: '" .. directions .. "' (length: " .. #directions .. "), curnode: " .. curnode)
	if #directions > 0 then
		-- we still have somewhere that we can go
		--print("This node is not a dead end yet.")
		local curdirnum = math.random(0, #directions)
		local curdir = string.sub(directions, curdirnum, curdirnum)
		if curdir == "u" then
			world[cy - 1][cx] = " "
			world[cy - 2][cx] = " "
			cy = cy - 2
		elseif curdir == "d" then
			world[cy + 1][cx] = " "
			world[cy + 2][cx] = " "
			cy = cy + 2
		elseif curdir == "l" then
			world[cy][cx - 1] = " "
			world[cy][cx - 2] = " "
			cx = cx - 2
		elseif curdir == "r" then
			world[cy][cx + 1] = " "
			world[cy][cx + 2] = " "
			cx = cx + 2
		end
		
		table.insert(nodes, { x = cx, y = cy })
	else
		--print("The node at " .. curnode .. " is a dead end.")
		table.remove(nodes, curnode)
		if #nodes > 0 then
			--print("performing teleport.");
			curnode = math.random(1, #nodes)
			--print("New node: " .. curnode)
			-- print("Nodes table: ")
			-- print_r(nodes)
			cx = nodes[curnode]["x"]
			cy = nodes[curnode]["y"]
		else
			--print("Maze generation complete, no teleportation necessary.")
		end
	end
	--printspace(world, width, height)
end

printspace(world, width, height)
end_time = os.clock()
print("Generation completed in " .. (end_time - start_time) .. "s.")