SHARE
TWEET

pathFinder2

Doob Mar 23rd, 2017 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. local WORLD, SIDE = {}, {{1,0,0},{-1,0,0},{0,0,1},{0,0,-1},{0,1,0},{0,-1,0}}
  2. local HUGE, UNPK, INSRT, PRS = math.huge, table.unpack, table.insert, pairs
  3.  
  4. local function hash(x, y, z)
  5.   x, z = x+134217728, z+134217728
  6.   return y|(x<<8)|(z<<36)
  7. end
  8.  
  9. local function unhash(h)
  10.   return ((h&68719476480)>>8)-134217728, h&255, ((h&-68719476736)>>36)-134217728
  11. end
  12.  
  13. local function delta(x1, y1, z1, x2, y2, z2)
  14.   return (x1-x2)^2+(y1-y2)^2+(z1-z2)^2
  15. end
  16.  
  17. -- FRONT/MARKED = { {x, y, z, d_total, d_target, parent}, ... }
  18. local function getPath(sX, sY, sZ, tX, tY, tZ)
  19.   local S, T, d = hash(tX, tY, tZ), hash(sX, sY, sZ), delta(sX, sY, sZ, tX, tY, tZ)
  20.   if not WORLD[S] or not WORLD[T] then return nil end
  21.   local FRONT, MARKED, PATH, DIR = {[S]={tX, tY, tZ, d, d, S}}, {}, {}, 1
  22.   local c, t, cX, cY, cZ, pX, pY, pZ, a, b, ch, N
  23.   while true do
  24.     c, t, d = nil, HUGE, HUGE
  25.     for i, j in PRS(FRONT) do
  26.       if j[4] < t and j[5] < d then
  27.         c, t, d = i, j[4], j[5]
  28.       end
  29.     end
  30.     if c then
  31.       MARKED[c], FRONT[c] = {UNPK(FRONT[c])}, nil
  32.       cX, cY, cZ = MARKED[c][1], MARKED[c][2], MARKED[c][3]
  33.       for s = 1, #SIDE do
  34.         pX, pY, pZ = cX+SIDE[s][1], cY+SIDE[s][2], cZ+SIDE[s][3]
  35.         ch = hash(pX, pY, pZ)
  36.         if WORLD[ch] and not MARKED[ch] and not FRONT[ch] then
  37.           a, b = delta(pX, pY, pZ, sX, sY, sZ), delta(pX, pY, pZ, tX, tY, tZ)
  38.           if (s > 0 and s < 5) and s ~= DIR then
  39.             DIR, a = s, b-a
  40.           end
  41.           FRONT[ch] = {pX, pY, pZ, a, b, c}
  42.           if ch == T then
  43.             N = ch
  44.             for i, j in PRS(FRONT) do
  45.               MARKED[i] = {UNPK(j)}
  46.             end
  47.             FRONT = nil
  48.             while N ~= S do
  49.               INSRT(PATH, {unhash(N)})
  50.               if MARKED[N] then
  51.                 N, MARKED[N] = MARKED[N][6], nil
  52.               end
  53.             end
  54.             INSRT(PATH, {tX, tY, tZ})
  55.             return PATH
  56.           end
  57.         end
  58.       end
  59.     else
  60.       return nil
  61.     end
  62.   end
  63.   if os.clock() > 0.5 then
  64.     return nil
  65.   end
  66. end
  67. --[[
  68. for x = 1, 10 do
  69.   for y = 1, 10 do
  70.     if math.random(0, 3) ~= 0 then
  71.       WORLD[hash(x, y, 0)] = true
  72.     end
  73.   end
  74. end
  75. local g = getPath(1, 1, 0, 10, 10, 0)
  76. if not g then
  77.   print('PATH NOT FOUND')
  78. end
  79. local a,c=''
  80. for x = 1, 10 do
  81.   for y = 1, 10 do
  82.     for i = 1, #g do
  83.       if g[i][1] == x and g[i][2] == y then
  84.         c=true
  85.       end
  86.     end
  87.     if c then
  88.       a, c = a..'o', nil
  89.     else
  90.       if WORLD[hash(x, y, 0)] then
  91.         a = a..' '
  92.       else
  93.         a = a..'x'
  94.       end
  95.     end
  96.   end
  97.   a = a..'\n'
  98. end
  99. print(a)
  100. ]]
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