Java 2d 游戏中的路径查找？

StackOverflow https://stackoverflow.com/questions/623095

题

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

所有幽灵都会在屏幕的随机区域启动，然后它们必须朝着吃豆人角色前进。当玩家控制吃豆人并移动它时，他们应该跟随它并尽可能靠近他。

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

对于玩家和每个幽灵，我可以检索 X、Y、图像宽度和高度属性。另外，我已经有了碰撞检测算法，所以不用担心这个，只担心幽灵找到吃豆人的路。

有帮助吗？

解决方案

对于一个好的寻路算法，使用 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年代早期的街机游戏可能不会使用复杂的寻路算法。

其他提示

如果你只有一个像素网格 - 一个“大区域”，吃豆人和吃豆人可以在上面自由移动 - 那么最短路径很简单 - 幽灵和吃豆人之间的一条直线。

但“最短路径”总是意味着我们正在尝试解决图论问题。（我假设有图形知识，一些图论，adj.矩阵等！）

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

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

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

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

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

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

现在，吃豆人不能沿对角线移动。从中心到右下角需要 2 次“跳跃”，而不是 1 次。

要继续进展：

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

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

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

进入一个*。通过构建图（使用邻接矩阵或节点列表），您可以使用 A* 算法来查找最短路径。其他算法包括 Dijkstra 算法。还有很多其他的！但首先您需要用图表来构建问题，然后考虑如何从节点 A (pacman) 到节点 B (ghost)。

希望有帮助！

这已经很长一段时间了，但是从记忆中看，吃豆人的鬼魂在寻路方面做得并不多。他们会做一个相当标准的随机迷宫遍历，直到他们“发现”为止。你，它涉及沿着走廊的轴向你找到一条畅通无阻的路径，然后他们会直接朝你走来，直到你从他们的视线中消失，然后他们会恢复一个随机的模式。在更高的水平上，吃豆人会在他身后留下隐形痕迹一段时间鬼魂将“闻”出来。有时跟着。

当Pac-Man上电时，算法的唯一区别在于，当他们发现你时，鬼魂会逃离你而不是向你移动。

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

直接走向你的敌人是一个开始，但是当你添加一个迷宫时，你会想要添加一些更聪明的寻路，这样你的鬼魂就不会陷入弯道或死路。

以下教程是一个很好的轻量级指南，可以开始使用A *，并提供可下载的示例。

基于平铺地图的路径查找

在《吃豆人》中，所有幽灵都有不同的追逐算法

  • 眨眼 -> 追逐。通常会采取最短的路线到你身边，并且倾向于跟随。
  • 小指 -> 伏击。倾向于采取更迂回的方式来玩吃豆人。致命。（pinky和blinky在选择方向时往往会做出不同的选择，经常将玩家困在角落里）
  • 墨色 -> 怪胎。这家伙的行为很奇怪。他在棋盘上相当随机地移动，但有时当他靠近时会追逐。
  • 克莱德 -> 白痴。随机移动。威胁不大。

鬼魂的动作有一个有趣的模式：有时，他们会同时停止追捕吃豆人，并返回迷宫各自的角落，进入“分散模式”。

该算法的完整描述位于 吃豆人档案

问候

纪尧姆

您可以开始查看A *（明星）

这是一个页面，其中包含指向其他路径查找算法的链接。

[编辑] gah ...大脑太慢了...忘了这本书，它是C或C ++（我忘了哪个），但你仍然可以得到Java的概念。它可能不是你阅读最容易的，但总体来说还不错。为David M. Bourg，Glenn Seemann AI for Game Developers 。

我认为在pacman的每一步行动中都要选择最短路径算法。一个非常好的实现是 Dijkstra的算法。

总结一下：将迷宫可视化为具有顶点和边缘的图形。每条边都有一个等待（在你的情况下，所有边都有相同的重量）。该算法通过向下移动每个直接可到达边缘一步，找到从源顶点到目标顶点的最短路径。然后在下一个顶点上你做同样的事情并继续做，直到你到达目标。到达的第一条路径是最短的路径。可以对此算法进行许多优化，以加快诸如考虑到pacman处于其先前位置的位置以及它移动到哪个方向之类的事情，以便您可以在算法中获得一些heiristics。我建议在每次移动时找到从每个鬼到pacman的最短路径，并将鬼移向那个方向。最终距离将减少，你将能够捕捉到pacman。

另一种启发式方法，可以用它来找到从pacman可以到达的所有直接边缘，并尝试用鬼来覆盖尽可能多的这些顶点。因此，不是将pacman设置为目标顶点，而是将pacman设置为目标立即可达的顶点，结果将是可用的鬼魂将试图掩盖pacman的主要逃生路线并抓住他。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top