Any help with pathfinding algorithm appreciated!

Help and Feedback Scripting Support
#1

Hello! I am working on a pathfinding system using A* pathing algorithm

I am looking for some suggestions with a problem im having ( theres no such thing as a stupid suggestion / attempt ) lol

This is how my map looks:

image
image1210×436 105 KB

I need to go from point A ( the Yellow spot ) to point B ( the Red spot )
so far I am able to find a path that goes from A to B, but I don’t know how to narrow down the path from a little bit of randomness after finding the path.

so heres another Image with some drawings to help point out my problem:

this is going to be our new point A and B

image
image780×262 122 KB

Only using the nodes with numbers you can find the correct path it should choose when we finish and find the solution its the straightest line you can make

Starting at A:
0
21.57
20.38
19.67
18.22
17.42

image
image780×262 122 KB

but the problem im having is how do I know ( from code that this path is the correct one? )

Heres what we know so far:

all of the yellow nodes w/ numbers are on the path to the goal

the number displays the distance to the goal + length of the path to the previous yellow node

each node ( spot )
has connections and they are all stored in each node’s table like this:

local Nodes = {
     [node] = { Connections = {Other_node_reference,Other_node_reference} }
      -- up to 8 ( also has other data, but it doesnt help here )
}

Anything would be appreciated! thank you for reading.

3 Likes
#2

For randomness, I would do this…
Each time you travel to a node, check if there is a chance for random deviation from the path
If there is, then look at a random neighbor node that is not the next normal node on the path
if that random node can complete the journey, without passing through your current node, then move to that node, if not, select another random neighbor, keeping track of nodes tried and failed. If all neighbors fail, just move to next node and repeat process.

2 Likes
#3

Why is there randomness in the path finding? Are you introducing it on purpose, and why?

In the last picture it really looks like some yellow nodes are not on the path, so what’s going on with that?

2 Likes
#4

Yeah nice questions!

It isn’t “randomness” I don’t know how to explain it well.

Well I was introducing extra nodes so that it wouldn’t just take the closest node
because it would just end up skipping the fastest path because there are odd nodes

I basically just take the two cheapest nodes I possibly can so if there is a possible second path it would explore it as it finds the fastest path

this is what im thinking:
image

theres the black path thats faster to the goal
and the blue one that still gets a little bit of exploration as the costs are very similar

2 Likes
#5

Wait, do you have a pathfinding algorithm implemented already and want to tweak it, or are you asking how to make one?

If it’s the former: share your algorithm and what the problem is

If it’s the latter: use A*, there’s a million implementations online

#6

well I am using A* but I tweaked it a little bit, I like it, but I dont have any ideas to narrow the path down

2 Likes
#7

What do you mean “narrow the path down”?

Also, how did you modify A*?

#8

thats basically it
and even without this I have sometimes clumps of nodes that had to be explored to find the goal

2 Likes
#9

I’m sorry, I’m still having trouble understanding the question. Could you share your code for pathfinding?

Could you also try explaining what your current problem with it is, another way?

If your question is “how do I not explore bad paths” the answer is that in general you can’t—pathfinding algorithms must explore unfruitful paths, since they don’t know the best path, by definition!

You can tweak your A* heuristic however you want, which may change your paths slightly or improve its run time, but it looks like it’s working as expected.

#10

Yeah that all makes sense

the question is how do I take this path with tons of stray nodes and remove the strays to find the actual “best path” through all of them

2 Likes
#11

Oh I see, it sounds like you’re just missing a few steps of A*

You’re supposed to be keeping track of each node’s “parent” node, i.e. where it came from, and updating that as you find better parents.

Then when the goal node is finally added to the closed set, you just look at the chain of parents, starting from the goal node, and ending at the start node.

In this way you build a single continuous (but reversed) path between the start and end.

2 Likes
#12

oh cool I didnt think about it lol

I think ill try that + maybe go over the online implementations more

3 Likes
#13

Just to add to this and hopefully clear it up even more xD

A* is complete and optimal (in terms of the result), meaning it always finds a path (if one exists) and it always finds the best path. If you’ve got A* implemented right then you won’t need to fiddle with the output at all to get the optimal path between two nodes.

1 Like
#14

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.