PacMan角色AI建议，以获得最佳下一个方向

Question

首先，这是关于PacMan的AI而不是鬼怪。

我正在编写一个Android动态壁纸，它会在您的图标周围播放PacMan游戏。虽然它支持通过屏幕触摸来接受用户建议，但大部分游戏将由AI来玩。我已经完成了99%的游戏编程，但是PacMan本身的AI仍然非常薄弱。我正在寻求帮助开发一个良好的AI来确定PacMan下一步的行进方向。

我的初步计划是：

1. 为每个方向初始化一个分数计数器，初始值为零。
2. 从当前位置开始，并使用BFS遍历四个可能的初始方向，将它们添加到队列中。

3. 从队列中弹出一个元素，确保它尚未被“看到”，确保它是一个有效的棋盘位置，并根据以下规则将当前单元格的值添加到相应的初始方向分数中：

   1. 有点：加10分
   2. 有能量增强道具：加50分
   3. 有水果：加上水果价值（随等级变化）
   4. 有朝向PacMan的幽灵：减200分
   5. 有远离PacMan的幽灵：不进行操作
   6. 有垂直行进的幽灵：减50分
   7. 将单元格的值乘以基于到达该单元格的步数的百分比，步数越多，距离初始方向越近，单元格的值就越接近于零。

   并将当前单元格的三个可能方向入队。

4. 一旦队列为空，请找到四个可能的初始方向中得分最高的一个，并选择它。

在纸面上听起来不错，但幽灵们会极快地包围PacMan，他会在同两三个单元格中来回抽搐，直到其中一个接近他。调整幽灵存在的值也没有帮助。我的最近点BFS至少可以在游戏结束前达到第2或第3关。

我正在寻找编写正确AI的代码、想法和/或资源链接--最好是前两者。我希望在本周末发布这个应用，所以我有点急。非常感谢任何帮助。

---

顺便说一下，这是手动转载在GameDev.StackExchange上的

- Jake Wharton

---

这将更适合在http://gamedev.stackexchange.com上。 - ManiacZX

@ManiacZX 谢谢你通知我。我不知道那个网站的存在。我会记住这个网站以便今后发布或重新发布这个问题时使用。 - Jake Wharton

我不记得Pacman的确切规则，即Pacman是否必须不断移动。如果您不关心完全遵循原始的Pacman规则，我还会在Pacman的可能行动列表中添加“停留”选项。http://www-inst.eecs.berkeley.edu/~cs188/archives.html有一些有趣的资源供您查看。 - nevets1219

Answer 1

如果PacMan卡在一个位置并开始来回抽搐，那么这表明在运行度量后，他可以选择的不同移动具有非常相似的分数。然后，幽灵位置的微小变化将导致最佳移动来回翻转。您可能需要考虑添加一些hysteresis以防止发生这种情况。

设置：选择一个随机移动并记录它的得分为0。

对于每个步骤：

1. 对可用移动运行评分函数。
2. 如果最高分比记录分数高x％，则使用此分数和移动覆盖记录分数和移动。
3. 应用移动。

这样做的效果是PacMan不再在每个步骤中选择“最佳”移动，但似乎贪婪的局部搜索也不是最优的。它将使PacMan更加一致并停止抽搐。

- Andrew

Answer 2

有一种方法可以将PacMan转换为“路径跟随”模式。计划是检测特定情况，计算预先绘制的PacMan要跟随的路径，然后为该路径计算早期退出条件。您可以在几种情况下使用此功能。

当PacMan被三个方向上的幽灵包围在一定距离内时，创建一个出口路径，使PacMan远离幽灵或朝向能量增强器。退出情况是他吃掉能量增强器或不再被包围。

当PacMan吃掉能量增强器时，创建一条路径以吃掉附近的一些幽灵。退出情况是路径上没有幽灵，重新计算路径。或者如果附近没有幽灵，则完全退出该模式。

当剩余的点数少于一半或附近没有点时，进入一条路径以去吃掉一些点，避开幽灵。当幽灵靠近时重新计算路径，或者如果有几个幽灵附近，则完全退出它。

当没有需要路径的情况时，您可以恢复到之前编程的默认AI。

- Erick Robertson

Answer 3

你可以使用蚁群优化技术来寻找通往许多图标以获取高分或食物的最短可见路径。

- Buhake Sindi

Answer 4

我对人工智能或特定算法不是很了解，但以下是一些你可以尝试的方法，也许可以让你接近政府工作的要求 :)

对于围绕他迅速出现的幽灵问题，也许幽灵人工智能太强大了？我知道在经典游戏《吃豆人》中每个幽灵都有特定的行为，如果你还没有考虑到这一点，你可能需要考虑一下。

为了消除回溯，你可以为最近遍历的节点创建一个权重惩罚，这样他就不太倾向于返回之前的路径。如果这还不足以让他朝一个方向或另一个方向前进，那么你可以对吸引力惩罚进行对数级别的增加，这样一个路径将会在非常快的速度上变得比其他路径更具吸引力。

对于他被幽灵抓住的问题，你可以在幽灵到达危险节点附近时，从一般的目标导向算法转换为逃避算法。

- Merlyn Morgan-Graham

Answer 5

了解机器人的“推理”方式可能会对您有所帮助（正如在这个优秀的dossier中所解释的那样）。例如，了解幽灵的追逐/分散模式将使您能够获得“危险”位置的点等等。

我添加这个答案是知道这不是您正在寻找的最佳解决方案（因为您想在下周交付..），但也许对未来阅读此内容的某些人有用。有点像时间胶囊 :)

- lorenzog

Answer 6

你应该查看反对象的描述，这是Pacman幽灵用来穿越迷宫的技术。特别要注意：

每个反对象或代理都有一个相同且简单的算法，在游戏的每一轮运行该算法。不是让幽灵足够聪明地解决迷宫周围的“最短路径”问题，而是创建了“吃豆人气味”的概念，并且每个方块负责说明其方块上有多少吃豆人气味。

所以你可以考虑类似的基于气味控制Pacman的技术，也许Pacman更喜欢穿越具有较小气味量的路径；这将减少他走重复路线的机会。

- Adamski