Java 2d 游戏中的路径查找?
-
05-07-2019 - |
题
本质上它是我正在开发的一款吃豆人克隆游戏。我有一个 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的主要逃生路线并抓住他。