Multithreading doesn't work if I start more than 1 other thread

So I am actually trying to implement my own version of the A* algorithm and to improve performance I want the actual pathfinding for every seeker to be multithreaded:

It works pretty well until the moment I activate a second seeker:

Like you can see it stops after 15 iterations in the algorithm and the first started thread gets kind of killed by the following.

I am using the C# ThreadPool class for my thread management but I tried also to use the Thread class. It is the same result.

Implementation of my threading:

public static void RequestPath(PathRequest _request)
{
    Debug.Log("Queueing PathRequest...");
    ThreadPool.QueueUserWorkItem(instance.StartThreadedPathfinding, _request);
}

The called method:

private void StartThreadedPathfinding(object _stateInfo)
{
    PathRequest request = (PathRequest)_stateInfo;
    m_pathfinder.FindPath(request, OnPathFound);
}

And FindPath:

public void FindPath(PathRequest _request, Action<PathResult> _callback)
{
    Debug.Log("Starting A* Algorithm");
    BinaryHeap<Node> openList = new BinaryHeap<Node>(GridSize);
    HashSet<Node> closedList = new HashSet<Node>();

    Node startNode = _request.Start;
    Node targetNode = _request.Target;

    bool success = false;

    openList.Add(startNode);

    while (openList.Count > 0)
    {
        Debug.Log(Thread.CurrentThread.ManagedThreadId + ": " + Thread.CurrentThread.ThreadState.ToString());
        Node currentNode = openList.RemoveFirst();

        if (currentNode == targetNode)
        {
            // TODO: Path found -> _callback
            success = true;
            Debug.Log("Path found");
            _callback(new PathResult(null, success, _request.Callback));
            return;
        }

        closedList.Add(currentNode);

        foreach (Node neighbour in currentNode.m_neighbours)
        {
            if (closedList.Contains(neighbour))
            {
                continue;
            }

            int tentativeG = currentNode.m_gCost + GetDistance(currentNode, neighbour);
            if (openList.Contains(neighbour) && tentativeG > neighbour.m_gCost)
            {
                continue;
            }

            neighbour.m_parent = currentNode;
            neighbour.m_gCost = tentativeG;
            neighbour.m_hCost = GetDistance(neighbour, targetNode);

            if (openList.Contains(neighbour))
            {
                openList.UpdateItem(neighbour);
            }
            else
            {
                openList.Add(neighbour);
            }
        }
    }

    // TODO: No path to the target exists -> calculate some path
    success = false;
    Debug.Log("No existing path");
    _callback(new PathResult(null, success, _request.Callback));
    return;
}

RequestPath and StartThreadedPathfinding are in a class called PathRequestManager and FindPath is in an other class called Pathfinder.

Another point is that the threads don’t just stop because of an error or sth like that but are still somehow running I think because after I started the scene in Unity I have to kill the Unity-process in the taskmanager because sth is stuck (CPU-Load is always about 80% when I have to do that)
Thought about deadlocks but couldn’t find any.

I would be glad if someone could help me here and if you need more information about the source code feel free to ask :slight_smile:

PS: I also posted this question on stackoverflow: Stackoverflow Question

Solving multithreading issues is not easy especially when we don’t see the whole code. However i see one big conceptional problem: You seem to share the same data between multiple threads. Specifically your “Nodes”.

On the one hand your node structure could theoretically be changed from the main thread while another thread is using that data. This could lead to unpredictable results.

On the other hand each of your worker threads seems to set certain fields on the nodes (m_parent, m_gCost, m_hCost). That means they most likely will corrupt the data set by other threads.

You also don’t seem to reset any of those values when you’re done.

Further more you have to be careful what you’re doing inside your callbacks. Those callbacks will run on the worker thread(s) so you can’t use the Unity API in those callbacks.

If you want / need to work on your actual node tree you want to implement the necessary per-node-data inside your worker thread (using a dictionary to associate a utility class with each node). So nobody is altering the shared data. However you still might have the problem that the main thread may alter something in the node tree which might cause problems in your worker threads. Though we can’t tell as we only see a small piece of your setup.