-
-
Notifications
You must be signed in to change notification settings - Fork 97
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add an AStar function to get partial path if end point is unreachable #277
Comments
Hmm. I actually use that Navigation2D returns empty path for unreachable points to figure out if actor can't go there |
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. |
Honestly now that i've got more experience i can think of a solution |
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. |
turns out my last solution was extremely inefficient for my 3D grid, so I added this feature to my version of Just use the 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. |
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. |
This issue was reported a while ago so there's a chance it will never be seen by anyone (unless specifically looking for it). I would really like to have a clean solution and avoid having to implement my own pathfinding solution. |
cc @smix8
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 🙂 |
@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 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 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. |
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() |
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 me to illustrate - But this is what I would expect: 6BQsu7i.1.mp4Maybe 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. |
@Shiva-Shadowsong Please continue the discussion in godotengine/godot#93409 🙂 |
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 likeget_partial_point_path
or potentially a bool/enum passed into the currentget_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.
The text was updated successfully, but these errors were encountered: