ID:2850958
 
Problem description:

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.
Looks good, only thing that comes to mind is that you're modifying a value on the turfs themselves instead of storing a temporary list of turfs with their perceived values. Might be an issue if you use it with spawn() and multiple things are doing stuff, maybe. All the input I got from reading it, don't quite understand the extra cost values tho and their chosen values.

Example

// Instead of
Start.H = HCalc(Start,End,mode)
// Could define a variable inside of the proc
var list/Turfs[Start] = HCalc(Start,End,mode)


edit: Right after the loops you could define all those variables outside of the loop for improved performance.
In response to Kozuma3
Yeah, I get what you mean - I had originally started by using a /node datum or even /obj/node instead of directly modifying turf values, but I figured the overhead of creating/deleting objects would be higher than modifying the turfs - I'll look at the temp_list idea though.

Oh, looking at your example that uses associative lists, will that still work if I want to store the G, the F, and the Dir? I thought that an assoc. list could only store a single value per entry - Would I need to use several lists, a la

var list/TurfDir[Start] = null
var list/TurfG[Start] = 0
var list/TurfF[Start] = HCalc(Start,End,mode) + TurfG[Start]


As for my extra costs, the +0.414 is adding sqrt(2) when moving diagonally so the algorithm will prefer moving N/E/S/W, though that's really just a matter of preference.

The +.25 when turning is to mak the algorith favor continuing to move in the same direction instead of turning if all else would be the same - this is to reduce paths that look like "Stairs" when using caridinal-only pathing, as I am using the algorithm for level generation. These values will likely be tweaked and/or ignored depending on the use-case.
In response to Braekyn
Braekyn wrote:
Would I need to use several lists, a la

Up to you :D

var list/Turfs[Start] = list( HCalc(Start,End,mode), value2, value3 )
In response to Kozuma3
Kozuma3 wrote:
Braekyn wrote:
Would I need to use several lists, a la

Up to you :D

var list/Turfs[Start] = list( HCalc(Start,End,mode), value2, value3 )


Oh, right, grids XD

So, to access a var it'd be something like...

Turfs[Turf][1] == {Turf.H}
Turfs[Turf][2] == {Turf.G]


?
In response to Braekyn
Braekyn wrote:
So, to access a var it'd be something like...

> Turfs[Turf][1] == {Turf.H}
> Turfs[Turf][2] == {Turf.G]
>


Yup! And lets say Turf.H was a list with 4 elements,

Turfs[Turf][1][3]


Would get the 3rd element in Turf.H
In response to Kozuma3
Thanks for your help! I'm in the process of modifying the proc to take advantage of that, I'll let you know if I have any further issues
Also instead of strings "O" & "C" you could use defines

#define MODE_O 0
#define MODE_C 1
In response to Kozuma3
Took a bit - I actually ended up re-writing it form scratch to avoid confusion when attempts to modify were causing issues - But it's working great now, and as a bonus it is completely object-independent! I can use it with my level generator, using rooms as nodes, to have coarse path-finding with the same code. Thanks so much for your input!

As for modes, I'll leave it as-is, as it's simpler to swap between while running.

Additionally, I added in a "random" modifier so I can adjust how close to perfect the algorithm stays - Perfect for randomly generated hallways