We should deprecate / rename the AStar classes and create a general Graph class with a wide variety of algorithms

[DevJac]

Currently the AStar* classes (AStar2D, AStar3D, etc) store a graph; the internal state of an AStar class is a graph, that's it, just a graph. The AStar classes then implement the AStar algorithm on this graph, and also a few supporting methods.

The problem is the "AStar" naming of the AStar classes implies they are an algorithm which contains some graph data. It's more accurate to say the class is a graph with some graph related algorithms implemented as methods, the one and only of those being AStar currently.

I propose we create a "Graph" object similar to the AStar classes, and implement a wider variety of graph based algorithms, more than just AStar (AStar would still be one of them though).

Here are some questions I've thought of that cannot be answered by the current AStar classes (as far as I know):

• What is the closest point to a given point?
• What are the 5 closest points to a given point?
• What is the cost of moving from point A to point B?
• What are all possible paths going from point A to point B under a certain cost?
• What is the longest path between A and B that doesn't repeat points?
• Is the graph a directed acyclic graph?
• What cycles are in this graph? (A cycle is a sequence of nodes that form a circle, without repeating points.)
• What is the longest cycle?
• What is the shortest cycle?

These are all reasonable questions to ask about the graph stored in an AStar class. Are we going to put all these algorithms in a class named after only one of them?

[DevJac]

Another problem with AStar2D and friends is that they store weighted vertices and plain edges. That is, the vertices have weights, and the edges do not have weights.

How would you represent the following given that data structure?

Let's say I have 3 vertices, A, B, and C arranged in a triangle. Let's say it's part of a game or something, whatever. Moving from A to B costs 1 point, moving from A to C costs 1 point, but moving from B to C costs 2 points.

How would you represent this situation in the AStar2D data structure? You can't, not in a very natural way at least. (The cost functions can be overridden, so technically can do anything I suppose.)

Graphs would be better stored as plain vertices and weighted edges. That is, the edges should have a weight, not the vertices.

[dsaltares]

Rather than deprecating AStar, for the sake of backwards compatibility, we could do something else.

We could create Graph2D and Graph3D classes that purely hold data. Then we could have AStar classes and other functions/classes that make use of the Graph data structure and provide different algorithms.

I guess the drawback is that different algorithms could have different performance profiles and therefore benefit from slightly different data structure implementations.

[DevJac]

That design decision would require us to classify various algorithms. For instance:

Is finding the shortest path between A and B an AStar algorithm? Of course, that's classic AStar.

Is finding all possible shortest paths between A and B (because there might be ties) an AStar algorithm? Probably, maybe.

Is finding the 10 shortest paths an AStar algorithm? Maybe.

Is finding the shortest cycle in the graph an AStar algorithm? Probably not?

There's advantages to classifying various algorithms into buckets ("this is AStar, but this isn't"), but there's also advantages to just having a flat collection of algorithms / functions with good documentation.

[NathanNgo]

@dsaltares would there be any benefit to differentiating between Graph2D and a Graph3D? A representation of a graph could abide both 2D and 3D, right?

[dsaltares]

They have to reference Vector2 and Vector3 data points. However, I guess this can be achieved via Variant as shown here #3848.

[NathanNgo]

Fair point. Would it be worthwhile having a more generalised graph datastructure? Rather than graph data representing points in space, we could have user-defined properties to conduct the algorithms on, or is that not particularly worth the effort in terms of the value we'd get out of it?

[Zireael07]

This has already been requested and discussed in #3848

[glasswings]

I was going to oppose this on the grounds that NavigationServer has a lot more state than just a graph, but in the interest of being less wrong I opened core/math/a_star.cpp

And, huh, it is just a graph. Why is it in core anyway? Grandfathered in I guess, it was added in 2016.

My perspective is that I like to do Advent of Code from scratch each year, and each year I end up with a messy little graph library because of course I do. So I feel that it's relatively easy to take the idea of "do graph stuff" and modularize it as an extension. That's a perfect chance to fix things like edge weights vs vertex weights (yes, edge weights make more sense to me) and also to see which other developers are interested. Issue 3848 shows there is interest.