local A=game:GetService("\082\101\112\108\105\099\097\116\101\100\083\116\111\114\097\103\101")local p=A:WaitForChild("\077\111\100\117\108\101\115")local f=require(p.src.utils.Logger)local R=require(p.M)local u=A:WaitForChild("\077\111\100\101\108\115")local K=require(script.Parent.MazeBacktrace)local d=require(script.Parent.Maze)local i=u.Prefabs local g=u.Misc local S=u.Money local T="\070\108\111\111\114\080\097\114\116"function getCenterVector(A,p)return Vector3.new(A/2,0,p/2)end function removePitch(A,p)local f,R,u=A:ToOrientation()return CFrame.new(A.Position)end function getCorrectCframe(A,p)local f=CFrame.new(A.Position)local R=f:inverse()*p return A*R end function partToTerrain(A,p)workspace.Terrain:FillBlock(A.CFrame,A.Size,p)end function partToRegion3(A)local p=math.abs local f=A.CFrame local R=A.Size local u,K,d=R.X,R.Y,R.Z local i,g,S,T,J,c,s,W,O,M,Q,k=f:components()local q=.5*((p(T)*u+p(J)*K)+p(c)*d)local B=.5*((p(s)*u+p(W)*K)+p(O)*d)local P=.5*((p(M)*u+p(Q)*K)+p(k)*d)local n=i-q local v=g-B local t=S-P local G=i+q local e=g+B local U=S+P local F,Z=Vector3.new(n,v,t),Vector3.new(G,e,U)return Region3.new(F,Z)end function randomPos(A)local p=A.blockWidth/2-A.partThickness local f=R.range(2,p)local u=R.range(-2,-p)local K=R.append(f,u)local d=R.sample(K)return d[1]end function randomRotation(A)return CFrame.new(A)*CFrame.fromOrientation(0,math.random(1,360),0)end function AddRandomPart(A,p,f,R)local u=g[R.randomStuffFolder]:GetChildren()local K=u[math.random(1,#u)]local d=K:Clone()local i=Vector3.new(randomPos(R),0,randomPos(R))local S if d:IsA("\066\097\115\101\080\097\114\116")then S=d.Size else S=d.PrimaryPart.Size end local T=R.blockWidth/2-S.X/2 local J=S.Y/2 local c=R.blockWidth/2-S.Z/2 local s=randomRotation((A+Vector3.new(T,J,c))+i)local W=getCorrectCframe(p,s)if d:IsA("\066\097\115\101\080\097\114\116")then d.CFrame=W else d:SetPrimaryPartCFrame(W)end d.Parent=f end function AddCoinPart(A,p,f,R)local u=S:GetChildren()local K=u[math.random(1,#u)]local d=K:Clone()local i if d:IsA("\066\097\115\101\080\097\114\116")then i=d.Size else i=d.PrimaryPart.Size end local g=R.blockWidth/2-i.X/2 local T=i.Y/2 local J=R.blockWidth/2-i.Z/2 local c=randomRotation(A+Vector3.new(g,T,J))local s=getCorrectCframe(p,c)if d:IsA("\066\097\115\101\080\097\114\116")then d.CFrame=s else d:SetPrimaryPartCFrame(s)end d.Parent=f end function AddRandomParts(A,p,f,R)AddCoinPart(A,p,f,R)local u=math.random(1,2)if u==1 then AddRandomPart(A,p,f,R)end end function MakeBlock(A)local p=Instance.new("\080\097\114\116")p.Anchored=true p.Size=Vector3.new(A.partThickness,A.blockHeight,A.blockWidth)return p end function DrawBlock(A,p,f,R,u)local K=MakeBlock(u)local d=A.X local g=A.Y local S=A.Z local T=K.Size.Y/2 local J=K.Size.Z/2 local c=CFrame.new(d,g+T,S+J)if R then local A=math.rad(90)c=CFrame.new(d+J,g+T,S)*CFrame.Angles(0,A,0)end K.CFrame=c K.CFrame=getCorrectCframe(p,K.CFrame)if not u.onlyBlocks then partToTerrain(K,u.wallMaterial)else K.Parent=f end if u.addKillBlocks then local A="\075\105\108\108\098\114\105\099\107"local p=i[A]:Clone()p.Size=Vector3.new(3,4,u.blockWidth)p.CFrame=K.CFrame+Vector3.new(0,u.blockHeight-7,0)p.Transparency=1 p.Parent=f end end function DrawDummyFloor(A,p,f)local R=A:Clone()R.Size=R.Size+Vector3.new(f.blockWidth*3,f.blockHeight*3,f.blockWidth*3)R.Transparency=.9 R.Parent=p R.CanCollide=false end function DrawPart(A,p,f,R,u,K,d,i)local g=Instance.new("\080\097\114\116")g.Size=Vector3.new(R,K.ceilingFloorThickness,u)g.Name=d g.CanCollide=true g.Anchored=true g.CFrame=CFrame.new(A+getCenterVector(R,u))g.CFrame=getCorrectCframe(p,g.CFrame)if not K.onlyBlocks then g.Parent=f g.Transparency=1 g.CanCollide=false partToTerrain(g,i)else g.Parent=f end end function DrawFloor(A,p,f,R,u,K)DrawPart(A,p,f,R,u,K,T,K.groundMaterial)end function DrawCeiling(A,p,f,R,u,K)DrawPart(A,p,f,R,u,K,"\067\101\105\108\105\110\103",K.wallMaterial)end function DrawStart(A,p,f)local R="\083\112\097\119\110\080\108\097\099\101\104\111\108\100\101\114"local u=i[R]:Clone()u.CFrame=CFrame.new(A)u.CFrame=getCorrectCframe(p,u.CFrame)u.Parent=f end function DrawFinish(A,p,f)local R="\070\105\110\105\115\104\080\108\097\099\101\104\111\108\100\101\114"local u=i[R]:Clone()u.CFrame=CFrame.new(A)u.CFrame=getCorrectCframe(p,u.CFrame)u.Parent=f end local function J(A,p,f,R,u)local K=u.blockWidth*#A[1]local d=u.blockWidth*#A warn("\080\111\115\105\116\105\111\110\105\110\103 \077\097\122\101\058 ",f)local i=2048 warn("\083\105\122\101 \105\110 \115\116\117\100\115\058"..(tostring(K)..("\044 \104\101\105\103\104\116\058"..tostring(d))))if i<K or i<d 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(i))end DrawFloor(f+Vector3.new(0,-u.ceilingFloorThickness/2,0),R,p,K,d,u)if u.addCeiling then DrawCeiling(f+Vector3.new(0,u.blockHeight+u.ceilingFloorThickness/2,0),R,p,K,d,u)end if u.addStartAndFinish then local A=Vector3.new(u.blockWidth/2,0,u.blockWidth/2)DrawStart((f+Vector3.new(2,6,2))+A,R,p)local i=u.blockWidth-2 local g=Vector3.new(i/2,2,i/2)local S=Vector3.new(K-i,0,d-i)DrawFinish((f+S)+g,R,p)end local g=0 local S={}function cachePart(A,f)local K=tostring(A)..tostring(f)if not S[K]then S[K]=true DrawBlock(A,R,p,f,u)else end end for K=1,#A,1 do for d=1,#A[1],1 do local i=(u.blockWidth+g)*(d-1)+g local S=(u.blockWidth+g)*(K-1)+g local T=A[K][d]if not T.north:IsOpened()then local A=Vector3.new(i,0,S)cachePart(f+A,true)end if not T.east:IsOpened()then local A=Vector3.new(i+u.blockWidth,0,S)cachePart(f+A,false)end if not T.south:IsOpened()then local A=Vector3.new(i,0,S+u.blockWidth)cachePart(f+A,true)end if not T.west:IsOpened()then local A=Vector3.new(i,0,S)cachePart(f+A,false)end if u.addRandomModels then local A=Vector3.new(i,u.ceilingFloorThickness/2.5,S)AddRandomParts(f+A,R,p,u)end end end end local c={}local s="\077\097\122\101"function c.clean(p,A)warn("\067\108\101\097\110 \109\097\122\101 \102\114\111\109 \108\111\099\097\116\105\111\110\058",A.location)local f=A.location local R=f:FindFirstChild(s)if R then local p=R:FindFirstChild(T)p.Size=p.Size+Vector3.new(A.blockWidth*3,A.blockHeight*5,A.blockWidth*3)workspace.Terrain:FillBlock(p.CFrame,p.Size,Enum.Material.Air)R:Destroy()end end function c.generate(p,A)local f=A.width local R=A.height local u=A.location warn("\071\101\110\101\114\097\116\105\110\103 \109\097\122\101  \119\105\100\116\104\058"..(f..("\044 \104\101\105\103\104\116\058"..R)))local i=d:new(f,R,true)K(i)local g=Instance.new("\070\111\108\100\101\114")g.Name=s g.Parent=u local S=Vector3.new(0,0,0)local T=CFrame.new(0,0,0)if u:IsA("\066\097\115\101\080\097\114\116")then S=u.Position T=u.CFrame warn("\085\115\105\110\103 \112\097\114\116 \108\111\099\097\116\105\111\110")end J(i,g,S,T,A)end return c
local ReplicatedStorage = game:GetService('ReplicatedStorage')
local Modules = ReplicatedStorage:WaitForChild('Modules')
local logger = require(Modules.src.utils.Logger)
local M = require(Modules.M)

local Models = ReplicatedStorage: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 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 randomPos(settings)
	local areaHalfWidth = settings.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[settings.randomStuffFolder]: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 = settings.blockWidth / 2 - partSize.X / 2
	local halfY = partSize.Y / 2
	local halfZ = settings.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 = settings.blockWidth / 2 - partSize.X / 2
	local halfY = partSize.Y / 2
	local halfZ = settings.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)
	AddCoinPart(pos, cframe, folder, settings)

	local willAdd = math.random(1, 2)
	if willAdd == 1 then
		AddRandomPart(pos, cframe, folder, settings)
	end
end

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

	newBlock.Anchored = true
	newBlock.Size = Vector3.new(settings.partThickness, settings.blockHeight, settings.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, settings.blockWidth)
		killBlock.CFrame = newBlock.CFrame + Vector3.new(0, settings.blockHeight - 7, 0)
		killBlock.Transparency = 1
		killBlock.Parent = folder
	end
end

function DrawDummyFloor(floor, folder, settings)
	local floor2 = floor:Clone()
	floor2.Size =
		floor2.Size + Vector3.new(
			settings.blockWidth * 3,
			settings.blockHeight * 3,
			settings.blockWidth * 3
		)
	floor2.Transparency = 0.9
	floor2.Parent = folder
	floor2.CanCollide = false
end

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

	floor.Size = Vector3.new(width, settings.ceilingFloorThickness, height)

	floor.Name = name
	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, material)
	else
		floor.Parent = folder
	end
end

function DrawFloor(pos, cframe, folder, width, height, settings)
	DrawPart(pos, cframe, folder, width, height, settings, floorPartName, settings.groundMaterial)
end

function DrawCeiling(pos, cframe, folder, width, height, settings)
	DrawPart(pos, cframe, folder, width, height, settings, 'Ceiling', settings.wallMaterial)
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 = settings.blockWidth * #maze[1]
	local maze_height = settings.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 + Vector3.new(0, -settings.ceilingFloorThickness / 2, 0),
		cframe,
		folder,
		maze_width,
		maze_height,
		settings
	)

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

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

		local finisWidth = settings.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 = (settings.blockWidth + blockDepth) * (xi - 1) + blockDepth
			local pos_z = (settings.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 + settings.blockWidth, 0, pos_z)
				cachePart(pos + p, false)
			end

			if not cell.south:IsOpened() then
				local p = Vector3.new(pos_x, 0, pos_z + settings.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, settings.ceilingFloorThickness / 2.5, pos_z)
				AddRandomParts(pos + p, cframe, folder, settings)
			end
		end
	end
end

local MazeGenerator = {}

local mazeFolderName = 'Maze'

function MazeGenerator:clean(settings)
	warn('Clean maze from location:', settings.location)
	local location = settings.location
	local mazeFolder = location:FindFirstChild(mazeFolderName)

	if mazeFolder then
		local floor = mazeFolder:FindFirstChild(floorPartName)
		floor.Size =
			floor.Size + Vector3.new(
				settings.blockWidth * 3,
				settings.blockHeight * 5,
				settings.blockWidth * 3
			)

		workspace.Terrain:FillBlock(floor.CFrame, floor.Size, Enum.Material.Air)
		mazeFolder:Destroy()
	end
end

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 = 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