我目前正在尝试在我的2D横版卷轴游戏中使用A*路径查找算法，这款游戏的世界是程序化生成的（类似于《泰拉瑞亚》的地形）。

我使用了这个资源：http://www.redblobgames.com/pathfinding/a-star/introduction.html

主要参考了以下伪代码：

frontier = PriorityQueue()frontier.put(start, 0)came_from = {}cost_so_far = {}came_from[start] = Nonecost_so_far[start] = 0while not frontier.empty():   current = frontier.get()   if current == goal:      break   for next in graph.neighbors(current):      new_cost = cost_so_far[current] + graph.cost(current, next)      if next not in cost_so_far or new_cost < cost_so_far[next]:         cost_so_far[next] = new_cost         priority = new_cost + heuristic(goal, next)         frontier.put(next, priority)         came_from[next] = current

我的问题是：在一个大型程序化生成的2D横版卷轴游戏世界中，如何选择前沿节点？通往特定瓦片的路径可能距离很远，显然遍历整个地图是不明智的。

我希望能高效地完成这个任务，任何帮助都将不胜感激！

回答：

我从未听说过它被称为“前沿”，一直都是“开放列表”，你可以将所有可以到达的节点——邻居——放入其中。

在性能方面，我使用过以下方法：

1) 将计算放在另一个线程中：（不是协程）查看这里的ThreadedJobhttp://answers.unity3d.com/questions/357033/unity3d-and-c-coroutines-vs-threading.html 这会造成延迟——结果会在你调用后的几帧内出现，你可以：a) 只是等待；b) 开始朝目标的大致方向移动，并在结果准备好后更改路径；c) 即使剩余部分尚未准备好，也可以前往路径的第一个节点。

2) 缓存结果：Dictionary<Vector4, List<Vector2>> pathCache; 其中键Vector4是startPosX,startPosY,finishPosX,finishPosY，值List是A*的结果。由于路径是对称的，当你寻找从A到B的路径时，你还应该检查缓存中是否有从B到A的路径，并反转路径。