pathfinding help

[dense gust]

I'm making A* star and I don't know how to calculate h costs and g costs
Should I be using distance chip or ?

[junior peak]

Pathlength is calculated as you go, by default, every node should be infinity, except for start which should be 0. Every time you visit a node, you set its pathlength to CurrentNodePathLength + DistanceBetweenNodeAndCurrentNode, but only if CurrentNodePathLength + DistanceBetweenNodeAndCurrentNode + CurrentNodeDistanceToEnd (aka the would-be F value of this node) is less than the nodes stored F value

F Value or "Pathlength + Distance To End" is quite literally the path length of that node (Should be a List<Float>) plus the distance between that node and the end node (using Add and Distance)

[dense gust]

So since my start node will be changing every 1 second or so, I have to calculate the pathlength of each node available every time my start node changes right?

[junior peak]

Yes

Remember that path length does not equal distance from start

[dense gust]

Path length = current node pathlength+ distance between node and current node
Which means if I'm on node 5 and it's pathlength = 5
And distance from current node and let's say node 6 is 1
Node 6 pathlength= 6?

[junior peak]

Yes

[dense gust]

Thanks 👍

[fresh shore]

Yo cryptic so is this similar to the Dijkstra Method?
If yes can't I just like do this

The monsters closest node from it's Node destination

I already created the lists for the nodes and the path they can go

[junior peak]

A* is a better version of Dijkstra's, but its more CPU expensive

Both of them are essentially the exact same thing, but A* takes into account distance from target node

[fresh shore]

But don't I have to calculate the node to the other node when it's visited?

[junior peak]

You will if you want to calculate the pathlength, with both require

[fresh shore]

Do I need to do it tho?

[junior peak]

need to do what?

[fresh shore]

Calculate the pathlenght

[junior peak]

Yes

[fresh shore]

Because im using Dijkstra

[junior peak]

Dijkstra's entire algorithm is "the next node to calculate is the node with the lowest pathlength that hasnt been visited yet"

A* is "The next node to calculate is the node with the lowest pathlength + distance from target that hasnt been visited yet"

[fresh shore]

So I should

Create the two lists of the possible path each node can go to

Then how would have to create another list to check for it's distance and set it somehow in a list?

[junior peak]

I dont think you understand how pathfinding works

if you had a list of paths from any node to any node, you wouldnt need to path find

[fresh shore]

I kinda do I just have to re-watch the vid again because the last time I watched it was weeks ago

[junior peak]

https://www.youtube.com/watch?v=pVfj6mxhdMw&t=8s

[fresh shore]

That's the one I watched

By what I understand from it
That I need to have to lists

Each node
And every path the node can go to

[fresh shore]

So could I some how f around with a Get closest chip to make it somehow work?

Yes

[junior peak]

No

[junior peak]

You need to have a couple lists:

• nodes
• node connections
• unvisited nodes
• visited nodes
• pathlengths of each node

I forgor the rest

[fresh shore]

What if i got every pathlength

Do i still need the visited and unvisited list if I want to publish a game

[junior peak]

You need the visited and unvisted nodes to make the algorithm

[fresh shore]

I don't get it

[junior peak]

I give up

Pathfinding is hard

You’ll learn it eventually if you keep trying

or you wont, you’ll give up, learn more circuits, remember, get inspired, and start learning again

[fresh shore]

Ight man still thx for trying to help

[fresh shore]

So I tried using ur invention for help to understand

But I keep getting an error saying

List already has 65 items

[azure gale]

Oooooh. So that’s the reason why people don’t help on pathfinding algorithms or tell you how to do them

[azure gale]

Show your circuits

I kind of forgot how to use cryptics Astar. I had it working like a month ago but then I forgot how to do node connections ☠️

[floral yew]

Do you use invisible collisions as Nodes in recroom?

Or trigger volumes?

[fresh shore]

.

[azure gale]

Either or

[fresh shore]

What about if I want to make A*, do i still need these lists?

[junior peak]

Yes, A* is basically identical to Dijkstra but it takes into account the distance from the end node, the “F Value”

[fresh shore]

For the unvisited and visited lists, does it have to be a list variable?

[junior peak]

Yes

well, it doesnt need to be, but its faster

[fresh shore]

OK thx

[azure gale]

What is the difference between Dijkstra and A*?

Don’t they both take the shortest route?

[junior peak]

They are both pathfinding algorithms

A* is faster but more computationally expensive

[azure gale]

And by how faster?

Like by how much faster is A* than Dijkstra?

[junior peak]

alot

well, depends on the maze

There is little but noticable difference in closed paths (Like a hallway game, or a game that takes place in a building), but there is a MASSIVE difference when in open areas

https://www.youtube.com/watch?v=g024lzsknDo

Notice how the "Cost" of both paths are equal, but disjtra visits WAY more nodes

[azure gale]

Jesus Christ

[fresh shore]

@junior peak
So Im trying to figure out how I should convert all of my paths in to my nodes so I can calculate the F cost

But a List get element can only have 1 Index that's it

How can I get the nodes checked all at once?

[junior peak]

huh??

F Cost is calculated as the path is found

You dont pre-bake your paths

[fresh shore]

OK, but how do I get all of my nodes with only 1 get list element chip

[junior peak]

You iterate through them with a custom loop

You can try For or For Each, but those might skyrocket your CPU

[fresh shore]

Any other better way?

[supple salmon]

Custom for loops

[junior peak]

No

If you want to iterate for each node, you must either make your own For Each to reduce CPU, or use For Each

[fresh shore]

Ight, one more thing.

So u said I should calculate the F cost as the path is found, how am I supposed to do that

[supple salmon]

Distance from the node to the endpoint

[fresh shore]

Yeah but what did he mean by "as the path is found"

[fresh shore]

^

[supple salmon]

I’ve only used dijkstras, but I think he means its calculated as the agent meets a node

[junior peak]

F Value = Distance From End Node + Pathlength

Pathlength = Distance From Previous Node + Previous Node Pathlength

[fresh shore]

No, I got that I meant the other question😅

[fresh shore]

.

[azure gale]

Wait so what if the algorithm hits a wall?

[junior peak]

A* yes?

When the pathfinding starts, you set the pathlength of every node to Infinity, except for the starting node, which gets set to 0, and you set the F Value of every node to 0, except for the start node, which gets set to Distance(Start, End)

After, you pick the node with the lowest F Value that hasnt been visited yet
Because every other node will be at Infinity except for the start node, it picks the start node first

It should now look at each one of its neighbors
If Current Node Pathlength + Distance(Current, Neighor) is less than the Pathlength of the neighbor node, set the path length of the neighbor node to Current Node Pathlength + Distance(Current, Neighbor), set the F Value of the neighbor node to Current Node Pathlength + Distance(Current, Neighor) + Distance(Neighbor, End), set the From Node of the neighbor node to Current Node (This is for filtering the path later)

When finished, it marks the Current Node as visited, then picks the node with the lowest F value that hasn't been visited yet, and repeats the above steps until it runs out of nodes, or Visited Nodes contains the target node

Once Visited Nodes contains the target node, you need to filter the path

Set Filtered Path to a List Create only containing the end node
Find the node the first node in the Filtered Path list in from, insert it in the first index of the Filtered Path
Repeat until Filtered Path contains the start node

[supple salmon]

How many loops run when you get the path once? For a 15 node setup

[junior peak]

Lists required are:
Pathlength
F Value
Visited Nodes
Unvisted Nodes
From Nodes
Filtered Path

[junior peak]

The same amount of loops as a 1 billion node setup

[supple salmon]

So it runs each loop once per node?

Btw it’s 2 am I’m just asking without thinking much

[fresh shore]

Gawd damn

You Fr a fuckin life saver

I was stuck for hours

[azure gale]

So would 1 billion nodes take longer than 14 nodes? Also how would 1 billion nodes work. Lists have a 65 cap limit

[dense gust]

String split With a string of any character with the length of 512 so
If ur string is "A" have a string of 512 A's set the seperator to the chosen character so in my case "A" this will give u a list of 512 items for a string list to get a list int plug the string list to a list get all indices of
Set the string to " "

I have no idea about 1 billion pretty sure he's just giving an example, a * doesn't go through all nodes, it goes through open node which u find as u go so it depends, a farther path takes more time than a shorter path

[stray elk]

Why do you use string variables for nodes?

[azure gale]

Actually, I have no idea

I’m guessing it’s for node connections?

[dense gust]

Node connections, and to make a list int with what I said above

[stray elk]

Sorry if this is a dumb question but how does it know it’s a neighbor because of the int?

[dense gust]

U can figure out the neighbors with circuits and store them in the list<string variable

[stray elk]

Would you just put all the nodes in a list and get the closest ones from the current node?

[dense gust]

U use a raycast method

[stray elk]

Ohhh

Thanks

[fresh shore]

What I did was
I had a list full of my nodes in and order

And I had another string list with the same order and I put every neighbor node into one string in that list

[stray elk]

Aren’t the nodes discovered as you go tho?

[fresh shore]

That's a different method

What I did, is I discovered them for each node

Then put them in a list in the same order of index like the nodes

[supple salmon]

@junior peak I have a question if you don't mind. If you intend to make a never ending ai with can pathfind the same nodes over and over until it finds players, do I still need to label which ones have been visited and which haven't?

[junior peak]

yes

[fresh shore]

Yo

So could I just make 2 ai's
But the second wouldn't be an actual ai

So I let the first Ai do the whole Astar pathfinding but like very very fast

And my Second System is the Main Ai Wich follows Where the Astar system "Goes" while it's giving me the right path to the player while it's rapidly running

[junior peak]

?

[fresh shore]

Editied

[junior peak]

mate like anything is possible in Cv2

just fuck around and find out

[fresh shore]

Ok

[stray elk]

What if you just got the neighbors of each node and then just checked the neighbor closest too the end node and repeated until you reach the end node

Wouldn’t this technically create the shortest path?

[junior peak]

thats what BFS is, and, no

[stray elk]

Oh ok. But back to the A* system, when you order the string list like 1, 2, 3 would the “1, 2, and 3” be the elements on the list of vector3s? So “1” on the string list would represent the first element on the vector3 list?

If that makes sense

Otherwise which of the nodes would 1 on the string list represent

[junior peak]

0 is the first, not 1

[fresh shore]

Why a list int tho?

[dense gust]

Each node has a provided index

[fresh shore]

Is it really needed?

[dense gust]

Wdym

[fresh shore]

Why do you need the list int?

[dense gust]

.

[fresh shore]

Why would I have to provide a index in a list

[dense gust]

The path is provided like this path is formatted like this
Index starts at 0 so 0-513 nodes is possible
Index 0 is start node

Also

To store f and h costs

[fresh shore]

How would I store the fcost

Insert in list

Or add

[dense gust]

List set element

[fresh shore]

Why would I set the F costs element

In a list

[dense gust]

That's the part of pathfinding

[fresh shore]

With the int if the F cost changes every time the ai has a new target

[dense gust]

No

[fresh shore]

Oh I would have to reset if it visited all nodes

[dense gust]

U reset when the start the path search

[junior peak]

Every time you start a new path, you need to reset visited nodes, unvistied nodes, F Value, and Pathlength

[stray elk]

What about if its chasing a player thats moving from node to node?

Im guessing get the closest node then figure out the index of that node and set that as the end node?

[fresh shore]

I get everything now

[fresh shore]

No that would just go to the same node over and over

[stray elk]

Then what do you do

[fresh shore]

.

[fresh shore]

.

[fresh shore]

Yo one question.
Do I have to store the h cost?

[junior peak]

tf is the h cost

[fresh shore]

.

[fresh shore]

.

[junior peak]

I know that A* uses F value and Pathlength
Pathlength = path length from start
F Value = Pathlength + Distance from end

tf is h value

[stray elk]

H dosen’t exist

[junior peak]

well, H AFAIK is the "Heuristic Cost", but im not exactly sure what it is

[stray elk]

I thought H cost was distance from from end?

[junior peak]

oh fuck that would make sense

if pathlength = length of path and H cost = distance from end, then no @fresh shore you wouldnt need to store H cost, since you can always find that using Distance

F Value should be stored in a list, else you're just making Dijsktra

[fresh shore]

Ight

[fresh shore]

How would I set every pathlength to inf?

[junior peak]

with integers you cant, so set it to 2^31-1

[fresh shore]

OK sorry for the questions

But let's say the target node keeps updating because the player keeps moving

Would I have to reset everytime?

Because the first node has to be distance (start, end)