吃豆人寻路算法 [英] Pathfinding Algorithm For Pacman

问题描述

我想实现《吃豆人》游戏.对于AI而言，在很多论坛上都看到过它，我正在考虑使用A *算法.但是，我通过广度优先搜索"进行了一些简单的寻路(从点a到点b，中间有一些障碍)，发现它总是提供最佳路径.我猜可能是因为在像pacman这样的游戏中，它使用简单的寻路，图中没有成本的概念.那么，如果我在Bacman中使用BFS而不是A *进行寻路，就可以了吗?

解决方案

有关路径查找，请注意以下内容

• BFS将比A *看更多的节点，这使得它慢得多
• A *的答案与BFS相同
• A *真的很容易实现
  • 使用曼哈顿距离进行启发式-这非常容易实现，并且导致非常有效的搜索
  • 查看 http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html 了解更多信息(整个系列真的很有趣)

如果您正在谈论幽灵AI，请查看乍得提到的页面:吃豆人档案-幽灵实际上在确定如何使其到达目标图块时仅使用了欧几里得距离，这在某些情况下使他们很难找到吃豆人. >

I wanted to implement the game Pacman. For the AI, I was thinking of using the A* algorithm, having seen it on numerous forums. However, I implemented the Breadth First Search for some simple pathfinding (going from point a to point b with certain obstacles in between) and found it gave the optimum path always. I guess it might be because in a game like pacman which uses simple pathfinding, there is no notion of costs in the graph. So, will it be OK if I use BFS instead of A* for pathfinding in Pacman?

解决方案

For path-finding, note the following

• BFS will look at a lot more nodes than A* will, which makes it much slower
• A* will come up with the same answer as BFS
• A* is really easy to implement
  • Use Manhattan Distance as your heuristic - this is insanely easy to implement, and leads to very efficient searches
  • Look at http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html for more information (the entire series is really interesting)

If you're talking about the ghost AI, check out the page Chad mentioned: The Pac-Man Dossier - the ghosts actually just use the euclidean distance when determining how to make it to their target tiles, which makes them very bad at finding Pac Man in some cases.

这篇关于吃豆人寻路算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！