Manual Astar system

This is a READ-ONLY snapshot of the Godot Community Forums when TwistedTwigleg was the owner, which is hosted for archival reasons only. The current Godot Community Forums can be found here.

Some links may point to external websites, including the current Godot Community Forums. These websites are not associated with TwistedTwigleg.

TwistedMind

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.

Erich_L

TwistedMind Are you not using the AStar class built into Godot? It will do everything you need it to

TwistedMind

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

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 !

Megalomaniak

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?

TwistedMind

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

Erich_L

Megalomaniak last time I tried I found godot's aStar wasn't multi-thread safe

cybereality

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

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.

TwistedMind

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 ?

cybereality

I still doubt the built-in A* code won't work, but I don't know enough to tell you what to do exactly.

Kojack

I'm fighting the urge to go off on a tangent and give a code review of the A* implementation posted above. 🙂

Megalomaniak

Kojack

Ok. 🙂

First up, it's python, not GDScript. 🙂
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).
The open list is used in two spots: find the best f and check if node is open. The best f does need a list, but the check if open can be a flag too to remove another loop. Probably best to make node state an enum, there's only 3 options (open, closed, neither).
The cost of moving diagonals is 1. Usually you'd make it higher, diagonal movement is 1.41 times further than non diagonal. So it would think a zigzag path is as fast as a straight path.
The heuristic is using dxdx+dydy. I've never seen that used without a square root (to get euclidean distance). It would mean the cost is exponential with distance. Usually manhattan (if no diagonals) or chebyshev (if diagonals) distance is used.
The use of "continue" in the open and closed list loops is wrong. If it finds the node in the closed list, it doesn't actually stop it from being used. The continues need to continue the outer loop of the 8 adjacents, not the inner searching loops. If the loops were replaced with a flag check like mentioned above, the continues would apply to the correct loop.

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

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/)

Megalomaniak

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.

Kojack

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.

TwistedMind

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

cybereality

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.

Kojack

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