如何加快我的寻路算法

如何加速代码？我做错了什么？我有一个二维的细胞阵列，用来存储关于细胞内物质的数据。我有一张只有100x100的地图，上面有10个殖民者，这已经造成了冻结。尽管我的比赛很粗糙。

我什么时候应该为殖民者建造一条路线？他走的每一步？因为如果一堵意想不到的墙出现在他的路上。然后他将不得不立即改变路线。

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class PathFinding : MonoBehaviour
{
    public MainWorld MainWorld;
    public MainWorld.Cell CurrentWorldCell;
    public MainWorld.Cell NeighborWorldCell;
    public List<MainWorld.Cell> UnvisitedWorldCells;
    public List<MainWorld.Cell> VisitedWorldCells;
    public Dictionary<MainWorld.Cell, MainWorld.Cell> PathTraversed;
    public List<MainWorld.Cell> PathToObject;
    public List<MainWorld.Cell> FindPath(MainWorld.Cell StartWorldCell, string ObjectID)
    {
        CurrentWorldCell = new MainWorld.Cell();
        NeighborWorldCell = new MainWorld.Cell();
        UnvisitedWorldCells = new List<MainWorld.Cell>();
        VisitedWorldCells = new List<MainWorld.Cell>();
        PathTraversed = new Dictionary<MainWorld.Cell, MainWorld.Cell>();
        UnvisitedWorldCells.Add(StartWorldCell);
        while (UnvisitedWorldCells.Count > 0)
        {
            CurrentWorldCell = UnvisitedWorldCells[0];
            NeighborWorldCell = MainWorld.Data[CurrentWorldCell.Position.x, CurrentWorldCell.Position.y + 1];
            CheckWorldCell(CurrentWorldCell, NeighborWorldCell, ObjectID);
            NeighborWorldCell = MainWorld.Data[CurrentWorldCell.Position.x + 1, CurrentWorldCell.Position.y];
            CheckWorldCell(CurrentWorldCell, NeighborWorldCell, ObjectID);
            NeighborWorldCell = MainWorld.Data[CurrentWorldCell.Position.x, CurrentWorldCell.Position.y - 1];
            CheckWorldCell(CurrentWorldCell, NeighborWorldCell, ObjectID);
            NeighborWorldCell = MainWorld.Data[CurrentWorldCell.Position.x - 1, CurrentWorldCell.Position.y];
            CheckWorldCell(CurrentWorldCell, NeighborWorldCell, ObjectID);
            UnvisitedWorldCells.Remove(CurrentWorldCell);
            if (CurrentWorldCell.ObjectID == ObjectID)
            {
                return CreatePath(StartWorldCell, CurrentWorldCell);
            }
        }
        return null;
    }
    public void CheckWorldCell(MainWorld.Cell CurrentWorldCell, MainWorld.Cell NeighborWorldCell, string ObjectID)
    {
        if (VisitedWorldCells.Contains(NeighborWorldCell) == false)
        {
            if (NeighborWorldCell.IsPassable == true ||
                NeighborWorldCell.ObjectID == ObjectID)
            {
                UnvisitedWorldCells.Add(NeighborWorldCell);
                VisitedWorldCells.Add(NeighborWorldCell);
                PathTraversed.Add(NeighborWorldCell, CurrentWorldCell);
            }
            else
            {
                VisitedWorldCells.Add(NeighborWorldCell);
            }
        }
    }
    public List<MainWorld.Cell> CreatePath(MainWorld.Cell StartWorldCell, MainWorld.Cell EndWorldCell)
    {
        PathToObject = new List<MainWorld.Cell>();
        PathToObject.Add(EndWorldCell);
        while (PathToObject[PathToObject.Count - 1] != StartWorldCell)
        {
            PathToObject.Add(PathTraversed[PathToObject[PathToObject.Count - 1]]);
        }
        PathToObject.Reverse();
        return PathToObject;
    }
}

在寻路循环的每次迭代中，都会对四个相邻单元格中的每一个进行检查。在每次检查中，您都在搜索VisitedWorldCells列表。如果列表中有许多单元格，这可能是您的第一个问题。接下来，将一个元素添加到一个或三个列表中。处理列表很慢。要创建路径，您需要制作一个列表并添加一组元素。每帧做10次是不合理的。

使用预先分配的二维布尔数组。你知道地图有多大。

bool[,] array = new bool[mapSizeX, mapSizeY];

使用这个，你可以直接用之类的东西检查细胞

if(!VistedWorldCells[14,16])

而不是检查整个VisitedWorldCells列表(根据MainWorld.Cell的类型，这也可能是一个缓慢的比较(。

预分配的数组和直接检查/设置值将使速度加快几个数量级。

据我所知，您的算法是一个简单的广度优先搜索。第一步应该是用队列替换UnvisitedWorldCells列表(通常称为"开放集"(，用hashSet替换VisitedWorldCells列表(通常也称为闭集(。或者只使用二维数组进行恒定时间查找。您还可以考虑使用更紧凑的节点表示，比如一对简单的x/y坐标。

下一个改进步骤是Djikstras最短路径算法。如果你四处搜索，有很多例子可以说明这是如何工作的。这以类似的方式工作，但对未访问的单元格使用优先级队列(通常是最小堆(，这允许指定不同的"成本"。

下一步可能是A*，这是一个寻路的"最佳"算法，但如果你只有100x100个节点，我预计不会有太大的差异。这使用启发式方法来猜测首先访问哪些节点，因此优先级队列不仅使用遍历到节点的成本，还使用估计的剩余成本。

和往常一样，当涉及到性能时，您应该测量和分析代码以发现瓶颈。

何时到路径查找将是一个更复杂的问题。一个相当简单且可能有效的解决方案是创建一次路径，然后按照它进行操作。如果一个节点被阻塞，那么你可以重新进行路径查找。您还可以每隔n秒重新进行寻路，以防出现更好的路径。如果你有多个单元，你可能会引入额外的要求；推动"；挡住部队的去路，在他们穿过狭窄的通道时，试图将一组组部队保持在一个紧凑的小组中等等。你可能会花数年时间考虑每一个可能的特征。

相关内容

最新更新

热门标签：