• API
• FAQ
• Tools
• Archive
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
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.

Top