maze = maze or {}

function newStack()
	local meta = {
		pop = function( s )
			s.size = s.size -1
			return s[s.size +1]
		end,

		push = function( s, val )
			s.size = s.size +1
			s[s.size] = val
		end
	}

	meta.__index = meta

	local stack = { size = 0 }
	setmetatable( stack, meta )

	return stack
end

function fillArray( value, sizeY, sizeX )
	local res = {}

	for y = 1, sizeY, 1 do
		res[y] = {}

		for x = 1, sizeX, 1 do
			res[y][x] = value
		end
	end

	return res
end

local dirMod = {
	{ 1, 0 },	{-1, 0 },
	{ 0, 1 },	{ 0,-1 }
}

function maze.generate( sizeX, sizeY )
	local visits  = fillArray( false, sizeY, sizeX )
	local v_walls = fillArray( true,  sizeY, sizeX -1 )
	local h_walls = fillArray( true,  sizeY -1, sizeX )

	local x, y = 1, 1
	local cDir = 0

	local tValid = false
	local tX, tY = 0, 0

	local stack = newStack()

	while( true ) do
		visits[y][x] = true

		cDir = (cDir + math.random(3)) % 4 --Choose a random direction eatch time

		-- Choose a valid direction to travel
		tValid = false
		for i = 1, 4, 1 do
			tX = x + dirMod[cDir +1][1]
			tY = y + dirMod[cDir +1][2]

			if ( 0 < tX && 0 < tY && tX <= sizeX && tY <= sizeY ) then
				local isOpen = !visits[tY][tX]

				if ( isOpen || math.random(8) == 1 ) then -- In rare cases, open already visited tiles, to avoid the 'perfect' maze

					if ( cDir < 2 ) then
						v_walls[y][x - cDir %2] = false
					else
						h_walls[y - cDir % 2][x] = false
					end

					if ( isOpen ) then -- Only push a tile one time
						stack:push( x )
						stack:push( y )

						tValid = true

						x = tX
						y = tY

						break
					end
				end
			end

			cDir = ( cDir +1 ) % 4
		end

		if ( !tValid ) then	-- Fully enclosed tile, nowhere to step, pop a new one from the stack
			if ( stack.size <= 0 ) then
				break
			else
				y = stack:pop()
				x = stack:pop()
			end
		end
	end

	local maze = {
		sizeX = sizeX,
		sizeY = sizeY,

		v_walls = v_walls,
		h_walls = h_walls
	}

	return maze
end