Add Parallel AStar map functionality

[KnightNine]

Describe the project you are working on

I have entities of different heights and sizes which must use a different Astar map to accommodate for variations in each entities' size and height.

Describe the problem or limitation you are having in your project

I have to load in several astar maps for each entity shape that uses astar movement which is really slow because of this. And I assume it takes up additional ram to have multiple instances of each Astar map (though I haven't experienced much of a performance drop myself so it may be insignificant).

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Add an additional parallel_support_array int array variable to each Astar point which lists what "pathing support" that point has. And add an additional parameter to get_point_path() called parallel _index which restricts the generated path to only use points which contain the index defined within its parallel_support_array (or rather a parallel _index_array parameter to include Astar points whos parallel_support_array contains any of the indexes listed for added flexibility).

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Here's an example of how this can be used: say you have a small cave and you have two characters. one character is small and can fit within the cave but the other is too big to walk through the cave even though it is a shorter distance.

So the Astar points that go through the cave that are blue can only support small characters and thus their parallel_support_array would only contain index 0 to represent small characters (parallel_support_array = [0]). the Astar points which exists around the cave that are far away enough from the walls (red) could support index 0 and index 1 to represent small and large characters (parallel_support_array = [0,1])

the large character would then be using astar points that support index 1 around the cave since it is too large to go through the cave. and the small character can use any of the astar points which support index 0 and would take the shorter path through the cave.

And this can be used for all manner of different types of pathing restrictions (e.g. one character can walk on water and the other cant)

If this enhancement will not be used often, can it be worked around with a few lines of script?

My only contention is whether or not this implementation is slower than having separate Astar maps for each entity type (since every point would need to be checked for support) but I don't see why it wouldn't be used often due to its flexibility.

Is there a reason why this should be core and not an add-on in the asset library?

this feature is tied to the core functions.

[Calinou]

Have you seen https://github.com/godotengine/godot/pull/64326 ? It may address your need in a different way.

[KnightNine]

Have you seen godotengine/godot#64326 ? It may address your need in a different way.

I'm trying to run the example project but it just gives me a Can't open project at 'C:/Users/USER_NAME/Desktop/one to many example/example/project.godot', its `config_version` (5) is from a more recent and incompatible version of the engine. Expected config version: 4. error.

what version of Godot do I need?

from what I can understand by reading the code, it is able to be more efficient by somehow keeping and using the pathing data from an "initial scan" of connected points to the target point? So calls of 'get_point_path()' already has the connections to the target_point and doesn't need to re-scan the grid's connections every time.

I don't think that has anything to do with this issue but it's useful to look at an edit of godot's core files to see how to add new functions if I go ahead with implementing this feature myself.

[halgriffiths]

Instead of an array + an index to define who can use a path, it would probably make more sense to implement it as a bitmask, like we do for (eg) collision layers.

what version of Godot do I need?

You need to checkout the PR's branch (halgriffiths:djikstra-pathfinding) and build the engine using scons (https://docs.godotengine.org/en/stable/development/compiling/index.html) , then open the project with the godot executable which appears in the ./bin/ folder.

[smix8]

As mentioned in other related proposals and issues the AStar classes should get a "navigation_layers" bitmask same as all the other navigation related nodes and functions. Users are already familiar with the layer use as bitmask are uses everywhere in Godot for this purpose from navigation to collision to visuals. They are also memory cheap / performant compared to the proposed array solution. The point / segment structure inside AStar classes already exists to add the bitmask, the pathfinding logic needs small adjustments to it.

[KnightNine]

AStar classes should get a "navigation_layers" bitmask

@smix8

Yeah that's exactly what I was thinking when coding it myself , the "navigation_layers" bitmask system is way more efficient than the array idea I suggested (and it can be stored in my pool_int_array for the set_as_bulk_array() function for Astar I suggested earlier), but I haven't seen any proposals for this here. maybe you could link one.