Question A* pathfinding to find the closest of a list

I'm struggle to find a solution using A* pathfinding to get the nearest GameObject from a list giving a point. I'm trying something like the below, but the main problem with this approach is that path calculations are async so it can't work unless I can find a way to wait it to calculate and them get access to path's total length. Any suggestions?

Code (CSharp):

1.     public GameObject FindClosestVillager(Transform point)
2.     {
3.         GameObject[] villagers;
4.         villagers = GameObject.FindGameObjectsWithTag("villagers");
5.         GameObject closestVillager;
6.  
7.         foreach (var villager in villagers)
8.         {
9.             Path path = ABPath.Construct(villager.transform.position, point.position, OnPathCalculated);
10.             AstarPath.StartPath(path);
11.  
12.             // test the total length and find the nearest
13.         }
14.  
15.         return closestVillager;
16.     }
17.  
18.     void OnPathCalculated(Path path)
19.     {
20.         print("total length" + path.GetTotalLength());
21.  
22.     }

 

Delegate queue to marshal tasks from other threads to the main thread:

https://forum.unity.com/threads/how...-everytime-it-is-called.1148354/#post-7370375

 

Just a reminder that A* isn't the only path finding algorithm in the world. It's advantage over other pathfinding algorithms apply only in very specific situations.

Path finding algorithms like BFS and Dijkstra allow you to directly find shortest path from single point to every point on the map at the same cost as finding path between pair of points. With small tweak you can even find shortest path from every point of the map to a set of points. Very useful if you have a bunch of villagers which need to return collected resources to nearest warehouse (doesn't matter which one). Floyd-Warshal can even find the shortest path between all the pairs of points, not practical in most situations, but in some very specific ones it can be.

Whether it's faster to run Dijkstra once or A* n times will depend on your specific amount of "villagers" and size of map. But it's a tool you should keep in mind when making a strategy or colony sim style games with large amount of units that need to path find all the time.


If you are you using the asset I think you are, seems like the paid version of it also supports doing one to many or many to many queries I mentioned. It's a bit misleading because even though the asset itself is called "A* pathfinding project" it also implements other pathfinding algorithms.

 

One way to solve this problem would be to use the CompletePathIfPossible method of the Path class to try and complete the path calculation synchronously. This method will return true if the path was successfully calculated and false if it is still being calculated asynchronously.

You can use this method in a loop to continuously check if the path calculation has completed, and then break out of the loop once it has. Here's an example of how you could modify your code to do this:

Code (CSharp):

1. public GameObject FindClosestVillager(Transform point)
2. {
3.     GameObject[] villagers;
4.     villagers = GameObject.FindGameObjectsWithTag("villagers");
5.     GameObject closestVillager = null;
6.     float closestDistance = float.MaxValue;
7.     foreach (var villager in villagers)
8.     {
9.         Path path = ABPath.Construct(villager.transform.position, point.position, OnPathCalculated);
10.         AstarPath.StartPath(path);
11.         while (!path.CompletePathIfPossible())
12.         {
13.             // Wait for the path calculation to complete
14.         }
15.         // Calculate the distance to the target point
16.         float distance = path.GetTotalLength();
17.         // Update the closestVillager and closestDistance if this path is shorter
18.         if (distance < closestDistance)
19.         {
20.             closestVillager = villager;
21.             closestDistance = distance;
22.         }
23.     }
24.     return closestVillager;
25. }
26.  

Note that this approach will block the main thread until the path calculation for each villager has completed, which may not be desired if you have a large number of villagers and the path calculations are expensive. In that case, you may want to consider using a different approach, such as calculating the paths asynchronously and storing the results in a data structure that you can use to find the closest villager later.

 

Thank you all for the replies. I took a look on the A* classes and found a simple solution that worked quite well for my scenario where I don't have too many villagers to test: AstarPath.BlockUntilCalculated(path), as the name says, blocked the code and waited for the path to be calculated.
The final code:

Code (CSharp):

1. public GameObject FindClosestVillager(Transform point)
2.     {
3.         GameObject[] villagers;
4.         villagers = GameObject.FindGameObjectsWithTag("villagers");
5.         GameObject closestVillager = null;
6.         float closestDistance = float.MaxValue;
7.         foreach (var villager in villagers)
8.         {
9.             Path path = ABPath.Construct(villager.transform.position, point.position);
10.             AstarPath.StartPath(path);
11.             AstarPath.BlockUntilCalculated(path);
12.  
13.             float distance = path.GetTotalLength();
14.  
15.             if (distance < closestDistance)
16.             {
17.                 closestVillager = villager;
18.                 closestDistance = distance;
19.             }
20.          
21.         }
22.         return closestVillager;
23.     }