我想实现游戏Pacman。就AI而言，我考虑使用A*算法，在很多论坛上看到过它。然而，我实现了BFS用于一些简单的路径规划（从点a到点b，中间有一些障碍物），发现它总是给出最优路径。我猜可能是因为在像Pacman这样使用简单路径规划的游戏中，图形上没有成本概念。所以，如果我在Pacman中使用BFS而不是A*作为路径规划，是否可以？
6个回答
26
那要看你是否想让鬼像《吃豆人》中那样运作了。
这里有关于鬼的追逐人工智能如何运作的描述（它们每个鬼都有不同的方式）。确保也阅读上面关于它们如何实际到达其目标块的第三章。那个页面是对《吃豆人》进行深入分析的，非常有趣。
- Chad Birch
2
谢谢Chad。我之前没有看过那篇文章。 - Audie
3好的，以下是翻译内容：标题: 《吃豆人》档案第一章： 简介自从1980年由日本游戏公司Namco开发后，《吃豆人》就成为了一款受欢迎的经典游戏。在这个游戏中，玩家需要通过控制一个黄色的圆形角色来吃掉屏幕上的所有点，并避免被四个鬼魂碰到，同时还要尽可能地吃掉四个大点，使鬼魂变成蓝色并可被吃掉。虽然看起来十分简单，但《吃豆人》却有着复杂的游戏机制和隐藏的技巧。例如，当玩家吃下四个大点后，随即可以通过吃掉特定的水果获得额外分数。此外，在某些关卡中，四个鬼魂会具有不同的行为模式，这也增加了游戏的挑战性。《吃豆人》的成功促使了许多后续版本和变种游戏的出现，例如《超级吃豆人》、《吃豆人冒险》等等。该游戏还影响了整个游戏界，成为了游戏史上不可或缺的一部分。 - arynaq
19
对于寻路，请注意以下内容
- BFS将查看比A*更多的节点，这使其变得更慢
- A*将得出与BFS相同的答案
- A*非常容易实现
- 使用曼哈顿距离作为启发式算法-这非常容易实现，并且可以导致非常有效的搜索
- 查看http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html获取更多信息（整个系列非常有趣）
如果您在谈论幽灵AI，请查看Chad提到的页面：The Pac-Man Dossier-幽灵实际上只是在确定如何到达目标方块时使用欧几里德距离，这使得它们在某些情况下很难找到Pac Man。
- Daniel G
3
很遗憾，Pac-Man反汇编程序已被删除。 - Anonym Mus
1A*算法在一般情况下并不是最优的，正如你所说。只有在使用可接受且一致的启发式函数时，才能保证找到最优解。 - b3bop
1@b3bop 对于一般情况，你说得对。我是在讨论在网格上使用曼哈顿距离（即 Pac-Man 迷宫）的情况。在这种情况下，启发式函数既可行又连续，A* 算法将得出与 BFS 相同的答案。 - Daniel G
4
取决于具体情况。BFS算法在完备性和优化性方面都表现出色（可以找到最优解）。
缺点是，它可能需要很长很长的时间才能找到最优解！此外，根据问题的分支因子，您可能很快就会耗尽内存。
如果您没有性能问题，则可以继续使用BFS，但如果要在巨大的迷宫中尝试它，则可能需要一段时间才能获得解决方案。
我建议您尝试使用A*算法，这是我认为最好的搜索策略。即使您没有使用BFS的问题，实现A*也是一个不错的算法，您将学习到很多有用的东西。
缺点是，它可能需要很长很长的时间才能找到最优解！此外，根据问题的分支因子，您可能很快就会耗尽内存。
如果您没有性能问题，则可以继续使用BFS，但如果要在巨大的迷宫中尝试它，则可能需要一段时间才能获得解决方案。
我建议您尝试使用A*算法，这是我认为最好的搜索策略。即使您没有使用BFS的问题，实现A*也是一个不错的算法，您将学习到很多有用的东西。
- mcabral
1
如果没有使用边权重，BFS将始终给出最短路径。如果您不需要边权重，我建议使用它。您随时可以稍后切换。
- rlbond
3
谢谢！我有预感那可能是这种情况。 - Karan
BFS虽然慢，但是不必要。 - user151496
对于一个简单的吃豆人游戏来说，这似乎不太重要。 - rlbond
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接