Maze Generator by nimaid

-- A maze generator using the recursive backtracker method.
-- Made by nimaid
-- Maze will start 1 block in front of the turtle.
-- It will build in the horizontal direction (right) (2 * width) + 1 blocks
-- It will build in the vertical direction (forward) (2 * height) + 1 blocks
-- Make sure the turtle is fueled.
-- It will hang when it runs out of materials, and will resume when given more.
-- Make sure the space is clear for 1 block up and to the sides of the final sized maze.
-- Keep mobs away from the building turtle.

turtle.select(1)

function select_filled_slot()
  while turtle.getItemCount() == 0 do
    if turtle.getSelectedSlot() == 16 then
      turtle.select(1)
    else
      turtle.select(turtle.getSelectedSlot() + 1)
    end
  end
end

turtle.refuel()
write("\nHorizontal cells: ")
width = tonumber(read())
write("Vertical cells: ")
height = tonumber(read())
write("Maze Height: ")
vheight = tonumber(read())
print("\nCreating initial grid...")

turtle.forward()
turtle.turnLeft()
turtle.turnLeft()

for j = 0, (width * 2) do
  for i = 0, (height * 2) do
    select_filled_slot()
    turtle.back()

    if j % 2 == 1 then
      if i % 2 == 0 then
        select_filled_slot()
        turtle.place()
      end
    else
      turtle.place()
    end
  end

  if j % 2 == 0 then
    turtle.turnLeft()
    turtle.forward()
    turtle.turnLeft()
    turtle.back()
  else
    turtle.turnRight()
    turtle.forward()
    turtle.turnRight()
    turtle.back()
  end
end

turtle.back()
turtle.turnLeft()
turtle.dig()
turtle.forward()
turtle.forward()

direction = 4

function face_dir(dir)
  while direction ~= dir do
    if direction == 1 and dir == 4 then
      turtle.turnLeft()
      direction = 4
    elseif direction == 4 and dir == 1 then
      turtle.turnRight()
      direction = 1
    elseif dir < direction then
      turtle.turnLeft()
      if direction == 1 then
        direction = 4
      else
        direction = direction - 1
      end
    else
      turtle.turnRight()
      if direction == 4 then
        direction = 1
      else
        direction = direction + 1
      end
    end
  end
end

stack = {}

cell_visited = {}
for i = 1, width do
  cell_visited[i] = {}
  for j = 1, height do
    cell_visited[i][j] = false
  end
end

cell_visited[width][height] = true

current_position = {width, height}

function update_position(dir)
  if dir == 1 then
    current_position[2] = current_position[2] + 1
  elseif dir == 2 then
    current_position[1] = current_position[1] + 1
  elseif dir == 3 then
    current_position[2] = current_position[2] - 1
  elseif dir == 4 then
    current_position[1] = current_position[1] - 1
  end
end

function move_dir(dir)
  face_dir(dir)
  turtle.dig()
  turtle.forward()
  turtle.forward()

  table.insert(stack, dir)

  update_position(dir)

  cell_visited[current_position[1]][current_position[2]] = true
end

function can_move(dir)
  if dir == 1 then
    if current_position[2] == height then
      return false
    elseif cell_visited[current_position[1]][current_position[2] + 1] then
      return false
    else
      return true
    end
  elseif dir == 2 then
    if current_position[1] == width then
      return false
    elseif cell_visited[current_position[1] + 1][current_position[2]] then
      return false
    else
      return true
    end
  elseif dir == 3 then
    if current_position[2] == 1 then
      return false
    elseif cell_visited[current_position[1]][current_position[2] - 1] then
      return false
    else
      return true
    end
  elseif dir == 4 then
    if current_position[1] == 1 then
      return false
    elseif cell_visited[current_position[1] - 1][current_position[2]] then
      return false
    else
      return true
    end
  else
    return false
  end
end

function viable_directions()
  local dirs = {}

  for i = 1, 4 do
    if can_move(i) then
      table.insert(dirs, i)
    end
  end

  return dirs
end

function move_back()
  if #stack == 0 then
    return false
  end

  local orig_dir = table.remove(stack)

  face_dir(orig_dir)
  turtle.back()
  turtle.back()

  local rev_dir = orig_dir + 2
  while rev_dir > 4 do
    rev_dir = rev_dir - 4
  end

  update_position(rev_dir)
  return true
end

math.randomseed(os.time())

made_entrance = false

function step()
  if current_position[1] == 1 and current_position[2] == 1 and not made_entrance then
    face_dir(3)
    turtle.dig()
    made_entrance = true
    end
  possible_dirs = viable_directions()
  if #possible_dirs > 0 then
    local dir_to_move = possible_dirs[math.random(#possible_dirs)]
    print("Moving in direction ", dir_to_move)
    move_dir(dir_to_move)
    return true
  else
    print("Can't move anywhere.")
    if not move_back() then
      print("\nMaze generation is done.")
      return false
    else
      print("Backtracked a step")
      return true
    end
  end
end

curr_step = 0
while step() do
  curr_step = curr_step + 1
  print("\nStep: ", curr_step)
end

face_dir(2)
turtle.forward()
turtle.up()
face_dir(3)
turtle.back()

function extend_up_step()
  select_filled_slot()
  if turtle.detectDown() then
    for x = 2, vheight do
      turtle.up()
      turtle.placeDown()
    end

    turtle.forward()

    for x = 2, vheight do
      turtle.down()
    end
  else
    turtle.forward()
  end
end

print("\nExtending walls upwards...")

face_dir(3)
for i = 0, width * 2 do
  for j = 0, height * 2 do
    extend_up_step()
  end

  if i ~= width * 2 then
    face_dir(4)
    turtle.forward()
    if i % 2 == 0 then
      face_dir(1)
    else
      face_dir(3)
    end
    turtle.forward()
  end
end

print("\nDone extending walls.")

turtle.down()
face_dir(1)

print("\nMaze complete!")