我想实现游戏吃豆人。对于 AI，我正在考虑使用 A* 算法，在许多论坛上都看到过。但是，我为一些简单的寻路（从 a 点到 b 点，中间有某些障碍物）实施了广度优先搜索，并发现它总是给出最佳路径。我想这可能是因为在像吃豆人这样使用简单寻路的游戏中，图表中没有成本的概念。那么，如果我在 Pacman 中使用 BFS 而不是 A* 进行寻路可以吗？
问问题
34945 次
6 回答
25
好吧，这取决于，你真的想让鬼像在吃豆人中那样工作吗？
下面是关于鬼魂追逐 AI 工作原理的描述（它们各自的工作方式不同）。请务必阅读上述章节，了解他们如何实际尝试到达目标图块。该页面是对吃豆人的精彩深入分析，读起来很有趣。
于 2010-04-08T23:04:27.787 回答
19
对于寻路，请注意以下几点
- BFS 将查看比 A* 更多的节点，这使得它慢得多
- A* 将得出与 BFS 相同的答案
- A* 真的很容易实现
- 使用曼哈顿距离作为你的启发式方法——这非常容易实现，并导致非常有效的搜索
- 查看http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html了解更多信息（整个系列真的很有趣）
如果您在谈论幽灵 AI，请查看 Chad 提到的页面：吃豆人档案- 幽灵实际上只是在确定如何到达目标图块时使用欧几里德距离，这使得它们在寻找 Pac 方面非常糟糕在某些情况下是人。
于 2010-04-08T23:35:48.280 回答
4
这取决于。BFS 既完整又最优（从某种意义上说，它找到了最优解）
不足之处？可能需要很长时间才能找到它！此外，根据问题的影响因素，您可能会很快耗尽内存。
如果你没有性能问题，那就保留 BFS，但如果你想在一个巨大的迷宫中尝试它，那么可能需要一段时间才能得到解决方案。
我建议您尝试 A*，恕我直言，最好的搜索策略。即使你对 BFS 没有任何问题，A* 也是一个很好的算法，你会学到很多很酷的东西。
于 2010-04-08T23:06:33.620 回答
1
如果不使用边权重，BFS 将始终给出最短路径。如果您不需要边缘权重，我会使用它。您以后随时可以切换。
于 2010-04-08T23:04:09.033 回答
0
相关问题，这可能会回答您的问题：Java 2d 游戏中的路径查找？
于 2010-04-08T23:06:14.010 回答