Pathfinder

function deepcopy(object)
    local lookup_table = {}
    local function _copy(object)
        if type(object) ~= "table" then
            return object
        elseif lookup_table[object] then
            return lookup_table[object]
        end
        local new_table = {}
        lookup_table[object] = new_table
        for index, value in pairs(object) do
            new_table[_copy(index)] = _copy(value)
        end
        return setmetatable(new_table, getmetatable(object))
    end
    return _copy(object)
end

function findPath()
   while (true) do

      --if empty, then no path exists
      if #paths == 0 then
         return {}
      end

      colorNumber = colorNumber + 40/MAP_SIZE

      endOfPath = paths[1][#paths[1]]
      currentX = endOfPath[1]
      currentY = endOfPath[2]

      --check
      if grid[currentX][currentY] == GOAL then
         pathFound = 1
         return deepcopy(paths[1])
      end

      --up
      if currentY > 1 then
         x,y = currentX, currentY - 1
         if grid[x][y] == BLANK then
            path = deepcopy(paths[1])
            table.insert(path, {x, y})
            table.insert(paths, deepcopy(path))
            grid[x][y] = BLANK_CHECKED
            colorGrid[x][y] = colorNumber
         elseif grid[x][y] == GOAL then
            pathFound = 1
            return deepcopy(paths[1])
         end
      end

      --right
      if currentX < MAP_SIZE then
         x,y = currentX + 1, currentY
         if grid[x][y] == BLANK then
            path = deepcopy(paths[1])
            table.insert(path, {x, y})
            table.insert(paths, deepcopy(path))
            grid[x][y] = BLANK_CHECKED
            colorGrid[x][y] = colorNumber
         elseif grid[x][y] == GOAL then
            pathFound = 1
            return deepcopy(paths[1])
         end
      end

      --down
      if currentY < MAP_SIZE then
         x,y = currentX, currentY + 1
            if grid[x][y] == BLANK then
            path = deepcopy(paths[1])
            table.insert(path, {x, y})
            table.insert(paths, deepcopy(path))
            grid[x][y] = BLANK_CHECKED
            colorGrid[x][y] = colorNumber
         elseif grid[x][y] == GOAL then
            pathFound = 1
            return deepcopy(paths[1])
         end
      end

      --left
      if currentX > 1 then
         x,y = currentX - 1, currentY
         if grid[x][y] == BLANK then
            path = deepcopy(paths[1])
            table.insert(path, {x, y})
            table.insert(paths, deepcopy(path))
            grid[x][y] = BLANK_CHECKED
            colorGrid[x][y] = colorNumber
         elseif grid[x][y] == GOAL then
            pathFound = 1
            return deepcopy(paths[1])
         end
      end

      --remove front path
      table.remove(paths, 1)

      --if empty, then no path exists
      if #paths == 0 then
         return {}
      end

      if drawing == 1 then
         return paths[1]
      end
   end
end

function addPath(pathArg)
   for x = 1, MAP_SIZE do
      for y = 1, MAP_SIZE do
         if grid[x][y] == PATH then
            grid[x][y] = BLANK_CHECKED
         end
      end
   end

   for key, value in pairs(pathArg) do
      grid[value[1]][value[2]] = PATH
   end
   grid[startX][startY] = START
end

function init()
   MAP_SIZE = mapSizes[sizeIndex]
   TILE_SIZE = 600/MAP_SIZE

   grid={}
   for rowNum = 1, MAP_SIZE do
      row={}
      for i = 1, MAP_SIZE do
         if math.random() < WALL_DENSITY then
            row[i] = WALL
         else
            row[i] = BLANK
         end
      end
      grid[rowNum] = row
   end

   --place start and goal
   startX = math.floor(math.random()*MAP_SIZE) + 1
   startY = math.floor(math.random()*MAP_SIZE) + 1

   while true do
      goalX = math.floor(math.random()*MAP_SIZE) + 1
      goalY = math.floor(math.random()*MAP_SIZE) + 1
      if goalX ~= startX or goalY ~= startY then
         break
      end
   end

   colorNumber = 0
   colorGrid = deepcopy(grid)

   mostPaths = 0

   pathFound = 0

   grid[startX][startY] = START
   grid[goalX][goalY] = GOAL

   --paths: queue of paths
   paths = {{{startX, startY}}}
end

function love.load()
   math.randomseed(os.time())

   mapSizes  = {  3,   4,   5,   6,  8, 10, 12, 15, 20, 40, 50, 60, 75, 100, 120, 150, 200, 300, 600}
   tileSizes = {200, 150, 120, 100, 75, 60, 50, 40, 20, 15, 12, 10,  8,   6,   5,   4,   3,   2,   1}
   sizeIndex = 12

   drawing = 1

   BLANK = 0
   BLANK_CHECKED = 4
   WALL = 1
   START = 2
   GOAL = 3
   PATH = 5

   MAP_SIZE = 60
   WALL_DENSITY = 0.35
   TILE_SIZE = 10

   restart = 0
   autoRestart = 0

   drawPath = 1

   init()
end

function love.update(dt)
   if restart == 1 or (autoRestart == 1 and (pathFound == 1 or #paths == 0)) then
      restart = 0
      init()
   end

   addPath(findPath())
end

function setCheckedColor(number)
   x = 256
   m = 1

   number = number % (x*6)

   -- cyan -> green
   if number < x-1 then
      love.graphics.setColor(0, 255, 255 - number*m)

   elseif number  < x+1 then
      love.graphics.setColor(0, 255, 0)

   -- green -> yellow
   elseif number < 2*x-1 then
      love.graphics.setColor((number-x)*m, 255, 0)

   elseif number  < 2*x+1 then
      love.graphics.setColor(255, 255, 0)

   -- yellow -> red
   elseif number < 3*x-1 then
      love.graphics.setColor(255, 255 - (number-2*x)*m, 0)

   elseif number  < 3*x+1 then
      love.graphics.setColor(255, 0, 0)

   -- red -> magenta
   elseif number < 4*x-1 then
      love.graphics.setColor(255, 0, (number-3*x)*m)

   elseif number  < 4*x+1 then
      love.graphics.setColor(255, 0, 255)

   -- magenta -> blue
   elseif number < 5*x-1 then
      love.graphics.setColor(255 - (number-4*x)*m, 0, 255)

   elseif number  < 5*x+1 then
      love.graphics.setColor(0, 0, 255)

   -- blue -> cyan
   elseif number < 6*x-1 then
      love.graphics.setColor(0, (number-5*x)*m, 255)

   elseif number  < 6*x+1 then
      love.graphics.setColor(0, 255, 255)


   end
end

function drawTile(c, x, y)
   if c == BLANK then
      love.graphics.setColor(255,255,255)
   elseif c == BLANK_CHECKED then
      setCheckedColor(colorGrid[x][y])
   elseif c == PATH then
      if drawPath == 1 then
         love.graphics.setColor(0, 0, 0)
      else
         setCheckedColor(colorGrid[x][y])
      end
   elseif c == WALL then
      love.graphics.setColor(127,127,127)
   elseif c == START then
      love.graphics.setColor(255,127,127)
   elseif c == GOAL then
      love.graphics.setColor(255,127,127)
   end
   love.graphics.rectangle("fill", (x-1)*TILE_SIZE, (y-1)*TILE_SIZE, TILE_SIZE, TILE_SIZE)
end

function drawPaths()
   if #paths > mostPaths then
      mostPaths = #paths
   end

   y = 10

   love.graphics.setColor(255,255,255)
   y=y+0 love.graphics.print("Paths: " .. #paths, 610, y)
   y=y+15 love.graphics.print("Most paths: " .. mostPaths, 610, y)

   y=y+30 love.graphics.print("Map: " .. MAP_SIZE .. "x" .. MAP_SIZE, 610, y)
   y=y+15 love.graphics.print("Wall density: " .. WALL_DENSITY*100 .. "%", 610, y)
   y=y+15 love.graphics.print("Auto-restart: " .. (autoRestart==1 and "On" or "Off"), 610, y)

   y=y+30 love.graphics.print("[+] Larger map", 610, y)
   y=y+15 love.graphics.print("[-] Smaller map", 610, y)
   y=y+15 love.graphics.print("[*] More walls", 610, y)
   y=y+15 love.graphics.print("[/] Fewer walls", 610, y)
   --y=y+15 love.graphics.print("[F4] Toggle full screen", 610, y)
   y=y+15 love.graphics.print("[F7] Toggle path drawing", 610, y)
   y=y+15 love.graphics.print("[F8] Toggle auto-restart", 610, y)
   y=y+15 love.graphics.print("[F9] Restart with animation", 610, y)
   y=y+15 love.graphics.print("[F10] Restart w/out animation", 610, y)
   y=y+15 love.graphics.print("[Esc] Quit", 610, y)
end

function love.draw()
   for x = 1, MAP_SIZE do
      for y = 1, MAP_SIZE do
         drawTile(grid[x][y], x, y)
      end
   end

   drawPaths()
end

function love.keyreleased(key, unicode)
   --F4: full screen
     if key == "f4" then
        love.graphics.toggleFullscreen()
     end

   --F8: auto restart
     if key == "f8" then
        autoRestart = math.abs(autoRestart - 1)
     end

   --F8: auto restart
     if key == "f7" then
        drawPath = math.abs(drawPath - 1)
     end

   --F9: restart
     if key == "f9" then
        drawing = 1
        restart = 1
     end

   --F10: restart without drawing
     if key == "f10" then
        drawing = 0
        restart = 1
     end

   -- +: bigger map
   if key == "kp+" then
      sizeIndex = sizeIndex + 1
      if sizeIndex > #mapSizes then
         sizeIndex = #mapSizes
      end
      restart = 1
   end

   -- -: smaller map
   if key == "kp-" then
      sizeIndex = sizeIndex - 1
      if sizeIndex < 1 then
         sizeIndex = 1
      end
      restart = 1
   end

   -- *: more walls
   if key == "kp*" then
      WALL_DENSITY = WALL_DENSITY + 0.05
      if WALL_DENSITY > 1 then
         WALL_DENSITY = 1
      end
      restart = 1
   end

   -- /: fewer walls
   if key == "kp/" then
      WALL_DENSITY = WALL_DENSITY - 0.05
      if WALL_DENSITY < 0 then
         WALL_DENSITY = 0
      end
      restart = 1
   end

   --Esc: exit
   if key == "escape" then
      love.event.push("quit")
   end
end