So, the code works okay, but it seems almost... Too simple, compared to any libraries that do the same thing? I'm trying to make it as modular as possible so that I can reuse the code for a few types of pathing I will be doing, but I feel like I'm locking myself into too many things.
Anyone mind looking over the code and seeing if anything jumps out at you as being inefficient or too "Brute-force"?
Main Code:
proc/GetPathTo(atom/A,atom/B,mode="O") // A = Start of path, B == End of path, mode is either "C"ardinal or "O"rdinal, depending if diagonals are allowed
set background=1
var
list
Final[0] // List to return
Open[0] // List of unvisited but scored nodes
Closed[0] // List of visited nodes
turf/Start = locate(A.x,A.y,A.z) //In case pathing from/to a mob or obj, get the loc
turf/End = locate(B.x,B.y,B.z) // ""
//Initialize//
Start.H = HCalc(Start,End,mode) // Calculate the heuristic distance of the first node
Start.F = Start.H+Start.G // Calculate the score of the first node
Open += Start // Add first node to Open List
//Main Loop//
while(Open.len) // While there are scored but unvisited nodes,
var/turf/Q = LowNode(Open) // Find the node with the lowest score and "Visit" it
Open -= Q // Move it from the Open list to the Closed list
Closed += Q
if(Q == End) // If it is the destination,
Final += Q // Add it to the Final list
break // And break the loop
var/list/ADJ = GetADJ(Q,mode) //Otherwise, get a list of adjacent nodes
//Child Loop//
for(var/turf/Child in ADJ-Closed) // Check each of them that haven't been visited
Open |= Child // If it isn't in the Open list already, add it.
var
temp_G = GCalc(Child,Q,mode) // Estimate the cost to move here
temp_F = temp_G + HCalc(Child,End,mode) //Estimate the final score
if(!Child.F || Child.F > temp_F) // If there isn't already a cheaper way to get there,
Child.P = Q // set Q as the parent,
Child.dir = get_dir(Q,Child)
Child.G = temp_G
Child.F = temp_F //and finilize cost/scores
//Move on to the next node in Open
//Finalizeation//
Closed |= Open // Add all nodes to Closed (For cleanup purposes)
while(Final[1] != Start) //Trace the path back from the End node by parents
var/turf/F = Final[1]
Final.Insert(1,F.P)
for(var/turf/T in Closed) // Clean up turf scores
ClearScore(T)
return Final // Return the final path
Additional Code:
//Math/Helper functions;
proc/HCalc(turf/A,turf/B,mode) // Calculate H
switch(mode) //Cardinal or Ordinal
if("C") // No diagnonals
return max(A.x-B.x , A.y-B.y)
if("O") // Including Diagonals
return (A.x-B.x) + (A.y-B.y)
proc/GCalc(turf/A,turf/P,mode) // Calculate G
var/malus // Aditional costs to move
if(abs(A.x-P.x)==abs(A.y-P.y)) malus += 0.414 // Diagonals are more expensive
if(get_dir(P,A) != P.dir) malus += 0.25 // Turning is a little more expensive
return P.G + A.cost + malus
proc/LowNode(list/Open) // Get lowest cost node from Open
var/turf/Q // Current lowest score
for(var/turf/N in Open)
if(!Q || N.F <= Q.F) // If first checked, or if lower-score than the current Q,
Q = N // Set as Q
return Q
//Just a function to get adjacent nodes, I haven't yet gotten to making a grid-agnostic version of this, but ideally I'd like to be able to use a similar function for an overarching "room" grid of nodes.
proc/GetADJ(turf/T,mode = "O")
if(!T.ADJ_O.len)
var/turf/north = locate(T.x, T.y+1, T.z)
var/turf/west = locate(T.x-1, T.y, T.z)
var/turf/east = locate(T.x+1, T.y, T.z)
var/turf/south = locate(T.x, T.y-1, T.z)
if (north) T.ADJ_O += north
if (west) T.ADJ_O += west
if (east) T.ADJ_O += east
if (south) T.ADJ_O += south
if(mode == "C")
return T.ADJ_O.Copy()
if(mode == "O" && !T.ADJ_D.len)
var/turf/northwest = locate(T.x-1, T.y+1, T.z)
var/turf/northeast = locate(T.x+1, T.y+1, T.z)
var/turf/southwest = locate(T.x-1, T.y-1, T.z)
var/turf/southeast = locate(T.x+1, T.y-1, T.z)
if (northwest) T.ADJ_D += northwest
if (northeast) T.ADJ_D += northeast
if (southwest) T.ADJ_D += southwest
if (southeast) T.ADJ_D += southeast
var/list/ADJ = T.ADJ_O + T.ADJ_D
return ADJ
Really, any kind of pointers would be great as a sanity check before I start building too much around it.
Example
edit: Right after the loops you could define all those variables outside of the loop for improved performance.