--
-- @ JimmyChance
--

local maze_size = {20, 20, 10} -- square maze
local cell_size = 20

cellStack = {}
rService = game:GetService("RunService")
directions = {
	["0, 1"] = 1,
	["0, -1"] = 3,
	["1, 0"] = 2,
	["-1, 0"] = 4,
} -- L,R,D,U
-- W: LDRU
map = {}
count = 0
maze = Instance.new("Model", workspace)
maze.Name = "Maze"

function makeBrick(c, h, s)
	local walls = c[3]
	local ch = Instance.new("Model", maze)
	ch.Name = "Cell"
	local cellpos = c[2]
	local p = Instance.new("Part", ch)
	p.Anchored = true
	p.Name = "Base"
	p.CFrame = CFrame.new(cellpos) * CFrame.new(0, -h/2, 0)
	p.Size = Vector3.new(cell_size, 1, cell_size)
	p.FormFactor = "Custom"
	for i = 1, 4 do
		local sb = Instance.new("Part", ch)
		sb.Anchored = true
		sb.FormFactor = "Custom"
		sb.Name = "Support Beam"
		sb.Size = Vector3.new(1, h, 1)
		local basepos = p.Position
		local sX = p.Size.X/2 - 0.5
		local sZ = p.Size.Z/2 - 0.5
		if i == 1 then
			sb.Position = basepos + Vector3.new(sX, h/2, sZ)
		elseif i == 2 then
			sb.Position = cellpos - Vector3.new(sX, 0, sZ)
		elseif i == 3 then
			sb.Position = cellpos + Vector3.new(sX, 0, -sZ)
		elseif i == 4 then
			sb.Position = cellpos - Vector3.new(sX, 0, -sZ)
		end
	end
	for i = 1, 4 do
		if walls[i] then
			local part = Instance.new("Part", ch)
			part.Name = "Wall"
			part.Anchored = true
			part.FormFactor = "Custom"
			local basepos = p.Position
			local sX = p.Size.X/2 - 0.5
			local sZ = p.Size.Z/2 - 0.5
			if i == 1 then
				part.Size = Vector3.new(cell_size - 2, h, 1)
				part.Position = cellpos + Vector3.new(0, 0, -sZ)
			elseif i == 2 then
				part.Size = Vector3.new(1, h, cell_size - 2)
				part.Position = cellpos + Vector3.new(-sX, 0, 0)
			elseif i == 3 then
				part.Size = Vector3.new(cell_size - 2, h, 1)
				part.Position = cellpos + Vector3.new(0, 0, sZ)
			elseif i == 4 then
				part.Size = Vector3.new(1, h, cell_size - 2)
				part.Position = cellpos + Vector3.new(sX, 0, 0)
			end
		end
	end
end

function createPositions(startPos, cellSize, mazeSize)
	local pos = startPos
	local xSize = mazeSize[1]
	local zSize = mazeSize[2]
	local height = mazeSize[3]
	for x = 1, xSize do
		map[x] = {}
		for z = 1, zSize do
			local posY = (startPos + Vector3.new(0, height/2, 0)).Y
			local p = Vector3.new((x - 1) * cellSize + startPos.X, posY, (z - 1) * cellSize + startPos.Z)
			 map[x][z] = {{x, z}, p, {true, true, true, true}, false}
		end
	end
	return map
end

function getNearby(cell, tab)
	local v = Vector2.new(cell[1][1], cell[1][2])
	local n = {}
	for i = 1, #tab do
		for h = 1, #tab[i] do
			local current = tab[i][h]
			local v2 = Vector2.new(current[1][1], current[1][2])
			local l = (v - v2).magnitude
			if l == 1 and not current[4] then
				local dir = (v - v2).unit
				local num = directions[tostring(dir)]
				n[#n + 1] = {current, num}
			end
		end
	end
	return n
end

function generateMaze(exitEnabled)
	local m = createPositions(Vector3.new(0, 0, 0), cell_size, maze_size)
	local xSize = maze_size[1]
	local zSize = maze_size[2]
	if exitEnabled[1] then
		local choice = exitEnabled[2]
		if choice == 0 then
			choice = math.random(zSize)
		end
		m[1][choice][3][2] = false
		choice = exitEnabled[3]
		if choice == 0 then
			choice = math.random(zSize)
		end
		m[xSize][choice][3][4] = false
	end

	cellStack[1] = {m[1][1], nil}
	repeat rService.RenderStepped:wait()
		local ncells = getNearby(cellStack[#cellStack][1], m)
		if #ncells > 0 then
			local ccell = ncells[math.random(#ncells)]
			local d = ccell[2]
			local q = d + 2
			if q > 4 then
				q = q - 4
			end
			ccell[1][4] = true
			ccell[1][3][q] = false
			cellStack[#cellStack + 1] = ccell
			local old = cellStack[#cellStack - 1]
			old[1][3][d] = false
			count = count + 1
		else
			table.remove(cellStack, #cellStack)
		end

			print(count)

	until count == xSize * zSize
	for x = 1, xSize do
		if m[x] then
			for z = 1, zSize do
				rService.RenderStepped:wait()
				makeBrick(m[x][z], maze_size[3], cell_size)
			end
		end
	end
end

wait(4)
generateMaze({true, 0, 0})