Multithread Pathfinding, Unit can't receive path array result,MultiThread Pathfinder, Unit can't receive the path array

Question

I have a pathfinder program using A* that i made following a tutorial. It works fine until i tried to make it multithread using async Task. The Thread works and the path is calculated, but when the path result is being passed to the Unit object, for some resaon only one or two Unit that receive the path array. where did i do wrong ?

ThreadRequestManager :

 public class ThreadRequestManager : MonoBehaviour {
 
     Queue<PathResult> results = new Queue<PathResult>();
 
     static ThreadRequestManager instance;
     ThreadPathfinding pathfinding;
 
     private void Awake()
     {
         instance = this;
         pathfinding = GetComponent<ThreadPathfinding>();
     }
 
     private void Update()
     {
         if (results.Count > 0)
         {
             int itemsInQueue = results.Count;
            
             lock (results)
             {
                 for(int i = 0; i < itemsInQueue; i++)
                 {
                     PathResult result = results.Dequeue();
                     result.callback(result.path, result.success);
                 }
             }
         }
     }
 
     public static async Task RequestPath(PathRequest request)
     {
         await Task.Run(() => instance.pathfinding.FindPath(request, instance.FinishedProcessingPath));
     }
 
     public void FinishedProcessingPath(PathResult result)
     {
         lock(results)
         {
             results.Enqueue(result);
         }
     }
 
 }
 
 public struct PathResult
 {
     public Vector3[] path;
     public bool success;
     public Action<Vector3[], bool> callback;
 
     public PathResult(Vector3[] path, bool success, Action<Vector3[], bool> callback)
     {
         this.path = path;
         this.success = success;
         this.callback = callback;
     }
 }
 public struct PathRequest
 {
     public Vector3 pathStart;
     public Vector3 pathEnd;
     public Action<Vector3[], bool> callback;
 
     public PathRequest(Vector3 _start, Vector3 _end, Action<Vector3[], bool> _callback)
     {
         pathStart = _start;
         pathEnd = _end;
         callback = _callback;
     }
 }

Units :

 public class ThreadUnits : MonoBehaviour {
 
     public Transform target;
     float speed = .5f;
     public Vector3[] path;
     int targetIndex;
 
     // Use this for initialization
     void Start()
     {
         ThreadRequestManager.RequestPath(new PathRequest(transform.position, target.position, OnPathFound));
     }
 
     public void OnPathFound(Vector3[] newPath, bool pathSuccess)
     {
         if (pathSuccess)
         {
             path = newPath;
             // FollowPath();
             StopCoroutine("FollowPath");
             StartCoroutine("FollowPath");
         }
     }
 
     IEnumerator FollowPath()
     {
         Vector3 currentWaypoint = path[0];
         while (true)
         {
             if (transform.position == currentWaypoint)
             {
                 targetIndex++;
 
                 if (targetIndex >= path.Length)
                 {
                    yield break;
                 }
                 currentWaypoint = path[targetIndex];
             }
             transform.position = Vector3.MoveTowards(transform.position, currentWaypoint, speed);
             yield return null;
         }
     }
     public void OnDrawGizmos()
     {
         if (path != null)
         {
             for (int i = targetIndex; i < path.Length; i++)
             {
                 Gizmos.color = Color.black;
                 Gizmos.DrawCube(path[i], Vector3.one);
                 if (i == targetIndex)
                 {
                     Gizmos.DrawLine(transform.position, path[i]);
                 }
                 else
                 {
                     Gizmos.DrawLine(path[i - 1], path[i]);
                 }
             }
         }
     }
 }

Pathfinder :

 public class ThreadPathfinding : MonoBehaviour {
 
     Grid grid;
 
     void Awake()
     {
         grid = GetComponent<Grid>();
     }
 
     public void  FindPath(PathRequest request, Action<PathResult> callback)
     {
         Stopwatch sw = new Stopwatch();
         sw.Start();
 
         Vector3[] waypoint = new Vector3[0];
         bool pathSuccess = false;
 
         Node startNode = grid.NodeFromWorldPoint(request.pathStart);
         Node targetNode = grid.NodeFromWorldPoint(request.pathEnd);
 
         print("thread :" + Thread.CurrentThread.ManagedThreadId);
 
         if (startNode.walkable && targetNode.walkable)
         {
             Heap<Node> openSet = new Heap<Node>(grid.MaxSize);
             HashSet<Node> closedSet = new HashSet<Node>();
             openSet.Add(startNode);
 
             while (openSet.Count > 0)
             {
                 Node currentNode = openSet.RemoveFirst();
                 closedSet.Add(currentNode);
 
                 if (currentNode == targetNode)
                 {
                     sw.Stop();
                     print("path found: " + sw.ElapsedMilliseconds);
                     pathSuccess = true;
                     break;
                 }
 
                 foreach (Node neighbour in grid.GetNeighbours(currentNode))
                 {
                     if (!neighbour.walkable || closedSet.Contains(neighbour))
                     {
                         continue;
                     }
                     int newMovCostToNeighhbour = currentNode.gCost + GetDistance(currentNode, neighbour);
                     if (newMovCostToNeighhbour < neighbour.gCost || !openSet.Contains(neighbour))
                     {
                         neighbour.gCost = newMovCostToNeighhbour;
                         neighbour.hCost = GetDistance(neighbour, targetNode);
                         neighbour.parent = currentNode;
 
                         if (!openSet.Contains(neighbour))
                         {
                             openSet.Add(neighbour);
                         }
                         else
                         {
                             openSet.UpdateItem(neighbour);
                         }
                     }
                 }
             }
         }
         if (pathSuccess)
         {
             waypoint = RetracePath(startNode, targetNode);
         }
         callback(new PathResult(waypoint, pathSuccess, request.callback));
     }
 
     Vector3[] RetracePath(Node startNode, Node endNode)
     {
         List<Node> path = new List<Node>();
         Node currentNode = endNode;
 
         while (currentNode != startNode)
         {
             path.Add(currentNode);
             currentNode = currentNode.parent;
         }
         Vector3[] waypoints = SimplifyPath(path);
         Array.Reverse(waypoints);
         return waypoints;
     }
 
     Vector3[] SimplifyPath(List<Node> path)
     {
         List<Vector3> waypoints = new List<Vector3>();
         Vector2 directOld = Vector2.zero;
 
         for (int i = 1; i < path.Count; i++)
         {
             Vector2 directNew = new Vector2(path[i - 1].gridX - path[i].gridX, path[i - 1].gridY - path[i].gridY);
             if (directNew != directOld)
             {
                 waypoints.Add(path[i-1].worldPosition);
             }
             directOld = directNew;
         }
         return waypoints.ToArray();
     }
 
     int GetDistance(Node nodeA, Node nodeB)
     {
         int disX = Mathf.Abs(nodeA.gridX - nodeB.gridX);
         int disY = Mathf.Abs(nodeA.gridY - nodeB.gridY);
 
         if (disX > disY)
             return 14 * disY + 10 * (disX - disY);
         return 14 * disX + 10 * (disY - disX);
     }
 }

Answer 1

Best Answer

Answer by Bunny83 · Jul 26, 2018 at 11:33 PM

Well, is your "pathfinding" class even thread safe? We can see that you have only one instance of your path finding class that is reused in every request. Are you sure that the FindPath class does not use / modify any shared resources?

edit

Apart from your problem (which we can't solve without knowing the implementation of your pathfinding) locks should generally be hold only as long as necessary. In your case you should just pull the results into a second collection and release the lock. After that you can actually process the results outside the lock.

Also even you have a lock in place you still are up for a race condition because you read the itemsInQueue before you lock the results. So in between reading the Count and entering the lock another thread could add another result. This is not really an issue in your case as the new missed result would simply be processed the next frame. However it's generally just a bad design. You really need to be careful when using threading.

Finally while a Queue<> Is quite handy when you dynamically want to queue elements and dequeue them. However in case of a pure transfer queue a simple List will work as well. The Queue uses internally a ring buffer which is unnecessary since when you process the results you always empty the queue. So two lists would be the best solution. Something like this:

 List<PathResult> results = new List<PathResult>();
 List<PathResult> results2 = new List<PathResult>();

 private void Update()
 {
     if (results.Count > 0)
     {
         lock (results)
         {
             results2.AddRange(results); // just copy the current results over
             results.Clear(); // clear the list
         }
         foreach(var result in results2) // work on our seperate list outside the lock
         {
             result.callback(result.path, result.success);
         }
         results2.Clear();
     }
 }

Though again, your actual issue is most likely that your pathfinding is not threadsafe.

Add comment · Show 5 · Share

necromancya · Jul 28, 2018 at 07:16 PM 0

Share

Thank you for your answer and input. the list optimization is helpful. Still, i think you're right. my pathfinding class maybe not threadsafe. Cause in the source tutorial that i followed, it uses inline threading, which still run in main thread. So i tried make it parallel, and the problem occur. i'll add my pathfinding class in the question

Bunny83 necromancya · Jul 28, 2018 at 08:33 PM 0

Share

With this approach it is impossible to run two pathfinder in parallel. You directly modity the cost of each node during the pathfinding. However the gCost, hCost and even the parent of each node depends on the current pathfinding task. If two run at the same time on the same nodes they will interfere each other and most likely will mess everything up. This could even end up in a deadlock. If two neighbor nodes get processed by two pathfinders at the same time you could end up with two nodes setting the parent to the other one. So your retrace would just jump between the two infinitely.

You have to impement this pathfinder completely different. You can not store this kind of information directly in the node. You could use a Dictionary which basically "extends" the node with the cost and parent values. If you have a lot nodes (>10k or 100k) the overhead could become an issue. Ins$$anonymous$$d you could store several sets of the costs and parent variables inside each node and give each pathfinding job a certain ID (array index) which set is used by which pathfinder. However this limits the number of parallel pathfinding jobs. Though it doesn't make any sense to use more pathfinding threads than there are cores in the CPU. It's more common to just use a single thread for pathfinding and use a task queue. So you process one task after the other within the same thread.

$$anonymous$$eep in $$anonymous$$d when your nodes can actually change (things like doors, obstacles or just cost changes) should not be done while a pathfinding task is running.

The general concept of threads is very easy to grasp. However the much more difficult and most important thing is to keep an eye on data concurrency. At no point should two threads by allowed to modify the same data. One thread writing other threads reading can work in some cases. However anything that doesn't involve atomic operations is a problem. For example List.Add is not an atomic operation.

I'm not sure which Heap class you're using for your openlist but keep in $$anonymous$$d that priority sorting can't be done based on instance variables as mentioned above. Everything would becomes way simpler when you just use a single dedicated pathfinding thread with a job queue.

necromancya Bunny83 · Jul 28, 2018 at 09:49 PM 0

Share

wow, your explanation really open my $$anonymous$$d. yes, the pathfinding task that run in the same nodes made the value of that node become messed up. if the path and nodes of each pathfinding task not interfere with each other, all is work. Now i really know where did i do wrong.

Yeah, using only one thread to do all the pathfinding calculation is the easy way. But, my assignment is to use multiple thread that run asynchronously. Is there any example how to write the thread safe A* pathfinder ?

Show more comments

Multithread Pathfinding, Unit can't receive path array result,MultiThread Pathfinder, Unit can't receive the path array

1 Reply

Your answer

Follow this Question

Related Questions