daily pastebin goal
69%
SHARE
TWEET

Pathfinder

Archon Jan 26th, 2012 79 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top