在Java 2D游戏中的路径查找？

Question

在Java 2D游戏中的路径查找？

javaalgorithmpseudocodepath-finding

6

这实质上是一个我正在开发的吃豆人克隆游戏。我有一个敌人类，创建了4个该类的实例，它们都代表游戏中的4个幽灵。

所有幽灵都会在屏幕的随机区域启动，然后他们必须朝着吃豆人角色前进。当玩家控制吃豆人四处移动时，幽灵应该跟随并采取最近的方式朝向他。

目前还没有迷宫/障碍物，因此整个地图（400x400像素）对它们来说是开放的地面。

对于玩家和每个幽灵，我可以检索到X、Y、图像宽度和高度属性。此外，我已经有了一种碰撞检测算法，因此不必担心，只需要让幽灵找到通往吃豆人的方式。

- Click Upvote

7个回答

6

如果你只有一个像素网格——一个“大场地”，Pacman和Ghost可以自由移动——那么最短路径很容易——就是Ghost和Pacman之间的直线。

但是，“最短路径”不可避免地意味着我们要解决一个图论问题。（我假设读者已经了解图形、一些图论、邻接矩阵等知识！）

在上面的情况下，将每个像素视为图上的一个节点。每个节点通过一条边连接到其相邻节点，并且每条边具有相等的“权重”（移动到“上方”的节点并不比移动到“下方”的节点慢）。

所以你有这个：（“*”=节点，“-，/，\，|”=边）

*-*-*
|\|/|
*-*-*  ... (etc)
|/|\|
*-*-*

如果Pacman在中心，它可以很容易地移动到任何其他节点。

更接近现实的情况可能是这样的：

*-*-*
| | |
*-*-*  ... (etc)
| | |
*-*-*

现在，Pacman无法对角移动。从中心到右下角需要进行2次“跳跃”，而不是一次。

继续进行：

*-*-*-*
| | | |
| | | |
| | | |
*-*-*-*
| | | |
*-*-*-*

现在，从中间的节点到顶部的节点需要3次跳跃。然而，向下移动只需要1次跳跃。

将任何游戏板设置转换为图形很容易。每个“交叉点”都是一个节点。两个交叉点之间的路径是一条边，该路径的长度是该边的权重。

输入A*算法。通过构建一个图（使用邻接矩阵或节点列表），您可以使用A*算法找到最短路径。其他算法包括Dijkstra算法等。但首先您需要将问题框架化为图形问题，然后考虑如何从节点A（吃豆人）到节点B（幽灵）。

希望这有所帮助！

- poundifdef

3

很久以前，据我记忆，Pac-Man中的幽灵在寻路方面并没有做太多工作。它们会进行标准的随机迷宫遍历，直到"发现"你，这涉及到沿着走廊轴线找到一条无阻碍路径向你移动，然后直接朝你移动，直到你从它们的视线中消失，此时它们会恢复随机模式。在更高的关卡中，Pac-Man会留下他身后的隐形痕迹，幽灵会"闻到"并有时跟踪它们。

当Pac-Man获得强化道具时，算法中唯一的区别是，当幽灵发现你时，它们会逃离你而不是向你移动。

因此，为了获得真实的体验，您可能根本不需要非常复杂的寻路算法。当然，如果您想要花哨一些，您可以实现A*算法。

- cygil

我一直有这样的感觉，原始的吃豆人游戏是预定义路径和路径查找的混合体。但这可能是由于静态起点造成的。 - guyumu

2

直接走向敌人是一个开始，但当你添加迷宫时，你会想要添加一些更智能的路径规划，这样你的幽灵就不会卡在弯道或死胡同里。

下面的教程是一个很好的轻量级指南，可帮助您开始使用A*算法，并提供可下载的示例。基于瓦片地图的寻路

- Daan van Yperen

1

在Pacman游戏中，所有的幽灵都有不同的追逐算法

Blinky -> 追逐。通常会选择最短的路线追赶你，并且倾向于跟随。
Pinky -> 埋伏。倾向于采取更迂回的方式追赶Pac-Man。致命。(Pinky和Blinky在选择方向时往往会做出不同的选择，经常将玩家困在一个角落里)
Inky -> 疯子。这个家伙行动很奇怪。他在棋盘上移动得相当随意，但有时在靠近时会追赶。
Clyde -> 白痴。随机移动。威胁不大。

幽灵们的移动中编程了有趣的模式：偶尔，它们会同时停止追赶Pac-Man并返回迷宫的各自角落，进入“散开模式”。

完整的算法描述可以在the pacman dossier找到

此致

Guillaume

- PATRY Guillaume

0

你可以开始看A*（A星）

这里还有一个页面，其中包含其他路径查找算法的链接。点击这里。

[编辑] 噫...我的大脑太慢了...我忘记了这本书，它是用C或C++编写的（我忘记了），但你仍然可以从中获取Java的概念。它可能不是最容易阅读的，但总体上还不错。《游戏开发人员的AI》David M. Bourg, Glenn Seemann。

- TofuBeer

0

我认为在每次Pacman移动时都应该采用最短路径算法。一个非常好的实现是Dijkstra算法。

简单总结一下：将迷宫视为具有顶点和边的图形。每条边都有一个等待时间（在您的情况下，所有边的权重相同）。该算法通过沿着每个可达边缘向下移动一步来找到从源顶点到目标顶点的最短路径。然后在下一个顶点上，您做同样的事情，并继续执行，直到到达目标。第一条到达的路径是最短路径。可以对此算法进行许多优化，以加快速度，例如考虑Pacman在其先前位置以及移动方向，以便在算法中获得一些启发式。我建议在每次移动时找到每个幽灵到Pacman的最短路径，并朝那个方向移动幽灵。最终距离会减少，您将能够抓住Pacman。

另一个可用的启发式方法是找到所有从吃豆人可以到达的直接边，然后尝试通过幽灵覆盖尽可能多的这些顶点。因此，我们不将吃豆人设置为目标顶点，而是将吃豆人可以直接到达的顶点设置为目标，结果是可用的幽灵将尝试覆盖吃豆人的主要逃生路线并捉住他。

- Faisal Feroz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- coobird · Accepted Answer

对于一个好的寻路算法，使用A*可能是个好主意，但是对于一个不需要复杂、高效或有效路径搜索的简单游戏来说，只需通过找到目标方向使角色向目标移动就足够了。

例如，让角色移动的决策，伪代码如下：

if (target is to the left of me):
    move(left);
else
    move(right);

if (target is above me):
    move(up);
else
    move(down);

是的，角色移动可能不会非常高效，但在每个游戏循环的迭代中，它会越来越接近目标。

我猜测，80年代早期的街机游戏可能不会使用复杂的路径查找算法。