Support Forum

Finding point in given area with shortest path

Hi :slight_smile: Using your plugin in our project, love it very much!

Now I am trying to implement sort of a “player-input assistance”, where it’s likely that I have a better idea where the player is trying to go than the input I’m actually receiving from him.

In essence, I have a grid graph (can have elevation as well, 2 floors), I have a point where player is holding the mouse for navigation (“go here”). And I would like to find a point on graph which has the shortest path to players position. I’d be ok if it was directly the graph node; point in between nodes would be even better but not 100% necessary.

As I imagine the problem in terms of what should be hopefully possible, it likely consists of 2 parts unless there’s a better native way:
1.) retrieve all valid points in an area given by a position and radius
2.) find paths/“on-graph distances” to all given points (1:N), and pick the shortest one
Even better would be, if “2.)” would just exit as soon as it either reaches any of the nodes in given area (area meaning point+radius); or if the shortest path already exceeds a given limit.

Illustration of my problem/goal:

Grid graph nodes = green
Player = blue
Mouse input = grey x
Area of interest = circle/sphere (doesn’t matter much) of given radius around the input
Point I want to find = red (with the shortest path from player of all nodes in area of interest)
// is fine if it was identical to the green point nearby, in case it’s not possible otherwise

I only care about the 1 retrieved point, so it would be perfect if the whole evaluation could exit as early as possible, and I could set a limit (max path length) for early exit, after which I’d handle the situation differently (just take the mouse input as target position, excluding the ‘assist’).

Anyway, would love to know what’s the best way to address this with your A* Pathfinding lib? Thank you!

1 Like

Hi

You might be interested in this page: https://arongranberg.com/astar/docs/pathendingcondition.html

1 Like

Yes that was very helpful :slight_smile:

In the end, I can’t stop the path right after it reaches the radius as in the linked example - in that case the player would always stop at R distance from otherwise correctly inputted position (for example looking at the image above - if player would be standing in the upper right corner, there’s no need to stop him right at the edge of the circle but we can continue to go further to the inputed position). But I can take that point (on the radius circle), and do a few iterations jumping on connected nodes in case any of them are even closer to the target point, and end when I’m not getting any closer anymore.
That is very much fine in my case (kinda small radius compared to the grid density = not many iterations needed to get to the center, pretty much just 2-3 usually) and it ends with great results.

Just “reach a node close enough using A* with the linked “ending condition”, and jump to it’s neighbor that’s the closest to the center (if any), and possibly jump to an even closer one from there…”.
Hopefully the explanation is understandable enough for anyone dealing with the same thing in the future.

Thank you! :slight_smile:

1 Like

got similar requirement. will try this method. Very amazed by the completeness of the plugin! :+1:

1 Like