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:
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
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.
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:
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
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.
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.
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.