Hello everyone,
For my project, i need to make a manual astar system. I was able to make a basic astar, with little obstacles but to avoid a bigger obstacle, it's another story.
I have find a way to detect when the algorythm is blocked, but i don't find the way to get around. I know i need to "close" the invalid cells, but how far ? If i close all, the algoryth will not find any way.
How can i do ? You must know the map is generated randomly for each game, it's no static.
Hello checkoutfirst,
This code was found already and yes its works, but it is incomplete.
Something missing: this code is for a maze, my project isn't a maze. Yes, this code works for little and middle distance, whitout bigs obstacles, except for the example i show. If you try your code to my example, you will see the problem isn't solved.
TwistedMind Are you not using the AStar class built into Godot? It will do everything you need it to
Erich_L This is the first thing i have tried when i got to know the astar system.
If i use a map cell 96 x 96, it's ok, but i need to copy this map, so that's mean i have a map of 96 x 96 x 8 copies and the class built take too long to set, because too many cells.
So i need something more... efficient.
Between that, i have found some mistake in my code and i finally did it: some double values was created in the open node list and some node wasn't excluded correctly.
Now i have a "live" astar which work as expected (i see the emojies isn't set yet ?). Hoorah !
TwistedMind This is the first thing i have tried when i got to know the astar system.
If i use a map cell 96 x 96, it's ok, but i need to copy this map, so that's mean i have a map of 96 x 96 x 8 copies and the class built take too long to set, because too many cells.So i need something more... efficient.
Couldn't you off load it to a worker thread and only periodically sync to main thread when the worker thread is done?
Can you explain why the Godot A* class doesn't work? That is implemented in C++, so should be faster than anything you can do with GDScript. I have read about A*, so I understand how it works, but I have not attempted to create it myself.
Megalomaniak This is something i was far to imagine, i don't know all tips and tricks of GDScript, yet.
cybereality Doesn't work ? I didn't say it doesn't work. I said it doesn't satisfy my needs. The class works perfectly basically.
If i can do what Megalomaniak says, to put the nodes points setter in a thread, it can be a positive way, according what you say, cybereality.
So the question is: is it "safe" ?
The first part of the work to do, i suppose, is this, right ?: https://docs.godotengine.org/en/stable/tutorials/performance/threads/using_multiple_threads.html
Megalomaniak last time I tried I found godot's aStar wasn't multi-thread safe
Erich_L Oh yeah, I expect this to require huge care in mutex massaging and who knows what else. Haven't really used godot's A* at all, but I didn't expect it to be safe per say. That doesn't mean it would be impossible to do tho.
TwistedMind This is something i was far to imagine, i don't know all tips and tricks of GDScript, yet.
Hmm, then it might be better to do something else to get a good grasp on multi threading first. This would certainly not be a beginner friendly task.
I still doubt the built-in A* code won't work, but I don't know enough to tell you what to do exactly.
I'm fighting the urge to go off on a tangent and give a code review of the A* implementation posted above. 
Ok.
I haven't run it, but my guess is the open list is going to grow infinitely since its adding already closed and worse g open nodes back onto the open list. But maybe its working fine, I'm just going off my gut reaction.
Sorry, going through withdrawal from not teaching path finding for a whole trimester.
In one of my projects, I have A* path finding of 15 million nodes. Takes a little less than a second to calculate a roughly 4000km path. (It's the entire OpenStreetMap road database for Australia). One day I'll go back and try optimising it.
I need to try D* sometime. That's A* with dynamic environments and path recalculation.
Megalomaniak Hmm, then it might be better to do something else to get a good grasp on multi threading first. This would certainly not be a beginner friendly task.
Do you agree if i say you than if i don't try it, i never learn it ? Whether it be the project, the basis still, right ?
Actually, i can't define if a non-class builded script will be efficient or not. What append when i control 50 items ? 100 ? What append if i control 50 items + 5 items goes to A to at B and B to A with a cyclic mode ?
At this point, let me go on to discover if what i have done will be sufficient or if i need to optimize it. I making the mecanics of my projects, i'm far away to the optimization part.
I can't move on with doubts, i need something clear and reliable. If you haven't possibilities to tell me, "yes it will work or not, it won't", i can't trust anyone and i will not move on. If you need informations about my project, i'll be happy to share you what you need.
Kojack , you say you have "A* path finding of 15 millions nodes". Your code writed in Python, GDScript or anything else ?
TwistedMind Do you agree if i say you than if i don't try it, i never learn it ?
If I'm understanding that line right, then yeah, of course you can learn a lot jumping into the deep end of the pool, but you also risk drowning.
"Fear prevents faith" (in us), Megalomaniak
I'm not fool, i have understand what you told me earlier, the thread subject will wait if not necessary.
General wisdom amongst most developer is to not optimize early because the optimization might become redundant or even worse, a detriment later on so my recommendation is to just get things working as intended then start thinking about what can be done to make it more performant. Off loading the work to another thread would be the last resort. There's likely a good few other things that can be done to get the frametime cost itself down, for an example:
Kojack While A* descriptions talk about open and closed lists, you don't want the closed list to actually be a list. The code is scanning an array many time to see if a node is in it. Instead just store a closed flag in the node, that takes the closed list from O(n) to O(1).
(for context: https://www.freecodecamp.org/news/my-first-foray-into-technology-c5b6e83fe8f1/)
TwistedMind you say you have "A* path finding of 15 millions nodes". Your code writed in Python, GDScript or anything else ?
It's C++ in my custom SFML based 2D engine.
One interesting optimisation for path finding (that would take a fair bit of precalculation to set up) is to brute force every combination.
A 96 x 96 map is 9216 nodes. You can store which direction to walk to reach all 9216 nodes inside of every node. That would only take 81MB of ram. Or 40.5MB if you pack the directions as 2 per byte. Now pathfinding from any map point to any map point is instant, every combination of start and end is embedded in the map.
The downside is its not dynamic, and the precalculation step would be HUGE, so it doesn't suit proc gen maps.
I see that Godot 4 Alpha 16 has a new path finding system added.
https://github.com/godotengine/godot/pull/62717
Godot 3.x has a graph based A* using a euclidean distance heuristic.
Overall it looks like a good implementation, except the heuristic function does a string lookup for a GDScript replacement algorithm for EVERY NODE. It really should do that once at the start of a path find pass, not for every node.
Anyway, apparently Alpha 16 has added a 2D grid based Jump Point Search path finder.
I've never tried Jump Point Search before. Here's a visualisation. It looks pretty interesting.
http://qiao.github.io/PathFinding.js/visual
(Also shows A, IDA, Dijkstra, etc
Megalomaniak Off loading the work to another thread would be the last resort.
Anytime I see someone suggest multi-threading as a solution to their problem... well... not only will it not fix the problem, it will likely create more problems that are unimaginable.
