Add an AStar function to get partial path if end point is unreachable

[giulianob]

Describe the project you are working on: 2d tile based game where character primarily walks through point and click.

Describe the problem or limitation you are having in your project: If the player clicks on a tile that they cannot reach the current A* implementation will just return an empty path. I would like the player to walk as close as possible to wherever was clicked instead. There is the "get_closest_point" function but it doesnt help when the player clicks on a point that is is the AStar grid but is not currently reachable from the player's position.

Describe how this feature / enhancement will help you overcome this problem or limitation: AStar will allow returning partial paths which would help the movement in my game tremendously. Right now I will probably have to replace with another AStar implementation that supports this.

Show a mock up screenshots/video or a flow diagram explaining how your proposal will work:

Assume that the top-left green square is the player and the black squares are walls. If I were to click on the bottom-right dark green square then currently AStar should just not return a path at all. Instead, I would like for it to return the path that leads the player to the purple square since that's the closest position that the player can reach.

Describe implementation detail for your proposal (in code), if possible: I believe this is a matter of keeping track of the node with the lowest "estimated cost" during the _solve function of AStar and returning a path to that node if it doesn't find a path to the goal. This could be another function like get_partial_point_path or potentially a bool/enum passed into the current get_point_path function.

If this enhancement will not be used often, can it be worked around with a few lines of script?: No, I would have to re-implement or use a completely different A* implementation.

Is there a reason why this should be core and not an add-on in the asset library?: This is just improved functionality on the current A* class.

[Ariorick]

Hmm. I actually use that Navigation2D returns empty path for unreachable points to figure out if actor can't go there

[KnightNine]

has there been any developments on this or is there an alternative method for doing this?

[Calinou]

has there been any developments on this or is there an alternative method for doing this?

Not that I know of. There's a new NavigationServer in 4.0, but it doesn't cover AStar functionality, only navmeshes.

[Ariorick]

Honestly now that i've got more experience i can think of a solution Instead of making black squares unpassable, you can make them very costly, so if there was any other way around, it would choose this way. But if this point can't be reached through grey squares, it will make a path through black squares. You can check resulting array if it has a black point and cancel movement when an actor reaches it. Although you should know that on a big map this can be very time consuming to check every other path before choosing black tiles. You can try to balance it's weight so it would give up and settle on black ones before checking every other path

[SRowick]

Any more solutions?

[KnightNine]

Any more solutions?

Pray to the Godot devs to implement this handy feature.

I didn't use Ariorick's suggestion because statically occupied positions on my map were not included on the Astar map, so I would need to have a separate map containing all static occupied positions as high cost positions instead which i would also need to update non-static occupied positions for. And I didn't want to go that in depth for this one issue, also there was the possibility that the AI actor using this system would travel to a position that's technically closest but also isolated and hard to reach.

I think what I did was: when no valid position within range of the desired area existed for the actor to travel to, I would shift the desired area one position towards the actor, cut the positions already tested by Astar from that area, then check for a valid position to travel to within this new area, and repeat that process if no position is found.

[KnightNine]

turns out my last solution was extremely inefficient for my 3D grid, so I added this feature to my version of astar.cpp here

Just use the get_proximity_id_path_of_last_pathing_call() function after calling get_id_path() or get_proximity_point_path_of_last_pathing_call() after calling get_point_path() if the pathing call could not reach the end point, and you will get an incomplete path to the closest point.

however the end point still needs to be a valid point when calling the pathing function in order to get the partial path.

There's a bunch of extra features in this modified Astar code but you can still use it as you would normally.

[fpinchon]

Any development on this?

Any chance we could get an official implementation of @KnightNine's "GetProximityPointPathOfLastPathingCall()"? Or even add a "allowPartialPathResult" boolean as a parameter so it returns the "best" path it could find if no complete path could be found.

Seems like a fairly frequent use case with no clean workaround, and shouldn't be too hard to develop.

[fpinchon]

This issue was reported a while ago so there's a chance it will never be seen by anyone (unless specifically looking for it). Is there any way to bump this issue further than by leaving a comment? Open a new issue (duplicate)?

I would really like to have a clean solution and avoid having to implement my own pathfinding solution. For now AStar2D works really well, it's simply missing a simple "GetClosestPath" function...

[Calinou]

cc @smix8

This issue was reported a while ago so there's a chance it will never be seen by anyone (unless specifically looking for it). Is there any way to bump this issue further than by leaving a comment? Open a new issue (duplicate)?

We encourage people to step up and implement the feature themselves (or pay someone to do it). If you are interested in working on this, please join the Godot Contributors Chat :slightly_smiling_face:

[KnightNine]

@fpinchon You are invited copy my code and translate my features to Astar2D and format them for a PR (as I have only implemented them for Astar3D so far).

Though you'd need to create 4 separate PRs: one for this feature, one for set_as_bulk_array() described here, one for the point layers, and one for octants. Unless the mods would allow for an Astar Overhaul in one PR.

My generic octant creation code isn't entirely done either, I want to allow for dynamic splitting of octants using a user defined function within GDscript to define the formation of octants (same way as set_straight_line_function() which I use to allow testing for straight paths if possible, considering that this function would vary based on the type of grid and the way that it is stored). Right now the way octant pathing adapts to disabled astar points is a bit jank but more efficient than not having it at all.

This branch contains all of my custom changes to 4.X which I sync from time to time. It lacks the changes to AStar3D.xml and AStar2D.xml to document the features/functions I've added and make them visible in the editor.

[Shiva-Shadowsong]

Still waiting for an official addition of such a feature.

In the meantime, one workaround I found to achieve a similar result is by checking if the point is solid and disabling its solid state to calculate a path to it, then making it solid again.

The path you receive will be the path to that blocked point, but you can just pop_back the last result from the array to exclude that last point, leaving you with a closest path to it.

Still, this is an ugly hack and will only work if there is an unblocked point anywhere next to the checked point. If the checked point is completely surrounded by other blocked points, you still get no result, so you'd have to account for that.

var usedHack = false

if aStar.is_point_solid(toCoords):
  aStar.set_point_solid(toCoords, false)
  usedHack = true

var path = aStar.get_id_path(fromCoords, toCoords, true)

if usedHack:
  aStar.set_point_solid(toPosCoords, true)
  path.pop_back()

[Calinou]

Still waiting for an official addition of such a feature.

This was implemented in 4.3: https://github.com/godotengine/godot/pull/88047

Check it out in 4.3.beta1 🙂

[Shiva-Shadowsong]

Still waiting for an official addition of such a feature.

This was implemented in 4.3: godotengine/godot#88047

Check it out in 4.3.beta1 🙂

Right, thanks for pointing out.

I noticed the presence of this allow_partial_path parameter in the documentation, unfortunately this doesn't seem to work if the target coordinates are a tile that's already set to blocked. If it's a non-blocked tile that's surrounded by blocking ones, then it works, but I was hoping to be able to give it a blocked position too and it would figure out the closest available one.

Allow me to illustrate - As it is right now with allow_partial_path - Can only request path to this unblocked tile in the middle of those trees, others don't return anything.

But this is what I would expect:

https://github.com/godotengine/godot-proposals/assets/15309863/504dc3ba-888e-40cc-9d6f-06ea5f73ab0b

Maybe it was intended not to return anything when a blocked coordinate is requested, but that isn't necessarily clear from the documentation nor have I seen the author of that PR talk about it.

[Calinou]

@Shiva-Shadowsong Please continue the discussion in https://github.com/godotengine/godot/issues/93409 🙂