forked from Courseplay/courseplay
-
Notifications
You must be signed in to change notification settings - Fork 0
/
astar.lua
282 lines (237 loc) · 8.75 KB
/
astar.lua
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
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
--[[
A* algorithm for LUA
Ported to LUA by Altair
21 septembre 2006
courseplay edit by hummel 2011
--]]
function courseplay:calcMoves(px, py, tx, ty, fruit_type, interval) -- Based on some code of LMelior but made it work and improved way beyond his code, still thx LMelior!
print("call calcMoves()");
if not courseplay:isField(py, px) then
return nil
end
interval = interval or 5;
local vertical_costs = 10
local diagnoal_costs = 14
px = courseplay.utils:roundToLowerInterval(px, interval);
py = courseplay.utils:roundToLowerInterval(py, interval);
tx = courseplay.utils:roundToLowerInterval(tx, interval);
ty = courseplay.utils:roundToLowerInterval(ty, interval);
--[[ PRE:
mapmat is a 2d array
px is the player's current x
py is the player's current y
tx is the target x
ty is the target y
Note: all the x and y are the x and y to be used in the table.
By this I mean, if the table is 3 by 2, the x can be 1,2,3 and the y can be 1 or 2.
--]]
--[[ POST:
closedlist is a list with the checked nodes.
It will return nil if all the available nodes have been checked but the target hasn't been found.
--]]
-- variables
local openlist = {} -- Initialize table to store possible moves
local closedlist = {} -- Initialize table to store checked gridsquares
local listk = 1 -- List counter
local closedk = 0 -- Closedlist counter
local tempH = math.abs(px - tx) + math.abs(py - ty)
local tempG = 0
openlist[1] = { x = px, y = py, g = 0, h = tempH, f = 0 + tempH, par = 1 } -- Make starting point in list
local xsize = (g_currentMission.terrainSize - 2)/2 -- horizontal map size
local ysize = xsize -- vertical map size
local curbase = {} -- Current square from which to check possible moves
local basis = 1 -- Index of current base
local max_tries = 2000
local max_distance_factor = 10
local air_distance = tempH
-- Growing loop
while listk > 0 do
-- Get the lowest f of the openlist
local lowestF = openlist[listk].f
basis = listk
for k = listk, 1, -1 do
if openlist[k].f < lowestF then
lowestF = openlist[k].f
basis = k
end
end
if closedk >= max_tries then
return nil
end
closedk = closedk + 1
table.insert(closedlist, closedk, openlist[basis])
curbase = closedlist[closedk] -- define current base from which to grow list
--courseplay:debug(string.format("a star check x: %f y %f - closedk: %d", curbase.x, curbase.y, closedk ), 4)
local wOK = true
local eOK = true -- Booleans defining if they're OK to add
local sOK = true -- (must be reset for each while loop)
local nOK = true
local nwOK = true
local seOK = true
local swOK = true
local neOK = true
-- Look through closedlist
if closedk > 0 then
for k = 1, closedk do
if closedlist[k].x == curbase.x + interval and closedlist[k].y == curbase.y then
wOK = false
end
if closedlist[k].x == curbase.x - interval and closedlist[k].y == curbase.y then
eOK = false
end
if closedlist[k].x == curbase.x and closedlist[k].y == curbase.y + interval then
sOK = false
end
if closedlist[k].x == curbase.x and closedlist[k].y == curbase.y - interval then
nOK = false
end
if closedlist[k].x == curbase.x + interval and closedlist[k].y == curbase.y - interval then
nwOK = false
end
if closedlist[k].x == curbase.x - interval and closedlist[k].y == curbase.y - interval then
neOK = false
end
if closedlist[k].x == curbase.x + interval and closedlist[k].y == curbase.y + interval then
swOK = false
end
if closedlist[k].x == curbase.x - interval and closedlist[k].y == curbase.y + interval then
seOK = false
end
end
end
-- Check if next points are on the map and within moving distance
if curbase.x + interval > xsize then
wOK = false
nwOK = false
swOK = false
end
if curbase.x - interval < -xsize then
eOK = false
neOK = false
seOK = false
end
if curbase.y + interval > ysize then
sOK = false
swOK = false
seOK = false
end
if curbase.y - interval < -ysize then
nOK = false
nwOK = false
neOK = false
end
-- If it IS on the map, check map for obstacles
--(Lua returns an error if you try to access a table position that doesn't exist, so you can't combine it with above)
if wOK and curbase.x + interval <= xsize and courseplay:areaHasFruit(curbase.x + interval, curbase.y, fruit_type) then
wOK = false
end
if eOK and curbase.x - interval >= -xsize and courseplay:areaHasFruit(curbase.x - interval, curbase.y, fruit_type) then
eOK = false
end
if sOK and curbase.y + interval <= ysize and courseplay:areaHasFruit(curbase.x, curbase.y + interval, fruit_type) then
sOK = false
end
if nOK and curbase.y - interval >= -ysize and courseplay:areaHasFruit(curbase.x, curbase.y - interval, fruit_type) then
nOK = false
end
-- check if the move from the current base is shorter then from the former parrent
tempG = curbase.g + interval
for k = 1, listk do
if wOK and openlist[k].x == curbase.x + interval and openlist[k].y == curbase.y then
if openlist[k].g > tempG then
--courseplay:debug("right OK 1", 4)
tempH = math.abs((curbase.x + interval) - tx) + math.abs(curbase.y - ty)
table.insert(openlist, k, { x = curbase.x + interval, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk })
end
wOK = false
end
if eOK and openlist[k].x == curbase.x - interval and openlist[k].y == curbase.y then
if openlist[k].g > tempG then
--courseplay:debug("left OK 1", 4)
tempH = math.abs((curbase.x - interval) - tx) + math.abs(curbase.y - ty)
table.insert(openlist, k, { x = curbase.x - interval, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk })
end
eOK = false
end
if sOK and openlist[k].x == curbase.x and openlist[k].y == curbase.y + interval then
if openlist[k].g > tempG then
--courseplay:debug("down OK 1", 4)
tempH = math.abs((curbase.x) - tx) + math.abs(curbase.y + interval - ty)
table.insert(openlist, k, { x = curbase.x, y = curbase.y + interval, g = tempG, h = tempH, f = tempG + tempH, par = closedk })
end
sOK = false
end
if nOK and openlist[k].x == curbase.x and openlist[k].y == curbase.y - interval then
if openlist[k].g > tempG then
--courseplay:debug("up OK 1", 4)
tempH = math.abs((curbase.x) - tx) + math.abs(curbase.y - interval - ty)
table.insert(openlist, k, { x = curbase.x, y = curbase.y - interval, g = tempG, h = tempH, f = tempG + tempH, par = closedk })
end
nOK = false
end
end
-- Add points to openlist
-- Add point to the right of current base point
if wOK then
--courseplay:debug("right OK", 4)
listk = listk + 1
tempH = math.abs((curbase.x + interval) - tx) + math.abs(curbase.y - ty)
table.insert(openlist, listk, { x = curbase.x + interval, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk })
end
-- Add point to the left of current base point
if eOK then
--courseplay:debug("left OK", 4)
listk = listk + 1
tempH = math.abs((curbase.x - interval) - tx) + math.abs(curbase.y - ty)
table.insert(openlist, listk, { x = curbase.x - interval, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk })
end
-- Add point on the top of current base point
if sOK then
--courseplay:debug("down OK", 4)
listk = listk + 1
tempH = math.abs(curbase.x - tx) + math.abs((curbase.y + interval) - ty)
table.insert(openlist, listk, { x = curbase.x, y = curbase.y + interval, g = tempG, h = tempH, f = tempG + tempH, par = closedk })
end
-- Add point on the bottom of current base point
if nOK then
--courseplay:debug("up OK", 4)
listk = listk + 1
tempH = math.abs(curbase.x - tx) + math.abs((curbase.y - interval) - ty)
table.insert(openlist, listk, { x = curbase.x, y = curbase.y - interval, g = tempG, h = tempH, f = tempG + tempH, par = closedk })
end
table.remove(openlist, basis)
listk = listk - 1
if closedlist[closedk].x == tx and closedlist[closedk].y == ty then
return courseplay:calcPath(closedlist)
end
end
return nil
end
function courseplay:calcPath(closedlist)
--print("\tcall calcPath()");
--[[ PRE:
closedlist is a list with the checked nodes.
OR nil if all the available nodes have been checked but the target hasn't been found.
--]]
--[[ POST:
path is a list with all the x and y coords of the nodes of the path to the target.
OR nil if closedlist==nil
--]]
if closedlist == nil then
return nil
end
local path = {}
local pathIndex = {}
local last = #(closedlist)
table.insert(pathIndex, 1, last)
local i = 1
while pathIndex[i] > 1 do
i = i + 1
table.insert(pathIndex, i, closedlist[pathIndex[i - 1]].par)
end
for n = #(pathIndex), 1, -1 do
table.insert(path, { x = closedlist[pathIndex[n]].x, y = closedlist[pathIndex[n]].y })
end
closedlist = nil
return path
end