如何快速检查网格点之间是否存在任何路径
本文关键字：是否 存在 任何 路径 之间 何快速 检查 网格 | 更新日期: 2023-09-27 18:36:13
我在游戏中使用了 A-star 算法，如果不存在路径，它会开始检查太多节点（网格很大），所以，正如我所看到的，我需要先检查是否存在任何路径。不要找到实际路径，只需检查它是否存在。我能想到的唯一算法是递归地淹没一个布尔矩阵。应该有更好的方法，对吧？
可选问题：如果目标单元格不存在路径，如何找到可访问（路径确实存在）且可能最接近原始目标的单元格？
A* 正是这样做的...所以不，没有明显更好的解决方法（文章链接可以在 http://en.wikipedia.org/wiki/Shortest_path_problem 中找到）
如果你可以做预处理，你可以给所有点上色，这样可以到达的对就被涂上了相同的颜色。如果颜色与没有路径不同，则稍后获得 2 分。
要查找接近点，您可以测量具有相同颜色的点的半径，然后开始查找到达该半径的路径。