SHARE
TWEET

Pathfinder

Archon Jan 26th, 2012 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function deepcopy(object)
  2.     local lookup_table = {}
  3.     local function _copy(object)
  4.         if type(object) ~= "table" then
  5.             return object
  6.         elseif lookup_table[object] then
  7.             return lookup_table[object]
  8.         end
  9.         local new_table = {}
  10.         lookup_table[object] = new_table
  11.         for index, value in pairs(object) do
  12.             new_table[_copy(index)] = _copy(value)
  13.         end
  14.         return setmetatable(new_table, getmetatable(object))
  15.     end
  16.     return _copy(object)
  17. end
  18.  
  19. function findPath()
  20.    while (true) do
  21.  
  22.       --if empty, then no path exists
  23.       if #paths == 0 then
  24.          return {}
  25.       end
  26.      
  27.       colorNumber = colorNumber + 40/MAP_SIZE
  28.      
  29.       endOfPath = paths[1][#paths[1]]
  30.       currentX = endOfPath[1]
  31.       currentY = endOfPath[2]
  32.      
  33.       --check
  34.       if grid[currentX][currentY] == GOAL then
  35.          pathFound = 1
  36.          return deepcopy(paths[1])
  37.       end
  38.      
  39.       --up
  40.       if currentY > 1 then
  41.          x,y = currentX, currentY - 1
  42.          if grid[x][y] == BLANK then
  43.             path = deepcopy(paths[1])
  44.             table.insert(path, {x, y})
  45.             table.insert(paths, deepcopy(path))
  46.             grid[x][y] = BLANK_CHECKED
  47.             colorGrid[x][y] = colorNumber
  48.          elseif grid[x][y] == GOAL then
  49.             pathFound = 1
  50.             return deepcopy(paths[1])
  51.          end
  52.       end
  53.      
  54.       --right
  55.       if currentX < MAP_SIZE then
  56.          x,y = currentX + 1, currentY
  57.          if grid[x][y] == BLANK then
  58.             path = deepcopy(paths[1])
  59.             table.insert(path, {x, y})
  60.             table.insert(paths, deepcopy(path))
  61.             grid[x][y] = BLANK_CHECKED
  62.             colorGrid[x][y] = colorNumber
  63.          elseif grid[x][y] == GOAL then
  64.             pathFound = 1
  65.             return deepcopy(paths[1])
  66.          end
  67.       end
  68.      
  69.       --down
  70.       if currentY < MAP_SIZE then
  71.          x,y = currentX, currentY + 1
  72.             if grid[x][y] == BLANK then
  73.             path = deepcopy(paths[1])
  74.             table.insert(path, {x, y})
  75.             table.insert(paths, deepcopy(path))
  76.             grid[x][y] = BLANK_CHECKED
  77.             colorGrid[x][y] = colorNumber
  78.          elseif grid[x][y] == GOAL then
  79.             pathFound = 1
  80.             return deepcopy(paths[1])
  81.          end
  82.       end
  83.      
  84.       --left
  85.       if currentX > 1 then
  86.          x,y = currentX - 1, currentY
  87.          if grid[x][y] == BLANK then
  88.             path = deepcopy(paths[1])
  89.             table.insert(path, {x, y})
  90.             table.insert(paths, deepcopy(path))
  91.             grid[x][y] = BLANK_CHECKED
  92.             colorGrid[x][y] = colorNumber
  93.          elseif grid[x][y] == GOAL then
  94.             pathFound = 1
  95.             return deepcopy(paths[1])      
  96.          end
  97.       end
  98.      
  99.       --remove front path
  100.       table.remove(paths, 1)
  101.      
  102.       --if empty, then no path exists
  103.       if #paths == 0 then
  104.          return {}
  105.       end
  106.    
  107.       if drawing == 1 then
  108.          return paths[1]
  109.       end
  110.    end
  111. end
  112.  
  113. function addPath(pathArg)
  114.    for x = 1, MAP_SIZE do
  115.       for y = 1, MAP_SIZE do
  116.          if grid[x][y] == PATH then
  117.             grid[x][y] = BLANK_CHECKED
  118.          end
  119.       end
  120.    end
  121.    
  122.    for key, value in pairs(pathArg) do
  123.       grid[value[1]][value[2]] = PATH
  124.    end
  125.    grid[startX][startY] = START
  126. end
  127.  
  128. function init()
  129.    MAP_SIZE = mapSizes[sizeIndex]
  130.    TILE_SIZE = 600/MAP_SIZE
  131.  
  132.    grid={}
  133.    for rowNum = 1, MAP_SIZE do
  134.       row={}
  135.       for i = 1, MAP_SIZE do
  136.          if math.random() < WALL_DENSITY then
  137.             row[i] = WALL
  138.          else
  139.             row[i] = BLANK
  140.          end
  141.       end
  142.       grid[rowNum] = row
  143.    end
  144.    
  145.    --place start and goal
  146.    startX = math.floor(math.random()*MAP_SIZE) + 1
  147.    startY = math.floor(math.random()*MAP_SIZE) + 1
  148.    
  149.    while true do
  150.       goalX = math.floor(math.random()*MAP_SIZE) + 1
  151.       goalY = math.floor(math.random()*MAP_SIZE) + 1
  152.       if goalX ~= startX or goalY ~= startY then
  153.          break
  154.       end
  155.    end
  156.    
  157.    colorNumber = 0
  158.    colorGrid = deepcopy(grid)
  159.    
  160.    mostPaths = 0
  161.    
  162.    pathFound = 0
  163.    
  164.    grid[startX][startY] = START
  165.    grid[goalX][goalY] = GOAL
  166.    
  167.    --paths: queue of paths
  168.    paths = {{{startX, startY}}}
  169. end
  170.  
  171. function love.load()
  172.    math.randomseed(os.time())
  173.    
  174.    mapSizes  = {  3,   4,   5,   6,  8, 10, 12, 15, 20, 40, 50, 60, 75, 100, 120, 150, 200, 300, 600}
  175.    tileSizes = {200, 150, 120, 100, 75, 60, 50, 40, 20, 15, 12, 10,  8,   6,   5,   4,   3,   2,   1}
  176.    sizeIndex = 12
  177.    
  178.    drawing = 1
  179.  
  180.    BLANK = 0
  181.    BLANK_CHECKED = 4
  182.    WALL = 1
  183.    START = 2
  184.    GOAL = 3
  185.    PATH = 5
  186.    
  187.    MAP_SIZE = 60
  188.    WALL_DENSITY = 0.35
  189.    TILE_SIZE = 10
  190.    
  191.    restart = 0
  192.    autoRestart = 0
  193.    
  194.    drawPath = 1
  195.    
  196.    init()
  197. end
  198.  
  199. function love.update(dt)
  200.    if restart == 1 or (autoRestart == 1 and (pathFound == 1 or #paths == 0)) then
  201.       restart = 0
  202.       init()
  203.    end
  204.    
  205.    addPath(findPath())
  206. end
  207.  
  208. function setCheckedColor(number)
  209.    x = 256
  210.    m = 1
  211.    
  212.    number = number % (x*6)
  213.    
  214.    -- cyan -> green
  215.    if number < x-1 then
  216.       love.graphics.setColor(0, 255, 255 - number*m)
  217.      
  218.    elseif number  < x+1 then
  219.       love.graphics.setColor(0, 255, 0)
  220.      
  221.    -- green -> yellow
  222.    elseif number < 2*x-1 then
  223.       love.graphics.setColor((number-x)*m, 255, 0)
  224.      
  225.    elseif number  < 2*x+1 then
  226.       love.graphics.setColor(255, 255, 0)
  227.      
  228.    -- yellow -> red
  229.    elseif number < 3*x-1 then
  230.       love.graphics.setColor(255, 255 - (number-2*x)*m, 0)
  231.      
  232.    elseif number  < 3*x+1 then
  233.       love.graphics.setColor(255, 0, 0)
  234.      
  235.    -- red -> magenta
  236.    elseif number < 4*x-1 then
  237.       love.graphics.setColor(255, 0, (number-3*x)*m)
  238.      
  239.    elseif number  < 4*x+1 then
  240.       love.graphics.setColor(255, 0, 255)
  241.      
  242.    -- magenta -> blue
  243.    elseif number < 5*x-1 then
  244.       love.graphics.setColor(255 - (number-4*x)*m, 0, 255)
  245.      
  246.    elseif number  < 5*x+1 then
  247.       love.graphics.setColor(0, 0, 255)
  248.      
  249.    -- blue -> cyan
  250.    elseif number < 6*x-1 then
  251.       love.graphics.setColor(0, (number-5*x)*m, 255)
  252.      
  253.    elseif number  < 6*x+1 then
  254.       love.graphics.setColor(0, 255, 255)
  255.      
  256.    
  257.    end
  258. end
  259.  
  260. function drawTile(c, x, y)
  261.    if c == BLANK then
  262.       love.graphics.setColor(255,255,255)
  263.    elseif c == BLANK_CHECKED then
  264.       setCheckedColor(colorGrid[x][y])
  265.    elseif c == PATH then
  266.       if drawPath == 1 then
  267.          love.graphics.setColor(0, 0, 0)
  268.       else
  269.          setCheckedColor(colorGrid[x][y])
  270.       end
  271.    elseif c == WALL then
  272.       love.graphics.setColor(127,127,127)
  273.    elseif c == START then
  274.       love.graphics.setColor(255,127,127)
  275.    elseif c == GOAL then
  276.       love.graphics.setColor(255,127,127)
  277.    end
  278.    love.graphics.rectangle("fill", (x-1)*TILE_SIZE, (y-1)*TILE_SIZE, TILE_SIZE, TILE_SIZE)
  279. end
  280.  
  281. function drawPaths()
  282.    if #paths > mostPaths then
  283.       mostPaths = #paths
  284.    end
  285.    
  286.    y = 10
  287.    
  288.    love.graphics.setColor(255,255,255)
  289.    y=y+0 love.graphics.print("Paths: " .. #paths, 610, y)
  290.    y=y+15 love.graphics.print("Most paths: " .. mostPaths, 610, y)
  291.    
  292.    y=y+30 love.graphics.print("Map: " .. MAP_SIZE .. "x" .. MAP_SIZE, 610, y)
  293.    y=y+15 love.graphics.print("Wall density: " .. WALL_DENSITY*100 .. "%", 610, y)
  294.    y=y+15 love.graphics.print("Auto-restart: " .. (autoRestart==1 and "On" or "Off"), 610, y)
  295.    
  296.    y=y+30 love.graphics.print("[+] Larger map", 610, y)
  297.    y=y+15 love.graphics.print("[-] Smaller map", 610, y)
  298.    y=y+15 love.graphics.print("[*] More walls", 610, y)
  299.    y=y+15 love.graphics.print("[/] Fewer walls", 610, y)
  300.    --y=y+15 love.graphics.print("[F4] Toggle full screen", 610, y)
  301.    y=y+15 love.graphics.print("[F7] Toggle path drawing", 610, y)
  302.    y=y+15 love.graphics.print("[F8] Toggle auto-restart", 610, y)
  303.    y=y+15 love.graphics.print("[F9] Restart with animation", 610, y)
  304.    y=y+15 love.graphics.print("[F10] Restart w/out animation", 610, y)
  305.    y=y+15 love.graphics.print("[Esc] Quit", 610, y)
  306. end
  307.  
  308. function love.draw()
  309.    for x = 1, MAP_SIZE do
  310.       for y = 1, MAP_SIZE do
  311.          drawTile(grid[x][y], x, y)
  312.       end
  313.    end
  314.    
  315.    drawPaths()
  316. end
  317.  
  318. function love.keyreleased(key, unicode)
  319.    --F4: full screen
  320.      if key == "f4" then
  321.         love.graphics.toggleFullscreen()
  322.      end
  323.      
  324.    --F8: auto restart
  325.      if key == "f8" then
  326.         autoRestart = math.abs(autoRestart - 1)
  327.      end
  328.      
  329.    --F8: auto restart
  330.      if key == "f7" then
  331.         drawPath = math.abs(drawPath - 1)
  332.      end
  333.      
  334.    --F9: restart
  335.      if key == "f9" then
  336.         drawing = 1
  337.         restart = 1
  338.      end
  339.      
  340.    --F10: restart without drawing
  341.      if key == "f10" then
  342.         drawing = 0
  343.         restart = 1
  344.      end
  345.      
  346.    -- +: bigger map
  347.    if key == "kp+" then
  348.       sizeIndex = sizeIndex + 1
  349.       if sizeIndex > #mapSizes then
  350.          sizeIndex = #mapSizes
  351.       end
  352.       restart = 1
  353.    end
  354.      
  355.    -- -: smaller map
  356.    if key == "kp-" then
  357.       sizeIndex = sizeIndex - 1
  358.       if sizeIndex < 1 then
  359.          sizeIndex = 1
  360.       end
  361.       restart = 1
  362.    end
  363.      
  364.    -- *: more walls
  365.    if key == "kp*" then
  366.       WALL_DENSITY = WALL_DENSITY + 0.05
  367.       if WALL_DENSITY > 1 then
  368.          WALL_DENSITY = 1
  369.       end
  370.       restart = 1
  371.    end
  372.      
  373.    -- /: fewer walls
  374.    if key == "kp/" then
  375.       WALL_DENSITY = WALL_DENSITY - 0.05
  376.       if WALL_DENSITY < 0 then
  377.          WALL_DENSITY = 0
  378.       end
  379.       restart = 1
  380.    end
  381.      
  382.    --Esc: exit
  383.    if key == "escape" then
  384.       love.event.push("quit")
  385.    end
  386. end
RAW Paste Data
Top