ID:2850958 Jan 27, 5:27 pm 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 // List to return Open // List of unvisited but scored nodes Closed // 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 != Start) //Trace the path back from the End node by parents var/turf/F = Final 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 + malusproc/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. Jan 27, 5:45 pm (Edited on Jan 27, 5:55 pm) Kozuma3  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 ofStart.H = HCalc(Start,End,mode)// Could define a variable inside of the procvar 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. Jan 27, 6:25 pm (Edited on Jan 27, 6:31 pm) 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] = nullvar list/TurfG[Start] = 0var 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. Jan 27, 6:58 pm In response to Braekyn Kozuma3  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 ) ``` Jan 27, 7:24 pm 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] == {Turf.H}Turfs[Turf] == {Turf.G] ``` ? Jan 27, 7:26 pm In response to Braekyn Kozuma3  Braekyn wrote: So, to access a var it'd be something like... ```> Turfs[Turf] == {Turf.H}> Turfs[Turf] == {Turf.G]> ``` Yup! And lets say Turf.H was a list with 4 elements, ```Turfs[Turf] ``` Would get the 3rd element in Turf.H Jan 27, 7:44 pm 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 Jan 27, 10:31 pm Kozuma3  Also instead of strings "O" & "C" you could use defines ```#define MODE_O 0#define MODE_C 1 ``` Jan 27, 10:48 pm 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 