Pacman游戏中的幽灵 AI

Question

我正在使用Java制作Pacman游戏。但是我对幽灵有疑问。

我知道幽灵的攻击方式不尽相同。我首先想要解决的问题是让幽灵追逐Pacman并且暂时不考虑它们之间的差异。

我向聪明的你们提出问题：最好的方法是什么，可以使幽灵追逐Pacman但有时会随机改变路径？我目前使用21x21的二维数组来记录墙的位置等信息，所以我想让幽灵尝试朝着Pacman当前所在的格子前进（例如前往10,14）。当然，幽灵应该避免穿过像Pacman一样的墙壁。我想知道如何实现这个功能，以及如何让幽灵有时停下来改变方向，这样就不会一直追逐，Pacman也有机会逃脱。也许你们中的一些人已经编过Pacman游戏或者知道一个好方法。任何帮助都将不胜感激。

（请注意，我目前正在上11年级的计算机科学课程，并且正在学习Java的第一个学期中）。

- ComputerLocus

---

对于那些抵制被盎格鲁撒克逊帝国同化的人来说，什么是11年级？ - Fred Foo

@larsmans 这是高中的第三年课程，尽管我现在还是高中二年级，但我迫不及待地想要学习这门课程。 - ComputerLocus

当然，我可以在您的用户资料中看到这个 :) - Fred Foo

Answer 1

如果您只是希望幽灵们不都表现得一样，每次遇到十字路口时，让他们的决策是一种合理的追逐默认值的随机混合（例如继续走最短距离到达Pacman的方式 - 使用Dijkstra算法在所有后继中选择最佳路径），并且加入一个随机选择。

- Pascal Cuoq

---

所以你的意思是让它们从交叉口随机选择一个转弯，但更有可能朝着吃豆人的方向前进？ - ComputerLocus

@Fogest 没错。防止幽灵聚集在一起但保持游戏趣味性的数值需要通过实验来确定（取决于迷宫的形状），我猜测50%的随机选择和50%的最短路径应该能得到可接受的结果。 - Pascal Cuoq

好的，我喜欢这个想法，很可能会使用类似于这个或@larsmans回答的东西。 - ComputerLocus

Answer 2

我发现这篇文章非常有帮助：理解《吃豆人》中幽灵的行为，它讲解了你需要知道的内容。

- Óscar López

---

是的，我知道每个幽灵都有自己的行为，但在我所学习的课程中，并不期望我们编写如此复杂的游戏。我只想先添加一个基本的追逐系统，而不是这么高级的方法。 - ComputerLocus

Answer 3

这里有一个可能性：对于幽灵可以走的所有步骤，计算出它是否会让它更接近Pacman。这可以用曼哈顿距离来完成，在2D网格中只是x距离+y距离。然后随机选择一步，更高的概率分配给那些实际上会让它更接近的步骤。

如果你有一个数组steps，其中前n_closing_in个步骤代表将幽灵带向Pacman的步骤，那么你可以为它们分配总概率prob_closing_in。

double total_probility = 1.;
for (int i=0; i<n_closing_in; i++) {
    step_prob[i] = prob_closing_in / n_closing_in;
    total_probability -= prob_closing_in / n_closing_in;
}

然后，同样地将剩余的total_probability分配到会使幽灵远离Pacman的步骤上。

Step random_step(Step[] possible_steps, double[] step_prob) {
    double r = Math.random();

    int i;
    for (i=0; i<possible_steps.length(); i++) {
        if (r < step_prob[i])
            break;
        r -= step_prob[i];
    }
    return possible_steps[i];
}

如果迷宫不是太复杂，并且被包围的概率大于>.5，则幽灵将以杂乱无章的方式出现并追逐吃豆人。

将prob_closing_in提高到1.会使游戏更加困难。

（以上所有代码都未经测试，可能包含错误。我对Java不太擅长。）

- Fred Foo

---

你有点让我摸不着头脑了。我以前从来没有学过 Steps。 - ComputerLocus

@Fogest：我在考虑使用 enum Step { LEFT, RIGHT, UP, DOWN } 这样的方式。 - Fred Foo

@Fogest：我指的是你应该以某种方式表示可能的步骤。我假设你有一个名为“Step”的类型，它可能是一个枚举或者一个类。这并不重要，只要你有一些方法来表示一个步骤可以向左、向右、向上或向下。你甚至可以使用一个“int”来实现这个目的。 - Fred Foo

你看，我不知道什么是步骤、类或枚举。我还没有学过这些。 - ComputerLocus

@Fogest：在你当地的图书馆里拿起任何一本Java书籍，查找类。它们是非常基础的。（而且我打赌你很快就必须学习它们了。） - Fred Foo

我会考虑的。如果我的学校图书馆也有一个的话，那就太好了。 - ComputerLocus

Answer 4

在我的大学AI课程中，我使用了较旧版本的Pacman Ghost AI框架进行了一些工作。看起来，当前版本可以在http://www.pacman-vs-ghosts.net/software（现已失效）找到。在这个框架中，您将开发自己的Ghost代理程序来尝试捕捉一个代理或用户控制的Pacman。

这对于尝试不同的AI技术非常有用。

回答您的问题，该框架中的关卡实际上是由图形而不是二维数组构建的。您可以查看代码以了解它们是如何做到的。

原始链接已失效，迄今为止我还没有找到官方的备用镜像。但是，以下内容可能会有所帮助：

理解Pac Man鬼行为 Ms Pac Man Vs Ghost AI (GitHub) PacMan_v6.2 (GitHub)

- Casey

---

我会看一下，但请考虑我的技能水平。 - ComputerLocus

我认为网站http://www.pacman-vs-ghosts.net/software已经停止运营了。我还能在哪里找到这个框架呢？ - user3575425

jumpnett。你有更新的链接吗？ - user3575425

Answer 5

实现这样的AI最简单的方法是使用一个朴素的图搜索算法。 BFS就是一个简单的算法，可以使用。但是，你需要实现一个启发式算法来更好地优化运行时间，因此从鬼代理到Pac-man的简单曼哈顿距离就足够了。

总结：BFS与曼哈顿距离启发式算法。

如果你想更精细地设计，使你的鬼更有效地狩猎，可以实现一个游戏状态启发式算法（基于鬼到Pac-man的距离以及Pac-man迄今为止吃掉的点数等）用于决定下一步鬼要采取哪个移动。在这种情况下，你可以使用修剪技术来缩短运行时间。

- ylun.ca