我正在尝试为 iPhone 创建一个 Pacman AI，不是 Ghost AI，而是 Pacman 本人。我使用 A* 进行寻路，并且启动并运行了一个非常简单的应用程序，它可以计算游戏板上 2 个图 block 之间避开墙壁的最短路径。
因此运行 1 个函数来计算 2 点之间的路径很容易。一旦函数到达 goalNode，我就可以通过每个图 block 的“parentNode”属性向后遍历路径并创建所需的动画。但在实际游戏中，状态不断变化，因此路径和动画也必须随之变化。我是游戏编程新手，所以我不太确定实现此目的的最佳方法。
我应该创建一个在后台运行的 NSOperation 并不断计算 goalNode 以及给定游戏当前状态的最佳路径吗？该线程还必须在某些时候通知主线程并为其提供信息。问题是什么？
我应该在什么时候通知主线程？
我应该用什么数据通知主线程？
...或者我完全偏离了？
非常感谢任何指导。
最佳答案
我对 pacman AI 的建议是使用洪水填充算法来计算到网格上每个图 block 的最短路径和总距离。这是一个比 A* 简单得多的算法，而且实际上比 A* 具有更好的最坏情况，这意味着如果您能负担得起每帧 A* 的费用，那么您就能负担得起洪水填充。
为了更详细地解释 a 中的性能比较，请想象 A* 中最坏的情况:由于死胡同，您最终必须在到达最终目的地之前探索网格上的每个图 block 。如果棋盘上有很多死胡同，这种理论上的情况是可能的，但在大多数现实世界的吃 bean 人棋盘上不太可能。洪水填充的最坏情况与最好情况相同，您只访问 map 上的每个图 block 一次。不同之处在于，泛洪填充的迭代步骤比 A* 迭代更简单(无启发式、无节点堆等)，因此泛洪填充访问每个节点的速度比 A* 更快。
实现非常简单。如果您将网格想象成一个图，每个图 block 都是一个节点，相邻图 block 之间没有墙的每条边都是图中的一条边，那么您只需对图进行广度优先遍历，跟踪您所在的节点从哪里出发以及您探索了多少个节点才到达那里。当您访问一个节点时，您将其标记为已访问，并且永远不会两次访问该节点。
这里有一些伪代码可以帮助您入门:
openlist = [ start_node ]
do
node = openlist.remove_first()
for each edge in node.edges
child = node.follow_edge(edge)
if not child.has_been_visited
child.has_been_visited = true
child.cost = node.cost + 1
child.previous = node
openlist.add(child)
while openlist is not empty
要弄清楚如何让 pacman 移动到某个地方，您可以从所需的节点开始，然后沿着 .previous 指针一直回到开头，然后反转列表。
这样做的好处是，您可以对到达 map 上任何图 block 的成本进行持续时间查询。例如，您可以循环遍历每个动力颗粒并计算哪一个最接近，以及如何到达那里。
您甚至可以用它来让幽灵知道当吃 bean 人处于“攻击”模式时返回吃 bean 人的最快方法!
您还可以考虑对每个幽灵进行洪水填充，在每个图 block 中存储最近的幽灵的距离。您可以限制您探索的最大距离，如果节点大于某个最大成本(8 个方 block ？)，则不将它们添加到打开列表中。然后，如果您稍后确实做了 A*，您可以根据鬼影的距离来偏置每个图 block 的成本。但这有点超出了您在问题中提出的要求。
它应该足够快，以便您可以在每一帧内进行内联操作，或者如果您愿意的话可以进行多线程操作。为了简单起见，我建议只在主游戏模拟线程(注意，不是 UI 线程)中执行此操作，因为当一切都说完并完成时，它确实应该非常快。
一个性能提示:您不必每帧都检查并清除“has_been_visited”标志，您只需使用一个搜索计数器来递增每帧。像这样:
openlist = [ start_node ]
do
node = openlist.remove_first()
for each edge in node.edges
child = node.follow_edge(edge)
if child.last_search_visit != FRAME_NUMBER
child.last_search_visit = FRAME_NUMBER
child.cost = node.cost + 1
child.previous = node
openlist.add(child)
while openlist is not empty
然后您只需在每一帧增加 FRAME_NUMBER 即可。
祝你好运!
关于iPhone寻路实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3444201/