-
-
Notifications
You must be signed in to change notification settings - Fork 452
/
AStar.dm
240 lines (210 loc) · 8.99 KB
/
AStar.dm
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
/*
A Star pathfinding algorithm
Returns a list of tiles forming a path from A to B, taking dense objects as well as walls, and the orientation of
windows along the route into account.
Use:
your_list = AStar(start location, end location, moving atom, distance proc, max nodes, maximum node depth, minimum distance to target, adjacent proc, atom id, turfs to exclude, check only simulated)
Optional extras to add on (in order):
Distance proc : the distance used in every A* calculation (length of path and heuristic)
MaxNodes: The maximum number of nodes the returned path can be (0 = infinite)
Maxnodedepth: The maximum number of nodes to search (default: 30, 0 = infinite)
Mintargetdist: Minimum distance to the target before path returns, could be used to get
near a target, but not right to it - for an AI mob with a gun, for example.
Adjacent proc : returns the turfs to consider around the actually processed node
Simulated only : whether to consider unsimulated turfs or not (used by some Adjacent proc)
Also added 'exclude' turf to avoid travelling over; defaults to null
Actual Adjacent procs :
/turf/proc/reachableAdjacentTurfs : returns reachable turfs in cardinal directions (uses simulated_only)
/turf/proc/reachableAdjacentAtmosTurfs : returns turfs in cardinal directions reachable via atmos
*/
#define PF_TIEBREAKER 0.005
//tiebreker weight.To help to choose between equal paths
//////////////////////
//datum/PathNode object
//////////////////////
#define MASK_ODD 85
#define MASK_EVEN 170
//A* nodes variables
/datum/PathNode
var/turf/source //turf associated with the PathNode
var/datum/PathNode/prevNode //link to the parent PathNode
var/f //A* Node weight (f = g + h)
var/g //A* movement cost variable
var/h //A* heuristic variable
var/nt //count the number of Nodes traversed
var/bf //bitflag for dir to expand.Some sufficiently advanced motherfuckery
/datum/PathNode/New(s,p,pg,ph,pnt,_bf)
source = s
prevNode = p
g = pg
h = ph
f = g + h*(1+ PF_TIEBREAKER)
nt = pnt
bf = _bf
/datum/PathNode/proc/setp(p,pg,ph,pnt)
prevNode = p
g = pg
h = ph
f = g + h*(1+ PF_TIEBREAKER)
nt = pnt
/datum/PathNode/proc/calc_f()
f = g + h
//////////////////////
//A* procs
//////////////////////
//the weighting function, used in the A* algorithm
/proc/PathWeightCompare(datum/PathNode/a, datum/PathNode/b)
return a.f - b.f
//reversed so that the Heap is a MinHeap rather than a MaxHeap
/proc/HeapPathWeightCompare(datum/PathNode/a, datum/PathNode/b)
return b.f - a.f
//wrapper that returns an empty list if A* failed to find a path
/proc/get_path_to(caller, end, dist, maxnodes, maxnodedepth = 30, mintargetdist, adjacent = /turf/proc/reachableTurftest, id=null, turf/exclude=null, simulated_only = TRUE, get_best_attempt = FALSE)
var/l = SSpathfinder.mobs.getfree(caller)
while(!l)
stoplag(3)
l = SSpathfinder.mobs.getfree(caller)
var/list/path = AStar(caller, end, dist, maxnodes, maxnodedepth, mintargetdist, adjacent,id, exclude, simulated_only, get_best_attempt)
SSpathfinder.mobs.found(l)
if(!path)
path = list()
return path
/proc/cir_get_path_to(caller, end, dist, maxnodes, maxnodedepth = 30, mintargetdist, adjacent = /turf/proc/reachableTurftest, id=null, turf/exclude=null, simulated_only = TRUE)
var/l = SSpathfinder.circuits.getfree(caller)
while(!l)
stoplag(3)
l = SSpathfinder.circuits.getfree(caller)
var/list/path = AStar(caller, end, dist, maxnodes, maxnodedepth, mintargetdist, adjacent,id, exclude, simulated_only)
SSpathfinder.circuits.found(l)
if(!path)
path = list()
return path
/// Pathfinding for bots
/proc/AStar(caller, _end, dist, maxnodes, maxnodedepth = 30, mintargetdist, adjacent = /turf/proc/reachableTurftest, id=null, turf/exclude=null, simulated_only = TRUE, get_best_attempt = FALSE)
//sanitation
var/turf/end = get_turf(_end)
var/turf/start = get_turf(caller)
if(!start || !end)
stack_trace("Invalid A* start or destination")
return FALSE
if( start.z != end.z || start == end ) //no pathfinding between z levels
return FALSE
if(maxnodes)
//if start turf is farther than maxnodes from end turf, no need to do anything
if(call(start, dist)(end) > maxnodes)
return FALSE
maxnodedepth = maxnodes //no need to consider path longer than maxnodes
var/datum/Heap/open = new /datum/Heap(/proc/HeapPathWeightCompare) //the open list
var/list/openc = new() //open list for node check
var/list/path = null //the returned path, if any
//initialization
var/datum/PathNode/cur = new /datum/PathNode(start,null,0,call(start,dist)(end),0,15,1)//current processed turf
open.Insert(cur)
openc[start] = cur
//then run the main loop
while(!open.IsEmpty() && !path)
cur = open.Pop() //get the lower f turf in the open list
//get the lower f node on the open list
//if we only want to get near the target, check if we're close enough
var/closeenough
if(mintargetdist)
closeenough = call(cur.source,dist)(end) <= mintargetdist
//found the target turf (or close enough), let's create the path to it
if(cur.source == end || closeenough)
path = new()
path.Add(cur.source)
while(cur.prevNode)
cur = cur.prevNode
path.Add(cur.source)
break
//get adjacents turfs using the adjacent proc, checking for access with id
if((!maxnodedepth)||(cur.nt <= maxnodedepth))//if too many steps, don't process that path
for(var/i = 0 to 3)
var/f= 1<<i //get cardinal directions.1,2,4,8
if(cur.bf & f)
var/T = get_step(cur.source,f)
if(T != exclude)
var/datum/PathNode/CN = openc[T] //current checking turf
var/r=((f & MASK_ODD)<<1)|((f & MASK_EVEN)>>1) //getting reverse direction throught swapping even and odd bits.((f & 01010101)<<1)|((f & 10101010)>>1)
var/newg = cur.g + call(cur.source,dist)(T)
if(CN)
//is already in open list, check if it's a better way from the current turf
CN.bf &= 15^r //we have no closed, so just cut off exceed dir.00001111 ^ reverse_dir.We don't need to expand to checked turf.
if((newg < CN.g) )
if(call(cur.source,adjacent)(caller, T, id, simulated_only))
CN.setp(cur,newg,CN.h,cur.nt+1)
open.ReSort(CN)//reorder the changed element in the list
else
//is not already in open list, so add it
if(call(cur.source,adjacent)(caller, T, id, simulated_only))
CN = new(T,cur,newg,call(T,dist)(end),cur.nt+1,15^r)
open.Insert(CN)
openc[T] = CN
cur.bf = 0
CHECK_TICK
// if(!path && get_best_attempt)
// path = new()
// path.Add(cur.source)
// while(cur.prevNode)
// cur = cur.prevNode
// path.Add(cur.source)
//reverse the path to get it from start to finish
if(path)
for(var/i = 1 to round(0.5*path.len))
path.Swap(i,path.len-i+1)
openc = null
//cleaning after us
return path
//Returns adjacent turfs in cardinal directions that are reachable
//simulated_only controls whether only simulated turfs are considered or not
/// Returns a list the src/caller can cross into
/turf/proc/reachableAdjacentTurfs(caller, ID, simulated_only)
var/list/L = new()
var/turf/T
var/static/space_type_cache = typecacheof(/turf/open/space)
for(var/k in 1 to GLOB.cardinals.len)
T = get_step(src,GLOB.cardinals[k])
if(!T || (simulated_only && space_type_cache[T.type]))
continue
if(!T.density && !LinkBlockedWithAccess(T,caller, ID))
L.Add(T)
return L
/turf/proc/reachableTurftest(caller, turf/T, ID, simulated_only)
if(T && !T.density && !(simulated_only && SSpathfinder.space_type_cache[T.type]) && !LinkBlockedWithAccess(T,caller, ID))
return TRUE
/// Returns adjacent turfs in cardinal directions that are reachable via atmos
/turf/proc/reachableAdjacentAtmosTurfs()
return atmos_adjacent_turfs
/// Check if there is a door that needs access in its way
/turf/proc/LinkBlockedWithAccess(turf/T, caller, ID)
var/adir = get_dir(src, T)
var/rdir = ((adir & MASK_ODD)<<1)|((adir & MASK_EVEN)>>1)
for(var/obj/structure/window/W in src)
if(!W.CanAStarPass(ID, adir))
return TRUE
for(var/obj/machinery/door/window/W in src)
if(!W.CanAStarPass(ID, adir))
return TRUE
for(var/obj/machinery/M in src)
if(!M.CanAStarPass(ID, adir, caller))
return TRUE
for(var/obj/machinery/door/firedoor/border_only/W in src)
if(!W.CanAStarPass(ID, adir, caller))
return TRUE
for(var/obj/O in T)
if(!O.CanAStarPass(ID, rdir, caller))
return TRUE
return FALSE
//yog procs
/turf/proc/reachableTurftestPlayer(caller, turf/T, ID, simulated_only)
if(T && !T.density && !LinkBlockedWithAccess(T, caller, ID) && !(simulated_only && SSpathfinder.space_type_cache[T.type]))
return TRUE
/turf/proc/reachableTurftestdensity(caller, turf/T, ID, simulated_only) //used for the sake of pathfinding while excluding turfs with dense objects
if(T && !T.density && !(simulated_only && SSpathfinder.space_type_cache[T.type]) && !LinkBlockedWithAccess(T,caller, ID))
for(var/obj/D in T)
if(!istype(D, /obj/structure/window) && D.density) //had to do it silly like this so rwindows didn't stop it outright
return FALSE
return TRUE
/turf/proc/wiringTurfTest(caller, turf/T, ID, simulated_only)
if(T && !T.density && !istype(T.loc, /area/space))
return TRUE