src/lua-star.lua

   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 local function distance(x1, y1, z1, x2, y2, z2)
  51   local dx = x1 - x2
  52   local dy = y1 - y2
  53   local dz = z1 - z2
  54   local s = dx * dx + dy * dy + dz * dz
  55   return s
  56 end
  57
  58 -- (Internal) Clamp a value to a range.
  59 local function clamp(x, min, max)
  60   return x < min and min or (x > max and max or x)
  61 end
  62
  63 -- (Internal) Return the score of a node.
  64 -- G is the cost from START to this node.
  65 -- H is a heuristic cost, in this case the distance from this node to the goal.
  66 -- Returns F, the sum of G and H.
  67 local function calculateScore(previous, node, goal)
  68
  69     local G = previous.score + 1
  70     local H = distance(node.x, node.y, node.z, goal.x, goal.y, goal.z)
  71     return G + H, G, H
  72
  73 end
  74
  75 -- (Internal) Returns true if the given list contains the specified item.
  76 local function listContains(list, item)
  77     for _, test in ipairs(list) do
  78         if test.x == item.x and test.y == item.y and test.z == item.z then
  79             return true
  80         end
  81     end
  82     return false
  83 end
  84
  85 -- (Internal) Returns the item in the given list.
  86 local function listItem(list, item)
  87     for _, test in ipairs(list) do
  88         if test.x == item.x and test.y == item.y and test.z == item.z then
  89             return test
  90         end
  91     end
  92 end
  93
  94 -- (Internal) Requests adjacent map values around the given node.
  95 local function getAdjacent(width, height, depth, node, positionIsOpenFunc, includeDiagonals)
  96
  97     local result = { }
  98
  99         local positions = {}
 100
 101     for x = -1, 1 do
 102     for y = -1, 1 do
 103     for z = -1, 1 do
 104                 local a = math.abs(x) + math.abs(y) + math.abs(z)
 105
 106                 if a ~= 0 and includeDiagonals or a == 1 then
 107                         table.insert(positions, {x = x, y = y, z = z})
 108                 end
 109     end
 110     end
 111     end
 112
 113     for _, point in ipairs(positions) do
 114         local px = clamp(node.x + point.x, 1, width)
 115         local py = clamp(node.y + point.y, 1, height)
 116         local pz = clamp(node.z + point.z, 1, depth)
 117
 118         local value = positionIsOpenFunc( px, py, pz )
 119         if value then
 120             table.insert( result, { x = px, y = py, z = pz  } )
 121         end
 122     end
 123
 124     return result
 125
 126 end
 127
 128 -- Returns the path from start to goal, or false if no path exists.
 129 function module:find(width, height, depth, start, goal, positionIsOpenFunc, useCache, excludeDiagonalMoving)
 130
 131     if useCache then
 132         local cachedPath = getCached(start, goal)
 133         if cachedPath then
 134             return cachedPath
 135         end
 136     end
 137
 138     local success = false
 139     local open = { }
 140     local closed = { }
 141
 142     start.score = 0
 143     start.G = 0
 144     start.H = distance(start.x, start.y, start.z, goal.x, goal.y, goal.z)
 145     start.parent = { x = 0, y = 0, z = 0 }
 146     table.insert(open, start)
 147
 148     while not success and #open > 0 do
 149
 150         -- sort by score: high to low
 151         table.sort(open, function(a, b) return a.score > b.score end)
 152
 153         local current = table.remove(open)
 154
 155         table.insert(closed, current)
 156
 157         success = listContains(closed, goal)
 158
 159         if not success then
 160
 161             local adjacentList = getAdjacent(width, height, depth, current, positionIsOpenFunc, not excludeDiagonalMoving)
 162
 163             for _, adjacent in ipairs(adjacentList) do
 164
 165                 if not listContains(closed, adjacent) then
 166
 167                     if not listContains(open, adjacent) then
 168
 169                         adjacent.score = calculateScore(current, adjacent, goal)
 170                         adjacent.parent = current
 171                         table.insert(open, adjacent)
 172
 173                     end
 174
 175                 end
 176
 177             end
 178
 179         end
 180
 181     end
 182
 183     if not success then
 184         return false
 185     end
 186
 187     -- traverse the parents from the last point to get the path
 188     local node = listItem(closed, closed[#closed])
 189     local path = { }
 190
 191     while node do
 192
 193         table.insert(path, 1, { x = node.x, y = node.y, z = node.z } )
 194         node = listItem(closed, node.parent)
 195
 196     end
 197
 198     saveCached(start, goal, path)
 199
 200     -- reverse the closed list to get the solution
 201     return path
 202
 203 end
 204
 205 return module