Bunch of vehicle stucks themselves after astar calculation

xyz

TwistedMind Well you can consider it a trivial form of flocking. But the point is, with large groups of units each needs to have its own shortest path to the target. Otherwise the move could look rather strange.

TwistedMind

Allright. About the thread, when i give a move order, the code is:

for unit in listeUnitToMove:
        # i precise my script named Astar, not the built-in node
	var UnitPath = Astar.makePath(unit.position, Vector2(mousePos), Map, unit)
	unit.move(UnitPath )

If i have 30 units to move, that's means i must have 30 threads ?

xyz

TwistedMind If i have 30 units to move, that's means i must have 30 threads ?

I'd do all makePath() calculations in one thread if total execution time is in the ballpark of several frames. But you can do each in a separate thread too.

TwistedMind

I have tried to include the for loop in the thread, it works but i see a little freeze of 1-2 sec. A little anoying but acceptable.

I have tried to include the makepath only and i have the same result...

Something else come in my mind: I remember i used in the past the Astar build-in node and if i make links "go to" <-> "back to", or simply "go to", for a tilemap size of 96 x 96 (so 9216 cells), it was acceptable for the wait time, but more take more time.

Maybe i should precalculate all connexions in a thread, to decrease the time to wait before the game start and maybe it will more efficient ?

Anyway the trick for avoid units overlap still remain.

xyz

TwistedMind How so? There should be no freeze. That's the whole point of using thread(s).

TwistedMind Anyway the trick for avoid units overlap still remain.

Check the distance between unit centers. If it's less than some minimum, separate along the line that connects the centers, for the amount equal to the difference between minimum distance and actual distance. In other words - do a simple circle-vs-circle collision resolve.

TwistedMind

How so? There should be no freeze.

I agree with you, it's strange. Maybe something wrong in my own astar. I share you my script, to open and see it in godot.

xyz

TwistedMind Why not just use Godot's AStarGrid2D to do the calculations for you. It'd be much faster than iterating in GDScript.

TwistedMind

xyz Because i learned that just today and i see i can't use the new version because "full conversion" and "projects only" conversion make problems. I suspect it's because my OS is still on Windows 7, my computer hardware is old and i can't change it for the moment. So i'm stuck to 3.5.2, i think...

And i have little fear to waste too much time to adapt all my works for each new release version of godot... and if i encounter a bug on a recent version, i will need to wait. It will cannot works in long term.

I remember too someone says the A* node not thread friendly.

xyz

TwistedMind How your A* precalculation code looks like?

TwistedMind

You can get it here:

xyz

TwistedMind You can use Astar2D in 3.5. Its thread safety doesn't matter since you'll need threads only if you choose to go with your own code. Native A* calculations are probably fast enough.

If you insist on using your own, you first need to optimize that mega loop body:

Remove all var declarations
Eliminate all string comparisons Use enums instead of strings for type identification. Also avoid calling is_node_in_group(). Use flags instead.
Remove sequential array searches(i.e. Array::has())
Avoid rasizing arrays (Array::append() and Array::erase()), resize your arrays to maximum needed size in advance.

If it's still too slow after you thoroughly optimize it, run each unit's calculation in a thread.

TwistedMind

I can use Astar2D, certainly. But to connect all the points, its take too, very too much times ! Is there a way to "optimize" that, except decrease the number of cells ?

To be complete: i have a map size of 96 x 96, so 9216 cells. But, to make the illusion the world is "connected like a cylinder", i need to make a copy of this map as neighbor (see below). And so, there are so much tiles that take too much time to connect each Astar's point by Astar2D node.

So imagine a map size of 256 x 256 (maximum planned)...

I can't use viewports nodes because the unit needs a map coordinates from the others copies to make the transition between the real map and the copy, when i go to the opposite direction i must see that unit.

If is it possible to use the build-in node, it's all i demand. Actually, i just try to find a solution to the problem.

xyz

TwistedMind I can use Astar2D, certainly. But to connect all the points, its take too, very too much times ! Is there a way to "optimize" that

You need to do it only once at startup. If maps are premade you can calculate it offline, so you just load pre-calculated data and give it to Astar2D.
And it can be optimized. Don't use all tiles as nodes, only the corners. That's the way A* is supposed to be used.

How long does it actually take?

TwistedMind

When i launch the game sequence, the map is generated in gdscript with open simplex noise, it isn't prebuilded by hand.

I remember it take between than 30 seconds and 1 minute for 96 x 96 map size. With map's copies, I didn't check the time count but i know it is too long. I precise it was for all cells points, i suppose it take less longer if i include only corners...

But wait a minute: if i include only corners, how the unit supposed to know if there are obstacles in the middle of the path (yellow square = rocks) ???

And about corner, i must precise which corner from the tilemap, are these corners (second image) ?

xyz

TwistedMind But wait a minute: if i include only corners, how the unit supposed to know if there are obstacles in the middle of the path (yellow square = rocks) ???

Well just include all the obstacles. For A* there are only 2 types of tiles, passable and non-passable. A* nodes only need to be passable tiles that are at the corners of non-passable tiles.

If black tiles are non-passable then magenta tiles are all you need as A* nodes for pathfinding to work properly.

TwistedMind

xyz

I have forget to precise the units must move tile by tile, does it change something ?

So if i understand well, i just need to include these passable tiles (only red circles i mean, red arrows is to show the step passage) ?

xyz

TwistedMind If there are no obstacles in the straight line between start and end point then you don't need A* to calculate the path. Just "rasterize" the line that connects start and end point and you'll get the tile path. That's also the way to get paths between A* nodes when only corners are nodes. It's how A* is supposed to be used. Having every tile as an A* node is a massive overkill. A* should not be burdened with trivial non-obstacled movement from tile to tile.

TwistedMind

Ah... that radically change my interpretation about the A* system...

Just "rasterize" the line that connects start and end point and you'll get the tile path.

Excuse me, you lost me at this point. An exemple: My unit is in position (0, 0) and i click to the position (5, 0).

I see, on my screen, there are no obstacles but there is actually no any kind of "connexions" too, how the unit supposed to do to "know" it must pass to (1, 0), (2, 0), etc ?

Second example: if the unit must go to the same point 0, 0 -> 5, 0, but there are a rocks on pos (3, 0), it must use astar ?

So that's means:

If obstacle detected:
     move with astar
else:
     move from or with something

Something is dark here: how the unit may detects something without astar ?

xyz

TwistedMind Ah... this concept is radically change my interpretation about the A* system...

Yes, you've been misusing A*, that's why you get this enormous slowdowns. I'd suggest to switch to Godot 4 if you can because AStarGrid2D will handle all of the described things for you. If you still want to use 3.5 then cram as much work as you can on AStar2D. However in that case you'll have to handle some things on your own.

The main thing you need is a function that returns a list of tile coordinates that represent a direct linear path between two tiles. Something like:

get_direct_tile_path(Vector2i(0, 0), Vector2i(5, 0))

This should return [(0,0), (1,0), (2,0), (3,0), (4,0), (5,0)]
Having this function is crucial for all of it to work.
So once you have the function, you should setup A* as follows. This runs only once after the map has been generated:

Iterate through all tiles and determine which ones are corners. Those are your A* nodes.
For each corner (A*node) find all other nodes that can be connected to it with a linear path without obstacles. Here you can use your get_direct_tile_path() function to get the tiles and then check if any of them is an obstacle.
Now you have nodes and non-obstacled connections. This can be directly fed into AStar2D

Now for each individual pathfinding:

Ask your AStar2D to get you the path between your start/end. It will return a list of A* waypoints, the start/end points may or may not be A* nodes. This list now represents a non-obstacled movement path from start to end via waypoints
And finally use your get_direct_tile_path() function on each two consecutive waypoints to get the final tile-to-tile movement path.

TwistedMind

I definitively can't use Godot 4.x because something is too old in my computer (i tested and it's catastrophic, probably graphics by old OS)... I dont have as choice to continue with 3.5.2.

I don't know and i can't identifiate something similar to "get_direct_tile_path" but something comes in my mind: is it possible to draw a virtual line from A to B but is it possible to compare the "pixels" of this line with mapgrid ? Or maybe another option in another name ?

xyz

TwistedMind I don't know and i can't identifiate something similar to "get_direct_tile_path" but something comes in my mind: is it possible to draw a virtual line from A to B but is it possible to compare the "pixels" of this line with mapgrid ? Or maybe another option in another name ?

Yep, you identified the problem correctly. It's basically the same thing as line raseterization/pixelation. There's a well known classic algorithm for that: Bresenham's algorithm. You can probably find many implementations around the web. Note that there will be slight difference in implementation depending on whether your system allows for diagonal movement or not.

You can start by looking here, and search around some more.

« Previous Page Next Page »