c# - 如何快速检查网格点之间是否存在任何路径？

Question

我在我的游戏中使用 A-star 算法，如果不存在路径，它会开始检查太多节点(网格很大)，因此，正如我所见，我需要先检查是否存在任何路径。不是找到实际路径，只是检查它是否存在。我能想出的唯一算法是递归地填充 bool 矩阵。应该有更好的方法吧？

可选问题:如果不存在到目标单元格的路径，我如何找到可访问(路径确实存在)并且最接近原始目标的单元格？

Answer 1

A* 正是这样做的……所以没有明显更好的解决方法(可以在 http://en.wikipedia.org/wiki/Shortest_path_problem 中找到文章链接)

如果您可以进行预处理，您可以为所有点着色，以便可以到达的对具有相同的颜色。如果颜色与没有路径不同，则稍后您将获得 2 分。

要找到闭合点，您可以测量具有相同颜色的点的半径，然后开始寻找最接近该半径的路径。