我正在尝试为 iPhone 创建一个 Pacman AI，而不是 Ghost AI，而是 Pacman 本人。我正在使用 A* 进行寻路，并且我有一个非常简单的应用程序正在运行，它计算游戏板上 2 个瓷砖之间的最短路径，避开墙壁。
所以运行 1 个函数来计算 2 个点之间的路径很容易。一旦函数到达goalNode，我可以通过每个tile 'parentNode' 属性向后遍历路径并创建所需的动画。但在实际游戏中，状态是不断变化的，因此路径和动画也必须如此。我是游戏编程的新手，所以我不确定实现这一点的最佳方法。
我应该创建一个在后台运行的 NSOperation 并在给定当前游戏状态的情况下不断计算goalNode 和最佳路径吗？该线程还必须在某些时候通知主线程并为其提供信息。问题是什么？
我应该在什么时候通知主线程？
我应该用什么数据通知主线程？
......或者我在一起了吗？
非常感谢任何指导。
我对 pacman AI 的建议是，您使用洪水填充算法来计算到网格上每个图块的最短路径和总距离。这是一个比 A* 简单得多的算法，并且实际上比 A* 有更好的最坏情况，这意味着如果你能承受 A* 每帧，你就能承受洪水填充。
为了更详细地解释性能比较，请想象 A* 中最坏的情况：由于死胡同，您最终不得不在到达最终目的地之前探索网格上的每个图块。如果您在棋盘上有很多死胡同，这种理论案例是可能的，但在大多数现实世界的吃豆人棋盘中不太可能。洪水填充的最坏情况与最佳情况相同，您只访问地图上的每个图块一次。不同之处在于，洪水填充的迭代步骤比 A* 迭代更简单（无启发式、无节点堆等），因此使用洪水填充访问每个节点比使用 A* 更快。
实现非常简单。如果你把网格想象成一个图，每个图块都是一个节点，而相邻图块之间没有墙的每条边都是图中的一条边，你只需对图进行广度优先遍历，跟踪你来到了哪个节点从以及您探索了多少节点才能到达那里。您在访问节点时将其标记为已访问，并且从不访问节点两次。
这里有一些伪代码可以帮助您入门：
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 指针一直回到起点，然后反转列表。
这样做的好处是您可以不断地查询到达地图上任何图块的成本。例如，您可以遍历每个电源颗粒并计算哪个最接近，以及如何到达那里。
你甚至可以用它来让鬼知道当他们处于“攻击”模式时最快的方式回到吃豆人！
您还可以考虑来自每个幽灵的洪水填充，在每个图块中存储最近的幽灵有多远。您可以限制您探索的最大距离，如果节点大于某个最大成本（8 个正方形？），则不将节点添加到打开列表中。然后，如果你稍后做了 A*，你可以根据幽灵的接近程度来调整每个图块的成本。但这有点超出了您在问题中提出的要求。
它应该足够快，你可以在每一帧内联，或者如果你愿意，可以多线程。为简单起见，我建议只在您的主游戏模拟线程（注意，不是 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。
祝你好运！
有点不相关，但是你见过ASIPathFinder 框架吗？如果您有更高级的寻路需求，可能会有所帮助。