a-star - 一颗星：找到多个目标中最近的一个

Question

我正在做一个项目，我需要在 2D 网格中找到到最近（许多）目标节点的路径（任何节点中有 8 个连接：N、S、W、E、NW、NE、SW、SE）。途中可能会有墙壁阻挡路径。找到一个目标节点的路径是没有问题的，但是我怎样才能在合理的时间内找到最近的目标呢？我不认为为每个目标节点运行 A* 并获取每条找到要比较的路径的长度是合理的方法，还能怎么做？

A* 是否能够以某种方式找到到最近节点的路径，或者必须以其他方式找到最近的目标，然后将其作为唯一目标传递给 A*？

传奇：

白色 - 可步行

灰色 - 墙壁

蓝色——我自己

绿色 - 目标

红色 - 敌人（我计划在 X SQM 与敌人保持距离）

Answer 1

是的，只需将EstimatedDistanceToEnd(aka. h(x)) 设置为所有端节点的最小估计值。然后当你到达一个终端节点时停止搜索。

Answer 2

A* 用于知情搜索，其中我们有一些数据，而不仅仅是目标状态......根据您的问题，似乎没有相关数据，我们只知道我们的目标状态是什么。如果是这种情况，那么您可以简单地应用BFS。