This snippet requires ter13.prioritylist to work. Make sure you plug that snippet into your game before you attempt to implement this pathfinder.
#define SQRT2 1.414213
world
New()
..()
node_clear_loop()
var
__investigated_nodes = 0
__max_investigated_nodes = 1200
__pending_pathfinding = 0
proc
waitfor_nodes()
if(!__pending_pathfinding)
__pending_pathfinding = 1
sleep(TICK_LAG)
__pending_pathfinding = 0
else
sleep(TICK_LAG)
node_clear_loop()
set waitfor = 0
while(1)
sleep(TICK_LAG)
__investigated_nodes = 0
pathfinder
var/tmp
//These are all instance variables rather than local variables to give us a tiny speed boost for little effort.
__count
__maxcount
__dir //stores the direction of the neighbor node
__dir1
__dir2
turf/__t //stores the neighbor node
turf/__curpos //stores the current node
list/__visited1 = list() //the turfs that we have investigated from startpoint
list/__visited2 = list() //the turfs we have investigated from endpoint
prioritylist/__pending1 = new() //a sorted list of turfs we need to investigate
prioritylist/__pending2 = new() //a sorted list of turfs we need to investigate
list/__pathend = list() //a map identifying which turfs each end has touched
list/__closed = list() //a map of turfs identifying which turfs we've attempted to step through
__og //heuristic storage
__ng //heuristic storage
list/__g = list() //a map of turfs by g heuristic
list/__dirs = list(NORTH,EAST,SOUTH,WEST,NORTHEAST,SOUTHEAST,SOUTHWEST,NORTHWEST) //reference list of directions in order of investigation
list/__dir_success = list(0,0,null,0,0,0,null,0,0,0) //list of successful movements
max_dist = 0
node_wait = 0
cross_corners = 0
orthogonal = 0
proc
//get_path attempts to locate a path from one point to another via ref.
//returns a /path datum on success and null on failure
get_path(atom/movable/ref,turf/startpos,turf/endpos)
//initialize the pending, pathend, visited, and g heuristic lists
__pending1.Add(startpos,0)
__pending2.Add(endpos,0)
__visited1[startpos] = 1
__visited2[endpos] = 1
__g[startpos] = 0
__g[endpos] = 0
__pathend[startpos] = 1
__pathend[endpos] = 2
if(orthogonal)
__maxcount = 4
else
__maxcount = 8
//while there are nodes to investigate
while(__pending1.len && __pending2.len)
//get the top item in the start list
__curpos = __pending1.values[1]
__pending1.Cut(1,2)
//close the node
__closed[__curpos] = 1
//for each direction in the 8 directions:
for(__count=1;__count<=__maxcount;__count++)
__dir = __dirs[__count]
//get the neighbor in direction
__t = get_step(__curpos,__dir)
//if it's closed, don't bother checking the turf
if(__closed[__t])
continue
//if it's outside the maximum distance, don't check either
if(max_dist && get_dist(__t,startpos) > max_dist)
continue
//if the turf exists
if(__t)
//keep track of whether we can move into the turf
__dir_success[__dir] = __curpos.Exit(ref,__t,1) && __t.Enter(ref,__curpos,1)
//if we were successful
if(__dir_success[__dir])
//check whether we can cross corners
if(!cross_corners)
//check if we are currently moving diagonally
__dir1 = __dir&__dir-1
if(__dir1)
//get the component directions of the diagonal move
__dir2 = __dir ^ __dir1
//if we can't move through both tiles from the components, fail the diagonal.
if(!(__dir_success[__dir1] && __dir_success[__dir2]))
continue
__investigated_nodes++
//if we're meeting the other end of the pathfinder
if(__pathend[__t]==2)
//construct the path and return it
return build_path(__curpos,__t)
//apply the g heuristic based on added distance from last node
__og = __g[__t]
__ng = __og + ((__t.x - __curpos.x == 0 || __t.y - __curpos.y == 0) ? 1 : SQRT2)
//if we haven't visited this turf before
if(!__visited1[__t])
//set the g heuristic
__g[__t] = __ng
//apply the visited map
__visited1[__t] = __curpos
//set the path's end to start
__pathend[__t] = 1
//add the turf to the prioritylist according to the final heuristic
__pending1.Add(__t,__ng + (abs(__t.x - endpos.x) + abs(__t.y - endpos.y))) //Manhattan heuristic
//otherwise, if the pathing cost is less than the old cost
else if(__ng <= __og)
//update the g heuristic
__g[__t] = __ng
//apply the visited map
__visited1[__t] = __curpos
__pending1.Remove(__t)
//reset the position in the prioritylist according to the new heuristic
__pending1.Add(__t,__ng + (abs(__t.x - endpos.x) + abs(__t.y - endpos.y))) //Manhattan heuristic
//do the same for the opposite side of the path, only reversed
__curpos = __pending2.values[1]
__pending2.Cut(1,2)
__closed[__curpos] = 1
for(__count=1;__count<=__maxcount;__count++)
__dir = __dirs[__count]
__t = get_step(__curpos,__dir)
if(__closed[__t])
continue
if(max_dist && get_dist(__t,endpos) > max_dist)
continue
if(__t)
__dir_success[__dir] = __curpos.Exit(ref,__t,1) && __t.Enter(ref,__curpos,1)
if(__dir_success[__dir])
if(!cross_corners)
__dir1 = __dir&__dir-1
if(__dir1)
__dir2 = __dir ^ __dir1
if(!(__dir_success[__dir1] && __dir_success[__dir2]))
continue
__investigated_nodes++
if(__pathend[__t]==1)
return build_path(__t,__curpos)
__og = __g[__t]
__ng = __og + ((__t.x - __curpos.x == 0 || __t.y - __curpos.y == 0) ? 1 : SQRT2)
if(!__visited2[__t])
__g[__t] = __ng
__visited2[__t] = __curpos
__pathend[__t] = 2
__pending2.Add(__t,__ng + (abs(__t.x - startpos.x) + abs(__t.y - startpos.y))) //Manhattan heuristic
else if(__ng <= __og)
__g[__t] = __ng
__visited2[__t] = __curpos
__pending2.Remove(__t)
__pending2.Add(__t,__ng + (abs(__t.x - startpos.x) + abs(__t.y - startpos.y))) //Manhattan heuristic
if(node_wait && __investigated_nodes > __max_investigated_nodes)
waitfor_nodes()
return null
//this constructs a path from the data in this pathfinder.
//it returns a path datum with the turfs in sequential order
build_path(turf/pos1,turf/pos2)
var/path/p = new/path()
//go through the visited list to uncover the linked nodes in reverse order
while(pos1!=1)
p.turfs.Insert(1,pos1)
pos1 = __visited1[pos1]
//go through the visited list to uncover the linked nodes in forward order
while(pos2!=1)
p.turfs += pos2
pos2 = __visited2[pos2]
return p
Clear()
__visited1 = list()
__visited2 = list()
__pending1.Cut(1,0)
__pending2.Cut(1,0)
__g = list()
__closed = list()
__pathend = list()
__t = null
__curpos = null
//max_dist is the maximum distance this pathfinder will attempt to search before failing out.
//orthogonal is whether this pathfinder will not move diagonally
//cross_corners is used for non-orthogonal pathfinders, it will prevent crossing occupied corners.
//node_wait is whether this pathfinder will wait for heavy duty pathfinders to finish their work before continuing
New(max_dist=0,orthogonal=0,cross_corners=0,node_wait=0)
src.max_dist = max_dist
src.orthogonal = orthogonal
src.cross_corners = cross_corners
src.node_wait = node_wait
path
var
list/turfs = list()
proc
//this function will walk a player along the path until it reaches an obstacle.
//it will return 1 if successful, or 0 if failed.
Walk(atom/movable/ref,delay)
var/pos = 1
while(++pos < turfs.len)
. = ref.Move(turfs[pos],get_dir(turfs[pos-1],turfs[pos]))
if(!.)
return .
sleep(delay)
return ref.Move(turfs[turfs.len],get_dir(turfs[turfs.len-1],turfs[turfs.len]))
turf
Enter(atom/movable/O,atom/fromloc=null,pathing=0)
return ..()
Exit(atom/movable/O,atom/toloc=null,pathing=0)
return ..()
A few points about this algorithm. This algorithm is a lot slower than other variants of A* you will find on the hub. The reason for this, is I decided to sacrifice speed for the sake of accurate Enter()/Exit() behavior.
Be aware of this limitation when you use this. This algorithm is plenty fast enough for short-range pathfinding, but for longer range pathfinding it'll start to slow down. If people are interested, PM me, and I'll show you a variant of this code that allows a pathfinding operation to take multiple frames, which should allow for longer-range pathfinding operations.
I did some tests with relatively long-range pathfinding and decided to optimize this function a little bit. Notably, I dropped support for collisiontesting, and opted instead to simply use Enter()/Exit() per D4rK3's suggestion.
Ultimately, I came up with average seek times of about 7ms through fairly complex terrain and a medium distance, so I am going to call this one fairly quick.
Simply Devine copy paste this i shall.
I suppose this is for your laziness of the past two sunday's or three?