DevJac
commented
1 month ago The AStar* classes in general are poorly named and thought out IMO.
The data in an AStar* class is a graph, and there are dozens of useful algorithms that can be run on that graph. We've chosen to name the class that contains the graph after just one of those algorithms.
To illustrate my point another way. If we ever want some Dijkstra based algorithms, are we going to have a Dijkstra2D class, and the data in the Dijkstra2D class will be the same graph data that is in the AStar2D class?
We should have a general Graph object, that contains data about the graph, and implements many different algorithms, one of them being AStar.
m21-cerutti
Describe the project you are working on
A Hexagon 2D Strategy game.
Describe the problem or limitation you are having in your project
First, I would like in my game for players to choose the path they want, if they have the same cost. You can see in the image below one of the problem when it comes to pathfinding and player movement, there is three possible path, and each one could be taken.
After some researches about cost function and experiments, AStar with redefined
_estimate_costand_compute_costdoesn't quite work when it come to choose the path based on player interaction in one only step (like mouse position).Describe the feature / enhancement and how it helps to overcome the problem or limitation
What I would need is to have all possible paths (the X Shortest would work in my case, since all three path have the same cost), after that I could choose the path I want based on some math with the mouse (like choosing the extreme left or right with an axis orthogonal to the direction).
I think it could be usefull in a lot of others edge cases, with grid or hexagon, in 2D or 3D.
Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams
For the API, we could have multiple solutions.
The first, use as usual the AStarPath(for points and cost) get_point_path( int from_id, int to_id ) , that would make the first path, and then a
Array[AStarPath] get_shortest_paths( int from_id, int to_id, float max_cost )where we put the max_cost result from the first call. This would allow keeping part of the API, and do some kind of tweaking and optimisations. Would also allow to directly search paths with a max cost (empty list if none are found) if we want. But it has the downside if misused to be heavy in computation and memory for the second function (if we want all path to a destination with a too much high cost).Would need for that https://github.com/godotengine/godot-proposals/issues/5667 to allow retrieve the path cost.
The second would be to directly give a list of path based on the X shortest ones, and keep one as default (would be the same as the current one). Like
Array[AStarPath] get_shortest_paths( int from_id, int to_id, int max_number = 1 ), like that could be less intensive in computation, even if we would keepmax_numberas low as possible. It have the downside however we can't stop with cost, maybe we could have an optionnalmax_costto avoid worst cases where the second one is cost intensive (like labyrinth), this would be like an hybrid solution with the first one.If this enhancement will not be used often, can it be worked around with a few lines of script?
It would mean to do his own version of AStar, since the current implementation do not allow to reiterate on the result easily. Reiterate on the path given mean to do ourself part of the AStar algorithm.
Is there a reason why this should be core and not an add-on in the asset library?
Could be a pathfinding module, but since AStar2D is inside core, it would remains core.