一种独立线程上的路径查找算法

Question

我已经在我的统一2D游戏中实现了一个A*路径查找算法。一切正常，但当搜索一张大地图时，它会导致搭便车。

这个问题是由主线程上执行的While循环造成的.我希望算法能够在一个独立的线程上运行，以阻止游戏在函数运行时变得无力。

我对协同学的理解是，它们更适合用于顺序函数，而不是像这样的繁重计算。函数必须返回一个值或使用引用来附加一个值。

如何在不阻塞主线程的情况下实现这个CPU重的计算？即多线程？

编辑：

如Heisenbug所指出的那样，协同协作机制的当前实现。

从“繁重的计算函数”中提取的不完全，应该在许多帧中展开，甚至是工作负载。

//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#。关键是，这不是一个方便的解决方案，因为您需要将线程与引擎循环保持同步。这可能不是微不足道的事情。

我对协同学的理解是，它们更适合用于顺序函数，而不是像这样的繁重计算。

这不是真的。协同(它们只是迭代器块)的主要目标之一是将计算扩展到一段时间(多帧)，以避免打嗝。这是一种协作多任务处理的形式，因此您几乎可以从线程处理中获得所有好处，而不需要复杂的同步，因为coroutines 将被执行是在脚本的主循环更新完成之后完成的。

使用协同机制，您将负责执行每一帧的计算量，因此需要您组织代码以保持稳定的帧速率。在寻找路径的情况下，可能是这样的：

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

Answer 2

您应该能够按照惯例生成一个新线程，并执行您的计算，只要新线程不必与团结本身交互，就有很多方法可以完成这一任务，但很难说要使用哪一个线程。上一次我使用它时，团结并不支持一些.NET 4.0语言特性，比如任务，但这可能已经改变了。