Phins

Untitled

Jul 4th, 2017
115
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. findWay = function(
  2.     startx, starty,
  3.     endx, endy,
  4.     mazeMap,
  5.     wallTile, spaceTile, ...)
  6.    
  7.     if type(wallTile) == "table" then
  8.         isWall = function(n)
  9.             for _, v in pairs(wallTile) do
  10.                 if v == n then
  11.                     return true
  12.                 end
  13.             end
  14.             return false
  15.         end
  16.     else
  17.         isWall = function(n)
  18.             return wallTile == n
  19.         end
  20.     end
  21.    
  22.     if type(spaceTile) == "table" then
  23.         isSpace = function(n)
  24.             for _, v in pairs(spaceTile) do
  25.                 if v == n then
  26.                     return true
  27.                 end
  28.             end
  29.             return false
  30.         end
  31.     else
  32.         isSpace = function(n)
  33.             return spaceTile == n
  34.         end
  35.     end
  36.    
  37.     do -- Fast error check
  38.         local _, err = ...
  39.         assert(type(mazeMap) == "table" or err, "Mazemap is "..type(mazeMap).." table expected!")
  40.         assert(isSpace(mazeMap[startx][starty]) or err, "Start position is not clear!")
  41.         assert(isSpace(mazeMap[endx][endy]) or err, "End position is not clear!")
  42.         assert(wallTile ~= spaceTile or err, "Wall tile and Space tile are the same!")
  43.     end
  44.    
  45.     do -- Create default Varibles
  46.         yieldCount = 0
  47.         doYield = 1000
  48.        
  49.         nWays = 1
  50.        
  51.         minDepth = 65535
  52.         mazeMapDepth = { }
  53.        
  54.         allWays = { }
  55.         exitWays = { }
  56.        
  57.         bigMap = true
  58.        
  59.         retSingleExit = true
  60.     end
  61.    
  62.     do -- Check args
  63.         local t = ...
  64.         if type(t) == "table" then
  65.             doYield = t.doYield or doYield
  66.             retSingleExit = t.retSingleExit or retSingleExit
  67.             minDepth = t.minDepth or minDepth
  68.             -- bigMap = t.bigMap or bigMap
  69.         end
  70.     end
  71.    
  72.     do -- Create functions
  73.         getSTIT = function(tbl) -- get smallest table in table
  74.             local smlst = -1
  75.             for i, v in pairs(tbl) do
  76.                 if smlst == -1 or #tbl[smlst] > #v then
  77.                     smlst = i
  78.                 end
  79.             end
  80.             return tbl[smlst]
  81.         end
  82.        
  83.         dereference = function(tbl)
  84.             y = 0
  85.             local ret = { }
  86.             for i, v in pairs(tbl or { }) do
  87.                 if type(v) == "table" then
  88.                     ret[i] = dereference(v)
  89.                 else
  90.                     ret[i] = v
  91.                 end
  92.             end
  93.             return ret
  94.         end
  95.     end
  96.    
  97.     for x=1, #mazeMap do
  98.         mazeMapDepth[x] = { }
  99.         for y=1, #mazeMap[x] do
  100.             mazeMapDepth[x][y] = minDepth
  101.         end
  102.     end
  103.    
  104.     algorithm = function( -- Main body
  105.         currx, curry,
  106.         endx, endy,
  107.         mazeMap,
  108.         depth, nWay)
  109.         yieldCount = yieldCount + 1
  110.        
  111.         if currx == endx and curry == endy then
  112.             table.insert(exitWays, dereference(allWays[nWay]))
  113.             return nil
  114.         end
  115.        
  116.         -- if bigMap and #exitWays > 0 and #getSTIT(exitWays) > nWay then
  117.             -- return nil
  118.         -- end
  119.        
  120.         if yieldCount % doYield == 0 then
  121.             os.sleep(0)
  122.         end
  123.        
  124.         local firstWay = true
  125.         local oldWay = dereference(allWays[nWay] or { })
  126.        
  127.         if type(mazeMap[currx + 1]) == "table" then
  128.             if isSpace(mazeMap[currx + 1][curry]) and mazeMapDepth[currx + 1][curry] > depth then              
  129.                 mazeMapDepth[currx + 1][curry] = depth
  130.                
  131.                 if allWays[nWay] == nil then
  132.                     allWays[nWay] = { }
  133.                 end
  134.                
  135.                 table.insert(allWays[nWay], { currx + 1, curry })
  136.                 algorithm(currx + 1, curry, endx, endy, mazeMap, depth + 1, nWay)
  137.                
  138.                 firstWay = false
  139.             end
  140.         end
  141.        
  142.         if type(mazeMap[currx - 1]) == "table" then
  143.             if isSpace(mazeMap[currx - 1][curry]) and mazeMapDepth[currx - 1][curry] > depth then
  144.                 mazeMapDepth[currx - 1][curry] = depth
  145.                
  146.                 if firstWay then
  147.                     if allWays[nWay] == nil then
  148.                         allWays[nWay] = { }
  149.                     end
  150.                    
  151.                     table.insert(allWays[nWay], { currx - 1, curry })
  152.                     algorithm(currx - 1, curry, endx, endy, mazeMap, depth + 1, nWay)
  153.                    
  154.                     firstWay = false
  155.                 else
  156.                     nWays = nWays + 1
  157.                     allWays[nWays] = dereference(oldWay)
  158.                    
  159.                     table.insert(allWays[nWays], { currx - 1, curry })
  160.                     algorithm(currx - 1, curry, endx, endy, mazeMap, depth + 1, nWays)
  161.                 end
  162.             end
  163.         end
  164.        
  165.         if isSpace(mazeMap[currx][curry + 1]) and mazeMapDepth[currx][curry + 1] > depth then
  166.             mazeMapDepth[currx][curry + 1] = depth
  167.            
  168.             if firstWay then
  169.                 if allWays[nWay] == nil then
  170.                     allWays[nWay] = { }
  171.                 end
  172.                
  173.                 table.insert(allWays[nWay], { currx, curry + 1 })
  174.                 algorithm(currx, curry + 1, endx, endy, mazeMap, depth + 1, nWay)
  175.                
  176.                 firstWay = false
  177.             else
  178.                 nWays = nWays + 1
  179.                 allWays[nWays] = dereference(oldWay)
  180.                
  181.                 table.insert(allWays[nWays], { currx, curry + 1 })
  182.                 algorithm(currx, curry + 1, endx, endy, mazeMap, depth + 1, nWays)
  183.             end
  184.         end
  185.        
  186.         if isSpace(mazeMap[currx][curry - 1]) and mazeMapDepth[currx][curry - 1] > depth then
  187.             mazeMapDepth[currx][curry - 1] = depth
  188.            
  189.             if firstWay then
  190.                 if allWays[nWay] == nil then
  191.                     allWays[nWay] = { }
  192.                 end
  193.                
  194.                 table.insert(allWays[nWay], { currx, curry - 1 })
  195.                 algorithm(currx, curry - 1, endx, endy, mazeMap, depth + 1, nWay)
  196.                
  197.                 firstWay = false
  198.             else
  199.                 nWays = nWays + 1
  200.                 allWays[nWays] = dereference(oldWay)
  201.                
  202.                 table.insert(allWays[nWays], { currx, curry - 1 })
  203.                 algorithm(currx, curry - 1, endx, endy, mazeMap, depth + 1, nWays)
  204.             end
  205.         end
  206.     end
  207.    
  208.     algorithm(startx, starty, endx, endy, mazeMap, 0, 1)
  209.    
  210.     local tReturn = dereference(getSTIT(exitWays))
  211.    
  212.     do -- Delete Varible
  213.         isWall = nil
  214.         isSpace = nil
  215.        
  216.         yieldCount = nil
  217.         doYield = nil
  218.        
  219.         nWays = nil
  220.        
  221.         mazeMapDepth = nil
  222.         minDepth = nil
  223.        
  224.         allWays = nil
  225.        
  226.         exitWays = nil
  227.         retSingleExit = nil
  228.        
  229.         bigMap = nil
  230.        
  231.         getSTIT = nil
  232.         dereference = nil
  233.        
  234.         algorithm = nil
  235.     end
  236.    
  237.     return tReturn or false
  238. end
  239.  
  240. turnImage = function(tbl)
  241.     ima = { }
  242.     max = 0
  243.     for i, v in pairs(tbl) do
  244.         if #v > max then
  245.             max = #v
  246.         end
  247.     end
  248.     for i=1, max do
  249.         ima[i] = { }
  250.         for _, v in pairs(tbl) do
  251.             table.insert(ima[i], v[i])
  252.         end
  253.     end
  254.     return ima
  255. end
RAW Paste Data