c++ - 用于多个目标的 2D 瓦片 map 寻路

Question

我正在尝试用 C++ 创建一个简单的基于网格的游戏。寻路是其中必要的部分。我一直在寻找，但没有我要找的东西。

规则很简单。有一张 map 。尺寸一般不超过 100 x 100 block 。 1是地砖，0是墙。不允许沿对角线移动，因此每个网格只有 4 个方向。但是，大多数目标不止一个。我想找到最近的路。请记住，我们不能只计算，哪一个是最近的距离公式。距离较短的目标可以有更长的距离，因为有墙。我认为使用一种已知算法并针对每个目标重复并不是一个好主意，因为它会变慢。

你怎么看？我该怎么办？

Answer 1

这不是什么大问题。添加一个与所有真实目标距离为 1 的假设结束节点 E，并搜索到 E 的最佳路径。路径上的最后一个节点将是这些真实目标之一。