Pacman的寻路算法

Question

我想实现Pacman游戏.对于AI,我正在考虑使用A*算法,已在众多论坛上看到它.然而,我实现了广度优先搜索的一些简单的寻路(从点a到点b,其间有一定的障碍),并发现它始终给出了最佳路径.我想这可能是因为在像pacman这样使用简单寻路的游戏中,图中没有成本概念.那么,如果我在Pacman中使用BFS而不是A*进行寻路,那会没关系吗？

Answer 1

这取决于,你真的想让幽灵像他们在吃豆人一样工作吗？

这里描述了幽灵追逐AI的工作原理(它们各自的工作方式不同).请务必阅读上面的章节,了解他们实际上是如何尝试访问目标磁贴的.该页面对Pac-Man进行了非常深入的分析,有趣的阅读.

Answer 2

对于路径寻找,请注意以下内容

• BFS会查看比A*更多的节点,这会让它慢得多
• A*会得出与BFS相同的答案
• A*非常容易实现
  • 使用曼哈顿距离作为您的启发式算法 - 这非常容易实现,并且可以实现非常高效的搜索
  • 查看http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html获取更多信息(整个系列非常有趣)

如果你在谈论幽灵AI,请查看Chad提到的页面:吃豆人档案 - 鬼魂实际上只是在确定如何使其达到目标牌时使用欧几里德距离,这使得他们非常难以找到Pac在某些情况下的人.