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

基本上它是我正在研究的pacman克隆游戏。 我有一个Enemy类,并且创建了这个类的4个实例,它们代表了游戏中的4个幽灵。

所有幽灵都在屏幕的随机区域启动,然后他们必须朝着pacman角色前进。 当玩家控制pacman,移动它时,他们应该跟随它并采取最接近他的方式。

没有迷宫/障碍物(尚未)因此整个地图(400×400像素)都是开放的。

对于播放器和每个Ghost,我可以检索X,Y,图像宽度和高度属性。 此外,我已经有了一个碰撞检测算法,所以不用担心,只是鬼魂找到了通往pacman的方式。

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

如果你只有一个像素网格 – 一个“大场”,pacman和ghost可以自由地移动 – 那么最短的路径很容易 – 幽灵和pacman之间的直线。

但“最短路径”总是意味着我们正试图解决图论理论问题。 (我假设知识图,一些图论,调整矩阵​​等!)

在上面的情况中,将每个像素视为图形上的节点。 每个节点通过边缘连接到其邻居,并且每个边缘具有相等的“权重”(移动到“上方”​​上的节点并不慢于移动到“下方”节点)。

所以你有这个:(“*”= node,“ – ,/,\,|”= edge)

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

如果Pacman位于中心,它可以非常容易地移动到任何其他节点。

更接近现实的东西可能是:

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

现在,pacman无法对角移动。 从中心到右下角需要2个“跳”而不是一个。

继续进展:

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

现在,要从中间的节点转到顶部的节点,您需要3个跃点。 但是,向下移动只需要1跳。

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

进入一个*。 通过构造图形(使用adjency矩阵或节点列表),您可以使用A *算法来查找最短路径。 其他算法包括Dijkstra’s。 还有很多人! 但首先你需要用图表来表示你的问题,然后玩弄你如何从节点A(pacman)到节点B(ghost)。

希望有所帮助!

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

当吃豆人上电时,算法的唯一区别在于,当他们发现你时,鬼魂会逃离你,而不是向你移动。

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

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

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

基于图块的地图上的路径查找

在Pacman中,所有鬼都有不同的追逐算法

  • Blinky – >追逐。 通常会采用最短的路线给你,并倾向于遵循。
  • Pinky – >伏击。 倾向于采取更加迂回的方式来对抗pac-man。 致命。 (在选择方向时,小拇指和眨眼倾向于做出不同的选择,经常在角落里驯服玩家)
  • Inky – >怪胎。 这个家伙行为奇怪。 他相当随意地在棋盘上移动,但有时在他靠近时追逐。
  • 克莱德 – >白痴。 随机移动。 没有太大的威胁。

幽灵有一个有趣的模式编入他们的动作:偶尔,他们将同时停止并停止他们追逐吃豆人并返回迷宫的各自角落,进入“分散模式”。

在pacman档案中有完整的算法描述

问候

纪尧姆

你可以开始看A *(一颗星)

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

[编辑] gah …大脑太慢了…忘了这本书,它是C或C ++(我忘了哪个),但你仍然可以得到Java的概念。 它可能不是你阅读最容易的,但总体来说还不错。 由David M. Bourg,Glenn Seemann为游戏开发者提供AI 。

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

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

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