第一篇。
我为一个Unity游戏项目编写了一个最短路径脚本，虽然它可以运行，但它在大规模应用时变得很慢，以至于在执行时导致Unity崩溃。也就是说，对于单个测试字符，它的工作速度很慢，但是项目需要规模。
我并没有真正遵循任何已知的最短路径技术来创建它，而是我自己做的。它的工作方式是生成一系列递归方法，每个方法都包含一个for循环来探索网络中每个可能的节点，并为每个方法带来一个路径和路径列表。如果找到目标，或者当前路径比已知路径长，或者已经检查了新节点，则该方法终止。
下面是一些代码。我已经排除了最初调用这个递归方法的方法:void ExploreBranch(List<Point> stem, List<List<Point>> masterList, Point target)
{
if (masterList.Count > 0)
{
for (int m = 0; m < masterList.Count; m++)
{
List<Point> thisList = masterList[m];
if (stem.Count + 1 >= thisList.Count)
{
return;
}
}
}
Point lastPoint = stem[stem.Count - 1];
for (int c = 0; c < lastPoint.Connections.Count; c++)
{
List<Point> updatedRoute = new List<Point>(stem);
Point newConnection = new Point();
newConnection = lastPoint.Connections[c];
if (newConnection == target)
{
updatedRoute.Add(newConnection);
masterList.Add(updatedRoute);
return;
}
if (updatedRoute.Contains(newConnection))
{
continue;
}
updatedRoute.Add(newConnection);
ExploreBranch(updatedRoute, inspected, masterList, target);
}
}
所以，基本上这远远不够有效，我无法在这个基本框架内找到改进它的方法。我现在倾向于重新开始，或者尝试真正的实验，但我想我应该先检查这里。
这里的主要内容之一是，我需要保留角色在游戏中需要使用和遵循的实际路径。所以我们不仅需要知道路径有多短，还需要知道实际路径
如有任何意见，不胜感激。
我强烈建议您使用Dijkstra，因为您似乎意识到了这一点。它实现起来相当简单，并且可以扩展到理论上最优的A*。
我真的不理解代码示例，所以我是基于你的算法的描述。如果我误解了什么，我道歉。
考虑一个无限网格，其中单元格按上、右、下、左的顺序计算。其中起始节点位于目标节点的左侧。像你描述的一个简单的深度优先算法会先求顶节点，然后求那个的顶节点，以此类推。因为网格是无限的，所以它永远不会到达目标，即使它们只是彼此相邻。我也不确定它是否真的能保证你的终止条件下最短的路径，因为节点可以通过多条路径到达，而且找到的第一个节点不一定是最便宜的。
像djikstra这样的宽度优先算法会根据与起始节点的距离对评估节点进行排序，因此即使是无限图，它也会很快到达目标。
A*细化将根据到起始节点的距离+估计的剩余距离对评估节点进行排序，这明显更高效。但是它引入了一些复杂性，比如如何进行估计。特别是如果边的权重有很大的变化。还有进一步的改进可以通过使用近似解来提高性能，或者使用一些关于图的额外知识。