[ComputerCraft] Turtle Maze Solver

--[[
Do not delete this comment

Written by NickM13
Maze Mapper v1.0

Map any generated maze, as long as
	it does not contain loops or
	blocked regions, and saves data
	to a file.

Place turtle in bottom left corner, facing along the left side,
	the turtle will map any maze as long as it is to the
	front and right of him.

Format of file saved is in bytes,
	(0-1)MazeWidth (Left to Right)		because who wouldnt want a 65536x65536 maze?
	(2-3)MazeHeight (Forward to Back)
	(4+)width * height / 8, rounded up
		store 8 bits per byte for compression
		read using
		bit.brshift(BYTE, BitID(0-7)) % 2
		right to left

Thanks, and happy mazing!

Do not delete this comment
]]

tArgs = {...}

local debugging = true

local startX = 1
local startY = 1
local currX = 1
local currY = 1
local rotation = 0

local mazewidth = 0
local mazeheight = 0
local mazedata = {}
local preferredfilename = "Maze"

if tArgs[1] and tArgs[1] ~= "" then
	preferredfilename = tArgs[1]
end

local function dPrint(msg) --debug print
	if debugging then
		io.write(msg)
	end
end

local function checkFuel() --if fuel level is 0 or 1, wait
	if turtle.getFuelLevel() < 2 then
		print("Out of fuel, insert coal")
		repeat
			for i=1, 16 do
				if turtle.getItemCount(i) ~= 0 then
					turtle.select(i)
					if turtle.refuel() then break end
				end
			end
			if turtle.getFuelLevel() < 2 then
				os.pullEvent()
			end
		until turtle.getFuelLevel() >= 2
		print("Fueled: "..turtle.getFuelLevel())
	end
end

local function setRotation(face) --rotate to face(0-3)
	if face == nil or tonumber(face) == nil then return nil end
	face = face % 4
	direction_ = math.abs(face - rotation)
	dPrint("Rotate: "..direction_.." "..rotation.." "..face.."\n")
	if direction_ == 0 then return end
	if rotation == 0 and face == 3 then
		repeat
			turtle.turnLeft()
			rotation = (rotation - 1)%4
		until rotation == face
	elseif rotation == 3 and face == 0 then
		repeat
			turtle.turnRight()
			rotation = (rotation + 1)%4
		until rotation == face
	else
		if rotation < face then
			repeat
				turtle.turnRight()
				rotation = (rotation + 1)%4
			until rotation == face
		else
			repeat
				turtle.turnLeft()
				rotation = (rotation - 1)%4
			until rotation == face
		end
	end
end

local function forward() --move turtle one block forward, if block is saved as empty. If saved as empty and is not empty, force empty(dig)
	checkFuel()
	if rotation == 0 then
		if mazedata[currX][currY + 1] == 1 then return false end
		currY = currY + 1
	elseif rotation == 1 then
		if mazedata[currX + 1][currY]  == 1 then return false end
		currX = currX + 1
	elseif rotation == 2 then
		if mazedata[currX][currY - 1] == 1 then return false end
		currY = currY - 1
	elseif rotation == 3 then
		if mazedata[currX - 1][currY] == 1 then return false end
		currX = currX - 1
	end
	while not turtle.forward() do
		turtle.attack()
		turtle.dig()
		dPrint("Blocked!\n")
		os.sleep(2)
	end
	return true
end

local function extendWidth() --extend width for file compression
	mazewidth = mazewidth + 1
	table.insert(mazedata, {})
end

local function extendHeight() --extend height for file compression
	mazeheight = mazeheight + 1

end

local function getAvailable(x, y) --look for unchecked and empty blocks, then check them
	availablearray_ = {}
	for i=1, 2 do
		if ((i-2) + rotation)%4 == 0 then
			if (y >= mazeheight) then
				extendHeight()
			end
			if (mazedata[x][y + 1] == nil) then
				setRotation(((i-2) + rotation)%4)
				mazedata[x][y + 1] = turtle.detect() and 1 or 0
			end
			if (mazedata[x][y + 1] == 0) then
				table.insert(availablearray_, 0)
			end
		elseif ((i-2) + rotation)%4 == 1 then
			if (x >= mazewidth) then
				extendWidth()
			end
			if (mazedata[x + 1][y] == nil) then
				setRotation(((i-2) + rotation)%4)
				mazedata[x + 1][y] = turtle.detect() and 1 or 0
			end
			if (mazedata[x + 1][y] == 0) then
				table.insert(availablearray_, 1)
			end
		elseif ((i-2) + rotation)%4 == 2 then
			if (y > 1) then
				if (mazedata[x][y - 1] == nil) then
					setRotation(((i-2) + rotation)%4)
					mazedata[x][y - 1] = turtle.detect() and 1 or 0
				end
				if (mazedata[x][y - 1] == 0) then
					table.insert(availablearray_, 2)
				end
			end
		elseif ((i-2) + rotation)%4 == 3 then
			if (x > 1) then
				if (mazedata[x - 1][y] == nil) then
					setRotation(((i-2) + rotation)%4)
					mazedata[x - 1][y] = turtle.detect() and 1 or 0
				end
				if (mazedata[x - 1][y] == 0) then
					table.insert(availablearray_, 3)
				end
			end
		end
	end
	return availablearray_
end

local function findUnvisited(x, y) --check for unvisited cells nearby
	if (x > 1) then
		if (mazedata[x - 1][y] == nil) then
			return true
		end
	end
	if (y > 1) then
		if (mazedata[x][y - 1] == nil) then
			return true
		end
	end
	if (mazedata[x + 1][y] == nil) then
		return true
	end
	if (mazedata[x][y + 1] == nil) then
		return true
	end
	return false
end

local function save(preferred) --saving function, compressed file using all bits in each byte
	filename = preferred
	i=1
	if fs.exists(preferred) then
		print("File "..preferred.." already exists.")
	end
	while fs.exists(filename) do
		filename = preferred..tostring(i)
		i = i + 1
	end
	if fs.exists(preferred) then
		print("Renamed to "..filename)
	end
	print("Saving maze to: "..filename)
	mfile = fs.open(filename, "wb")
	mfile.write(mazewidth%256)		mfile.write(bit.brshift(mazewidth, 8))
	mfile.write(mazeheight%256)		mfile.write(bit.brshift(mazeheight, 8))
	compindex = 0
	compbyte = 0
	for x=1, mazewidth do
		for y=1, mazeheight do
			if mazedata[x][y] == nil or mazedata[x][y] == 1 then
				compbyte = compbyte + bit.blshift(1, compindex)
			end
			compindex = compindex + 1
			if compindex >= 8 then
				dPrint("CByte: ") dPrint(compbyte) dPrint("\n")
				mfile.write(compbyte)
				compindex = 0
				compbyte = 0
			end
		end
	end
	if compindex > 0 then
		mfile.write(compbyte)
	end
	mfile.flush()
	mfile.close()
end

newcells = true

local function render() --render after mapping for debug purposes
	print(mazewidth.." "..mazeheight)
	os.sleep(2)
	term.clear()
	for x=1, mazewidth do
		for y=1, mazeheight do
			term.setCursorPos(x, mazeheight - y + 1)
			if mazedata[x][y] == nil then
				term.setBackgroundColor(colors.blue)
			elseif mazedata[x][y] == 1 then
				term.setBackgroundColor(colors.red)
			elseif mazedata[x][y] == 0 then
				term.setBackgroundColor(colors.green)
			end
			io.write(".")
		end
	end
	term.setCursorPos(1, mazeheight + 1)
end

local function mapMaze() --map current bounding maze, save to next available mazes/maze+i file (i.e mazes/maze7)
	mazewidth = 0
	mazeheight = 0
	for i=1, #mazedata do
		table.remove(mazedata, 1)
	end
	extendWidth()
	extendHeight()
	repeat
		nearby = getAvailable(currX, currY)
		if (#nearby ~= 0) then
			for i=1, #nearby do
				setRotation(nearby[i])
				if forward() then break end
			end
		else
			dPrint("Turn Right\n")
			setRotation(rotation+1)
		end
		if currX == startX and currY == startY then
			newcells = findUnvisited(currX, currY)
		end
	until currX == startX and currY == startY and not newcells
	setRotation(0)
	save(preferredfilename)
end

local function cruise()
	repeat
		nearby = getAvailable(currX, currY)
		if (#nearby ~= 0) then
			for i=1, #nearby do
				setRotation(nearby[i])
				if forward() then break end
			end
		else
			dPrint("Turn Right\n")
			setRotation(rotation+1)
		end
		if currX == startX and currY == startY then
			newcells = findUnvisited(currX, currY)
		end
	until currX == startX and currY == startY and not newcells
end

for x=1, currX do
	extendWidth()
end

for y=1, currY do
	extendHeight()
end

mapMaze()