Unity - запуск алгоритма поиска пути в отдельном потоке

Question

Я реализовал алгоритм поиска пути A* в моей игре Unity 2D. Все работает, но это может привести к сбоям при поиске на широкой карте.

Проблема вызвана циклом while, выполняющимся в основном потоке. Я хочу, чтобы алгоритм мог запускаться в отдельном потоке, чтобы остановить запуск игры при запуске функции.

Мое понимание сопрограмм состоит в том, что их лучше использовать для последовательных функций, а не для сложных вычислений, подобных этому. Функция должна возвращать значение или использовать ссылки, чтобы прикрепить значение.

Как я могу реализовать этот тяжелый для CPU расчет, не блокируя основной поток? Т.е. многопоточность?

РЕДАКТИРОВАТЬ:

Текущая реализация сопрограмм, как указал Гейзенбаг.

Неполное извлечение из "тяжелой функции вычислений", которая должна распространяться в течение нескольких кадров даже на рабочие нагрузки.

//if the daemon is currently searching
public bool Searching;

//Create list for the algorithm
Pathfinding_Path Path = new Pathfinding_Path();
List<Pathfinding_Point> OpenList = new List<Pathfinding_Point>();
List<Pathfinding_Point> ClosedList = new List<Pathfinding_Point>();

//Agent is the object that shall pathfind, position is goal, callback
public IEnumerator Pathfind(GameObject Agent, Vector3 Position, Func<Pathfinding_Path,Vector3, bool,bool> Callback)
{
    //Abort if already searching
    if (Searching)
        yield break;

    Searching = true;

    //If the target position is not clear, abort
    if (!IsClear(Position))
    {
        Searching = false;
        yield break;
    }

    //Get the size of the agent
    Vector3 AgentSize = GetSize(Agent);

    //Start the algorithm
    Pathfinding_Point start = CreatePoint(AgentSize, Agent.transform.position, Position, 0);
    //Get possible steps from the first position
    CreateAdjacent(start, Position);
    //Add the node to the search tree
    OpenList.Add(start);

    //Keep track of how many iterations the function has ran (to not keep on going forever)
    int iterations = 0;

    //If there is an object to visit and the number of iterations is allowed
    while (OpenList.Count > 0 && iterations < 250)
    {
        iterations++;

        //Get the best node and visit it
        Pathfinding_Point point = GetBest(OpenList);
        OpenList.Remove(point);
        ClosedList.Add(point);    

        //Add all neighbors to the search tree
        foreach (Pathfinding_Point adjacent in point.Adjacent)
        {
            if (!ClosedList.Contains(adjacent))
            {
                if (!OpenList.Contains(adjacent))
                {
                    adjacent.Parent = point;


                    //The goal position is near, this is goal
                    if (Vector3.Distance(adjacent.Position, Position) <= AgentSize.sqrMagnitude * 0.5f)
                    {
                        //Add the final point to the path
                        Path.Add(adjacent);

                        //Get the last point
                        Pathfinding_Point step = Path.Points[0];
                        //Track backwards to find path
                        while(step.Parent != null){
                            Path.Add(step.Parent);
                            step = step.Parent;
                        }

                        Path.Finalize();

                        //Return the final path somehow (preferably using a callback method)
                        Callback(Path, Position, false);
                        Searching = false;
                        //Don't run the function no more
                        yield break;
                    } 
                    else if (IsClear(adjacent))
                    {
                        //Add to search tree
                        CreateAdjacent(adjacent, Position);
                        OpenList.Add(adjacent);
                    }
                }
                else
                {
                    //If the score is lower this way, re-calculate it
                    if (point.G + 1 < adjacent.G)
                    {
                        adjacent.G = point.G + 1;
                        adjacent.F = adjacent.G + adjacent.H;
                    }
                }
            }
        }
    }

    //If there are no more ways to go
    if(OpenList.Count == 0)
        yield break;

    //Here, the search has exceeded its limit on 250 iterations and shall continue after a small delay
    yield return new WaitForSeconds(0.005f);
    //The callback will run this function again, until the goal is reached or if there are no more nodes to visit
    Callback(Path, Position, true);
}

Обратный вызов, который должен обрабатывать различные случаи, которых может достичь функция поиска

//Path to use if it succeded, position that was the initial target, if the search is not yet finished and should be continued
bool GetPath(Pathfinding_Path Path, Vector3 pz, bool Continue)
{
    //Run the function again with the same parameters as the first time
    if (Continue)
    {
        StartCoroutine(Pathfinder.Pathfind(gameObject, pz, GetPath));
    }
    else if (Path.Points.Count > 0)
    {
        //A path has been found
        InvestigatePath = Path;
    }

    return true;
}

Answer 1

В конечном итоге вы можете использовать потоки как обычно в C#. Дело в том, что это не удобное решение, потому что вам нужно синхронизировать поток с циклом двигателя. Это не может быть тривиальным.

Мое понимание сопрограмм состоит в том, что их лучше использовать для последовательных функций, а не для сложных вычислений, подобных этому.

Это неправда. Одна из основных целей сопрограмм (они являются просто блоками итераторов) состоит в том, чтобы распределить вычисления по времени (несколько кадров), чтобы избежать икоты. Это форма совместной многозадачности, так что вы получите практически все преимущества многопоточности без усложнения синхронизации, потому что сопрограммы будут выполняться сразу после завершения основного цикла Обновление сценариев.

Используя сопрограммы, вы несете ответственность за то, сколько вычислений будет выполняться в каждом кадре, поэтому вы должны организовать свой код для поддержания стабильной частоты кадров. В случае поиска пути может быть что-то вроде этого:

IEnumerator PathFinding()
{
  while(!goalNodeReached)
  {
    VisitMaxNodes(maxNodesToVisit); // this function visit only a subset of the graph each frame
    yield return null;
  }
}

Answer 2

Вы должны иметь возможность создавать новый поток обычным способом и выполнять свои вычисления, пока новый поток не должен взаимодействовать с самим Unity, есть довольно много способов, которыми это может быть выполнено, но трудно сказать, какой из них использовать. В прошлый раз, когда я использовал его, Unity не поддерживал некоторые функции языка.NET 4.0, такие как Задачи, но это могло измениться.