1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
--[[
lua-star.lua
Copyright 2017 wesley werner <wesley.werner@gmail.com>
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see http://www.gnu.org/licenses/.
References:
https://en.wikipedia.org/wiki/A*_search_algorithm
https://www.redblobgames.com/pathfinding/a-star/introduction.html
https://www.raywenderlich.com/4946/introduction-to-a-pathfinding
]]--
--- Provides easy A* path finding.
-- @module lua-star
local module = {}
--- Clears all cached paths.
function module:clearCached()
module.cache = nil
end
-- (Internal) Returns a unique key for the start and end points.
local function keyOf(start, goal)
return string.format("%d,%d>%d,%d", start.x, start.y, goal.x, goal.y)
end
-- (Internal) Returns the cached path for start and end points.
local function getCached(start, goal)
if module.cache then
local key = keyOf(start, goal)
return module.cache[key]
end
end
-- (Internal) Saves a path to the cache.
local function saveCached(start, goal, path)
module.cache = module.cache or { }
local key = keyOf(start, goal)
module.cache[key] = path
end
-- (Internal) Return the distance between two points.
-- This method doesn't bother getting the square root of s, it is faster
-- and it still works for our use.
local function distance(x1, y1, x2, y2)
local dx = x1 - x2
local dy = y1 - y2
local s = dx * dx + dy * dy
return s
end
-- (Internal) Clamp a value to a range.
local function clamp(x, min, max)
return x < min and min or (x > max and max or x)
end
-- (Internal) Return the score of a node.
-- G is the cost from START to this node.
-- H is a heuristic cost, in this case the distance from this node to the goal.
-- Returns F, the sum of G and H.
local function calculateScore(previous, node, goal)
local G = previous.score + 1
local H = distance(node.x, node.y, goal.x, goal.y)
return G + H, G, H
end
-- (Internal) Returns true if the given list contains the specified item.
local function listContains(list, item)
for _, test in ipairs(list) do
if test.x == item.x and test.y == item.y then
return true
end
end
return false
end
-- (Internal) Returns the item in the given list.
local function listItem(list, item)
for _, test in ipairs(list) do
if test.x == item.x and test.y == item.y then
return test
end
end
end
-- (Internal) Requests adjacent map values around the given node.
local function getAdjacent(width, height, node, positionIsOpenFunc)
local result = { }
local positions = {
{ x = 0, y = -1 }, -- top
{ x = -1, y = 0 }, -- left
{ x = 0, y = 1 }, -- bottom
{ x = 1, y = 0 }, -- right
-- include diagonal movements
{ x = -1, y = -1 }, -- top left
{ x = 1, y = -1 }, -- top right
{ x = -1, y = 1 }, -- bot left
{ x = 1, y = 1 }, -- bot right
}
for _, point in ipairs(positions) do
local px = clamp(node.x + point.x, 1, width)
local py = clamp(node.y + point.y, 1, height)
local value = positionIsOpenFunc( px, py )
if value then
table.insert( result, { x = px, y = py } )
end
end
return result
end
-- Returns the path from start to goal, or false if no path exists.
function module:find(width, height, start, goal, positionIsOpenFunc, useCache)
if useCache then
local cachedPath = getCached(start, goal)
if cachedPath then
return cachedPath
end
end
local success = false
local open = { }
local closed = { }
start.score = 0
start.G = 0
start.H = distance(start.x, start.y, goal.x, goal.y)
start.parent = { x = 0, y = 0 }
table.insert(open, start)
while not success and #open > 0 do
-- sort by score: high to low
table.sort(open, function(a, b) return a.score > b.score end)
local current = table.remove(open)
table.insert(closed, current)
success = listContains(closed, goal)
if not success then
local adjacentList = getAdjacent(width, height, current, positionIsOpenFunc)
for _, adjacent in ipairs(adjacentList) do
if not listContains(closed, adjacent) then
if not listContains(open, adjacent) then
adjacent.score = calculateScore(current, adjacent, goal)
adjacent.parent = current
table.insert(open, adjacent)
end
end
end
end
end
if not success then
return false
end
-- traverse the parents from the last point to get the path
local node = listItem(closed, closed[#closed])
local path = { }
while node do
table.insert(path, 1, { x = node.x, y = node.y } )
node = listItem(closed, node.parent)
end
saveCached(start, goal, path)
-- reverse the closed list to get the solution
return path
end
return module
|
