ID:1666799   Aug 26 2014, 9:24 am (Edited on Aug 28 2014, 12:09 pm) This is a quick snippet demonstrating a fairly useful pathfinding algorithm. This pathfinding algorithm searches from both ends, resulting in much more ideal pathfinding times than standard A*. It doesn't find the most ideal path, it merely finds the first path, so some quirkiness is to be expected. 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.414213world New() ..() node_clear_loop()var __investigated_nodes = 0 __max_investigated_nodes = 1200 __pending_pathfinding = 0proc 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 = 0pathfinder 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_waitpath 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.
 <-> Aug 26 2014, 7:54 pm ANOTHER GARBAGE POST. sorry was on facebook. Simply Devine copy paste this i shall. I suppose this is for your laziness of the past two sunday's or three?
 <-> Aug 27 2014, 3:26 am I suppose this is for your laziness of the past two sunday's or three? Leave.
 <-> Aug 27 2014, 6:03 am In response to LILMESSI18 I haven't even been here in a while, but damn. That was rude. I'm just glad to see Ter is still helping out this unappreciative community.
 <-> Aug 27 2014, 6:04 am Ter13 BTFO
 <-> Aug 27 2014, 1:52 pm In response to Ter13 Ter13 wrote: I suppose this is for your laziness of the past two sunday's or three? Leave. I think he was trying to be funny, but failed o:
 <-> Aug 28 2014, 12:10 pm I've updated the pathfinder to have two new options. One is cross_corners, which will prevent mobs from passing through diagonal spaces on which one or more adjacent 45 degree component is blocked, and orthogonal, which allows you to do only 4-directional pathfinding instead of 8-directional.
 <-> Aug 29 2014, 4:14 am You sir, are a genius! Keep up the good work :)
 <-> Aug 30 2014, 12:45 am It was actually sarcasm but you know people on byond be having stick's in weird places. considering im an avid follower i don't get why he hates on me.
 <-> Sep 7 2014, 11:12 am Good job, as always Ter.