我正在我的游戏中使用A星算法，如果没有路径存在，它会开始检查太多的节点（网格非常大），所以我认为，我需要先检查是否存在任何路径。不是找到实际的路径，只是检查它是否存在。我能想到的唯一算法是递归地填充一个布尔矩阵。肯定应该有更好的方法，对吧？
可选问题：如果不存在通往目标单元的路径，如何找到一个可访问的单元（存在路径）并尽可能靠近原始目标？
1个回答
3
A*算法正是这样做的...所以没有更好的方法（有关文章链接可以在http://en.wikipedia.org/wiki/Shortest_path_problem中找到）。
如果您可以进行预处理，可以对所有可以到达的点进行着色，使其颜色相同。然后，当您获得2个点时，如果颜色不同，则表示没有路径。
要找到最近的点，您可以测量具有相同颜色的点的半径，然后开始寻找到达该半径最接近的路径。
如果您可以进行预处理，可以对所有可以到达的点进行着色，使其颜色相同。然后，当您获得2个点时，如果颜色不同，则表示没有路径。
要找到最近的点，您可以测量具有相同颜色的点的半径，然后开始寻找到达该半径最接近的路径。
- Alexei Levenkov
2
所以基本上就是，如我所说，递归地填充领域？ - Irdes
@Irdes - 是的 - 只需要做一次（如果有许多不相交的区域，您还可以获得更好的边缘修剪）...只需考虑一下 - 要检查是否存在路径，您需要检查所有点。 有不同的方法来表示这种数据。 考虑在http://gamedev.stackexchange.com上提问，因为您可能会得到更有针对性的答案。 - Alexei Levenkov
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接