local Z=script:FindFirstAncestor("\077\097\122\101\071\101\110\101\114\097\116\111\114\080\108\117\103\105\110")local I=require(Z:WaitForChild("\077"))local S=Z:WaitForChild("\077\111\100\101\108\115")local C=require(script.Parent.MazeBacktrace)local f=require(script.Parent.Maze)local L=S.Prefabs local n=S.Misc local y=S.Money local i=20 local s=25 local U="\070\108\111\111\114\080\097\114\116"function getCenterVector(Z,I)return Vector3.new(Z/2,0,I/2)end function removePitch(Z,I)local S,C,f=Z:ToOrientation()return CFrame.new(Z.Position)end function getCorrectCframe(Z,I)local S=CFrame.new(Z.Position)local C=S:inverse()*I return Z*C end function partToTerrain(Z,I)workspace.Terrain:FillBlock(Z.CFrame,Z.Size,I)end function partToRegion3(Z)local I=math.abs local S=Z.CFrame local C=Z.Size local f,L,n=C.X,C.Y,C.Z local y,i,s,U,k,r,V,w,N,Y,Q,g=S:components()local u=.5*((I(U)*f+I(k)*L)+I(r)*n)local o=.5*((I(V)*f+I(w)*L)+I(N)*n)local D=.5*((I(Y)*f+I(Q)*L)+I(g)*n)local F=y-u local O=i-o local b=s-D local l=y+u local t=i+o local p=s+D local M,c=Vector3.new(F,O,b),Vector3.new(l,t,p)return Region3.new(M,c)end function dummyPart(Z,I)local S=Instance.new("\080\097\114\116")S.Anchored=true S.Size=Vector3.new(.5,i,.5)S.Position=Z S.Parent=I end function randomPos(Z)local S=s/2-Z.partThickness local C=I.range(2,S)local f=I.range(-2,-S)local L=I.append(C,f)local n=I.sample(L)return n[1]end function randomRotation(Z)return CFrame.new(Z)*CFrame.fromOrientation(0,math.random(1,360),0)end function AddRandomPart(Z,I,S,C)local f=n:GetChildren()local L=f[math.random(1,#f)]local y=L:Clone()local i=Vector3.new(randomPos(C),0,randomPos(C))local U if y:IsA("\066\097\115\101\080\097\114\116")then U=y.Size else U=y.PrimaryPart.Size end local k=s/2-U.X/2 local r=U.Y/2 local V=s/2-U.Z/2 local w=randomRotation((Z+Vector3.new(k,r,V))+i)local N=getCorrectCframe(I,w)if y:IsA("\066\097\115\101\080\097\114\116")then y.CFrame=N else y:SetPrimaryPartCFrame(N)end y.Parent=S end function AddCoinPart(Z,I,S,C)local f=y:GetChildren()local L=f[math.random(1,#f)]local n=L:Clone()local i if n:IsA("\066\097\115\101\080\097\114\116")then i=n.Size else i=n.PrimaryPart.Size end local U=s/2-i.X/2 local k=i.Y/2 local r=s/2-i.Z/2 local V=randomRotation(Z+Vector3.new(U,k,r))local w=getCorrectCframe(I,V)if n:IsA("\066\097\115\101\080\097\114\116")then n.CFrame=w else n:SetPrimaryPartCFrame(w)end n.Parent=S end function AddRandomParts(Z,S,C,f)local L=I.range(1,5)AddCoinPart(Z,S,C,f)I.map(L,function()local I=math.random(1,10)if I==1 then AddRandomPart(Z,S,C,f)end end)end function MakeBlock(Z)local I=Instance.new("\080\097\114\116")I.Anchored=true I.Size=Vector3.new(Z.partThickness,i,s)return I end function DrawBlock(Z,I,S,C,f)local n=MakeBlock(f)local y=Z.X local U=Z.Y local k=Z.Z local r=n.Size.Y/2 local V=n.Size.Z/2 local w=CFrame.new(y,U+r,k+V)if C then local Z=math.rad(90)w=CFrame.new(y+V,U+r,k)*CFrame.Angles(0,Z,0)end n.CFrame=w n.CFrame=getCorrectCframe(I,n.CFrame)if not f.onlyBlocks then partToTerrain(n,f.wallMaterial)else n.Parent=S end if f.addKillBlocks then local Z="\075\105\108\108\098\114\105\099\107"local I=L[Z]:Clone()I.Size=Vector3.new(3,4,s)I.CFrame=n.CFrame+Vector3.new(0,i-7,0)I.Transparency=1 I.Parent=S end end function DrawFloor(Z,I,S,C,f,L)local n=Instance.new("\080\097\114\116")n.Size=Vector3.new(C,1,f)n.Name=U n.CanCollide=true n.Anchored=true n.CFrame=CFrame.new(Z+getCenterVector(C,f))n.CFrame=getCorrectCframe(I,n.CFrame)if not L.onlyBlocks then n.Parent=S n.Transparency=1 n.CanCollide=false partToTerrain(n,L.groundMaterial)else n.Parent=S end end function DrawCeiling(Z,I,S,C,f,L)local n=Instance.new("\080\097\114\116")n.Size=Vector3.new(C,1,f)n.Name="\067\101\105\108\105\110\103"n.CanCollide=true n.Anchored=true n.CFrame=CFrame.new(Z+getCenterVector(C,f))n.CFrame=getCorrectCframe(I,n.CFrame)if not L.onlyBlocks then n.Parent=S n.Transparency=1 n.CanCollide=false partToTerrain(n,L.wallMaterial)else n.Parent=S end end function DrawStart(Z,I,S)local C="\083\112\097\119\110\080\108\097\099\101\104\111\108\100\101\114"local f=L[C]:Clone()f.CFrame=CFrame.new(Z)f.CFrame=getCorrectCframe(I,f.CFrame)f.Parent=S end function DrawFinish(Z,I,S)local C="\070\105\110\105\115\104\080\108\097\099\101\104\111\108\100\101\114"local f=L[C]:Clone()f.CFrame=CFrame.new(Z)f.CFrame=getCorrectCframe(I,f.CFrame)f.Parent=S end local function k(Z,I,S,C,f)local L=s*#Z[1]local n=s*#Z warn("\080\111\115\105\116\105\111\110\105\110\103 \077\097\122\101\058 ",S)local y=2048 warn("\083\105\122\101 \105\110 \115\116\117\100\115\058"..(tostring(L)..("\044 \104\101\105\103\104\116\058"..tostring(n))))if y<L or y<n then warn("\070\108\111\111\114 \111\114 \067\101\105\108\105\110\103 \112\097\114\116 \105\115 \111\118\101\114 \109\097\120 \115\105\122\101\058"..tostring(y))end DrawFloor(S,C,I,L,n,f)if f.addCeiling then DrawCeiling(S+Vector3.new(0,i,0),C,I,L,n,f)end if f.addStartAndFinish then local Z=Vector3.new(s/2,0,s/2)DrawStart((S+Vector3.new(2,6,2))+Z,C,I)local f=s-2 local y=Vector3.new(f/2,2,f/2)local i=Vector3.new(L-f,0,n-f)DrawFinish((S+i)+y,C,I)end local U=0 local k={}function cachePart(Z,S)local L=tostring(Z)..tostring(S)if not k[L]then k[L]=true DrawBlock(Z,C,I,S,f)else end end for L=1,#Z,1 do for n=1,#Z[1],1 do local y=(s+U)*(n-1)+U local i=(s+U)*(L-1)+U local k=Z[L][n]if not k.north:IsOpened()then local Z=Vector3.new(y,0,i)cachePart(S+Z,true)end if not k.east:IsOpened()then local Z=Vector3.new(y+s,0,i)cachePart(S+Z,false)end if not k.south:IsOpened()then local Z=Vector3.new(y,0,i+s)cachePart(S+Z,true)end if not k.west:IsOpened()then local Z=Vector3.new(y,0,i)cachePart(S+Z,false)end if f.addRandomModels then local Z=Vector3.new(y,.4,i)AddRandomParts(S+Z,C,I,f)end end end end local r={}local V="\077\097\122\101"function r.generate(I,Z)local S=Z.width local L=Z.height local n=Z.location warn("\071\101\110\101\114\097\116\105\110\103 \109\097\122\101  \119\105\100\116\104\058"..(S..("\044 \104\101\105\103\104\116\058"..L)))local y=f:new(S,L,true)C(y)local s=n:FindFirstChild(V)if s then local Z=s:FindFirstChild(U)workspace.Terrain:FillBlock(Z.CFrame,Z.Size+Vector3.new(10,i*3,10),Enum.Material.Air)s:Destroy()end s=Instance.new("\070\111\108\100\101\114")s.Name=V s.Parent=n local r=Vector3.new(0,0,0)local w=CFrame.new(0,0,0)if n:IsA("\066\097\115\101\080\097\114\116")then r=n.Position w=n.CFrame warn("\085\115\105\110\103 \112\097\114\116 \108\111\099\097\116\105\111\110")end k(y,s,r,w,Z)end return r
local Root = script:FindFirstAncestor('MazeGeneratorPlugin')

local M = require(Root:WaitForChild('M'))

local Models = Root:WaitForChild('Models')

local recursive_backtracker = require(script.Parent.MazeBacktrace)
local Maze = require(script.Parent.Maze)

local Prefabs = Models.Prefabs
local Misc = Models.Misc
local Money = Models.Money

local blockHeight = 20
local blockWidth = 25

local floorPartName = 'FloorPart'

function getCenterVector(width, height)
	return Vector3.new(width / 2, 0, height / 2)
end

function removePitch(cf, defaultCf)
	local RX, RY, RZ = cf:ToOrientation()
	return CFrame.new(cf.Position)
end
function getCorrectCframe(hingeCF, doorCF)
	local withoutRotation = CFrame.new(hingeCF.Position)

	local offset = withoutRotation:inverse() * doorCF
	return hingeCF * offset
end

function partToTerrain(newBlock, material)
	--[[
	local region = partToRegion3(newBlock)
	region = region:ExpandToGrid(4)
	game.Workspace.Terrain:FillRegion(region, 4, settings.wallMaterial)
	]]

	workspace.Terrain:FillBlock(newBlock.CFrame, newBlock.Size, material)
end

function partToRegion3(obj)
	local abs = math.abs

	local cf = obj.CFrame -- this causes a LuaBridge invocation + heap alfolder to create CFrame object - expensive! - but no way around it. we need the cframe
	local size = obj.Size -- this causes a LuaBridge invocation + heap alfolder to create Vector3 object - expensive! - but no way around it
	local sx, sy, sz = size.X, size.Y, size.Z -- this causes 3 Lua->C++ invocations
	local x, y, z, R00, R01, R02, R10, R11, R12, R20, R21, R22 = cf:components() -- this causes 1 Lua->C++ invocations and gets all components of cframe in one go, with no alfolders
	-- https://zeuxcg.org/2010/10/17/aabb-from-obb-with-component-wise-abs/
	local wsx = 0.5 * (abs(R00) * sx + abs(R01) * sy + abs(R02) * sz) -- this requires 3 Lua->C++ invocations to call abs, but no hash lookups since we cached abs value above; otherwise this is just a bunch of local ops
	local wsy = 0.5 * (abs(R10) * sx + abs(R11) * sy + abs(R12) * sz) -- same
	local wsz = 0.5 * (abs(R20) * sx + abs(R21) * sy + abs(R22) * sz) -- same
	-- just a bunch of local ops
	local minx = x - wsx
	local miny = y - wsy
	local minz = z - wsz

	local maxx = x + wsx
	local maxy = y + wsy
	local maxz = z + wsz

	local minv, maxv = Vector3.new(minx, miny, minz), Vector3.new(maxx, maxy, maxz)
	return Region3.new(minv, maxv)
end

function dummyPart(position, folder)
	local newBlock = Instance.new('Part')

	newBlock.Anchored = true
	newBlock.Size = Vector3.new(0.5, blockHeight, 0.5)
	newBlock.Position = position
	newBlock.Parent = folder
end

function randomPos(settings)
	local areaHalfWidth = blockWidth / 2 - settings.partThickness
	local neg = M.range(2, areaHalfWidth)
	local posr = M.range(-2, -areaHalfWidth)
	local arr = M.append(neg, posr)

	local p = M.sample(arr)

	return p[1]
end

function randomRotation(position)
	return CFrame.new(position) * CFrame.fromOrientation(0, math.random(1, 360), 0)
end

function AddRandomPart(pos, cframe, folder, settings)
	local parts = Misc:GetChildren()
	local randomPart = parts[math.random(1, #parts)]
	local newBlock = randomPart:Clone()

	local randomPosition = Vector3.new(randomPos(settings), 0, randomPos(settings))

	local partSize
	if newBlock:IsA('BasePart') then
		partSize = newBlock.Size
	else
		partSize = newBlock.PrimaryPart.Size
	end

	local halfX = blockWidth / 2 - partSize.X / 2
	local halfY = partSize.Y / 2
	local halfZ = blockWidth / 2 - partSize.Z / 2

	local cf = randomRotation(pos + Vector3.new(halfX, halfY, halfZ) + randomPosition)

	local newCf = getCorrectCframe(cframe, cf)

	if newBlock:IsA('BasePart') then
		newBlock.CFrame = newCf
	else
		newBlock:SetPrimaryPartCFrame(newCf)
	end

	newBlock.Parent = folder
end

function AddCoinPart(pos, cframe, folder, settings)
	local parts = Money:GetChildren()
	local randomPart = parts[math.random(1, #parts)]
	local newBlock = randomPart:Clone()

	local partSize
	if newBlock:IsA('BasePart') then
		partSize = newBlock.Size
	else
		partSize = newBlock.PrimaryPart.Size
	end

	local halfX = blockWidth / 2 - partSize.X / 2
	local halfY = partSize.Y / 2
	local halfZ = blockWidth / 2 - partSize.Z / 2

	local cf = randomRotation(pos + Vector3.new(halfX, halfY, halfZ))

	local newCf = getCorrectCframe(cframe, cf)

	if newBlock:IsA('BasePart') then
		newBlock.CFrame = newCf
	else
		newBlock:SetPrimaryPartCFrame(newCf)
	end

	newBlock.Parent = folder
end

function AddRandomParts(pos, cframe, folder, settings)
	local times = M.range(1, 5)

	AddCoinPart(pos, cframe, folder, settings)
	M.map(times, function()
		local willAdd = math.random(1, 10)
		if willAdd == 1 then
			AddRandomPart(pos, cframe, folder, settings)
		end
	end)
end

function MakeBlock(settings)
	local newBlock = Instance.new('Part')

	newBlock.Anchored = true
	newBlock.Size = Vector3.new(settings.partThickness, blockHeight, blockWidth)

	return newBlock
end

function DrawBlock(pos, cframe, folder, vertical, settings)
	local newBlock = MakeBlock(settings)

	local x = pos.X
	local y = pos.Y
	local z = pos.Z

	local halfHeight = newBlock.Size.Y / 2
	local halfWidth = newBlock.Size.Z / 2

	local cf = CFrame.new(x, y + halfHeight, z + halfWidth)

	if vertical then
		local angle = math.rad(90)
		cf = CFrame.new(x + halfWidth, y + halfHeight, z) * CFrame.Angles(0, angle, 0)
	end

	newBlock.CFrame = cf

	newBlock.CFrame = getCorrectCframe(cframe, newBlock.CFrame)

	if not settings.onlyBlocks then
		partToTerrain(newBlock, settings.wallMaterial)
	else
		newBlock.Parent = folder
	end

	if settings.addKillBlocks then
		-- make top walls not walkable, by killing
		local killBlockName = 'Killbrick'
		local killBlock = Prefabs[killBlockName]:Clone()
		killBlock.Size = Vector3.new(3, 4, blockWidth)
		killBlock.CFrame = newBlock.CFrame + Vector3.new(0, blockHeight - 7, 0)
		killBlock.Transparency = 1
		killBlock.Parent = folder
	end
end

function DrawFloor(pos, cframe, folder, width, height, settings)
	local floor = Instance.new('Part')

	floor.Size = Vector3.new(width, 1, height)

	floor.Name = floorPartName
	floor.CanCollide = true
	floor.Anchored = true

	floor.CFrame = CFrame.new(pos + getCenterVector(width, height))

	floor.CFrame = getCorrectCframe(cframe, floor.CFrame)

	if not settings.onlyBlocks then
		floor.Parent = folder
		floor.Transparency = 1
		floor.CanCollide = false
		partToTerrain(floor, settings.groundMaterial)
	else
		floor.Parent = folder
	end
end

function DrawCeiling(pos, cframe, folder, width, height, settings)
	local floor = Instance.new('Part')

	floor.Size = Vector3.new(width, 1, height)

	floor.Name = 'Ceiling'
	floor.CanCollide = true
	floor.Anchored = true
	floor.CFrame = CFrame.new(pos + getCenterVector(width, height))
	floor.CFrame = getCorrectCframe(cframe, floor.CFrame)

	if not settings.onlyBlocks then
		floor.Parent = folder
		floor.Transparency = 1
		floor.CanCollide = false
		partToTerrain(floor, settings.wallMaterial)
	else
		floor.Parent = folder
	end
end

function DrawStart(pos, cframe, folder)
	local block = 'SpawnPlaceholder'
	local newBlock = Prefabs[block]:Clone()

	newBlock.CFrame = CFrame.new(pos)
	newBlock.CFrame = getCorrectCframe(cframe, newBlock.CFrame)
	newBlock.Parent = folder
end

function DrawFinish(pos, cframe, folder)
	local block = 'FinishPlaceholder'
	local newBlock = Prefabs[block]:Clone()

	newBlock.CFrame = CFrame.new(pos)
	newBlock.CFrame = getCorrectCframe(cframe, newBlock.CFrame)
	newBlock.Parent = folder
end

local function draw_maze(maze, folder, pos, cframe, settings)
	local maze_width = blockWidth * #maze[1]
	local maze_height = blockWidth * #maze

	warn('Positioning Maze: ', pos)
	-- part can have max size 2048
	local maxPartSize = 2048
	warn('Size in studs:' .. tostring(maze_width) .. ', height:' .. tostring(maze_height))
	if maxPartSize < maze_width or maxPartSize < maze_height then
		warn('Floor or Ceiling part is over max size:' .. tostring(maxPartSize))
	end

	DrawFloor(pos, cframe, folder, maze_width, maze_height, settings)

	if settings.addCeiling then
		DrawCeiling(
			pos + Vector3.new(0, blockHeight, 0),
			cframe,
			folder,
			maze_width,
			maze_height,
			settings
		)
	end

	if settings.addStartAndFinish then
		local offset = Vector3.new(blockWidth / 2, 0, blockWidth / 2)
		DrawStart(pos + Vector3.new(2, 6, 2) + offset, cframe, folder)

		local finisWidth = blockWidth - 2
		local finishOffset = Vector3.new(finisWidth / 2, 2, finisWidth / 2)
		local farCorner = Vector3.new(maze_width - finisWidth, 0, maze_height - finisWidth)
		DrawFinish(pos + farCorner + finishOffset, cframe, folder)
	end

	local blockDepth = 0

	local parts = {}
	-- TODO: remove duplicate walls

	function cachePart(p, vertical)
		local key = tostring(p) .. tostring(vertical)
		if not parts[key] then
			parts[key] = true
			DrawBlock(p, cframe, folder, vertical, settings)
			-- warn('Has same part already')
		else
		end
	end

	for zi = 1, #maze do
		for xi = 1, #maze[1] do
			local pos_x = (blockWidth + blockDepth) * (xi - 1) + blockDepth
			local pos_z = (blockWidth + blockDepth) * (zi - 1) + blockDepth

			local cell = maze[zi][xi]

			if not cell.north:IsOpened() then
				local p = Vector3.new(pos_x, 0, pos_z)
				cachePart(pos + p, true)
			end

			if not cell.east:IsOpened() then
				local p = Vector3.new(pos_x + blockWidth, 0, pos_z)
				cachePart(pos + p, false)
			end

			if not cell.south:IsOpened() then
				local p = Vector3.new(pos_x, 0, pos_z + blockWidth)
				cachePart(pos + p, true)
			end

			if not cell.west:IsOpened() then
				local p = Vector3.new(pos_x, 0, pos_z)
				cachePart(pos + p, false)
			end

			if settings.addRandomModels then
				local p = Vector3.new(pos_x, 0.4, pos_z)
				AddRandomParts(pos + p, cframe, folder, settings)
			end
		end
	end
end

local MazeGenerator = {}

local mazeFolderName = 'Maze'

function MazeGenerator:generate(settings)
	local width = settings.width
	local height = settings.height
	local location = settings.location
	warn('Generating maze  width:' .. width .. ', height:' .. height)

	local maze = Maze:new(width, height, true)

	recursive_backtracker(maze)

	local mazeFolder = location:FindFirstChild(mazeFolderName)

	if mazeFolder then
		local floor = mazeFolder:FindFirstChild(floorPartName)
		workspace.Terrain:FillBlock(
			floor.CFrame,
			floor.Size + Vector3.new(10, blockHeight * 3, 10),
			Enum.Material.Air
		)
		mazeFolder:Destroy()
	end

	mazeFolder = Instance.new('Folder')
	mazeFolder.Name = mazeFolderName
	mazeFolder.Parent = location

	local position = Vector3.new(0, 0, 0)
	local cframe = CFrame.new(0, 0, 0)
	if location:IsA('BasePart') then
		position = location.Position
		cframe = location.CFrame
		warn('Using part location')
	end

	draw_maze(maze, mazeFolder, position, cframe, settings)
end

return MazeGenerator