**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?