在 Java 2d 游戏中寻找路径？

Path finding in a Java 2d Game?

提问by Click Upvote

Essentially its a pacman clone game I'm working on. I have an Enemy class, and 4 instances of this class created which all represent 4 ghosts of the game.

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

All ghosts start up in random areas of the screen and then they have to work their way towards the pacman character. As the player controls the pacman, moving it around, they should follow it and take the nearest possible way towards him.

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

There is no maze/obstacles (yet) so the entire map (400x400 pixels) is open ground to them.

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

For the player and each Ghost, i can retrieve the X, Y, image width and height attributes. Also, i already have a collision detection algorithm, so not worried about that, just about the ghosts finding their way to pacman.

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

回答by coobird

For a good pathfinding algorithm, using A*would probably be a good idea, however, for a simple game that doesn't require sophisticated, efficient, nor effective path searching, simply having the characters move toward a target by finding out the direction of the target should be sufficient.

对于一个好的寻路算法，使用A*可能是一个好主意，但是，对于一个不需要复杂、高效或有效的路径搜索的简单游戏，只需让角色通过找出方向移动到目标目标应该足够了。

For example, the decision to make the character move, in pseudocode:

例如，让角色移动的决定，伪代码：

if (target is to the left of me):
    move(left);
else
    move(right);

if (target is above me):
    move(up);
else
    move(down);

Yes, the character is not going to make the most efficient movement, but it will get closer and closer to the target on each iteration of the game loop.

是的，角色不会做出最有效的移动，但它会在游戏循环的每次迭代中越来越接近目标。

It's also my guess that an arcade game from the early 80's probably wouldn't be using sophisticated pathfinding algorithms.

我也猜测 80 年代早期的街机游戏可能不会使用复杂的寻路算法。

回答by poundifdef

If you just have a grid of pixels - an "big field" on which pacman and ghost can move about freely - then the shortest path is easy - a straight line between the ghost and the pacman.

如果你只有一个像素网格——一个“大场”，吃豆子和鬼魂可以在上面自由移动——那么最短的路径很容易——鬼魂和吃豆子之间的一条直线。

But "shortest path" invariably means we're trying to solve a graph-theory problem. (I'm assuming knowledge of graphs, some graph theory, adj. matrices, etc!)

但是“最短路径”总是意味着我们正在尝试解决图论问题。（我假设了解图、一些图论、调整矩阵等！）

In the case above, consider each pixel to be a node on a graph. Each node is connected to its neighbors by an edge, and each edge has equal "weight" (moving to the node on "above" is no slower than moving to the node "below").

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

So you have this: ("*" = node, "-, /, \, |" = edge)

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

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

If Pacman is in the center, it can move to any other node very easily.

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

Something more closer to reality might be this:

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

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

Now, pacman cannot move diagonally. To go from the center to the bottom-right requires 2 "hops" rather than one.

现在，吃豆子不能对角移动。从中心到右下角需要 2 个“跳跃”而不是一个。

To continue the progression:

继续推进：

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

Now, to go from a node in the middle to a node at the top, you need 3 hops. However, to move toward the bottom only takes 1 hop.

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

It would be easy to translate any game-board setup into a graph. Each "intersection" is a node. The path between two intersections is an edge, and the length of that path is the weight of that edge.

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

Enter A*. By constructing a graph (use an adjency matrix or a list of nodes), you can use the A* algorithm to find the shortest path. Other algorithms include Dijkstra's. And many others! But first you need to frame your problem in terms of a graph, and then toy with how you'd go from node A (pacman) to node B (ghost).

进入一个*。通过构建图（使用邻接矩阵或节点列表），您可以使用 A* 算法找到最短路径。其他算法包括 Dijkstra 算法。还有很多其他的！但是首先您需要根据图表来构建您的问题，然后玩弄如何从节点 A（吃豆人）到节点 B（幽灵）。

Hope that helps!

希望有帮助！

回答by cygil

It's been a very long time, but from memory the ghosts in Pac-Man didn't do much in the way of pathfinding. They would do a fairly standard randomized maze traversal until they "spotted" you, which involved finding an unobstructed path along the axis of a corridor towards you, and then they would move directly towards you until you disappeared from their line of sight, whereupon they would resume a random pattern. On higher levels Pac-Man would leave invisible trails behind him for a while that the ghosts would "smell" and sometimes follow.

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

When Pac-Man got a power up, the only difference in the algorithm is that, when they spotted you, the ghosts would flee you instead of moving towards you.

当吃豆人通电时，算法的唯一区别是，当他们发现您时，鬼魂会逃离您而不是向您移动。

So, for an authentic experience, you probably don't need a very sophisticated pathfinding algorithm at all. If you want to be fancy, of course, you can implement A*.

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

回答by Daan van Yperen

Walking directly towards your enemies is a start but when you add a maze you'll want to add a bit smarter pathfinding so your ghosts don't get stuck in bends or dead ends.

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

The following tutorial is a great lightweight guide to get started with A*, with downloadable examples.

以下教程是 A* 入门的一个很好的轻量级指南，包含可下载的示例。

Path Finding on Tile based Maps

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

回答by PATRY Guillaume

in Pacman all of the ghost had a different chasing algorithm

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

• Blinky -> Chases. Will usually take the shortest route to you, and tends to follow.
• Pinky -> Ambushes. Tends to take a more roundabout way to pac-man. Deadly. (pinky and blinky tend to make different choice when choosing a direction , often caging the player in a corner)
• Inky -> Freak. This dude acts strangely. He moves about the board fairly randomly, but sometimes chases when he gets in close.
• Clyde -> Idiot. Moves randomly. Not much of a threat.

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

The ghosts have an interesting pattern programmed into their movements: occasionally, they will simultaneously cease and desist their pursuit of Pac-Man and return to their respective corners of the maze, entering "scatter mode".

鬼魂在它们的动作中编程了一个有趣的模式：偶尔，它们会同时停止并停止对吃豆人的追击，并返回迷宫的各自角落，进入“分散模式”。

there is a full description of the algo at the pacman dossier

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

regards

问候

Guillaume

纪尧姆

回答by TofuBeer

You could start looking at A* (A star)

你可以开始看 A*（A 星）

And here is a pagethat has links to other path finding algorithms.

而这里是一个页面有链接到其他寻路算法。

[edit] gah... brain is too slow... forgot about this book, it is C or C++ (I forget which), but you can still get the concepts for Java. It may not be the easiest for you to read, but isn't bad overall. AI for Game Developers by David M. Bourg, Glenn Seemann.

[edit] gah...脑子太慢了...忘记这本书了，是C还是C++（我忘了哪个），但你仍然可以获得Java的概念。它可能不是最容易阅读的，但总体来说还不错。 游戏开发者的人工智能 作者：David M. Bourg、Glenn Seemann。

回答by Faisal Feroz

I think go for the shortest path algorithm at every move made by pacman. A very good implementation is Dijkstra's algorithm.

我认为在吃豆子的每一个动作中都采用最短路径算法。一个很好的实现是Dijkstra 算法。

Just to summarize: Visualize the maze as a graph with vertices and edges. Each edge has a wait (in your case all the edges have same weight). The algorithm finds the shortest path from source vertice to target vertice by moving one step down each immediate reachable edge. Then on the next vertice you do the same and keep on doing until to you get to the target. The first path reached is the shortest path. There can be many optimizations done to this algorithm to speed up the things like taking into account where the pacman was in its previous position and in which direction it moved so that you can get some heiristics in the algorithm. I would suggest finding the shortest path from each ghost to pacman on every movement and move the ghost in that direction. Eventually the distance will reduce and you will be able to catch pacman.

总结一下：将迷宫可视化为具有顶点和边的图形。每个边缘都有一个等待（在您的情况下，所有边缘都具有相同的权重）。该算法通过将每个直接可达边向下移动一步来找到从源顶点到目标顶点的最短路径。然后在下一个顶点上做同样的事情并继续做直到到达目标。到达的第一条路径是最短路径。可以对该算法进行许多优化以加快处理速度，例如考虑吃豆人在其先前位置的位置以及移动的方向，以便您可以在算法中获得一些继承。我建议在每个动作中找到从每个鬼魂到吃豆子的最短路径，并将鬼魂朝那个方向移动。最终距离会减少，你将能够赶上吃豆子。

Another heuristic that can be used it to find all the immediate edges reachable from pacman and try to cover as many of these vertices as possible by ghosts. So instead of setting pacman as the target vertice we set the vertices immediatetly reachable by pacman as target, the result will be that the available ghosts will try to cover up themajor escape routes of pacman and catch him.

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