ComputerCraft 3D Maze Turtle Program

--TODO - distribute torches more intelligently?
--TODO - more efficient ladder placement? turtle makes many unecessary moves to place them
--TODO - better ladder placement? ladders sometimes switch sides of the maze


--USAGE
--for large mazes, set up 3 chests in a row, each with one block of space between them:
--Put blocks in chest 1, to the right in chest 2 put torches, and in chest 3 ladders
--put the turtle on top of chest 1
--fuel up your turtle
--fill inventory slot 1 with torches, 2 with ladders, the rest with blocks you want the maze to be built of
--set the maze dimension by editing w/h/d, values must be odd
--run the program - turtle will build forward and to the right, and up!

--When the turtle is done you will need to manually poke in any entrance/exit points you want to use.
--Any two spots will work, all points of the maze can reach all other points.  Some choices will be harder than others.


--To pull in API stub for offline development
if require then
  require "minecraft"
end

--width and height of maze, must be odd
w = 15
h = 9
d = 15


--To keep track of current position within the maze
--Z is height
curX = 0
curY = 0
curZ = 0 -- maze relative z
worldZ = 0 --world relative z


--These are maze relative N/S/E/W
--Wherever you turtle is pointing when you start the maze is "north"
--Turtle will start in the 'Southwest' corner of the maze
-- 0=N 1=E 2=S 3=W
curRotation = 0;



math.randomseed(os.time())
--math.randomseed(5)


--The light field below is only for debugging purposes
--You can remove it for performance reasons
cells = {}
--initialize cells
for i = 0,w-1 do
  cells[i] = {}
  for j = 0,d-1 do
    cells[i][j] = {}
    for k = 0,h-1 do
      cell = {visited = false,x=i,y=j,z=k,light=false}
      cells[i][j][k] = cell
    end
  end
end

--neighbors are two and only two cells away in cardinal directions
--this leaves the perimeter maze walls solid
--we tag each neighbor as vertical or not so we can go vertical less often
--for a more pleasant to navigate maze
function getNeighbors(cell)
  neighbors = {}
  count = 0
  x = cell.x
  y = cell.y
  z = cell.z
  if x+2 < w-1 then
    neighbor = {cell = cells[x+2][y][z], vertical = false }
    neighbors[count] = neighbor
    count = count + 1
  end
  if x-2 >= 1 then
    neighbor = {cell = cells[x-2][y][z], vertical = false }
    neighbors[count] = neighbor
    count = count + 1
  end
  if y+2 < d-1 then
    neighbor = {cell = cells[x][y+2][z], vertical = false }
    neighbors[count] = neighbor
    count = count + 1
  end
  if y-2 >= 1 then
    neighbor = {cell = cells[x][y-2][z], vertical = false }
    neighbors[count] = neighbor
    count = count + 1
  end
  if z+2 < h-1 then
    neighbor = {cell = cells[x][y][z+2], vertical = true }
    neighbors[count] = neighbor
    count = count+1
  end
  if z-2 >= 1 then
    neighbor = {cell = cells[x][y][z-2], vertical = true}
    neighbors[count] = neighbor
    count = count+1
  end

  return neighbors
end

--get a random neighbor cell that is unvisited
function getRandomUnvisitedNeighbor(cell)
  neighbors = getNeighbors(cell)
  unvisitedNeighbors = {}
  count = 0

  for k,v in pairs(neighbors) do
    if v.cell.visited == false then
      unvisitedNeighbors[count] = v
      count = count + 1
    end
  end

  --This holds off on vertical path choices until the last minute
  --So there are less up and down movements which are tiresome
  --for the player to navigate
  --you can just toss this if you prefer not to do this
  if count > 2 then
    for i = count-1,0,-1 do
      neighbor = unvisitedNeighbors[i]
      if neighbor.vertical == true then
        table.remove(unvisitedNeighbors,i)
        count = count - 1
      end
    end
  end


  if count == 0 then
    return nil
  end

  --get a random neihgbor
  r = math.random(count)-1;
  return unvisitedNeighbors[r].cell

end

--given two neighboring cells, get the cell between them
function cellBetween(cell1,cell2)
  if cell1.x > cell2.x then
    return cells[cell1.x-1][cell1.y][cell1.z]
  end

  if cell1.x < cell2.x then
    return cells[cell1.x+1][cell1.y][cell1.z]
  end

  if cell1.y > cell2.y then
    return cells[cell1.x][cell1.y-1][cell1.z]
  end

  if cell1.y < cell2.y then
    return cells[cell1.x][cell1.y+1][cell1.z]
  end

  if cell1.z > cell2.z then
    return cells[cell1.x][cell1.y][cell1.z-1]
  end

  if cell1.z < cell2.z then
    return cells[cell1.x][cell1.y][cell1.z+1]
  end

end

--the main recursive function to traverse the maze
function recur(curCell)

  --mark current cell as visited
  curCell.visited = true

  --check each neighbor cell
  for i = 1,6 do
     nCell = getRandomUnvisitedNeighbor(curCell)
    if nCell ~= nil then
      -- clear the cell between the neighbors
      bCell = cellBetween(curCell,nCell)
      bCell.visited = true
      --push current cell onto the stack and move on the neighbor cell
      recur(nCell)
    end
  end

end


--start point needs to be inside the perimeter
--and odd
recur(cells[1][1][1])

--Now we are done with the maze algorithm, and have a maze complete
--in memory in the cells table
--We must being building it with our turtle

lightSlot = 1   --inventory slot for lights
ladderSlot = 2 --inventory slot for ladders
lightCount = 0 --how many blocks since we last placed a light?
lightThreshold = 4 --how often to place lights


--For debugging
function printWorldLocation()
  print("World: (" .. curX .. "," .. curY .. "," .. worldZ .. ")")
end

function printMazeLocation()
  print("Maze: (" .. curX .. "," .. curY .. "," .. curZ ..")")
end



--find a slot with building material in it
function selectBlock()
    for i = 3, 16 do
            if turtle.getItemCount(i) > 0 then
                turtle.select(i)
                return true
            end
    end
    return false
end

--Place a block, first checking inventory
function blockDown()
    checkInventory()
    turtle.select(3)
    if turtle.getItemCount() == 0 then
        selectBlock()
    end
    turtle.placeDown()
end

--light can be anything that will place down on the floors
function placeLight()
    if lightCount > lightThreshold then
      if curZ +1 < h then
        --we have to much sure this current block has no vertical passage
        --above or below it as torch will interfere with ladder
        if cells[curX][curY][curZ+1].visited == false then
          if  cells[curX][curY][curZ-1].visited == false then
            turtle.select(lightSlot)
            turtle.placeDown()

            --below is for debugging only
            cells[curX][curY][curZ].light = true

            lightCount = 0
          end
        end
      end
    else
      lightCount = lightCount + 1
    end
end

--We always use these to turn to keep track of rotation
function turnRight()
    turtle.turnRight()
    curRotation = (curRotation +1) % 4
end

function turnLeft()
    turtle.turnLeft()
    curRotation = (curRotation-1) % 4
end

--Will orient to the direction specified
function orient(direction)
  while curRotation ~= direction do
    turnRight()
  end
end

--We use this to go forward to keep track of our x/y position
function forward()
    turtle.forward()
    if curRotation == 0 then
        curY = curY + 1
    elseif curRotation == 2 then
        curY = curY - 1
    elseif curRotation == 1 then
        curX = curX + 1
    elseif curRotation == 3 then
        curX = curX - 1
    end
end


--And we use these to go up and down to keep track of our Z position
function up()
    worldZ = worldZ + 1
    turtle.up()
end

function down()
    worldZ = worldZ - 1
    turtle.down()
end


function turnAroundOut()
    --if pointing "north" turn right
    if curRotation == 0 then
        turnRight()
        forward()
        turnRight()
    else
        turnLeft()
        forward()
        turnLeft()
    end
end

--when going back the other way
function turnAroundIn()
   if curRotation == 2 then
        turnRight()
        forward()
        turnRight()
    else
        turnLeft()
        forward()
        turnLeft()
    end
end

--Descends into vertical passages
--places ladders as it comes back up
function placeLadder()
  checkInventory()
  turtle.select(ladderSlot)
  down()
  down()
  turtle.placeDown()
  up()
  turtle.placeDown()
  up()
  turtle.placeDown()
end


function placeFloorLayerOut()
  print("FloorLayerOut")

    if curZ ~= 0 then
      up()
      turnRight()
      turnRight()
    end
    for x = 0, w-1 do
        for y = 0, d-1 do
            if cells[curX][curY][curZ].visited == false then
                blockDown()
            end
            if y < d-1 then
              forward()
            end

         end
         if x < w-1 then
          turnAroundOut()
        end
    end

end

function placeFloorLayerIn()
  print("FloorLayerIn");
   up()
    if curZ ~= 0 then
      turnRight()
      turnRight()
    end
    for x = w-1, 0,-1 do
        for y = d-1,0,-1 do
            if cells[curX][curY][curZ].visited == false then
                blockDown()
            end
            if y > 0 then
              forward()
            end

         end
         if x > 0 then
          turnAroundIn()
        end
    end
end


function placeWallLayer1In()
  print("wallLayer1In")
    up()
    turnRight()
    turnRight()
    for x = w-1,0,-1 do
      for y = d-1,0,-1 do
        if cells[curX][curY][curZ].visited then
          placeLight()
        else
          blockDown()
        end
        if y > 0 then
          forward()
        end
      end
      if x > 0 then
        turnAroundIn()
      end
    end
end



function placeWallLayer2Out()
  print("wallLayer2Out")
    up()
    turnRight()
    turnRight()
    for x = 0,w-1 do
      for y = 0,d-1 do
        if cells[curX][curY][curZ].visited == false then
          blockDown()
        end
        if y < d-1 then
          forward()
        end
      end
      if x < w-1 then
        turnAroundOut()
      end
    end
end

--This could be made more efficient
--Turtle could go directly to each vertical passage
function placeLaddersOut()
  print("placeLaddersOut")
  if curZ == 0 then
    return
  end
    turnRight()
    turnRight()
    for x = 0,w-1 do
      for y = 0,d-1 do
        if cells[curX][curY][curZ].visited then
          placeLadder()
        end
        if y < d-1 then
          forward()
        end
      end
      if x < w-1 then
        turnAroundOut()
      end
    end
end


--checks if we are running low on blocks, torches, or ladders
function checkInventory()

  --check building blocks
  totalBlocks = 0
  for i=3,16 do
    totalBlocks = totalBlocks + turtle.getItemCount(i)
  end

  --check torches
  torchCount = turtle.getItemCount(1)

  --check ladders
  ladderCount = turtle.getItemCount(2)

  if totalBlocks < 5 or torchCount < 5 or ladderCount < 5 then
    returnToOrigin()
    getMoreBlocks()
    resumeBuild()
  end

end

--resume coordinates
resX = 0
resY = 0
resZ = 0
resRotation = 0

--returns to starting chest
function returnToOrigin()
  resX = curX
  resY = curY
  resZ = worldZ
  resRotation = curRotation

  --point south then go past the edge of the maze
  orient(2)
  for i = 0,resY do
    forward()
  end

  --point west then go to point above chest
  orient(3)
  for i = 0, resX-1 do
    forward()
  end

  --drop down to above the chest
  for i = 0, resZ-1 do
    down()
  end


end

--fill up on all 3 resources
function getMoreBlocks()

  --get building blocks from 1st chest
  while turtle.suckDown(64) do
  end

  --get torches from 2nd chest which is assumed to be 2 blocks east
  --point east
  orient(1)
  forward()
  forward()
  turtle.select(1)
  turtle.suckDown(64-turtle.getItemCount()) --just enough to fill upt he stack

  --get ladders from 3rd chest assumed to be 2 more blocks east
  forward()
  forward()
  turtle.select(2)
  turtle.suckDown(64-turtle.getItemCount()) --just enough

  --point west and go back to above the start chest
  orient(3)
  forward()
  forward()
  forward()
  forward()

end

--return to the position we left off
function resumeBuild()

  --back up
  for i = 0, resZ -1 do
    up()
  end

  --point east
  orient(1)
  for i = 0, resX-1 do
    forward()
  end

  orient(0)
  for i = 0, resY do
    forward()
  end
  --resume original rotation
  orient(resRotation)
end


--prints ton of text representing maze state
function fullDebug()
for z = 0,h-1 do
  for y = 0,d-1 do
    for x = 0,w-1 do

      if cells[x][y][z].light == true and cells[x][y][z].visited == false then
        io.write("("..x..","..y..","..z.."):FF") --if you see this something went wrong
      elseif cells[x][y][z].light then
        io.write("("..x..","..y..","..z.."):**")
      elseif cells[x][y][z].visited == false then
        io.write("("..x..","..y..","..z.."):XX")
      else
        io.write("("..x..","..y..","..z.."):  ")
      end

    end
    io.write("\n")
  end
  io.write("\n")
end
end

--quick text representation of each layer of the maze
function debug()
for z = 0,h-1 do
  for y = 0,d-1 do
    for x = 0,w-1 do

      if (cells[x][y][z].light == true) and (cells[x][y][z].visited == false) then
        io.write("FF") --if you see this something went wrong
      elseif cells[x][y][z].light == true then
        io.write("**")
      elseif cells[x][y][z].visited == false then
        io.write("XX")
      else
        io.write("  ")
      end

    end
    io.write("\n")
  end
  io.write("\n")
end
end



hush = true --silences stub api prints, has no effect in game

turtle.forward() --move off the chest to starting position of maze
placeFloorLayerOut()
curZ = curZ + 1
placeWallLayer1In()
placeWallLayer2Out()
while true do
  print("loopstart")

  curZ = curZ + 1
  placeFloorLayerIn()

  if curZ == h-1 then
    break
  end

  placeLaddersOut()
  curZ = curZ + 1

  placeWallLayer1In()
  placeWallLayer2Out()
end

returnToOrigin()