PacMan字符AI对最优下一个方向的建议

Question

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

我正在写一个安卓实时壁纸，它在你的图标周围播放PacMan。虽然它支持用户的建议，通过屏幕触摸，大部分的游戏将由一个人工智能。我99%完成了游戏的所有编程，但是PacMan本身的AI仍然非常弱。我正在寻找帮助开发一个良好的人工智能，以确定吃豆人的下一个方向的旅行。

我最初的计划是：

1. 为每个方向初始化一个分数计数器，其值为零。
2. 从当前位置开始，通过将BFS添加到队列中，使用BFS向外遍历四个可能的初始方向。
3. 从队列中弹出一个元素，确保它尚未被“看到”，确保它是一个有效的板位置，并在相应的初始方向上添加一个基于以下内容的当前单元格的值：

1. Has a dot: plus 10
2. Has a power up: plus 50
3. Has a fruit: plus fruit value (varies by level)
4. Has a ghost travelling toward PacMan: subtract 200
5. Has a ghost travelling away from PacMan: do nothing
6. Has a ghost travelling perpendicular: subtract 50
7. Multiply the cell's value times a pecentage based on the number of steps to the cell, the more steps from the initial direction, the closer the value of the cell gets to zero.

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

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

这在纸上听起来不错，但是鬼魂包围PacMan的速度非常快，他在同一个两三个细胞里来回抽搐，直到有一个到达他。调整幽灵存在的值也没有帮助。我最近的点BFS至少可以在游戏结束前达到2或3级。

我正在寻找代码，思想和/或资源的链接来开发一个适当的人工智能--最好是前两者。我想在这个周末的某个时候在市场上发布这个，所以我有点着急。任何帮助都是非常感谢的。

FYI，这是在https://gamedev.stackexchange.com/questions/1861/pacman-character-ai-suggestions-for-optimal-next-direction上手动交叉发布的。

Answer 1

如果PacMan被卡在一个位置上，开始来回抽动，那么它表明，在运行度量之后，对他开放的不同动作有非常相似的分数。然后，鬼在位置上的微小变化会导致最好的动作来回翻转。您可能需要考虑添加一些迟滞来阻止这种情况的发生。

设置:选择一个随机移动，并记录它的分数为0。

每一步：

1. 在可用的移动上运行评分函数。
2. 如果最高分数大于记录分数x%，则覆盖记录分数并移动此记录。
3. 用这个动作。

这样做的效果是，PacMan不再会在每一步中选择“最佳”移动，但看起来并不是贪婪的本地搜索是最优的。它将使PacMan更加一致，并停止抽搐。

Answer 2

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

当PacMan在一定距离内四个方向中的三个方向被鬼魂包围时，创建一条出口路径，该路径要么将PacMan引离鬼魂，要么将其引向电源。退出的情况将是当他吃下权力或停止被包围。

当PacMan消耗能量时，创建一条路径来吃掉附近的鬼魂。退出的情况是当路径上没有鬼魂时，重新计算路径。或者如果附近没有鬼魂，就完全退出这个模式。

当剩下不到一半的点，或者附近没有点时，进入一条小径去吃一些点，避开鬼魂。当鬼魂靠近时，重新计算路径，如果附近有几个鬼魂，则完全退出。

当没有情况需要一个路径，那么你可以恢复到默认的AI你以前编程。

Answer 3

您可以使用蚁群优化技术找到最短的可见路径，从而导致许多图标吃或可以得到许多分数。