Allow connection of two or more AStar nodes

[tavurth]

Describe the project you are working on

Any project which uses multiple AStar nodes

Describe the problem or limitation you are having in your project

Currently there seems to be no way to link one AStar node to another AStar node.

This causes issues when a character reaches the boundary of the AStar node.

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

Connecting cells to different astar nodes would allow for easy cross boundary calculations.

Currently it seems like I have to setup a node merging system when using a chunked procedural terrain with a AStar navmesh.

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

Extend the connect_points by adding a new function connect_points_to which would take a different AStar node as it's first argument.

This would allow connection between two or more AStar nodes.

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

This should be part of the built in AStar

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

This should be part of the built in AStar

[lewiji]

I'm curious since I've never tried using multiple AStar nodes; in practice, wouldn't this eliminate any perceived performance benefits to having separate AStar nodes? Since AStar works as a graph, "linking" a point in one AStar node to another would essentially be the same thing as having one AStar node with all of the data inside, since once one point is linked to another, it's linked to all of the other points connected to that point. The separation of the data into distinct nodes then kind of collapses, since the internal representation of the AStar graph has to include both nodes' data.

I suppose the advantage would be that you could free an AStar node and have it automatically handle disconnecting that "section" of the graph.

In my game with procgen and AStar, I just have one AStar node and the "chunks" of the generated world handle adding their own points to it via an autoloaded script. I guess it could be neater to have each "chunk" have its own AStar node, but then again, it seems conceptually simpler to have one "graph" that's accessible to anything that needs it, because the objects in the world don't really care what "chunk" they're in, just whether they can find a path from A to B, regardless of chunk.

Curious to see others' thoughts as I'm not super knowledgeable about the internals of the AStar node.

[Zireael07]

Note that this proposal would allow a workaround for https://github.com/godotengine/godot/issues/43494

[lewiji]

Note that this proposal would allow a workaround for https://github.com/godotengine/godot/issues/43494

That's interesting, yeah - in my project I've used a nested cantor pairing function to turn a 3d translation into an id and have had to do a lot of wrangling with the results to get them not to overflow.

[tavurth]

Note that this proposal would allow a workaround for godotengine/godot#43494

That's interesting, yeah - in my project I've used a nested cantor pairing function to turn a 3d translation into an id and have had to do a lot of wrangling with the results to get them not to overflow.

You can also treat the ids as an array. Then a subclass holds the id_range for each virtual AStar cell inside the actual array. Each virtual AStar is a 2D grid of cells but kept in the AStar linearly, then the system can easily compute edges in the following way:

class CellHelper:
    # ...other stuff

    func get_edge(edge: int):
        match edge:
            EDGE_TOP:
                return range(id_range.x, id_range.x + n_columns)

            EDGE_LEFT:
                return range(id_range.x, id_range.y - n_columns, n_columns)

            EDGE_RIGHT:
                return range(id_range.x + n_columns, id_range.y, n_columns)

            EDGE_BOTTOM:
                return range(id_range.y - n_columns, id_range.y)

            _:
                push_error("[Error]: Invalid edge type <%s>" % edge)

    func get_connection_edge(with_cell: CellHelper):
        if with_cell == self: return null

        var delta = with_cell.origin - self.origin
        if delta.x == -1:
            return get_edge(EDGE_LEFT)

        elif delta.x == +1:
            return get_edge(EDGE_RIGHT)

        elif delta.z == -1:
            return get_edge(EDGE_TOP)

        elif delta.z == +1:
            return get_edge(EDGE_BOTTOM)

        else:
            push_warning("[Error]: Edge is too far <%s> <%s>" % [self.origin, with_cell.origin])
            return null

Then you just run an edge detection script on each chunk and connect them if they are side-by-side.

IDs start at zero and usually run up to 10 or 20k for me.

This is useful as it can handle the following example:

####0000
####0000
####0000
0000####
0000####
0000####

As well as the following examples:

0000####
0000####
0000####

####
####
####
####
0000
0000
0000