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

Question

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

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

没有迷宫/障碍物(尚未)所以整个地图(400x400像素)都是开放的.

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

Answer 1

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

Answer 2

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

但"最短路径"总是意味着我们正试图解决图论理论问题.(我假设有图形知识,一些图形理论,辅助矩阵等等!)

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

所以你有这个:("*"= node," - ,/,\,|"= edge)

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

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

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

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

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

继续进展:

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

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

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

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

希望有所帮助!