mirror of
https://github.com/goonstation/goonstation-2020.git
synced 2026-07-10 22:52:21 +01:00
Stephen
036a29b765
includes a lot of small things + fixes. big ones are Simple Lights, New Grab stuff, Disorient Eye/Ear protection armor values, access reprogrammer and deconstruction device also added flabo to the list of contributors, we missed her on the first go! check changelog for full list, i merged that too
351 lines
8.8 KiB
Plaintext
351 lines
8.8 KiB
Plaintext
/proc/AStar(start, end, adjacent, heuristic, maxtraverse = 30, adjacent_param = null, exclude = null)
|
|
var/list/open = list(start), list/nodeG = list(), list/nodeParent = list(), P = 0
|
|
while (P++ < open.len)
|
|
var/T = open[P], TG = nodeG[T]
|
|
if (T == end)
|
|
var/list/R = list()
|
|
while (T)
|
|
R.Insert(1, T)
|
|
T = nodeParent[T]
|
|
return R
|
|
var/list/other = call(T, adjacent)(adjacent_param)
|
|
for (var/next in other)
|
|
if (open.Find(next) || next == exclude) continue
|
|
var/G = TG + other[next], F = G + call(next, heuristic)(end)
|
|
for (var/i = P; i <= open.len;)
|
|
if (i++ == open.len || open[open[i]] >= F)
|
|
open.Insert(i, next)
|
|
open[next] = F
|
|
break
|
|
nodeG[next] = G
|
|
nodeParent[next] = T
|
|
|
|
if (P > maxtraverse)
|
|
return
|
|
|
|
|
|
//#define DEBUG_ASTAR
|
|
|
|
/proc/cirrAstar(turf/start, turf/goal, var/min_dist=0, proc/adjacent, proc/heuristic, maxtraverse = 30, adjacent_param = null, exclude = null)
|
|
#ifdef DEBUG_ASTAR
|
|
clearAstarViz()
|
|
#endif
|
|
|
|
var/list/closedSet = list()
|
|
var/list/openSet = list(start)
|
|
var/list/cameFrom = list()
|
|
|
|
var/list/gScore = list()
|
|
var/list/fScore = list()
|
|
gScore[start] = 0
|
|
fScore[start] = heuristic(start, goal)
|
|
var/traverse = 0
|
|
|
|
while(openSet.len > 0)
|
|
var/current = pickLowest(openSet, fScore)
|
|
if(distance(current, goal) <= min_dist)
|
|
return reconstructPath(cameFrom, current)
|
|
|
|
openSet -= current
|
|
closedSet += current
|
|
var/list/neighbors = getNeighbors(current, alldirs)
|
|
for(var/neighbor in neighbors)
|
|
if(neighbor in closedSet)
|
|
continue // already checked this one
|
|
var/tentativeGScore = gScore[current] + distance(current, neighbor)
|
|
if(!(neighbor in openSet))
|
|
openSet += neighbor
|
|
else if(tentativeGScore >= (gScore[neighbor] || 1.#INF))
|
|
continue // this is not a better route to this node
|
|
|
|
cameFrom[neighbor] = current
|
|
gScore[neighbor] = tentativeGScore
|
|
fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, goal)
|
|
traverse += 1
|
|
if(traverse > maxtraverse)
|
|
return null // it's taking too long, abandon
|
|
LAGCHECK(LAG_LOW)
|
|
return null // if we reach this part, there's no more nodes left to explore
|
|
|
|
|
|
|
|
/proc/heuristic(turf/start, turf/goal)
|
|
if(!start || !goal)
|
|
return null // yes, null, not a number, i need to track down why nulls are being passed in as turfs so i'm throwing this up the stack
|
|
// let's just do manhattan for now
|
|
return abs(start.x - goal.x) + abs(start.y - goal.y)
|
|
|
|
/proc/distance(turf/start, turf/goal)
|
|
if(!start || !goal)
|
|
return null
|
|
var/dx = goal.x - start.x
|
|
var/dy = goal.y - start.y
|
|
return sqrt(dx*dx + dy*dy)
|
|
|
|
/proc/pickLowest(list/options, list/values)
|
|
if(options.len == 0)
|
|
return null // you idiot
|
|
var/lowestScore = 1.#INF
|
|
for(var/option in options)
|
|
if(option in values)
|
|
var/score = values[option]
|
|
if(score < lowestScore)
|
|
lowestScore = score
|
|
. = option
|
|
else
|
|
continue // if we have no score for an option, ignore it
|
|
|
|
/proc/reconstructPath(list/cameFrom, turf/current)
|
|
var/list/totalPath = list(current)
|
|
while(current in cameFrom)
|
|
current = cameFrom[current]
|
|
totalPath += current
|
|
// reverse the path
|
|
. = list()
|
|
for(var/i = totalPath.len to 1 step -1)
|
|
. += totalPath[i]
|
|
#ifdef DEBUG_ASTAR
|
|
addAstarViz(.)
|
|
#endif
|
|
return .
|
|
|
|
/proc/getNeighbors(turf/current, list/directions)
|
|
. = list()
|
|
// handle cardinals straightforwardly
|
|
var/list/cardinalTurfs = list()
|
|
for(var/direction in cardinal)
|
|
if(direction in directions)
|
|
var/turf/T = get_step(current, direction)
|
|
cardinalTurfs["[direction]"] = 0 // can't pass
|
|
if(T && checkTurfPassable(T))
|
|
. += T
|
|
cardinalTurfs["[direction]"] = 1 // can pass
|
|
//diagonals need to avoid the leaking problem
|
|
for(var/direction in ordinal)
|
|
if(direction in directions)
|
|
var/turf/T = get_step(current, direction)
|
|
if(T && checkTurfPassable(T))
|
|
// check relevant cardinals
|
|
var/clear = 1
|
|
for(var/cardinal in cardinal)
|
|
if(direction & cardinal)
|
|
// this used to check each cardinal turf again but that's completely unnecessary
|
|
if(!cardinalTurfs["[direction]"])
|
|
clear = 0
|
|
if(clear)
|
|
. += T
|
|
|
|
// shamelessly stolen from further down and modified
|
|
/proc/checkTurfPassable(turf/T)
|
|
if(!T)
|
|
return 0 // can't go on a turf that doesn't exist!!
|
|
if(T.density) // simplest case
|
|
return 0
|
|
for(var/atom/O in T.contents)
|
|
if (O.density) // && !(O.flags & ON_BORDER)) -- fuck you, windows, you're dead to me
|
|
if (istype(O, /obj/machinery/door))
|
|
var/obj/machinery/door/D = O
|
|
if (D.isblocked())
|
|
return 0 // a blocked door is a blocking door
|
|
if (ismob(O))
|
|
var/mob/M = O
|
|
if (M.anchored)
|
|
return 0 // an anchored mob is a blocking mob
|
|
else
|
|
return 0 // not a special case, so this is a blocking object
|
|
return 1
|
|
|
|
|
|
|
|
#ifdef DEBUG_ASTAR
|
|
/var/static/list/astarImages = list()
|
|
/proc/clearAstarViz()
|
|
for(var/client/C in clients)
|
|
C.images -= astarImages
|
|
astarImages = list()
|
|
|
|
/proc/addAstarViz(var/list/path)
|
|
astarImages = list()
|
|
for(var/turf/T in path)
|
|
var/image/marker = image('icons/mob/screen1.dmi', T, icon_state="x3")
|
|
marker.color="#0F8"
|
|
astarImages += marker
|
|
for(var/client/C in clients)
|
|
C.images += astarImages
|
|
#endif
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/******************************************************************/
|
|
// Navigation procs
|
|
// Used for A-star pathfinding
|
|
|
|
// Returns the surrounding cardinal turfs with open links
|
|
// Including through doors openable with the ID
|
|
/turf/proc/CardinalTurfsWithAccess(var/obj/item/card/id/ID)
|
|
var/L[] = new()
|
|
|
|
// for(var/turf/simulated/t in oview(src,1))
|
|
|
|
for(var/d in cardinal)
|
|
var/turf/simulated/T = get_step(src, d)
|
|
//if(istype(T) && !T.density)
|
|
if (T && T.pathable && !T.density)
|
|
if(!LinkBlockedWithAccess(src, T, ID))
|
|
L.Add(T)
|
|
return L
|
|
/turf/proc/AllDirsTurfsWithAccess(var/obj/item/card/id/ID)
|
|
var/L[] = new()
|
|
|
|
// for(var/turf/simulated/t in oview(src,1))
|
|
|
|
for(var/d in alldirs)
|
|
var/turf/simulated/T = get_step(src, d)
|
|
//if(istype(T) && !T.density)
|
|
if (T && T.pathable && !T.density)
|
|
if(!LinkBlockedWithAccess(src, T, ID))
|
|
L.Add(T)
|
|
return L
|
|
|
|
|
|
/turf/proc/CardinalTurfsSpace()
|
|
var/L[] = new()
|
|
|
|
for (var/d in cardinal)
|
|
var/turf/T = get_step(src, d)
|
|
if (T && (T.pathable || istype(T, /turf/space)) && !T.density)
|
|
if (!LinkBlockedWithAccess(src, T))
|
|
L.Add(T)
|
|
|
|
return L
|
|
|
|
// Returns true if a link between A and B is blocked
|
|
// Movement through doors allowed if ID has access
|
|
/proc/LinkBlockedWithAccess(turf/A, turf/B, obj/item/card/id/ID)
|
|
|
|
if(A == null || B == null) return 1
|
|
var/adir = get_dir(A,B)
|
|
var/rdir = get_dir(B,A)
|
|
if((adir & (NORTH|SOUTH)) && (adir & (EAST|WEST))) // diagonal
|
|
var/iStep = get_step(A,adir&(NORTH|SOUTH))
|
|
if(!LinkBlockedWithAccess(A,iStep, ID) && !LinkBlockedWithAccess(iStep,B,ID))
|
|
return 0
|
|
|
|
var/pStep = get_step(A,adir&(EAST|WEST))
|
|
if(!LinkBlockedWithAccess(A,pStep,ID) && !LinkBlockedWithAccess(pStep,B,ID))
|
|
return 0
|
|
return 1
|
|
|
|
if(!DirWalkableWithAccess(A,adir, ID, exiting_this_tile = 1))
|
|
return 1
|
|
|
|
var/DirWalkableB = DirWalkableWithAccess(B,rdir, ID)
|
|
if(!DirWalkableB)
|
|
return 1
|
|
|
|
if (DirWalkableB == 2) //we found a door we can open! Let's open the door before we check the whole tile for dense objects below.
|
|
return 0
|
|
|
|
for (var/atom/O in B.contents)
|
|
if (O.density)
|
|
if (ismob(O))
|
|
var/mob/M = O
|
|
if (M.anchored)
|
|
return 1
|
|
return 0
|
|
|
|
if (O.flags & ON_BORDER)
|
|
if (rdir == O.dir)
|
|
return 1
|
|
else
|
|
return 1
|
|
|
|
return 0
|
|
|
|
// Returns true if direction is accessible from loc
|
|
// If we found a door we could open, return 2 instead of 1.
|
|
// Checks doors against access with given ID
|
|
/proc/DirWalkableWithAccess(turf/loc,var/dir,var/obj/item/card/id/ID, var/exiting_this_tile = 0)
|
|
.= 1
|
|
|
|
for (var/atom in loc)
|
|
if (!isobj(atom)) continue
|
|
var/obj/D = atom
|
|
|
|
if (D.density)
|
|
if (D.object_flags & BOTS_DIRBLOCK)
|
|
if (D.flags & ON_BORDER && dir == D.dir)//windoors and directional windows
|
|
if (D.has_access_requirements())
|
|
if (D.check_access(ID) == 0)
|
|
return 0
|
|
else
|
|
return 2
|
|
else
|
|
return 2
|
|
else if (!exiting_this_tile) //other solid objects. dont bother checking if we are EXITING this tile
|
|
if (D.has_access_requirements())
|
|
if (D.check_access(ID) == 0)
|
|
return 0
|
|
else
|
|
return 2
|
|
else
|
|
return 2
|
|
else
|
|
if (D.flags & ON_BORDER)
|
|
if (dir == D.dir)
|
|
return 0
|
|
else if (!exiting_this_tile) //dont bother checking if we are EXITING this tile
|
|
return 0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/turf/proc
|
|
AdjacentTurfs()
|
|
var/L[] = new()
|
|
for(var/turf/simulated/t in oview(src,1))
|
|
if(!t.density)
|
|
if(!LinkBlocked(src, t) && !TurfBlockedNonWindow(t))
|
|
L.Add(t)
|
|
return L
|
|
Distance(turf/t)
|
|
if(get_dist(src,t) == 1)
|
|
var/cost = (src.x - t.x) * (src.x - t.x) + (src.y - t.y) * (src.y - t.y)
|
|
cost *= (pathweight+t.pathweight)/2
|
|
return cost
|
|
else
|
|
return get_dist(src,t)
|
|
AdjacentTurfsSpace()
|
|
var/L[] = new()
|
|
for(var/turf/t in oview(src,1))
|
|
if(!t.density)
|
|
if(!LinkBlocked(src, t) && !TurfBlockedNonWindow(t))
|
|
L.Add(t)
|
|
return L
|
|
|
|
|