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的主要逃生路线并抓住他。