Advertisement
cadergator10

OpenComputers compatable A* Algorythm

Sep 27th, 2022 (edited)
1,027
1
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Lua 7.61 KB | None | 1 0
  1. --[[
  2.     Lua star example - Run with love (https://love2d.org/)
  3.     Copyright 2018 Wesley Werner <wesley.werner@gmail.com>
  4.  
  5.     Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
  6.  
  7.     The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
  8.  
  9.     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  10.  
  11.     References:
  12.     https://en.wikipedia.org/wiki/A*_search_algorithm
  13.     https://www.redblobgames.com/pathfinding/a-star/introduction.html
  14.     https://www.raywenderlich.com/4946/introduction-to-a-pathfinding
  15. ]]--
  16.  
  17. --- Provides easy A* path finding.
  18. -- @module lua-star
  19.  
  20. local module = {}
  21.  
  22. --- Clears all cached paths.
  23. function module:clearCached()
  24.     module.cache = nil
  25. end
  26.  
  27. -- (Internal) Returns a unique key for the start and end points.
  28. local function keyOf(start, goal)
  29.     return string.format("%d,%d,%d>%d,%d,%d", start.x, start.y, start.z, goal.x, goal.y, goal.z)
  30. end
  31.  
  32. -- (Internal) Returns the cached path for start and end points.
  33. local function getCached(start, goal)
  34.     if module.cache then
  35.         local key = keyOf(start, goal)
  36.         return module.cache[key]
  37.     end
  38. end
  39.  
  40. -- (Internal) Saves a path to the cache.
  41. local function saveCached(start, goal, path)
  42.     module.cache = module.cache or { }
  43.     local key = keyOf(start, goal)
  44.     module.cache[key] = path
  45. end
  46.  
  47. -- (Internal) Return the distance between two points.
  48. -- This method doesn't bother getting the square root of s, it is faster
  49. -- and it still works for our use.
  50.  
  51. local function distance(x1,y1,z1,x2,y2,z2)
  52.   local dx = x1 - x2
  53.   local dy = y1 - y2
  54.   local dz = z1 - z2
  55.   local s = dx * dx + dy * dy + dz * dz
  56.   return s
  57. end
  58.  
  59. -- (Internal) Clamp a value to a range.
  60. local function clamp(x, min, max)
  61.   return x < min and min or (x > max and max or x)
  62. end
  63.  
  64. -- (Internal) Return the score of a node.
  65. -- G is the cost from START to this node.
  66. -- H is a heuristic cost, in this case the distance from this node to the goal.
  67. -- Returns F, the sum of G and H.
  68. local function calculateScore(previous, node, goal)
  69.  
  70.     local G = previous.score + 1 + node.p
  71.     local H = distance(node.x, node.y, node.z, goal.x, goal.y, goal.z)
  72.     return G + H, G, H
  73.  
  74. end
  75.  
  76. -- (Internal) Returns true if the given list contains the specified item.
  77. local function listContains(list, item)
  78.     for _, test in ipairs(list) do
  79.         if test.x == item.x and test.y == item.y and test.z == item.z then
  80.             return true
  81.         end
  82.     end
  83.     return false
  84. end
  85.  
  86. -- (Internal) Returns the item in the given list.
  87. local function listItem(list, item)
  88.     for _, test in ipairs(list) do
  89.         if test.x == item.x and test.y == item.y and test.z == item.z then
  90.             return test
  91.         end
  92.     end
  93. end
  94.  
  95. local function getPowerTurn(start,point,facing)
  96.   --Facing 2=north, 3 = south, 4 = west, 5 = east
  97.   local function fresh(needed,thisis)
  98.     if needed == thisis then
  99.       return 0, facing
  100.     end
  101.     if needed == 2 then
  102.       if facing == 3 then
  103.         return 1.9
  104.       else
  105.         return 1
  106.       end
  107.     end
  108.     if needed == 3 then
  109.       if facing == 2 then
  110.         return 1.9
  111.       else
  112.         return 1
  113.       end
  114.     end
  115.     if needed == 4 then
  116.       if facing == 5 then
  117.         return 1.9
  118.       else
  119.         return 1
  120.       end
  121.     end
  122.     if needed == 5 then
  123.       if facing == 4 then
  124.         return 1.9
  125.       else
  126.         return 1
  127.       end
  128.     end
  129.   end
  130.   if point.y == -1 then
  131.     return 0.1, facing
  132.   elseif point.y == 1 then
  133.     return 0.1, facing
  134.   elseif point.x == -1 then
  135.     return fresh(4,facing), 4
  136.   elseif point.x == 1 then
  137.     return fresh(5,facing), 5
  138.   elseif point.z == -1 then
  139.     return fresh(2,facing), 2
  140.   elseif point.z == 1 then
  141.     return fresh(3,facing), 3
  142.   end
  143. end
  144.  
  145. -- (Internal) Requests adjacent map values around the given node.
  146. local function getAdjacent(width, height, length, node, positionIsOpenFunc)
  147.     local result = { }
  148.  
  149.     local positions = {
  150.         { x = 0, y = 0, z = -1 },  -- north
  151.         { x = -1, y = 0, z = 0 },  -- west
  152.         { x = 0, y = 0, z = 1 },   -- south
  153.         { x = 1, y = 0, z = 0 },   -- east
  154.         { x = 0, y = 1, z = 0 },   -- up
  155.         { x = 0, y = -1, z = 0}    -- down
  156.     }
  157.  
  158.     for _, point in ipairs(positions) do
  159.         local px = clamp(node.x + point.x, -1 * width, width)
  160.         local py = clamp(node.y + point.y, -1 * height, height)
  161.         local pz = clamp(node.z + point.z, -1 * length, length)
  162.         local value = positionIsOpenFunc( px, py, pz )
  163.         if value then
  164.             local power, facing = getPowerTurn(node,point,node.f)
  165.             table.insert( result, { x = px, y = py, z = pz, f = facing, p = power } )
  166.         end
  167.     end
  168.  
  169.     return result
  170.  
  171. end
  172.  
  173. -- Returns the path from start to goal, or false if no path exists.
  174. function module:find(width, height, length, start, goal, positionIsOpenFunc, useCache, distanceMode)
  175.  
  176.     if useCache then
  177.         local cachedPath = getCached(start, goal)
  178.         if cachedPath then
  179.             return cachedPath
  180.         end
  181.     end
  182.  
  183.     local success = false
  184.     local open = { }
  185.     local closed = { }
  186.  
  187.     start.score = 0
  188.     start.G = 0
  189.     start.H = distance(start.x, start.y, start.z, goal.x, goal.y, goal.z)
  190.     start.parent = { x = 0, y = 0, z = 0 }
  191.     table.insert(open, start)
  192.  
  193.     while not success and #open > 0 do
  194.  
  195.         -- sort by score or distance: high to low
  196.         if distanceMode == false then
  197.           table.sort(open, function(a, b) return a.score > b.score end)
  198.         else
  199.           table.sort(open, function(a, b) return a.H > b.H end)
  200.         end
  201.      
  202.         local current = table.remove(open)
  203.         table.insert(closed, current)
  204.  
  205.         success = listContains(closed, goal)
  206.  
  207.         if not success then
  208.  
  209.             local adjacentList = getAdjacent(width, height, length, current, positionIsOpenFunc, false)
  210.  
  211.             for _, adjacent in ipairs(adjacentList) do
  212.  
  213.                 if not listContains(closed, adjacent) then
  214.  
  215.                     if not listContains(open, adjacent) then
  216.  
  217.                         adjacent.score,_,adjacent.H = calculateScore(current, adjacent, goal)
  218.                         adjacent.parent = current
  219.                         table.insert(open, adjacent)
  220.  
  221.                     end
  222.  
  223.                 end
  224.  
  225.             end
  226.  
  227.         end
  228.  
  229.     end
  230.  
  231.     if not success then
  232.         return false
  233.     end
  234.  
  235.     -- traverse the parents from the last point to get the path
  236.     local node = listItem(closed, closed[#closed])
  237.     local path = { }
  238.  
  239.     while node do
  240.  
  241.         table.insert(path, 1, { x = node.x, y = node.y, z = node.z } )
  242.         node = listItem(closed, node.parent)
  243.  
  244.     end
  245.  
  246.     saveCached(start, goal, path)
  247.  
  248.     -- reverse the closed list to get the solution
  249.     return path
  250.  
  251. end
  252.  
  253. return module
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement