Pathfinding Help

[vivid sapphire]

So the gist of my algorithm is, set all costs to infinity, set the goal node's cost to 0 at the start, add the goal node index to the open list. loop through the open list > set current node. loop through all neighbors of current node and do cost calculations on them > grab neighbor with the lowest cost > add it to the open list > repeat until entire graph is visited. but the problem is after i add the goal node's neighbor with the lowest cost to the open list and then attempt to do the same on that node, that node's best cost neighbor is the goal node. so it keeps going back and forth adding the goal node and that neighbor node to the open list over and over. never getting to explore the rest of the graph. how would i go about finding the UNVISITED neighbor with the lowest cost?

[sand quail]

you stop keeping track of the lowest cost for visited nodes

I've tested it, once a node is visited, it cannot get a lower pathlength

So instead of keeping track of ALL costs, just keep track of unvisted costs, setting the costs of visited nodes to infinity

[fossil knoll]

I wish I knew what this meant I'm still trying to learn🙏

[vivid sapphire]

would you mark the current node as visited by setting it's cost to infinity before or after doing pathlength calculations on it's neighbors?

[sand quail]

After

[vivid sapphire]

finally got it working with pathlength instead of the crappy BFS method tysm 🙂

now comes optimization hell 😦

[vivid sapphire]

You can take a look at it here https://rec.net/room/DijkstraFieldTestRRS2

[fossil knoll]

I'll definitely check this out! you should also teach me😭🙏

[fallen minnow]

Plants Vs Zombies football zombie

[scenic quartz]

do you mean when u visit the node u make it inf?

[sand quail]

yes

[scenic quartz]

but what i did was when calculating the path to the goal i made it so every node had only 1 neighbor saved up wich was the lowest

[scenic quartz]

and would i need an visited list

[sand quail]

yes

[sand quail]

if every node only has 1 neighbor, you dont need to pathfind

thats called a line

[scenic quartz]

but lets say i have 100 ai and i want to make a heatmap how would i store visited node for each ai

[sand quail]

you dont

[scenic quartz]

so how does the ai know wich ones visited

wont it go in a loop?

[sand quail]

Pathfinding is not related to AI

[scenic quartz]

cuz u said the calculation i did is an line

[sand quail]

Your pathfinding algorithm keeps track of visited nodes via a List<Int> or List<Rec Room Object>, i prefer a List<Int>

When a node is visited, you add it (or its index) into the list

[sand quail]

yeah, because each node only had one neighbor, thats a line

spoiler

[scenic quartz]

oh u got it wrong i think, i meant by that
Every node has like 4 neighbors

and it chose the lowest one

[sand quail]

look i've explained pathfinding enough times just go find one of them

[scenic quartz]

like the nearest from the current node

[sand quail]

im trying to do stuff rn

[vivid sapphire]

sorry for the ping but do you think my vector field is good or na #circuits message

[sand quail]

it works thats for sure

but you dont have any speed statistics

my algorithm takes 0.0037s per node to run at 30% CPU (~2 seconds for 540 nodes)

Divide the time it takes to calculate the algorithm by the number of nodes you have

The timer should start once you start calculating the algorithm (not before its initialized, eg. not before it hasnt been reset for a new path) and stop once you have visited all (possible) nodes, eg. when it finishes

[scenic quartz]

ay cryptic sorry for the ping too, is it normal that a node baker takes 48 seconds with only 58 nodes in a list

[sand quail]

depends on how you did your circuits

[scenic quartz]

Yeah but lets say u made an node baker how long should i usally take

[sand quail]

oh, a node baker? that can take a LONG time

for my 540 nodes, my fastest time is like 3 minutes

but thats because you should only have to do it once, then it should be baked