Java 2d 游戏中的路径查找？
本质上它是我正在开发的一款吃豆人克隆游戏。 我有一个 Enemy 类，并创建了该类的 4 个实例，它们都代表游戏的 4 个幽灵。
所有幽灵都会在屏幕的随机区域启动，然后它们必须朝着吃豆人角色前进。 当玩家控制吃豆人并移动它时，他们应该跟随它并尽可能靠近他。
目前还没有迷宫/障碍物，因此整个地图（400x400 像素）对他们来说都是开放的。
对于玩家和每个幽灵，我可以检索 X、Y、图像宽度和高度属性。 另外，我已经有了一个碰撞检测算法，所以不用担心这个，只担心鬼魂找到吃豆人的路。
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.
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.
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
对于一个好的寻路算法，使用 A* 可能是一个好主意，但是，一个简单的游戏，不需要复杂、高效或有效的路径搜索，只需让角色通过找出目标的方向向目标移动就足够了。
例如，让角色移动的决定，用伪代码表示：
是的，角色不会做出最有效的移动，但它会在游戏循环的每次迭代中越来越接近目标。
我还猜测 80 年代初的街机游戏可能不会使用复杂的寻路算法。
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.
For example, the decision to make the character move, in pseudocode:
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.
如果你只有一个像素网格 - 一个“大区域”，吃豆人和吃豆人可以在上面自由移动 - 那么最短路径很简单 - 幽灵和吃豆人之间的一条直线。
但“最短路径”总是意味着我们正在尝试解决图论问题。 （我假设了解图、一些图论、调节矩阵等！）
在上面的情况下，将每个像素视为图上的一个节点。 每个节点都通过一条边与其邻居相连，并且每条边都具有相等的“权重”（移动到“上方”的节点并不比移动到“下方”的节点慢）。
所以你有这样的： ("*" = 节点，"-, /, \, |" = 边缘)
如果 Pacman 位于中心，它可以很容易地移动到任何其他节点。
更接近现实的事情可能是这样的：
现在，吃豆人不能沿对角线移动。 从中心到右下角需要 2 次“跳跃”，而不是 1 次。
继续前进：
现在，要从中间的节点到顶部的节点，您需要 3 跳。 然而，向底部移动只需要 1 跳。
将任何游戏板设置转换成图表都很容易。 每个“交叉点”都是一个节点。 两个交叉点之间的路径是一条边，该路径的长度就是该边的权重。
进入一个*。 通过构建图（使用邻接矩阵或节点列表），您可以使用 A* 算法来查找最短路径。 其他算法包括 Dijkstra 算法。 还有很多其他的！ 但首先您需要用图表来构建问题，然后考虑如何从节点 A (pacman) 到节点 B (ghost)。
希望有帮助！
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)
If Pacman is in the center, it can move to any other node very easily.
Something more closer to reality might be this:
Now, pacman cannot move diagonally. To go from the center to the bottom-right requires 2 "hops" rather than one.
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.
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).
Hope that helps!
已经过去很长时间了，但据我记忆，《吃豆人》中的鬼魂并没有在寻路方面做太多事情。 他们会进行相当标准的随机迷宫遍历，直到他们“发现”你，这涉及到沿着走廊的轴线找到一条通向你的无障碍路径，然后他们会直接向你移动，直到你从他们的视线中消失，然后他们将恢复随机模式。 在较高的水平上，吃豆人会在他身后留下一段看不见的痕迹，鬼魂会“闻到”，有时会跟随。
当吃豆人获得力量时，算法的唯一区别是，当它们发现你时，幽灵会逃离你而不是向你移动。
因此，为了获得真实的体验，您可能根本不需要非常复杂的寻路算法。 如果你想花哨，当然可以实现A*。
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* 入门指南，包含可下载的示例。
在基于图块的地图上查找路径
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.
Path Finding on Tile based Maps
在 Pacman 中，所有的幽灵都有不同的追逐算法
（pinky和blinky在选择方向时往往会做出不同的选择，经常将玩家困在角落里）
鬼魂的动作有一个有趣的模式：有时，它们会同时停止追寻吃豆人，并返回迷宫各自的角落，进入“分散模式”。
算法的完整描述
Guillaume
pacman dossier 中有该
in Pacman all of the ghost had a different chasing algorithm
(pinky and blinky tend to make different choice when choosing a direction , often caging the player in a corner)
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
regards
Guillaume
您可以开始查看 A*（A 星）
和 这里是一个页面，其中包含其他路径查找算法的链接。
[编辑] 啊...大脑太慢了...忘记了这本书，它是C 或C++（我忘了是哪一个），但你仍然可以获得Java 的概念。 对于您来说，它可能不是最容易阅读的，但总体来说还不错。 面向游戏开发者的 AI，作者：David M.格伦·西曼·布尔格。
You could start looking at A* (A star)
And here is a page that 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.
我认为 pacman 的每一个动作都采用最短路径算法。 一个非常好的实现是 Dijkstra 算法。
总结一下：将迷宫可视化为具有顶点和边的图。 每条边都有一个等待（在您的情况下，所有边都具有相同的权重）。 该算法通过在每个直接可达的边上向下移动一步来找到从源顶点到目标顶点的最短路径。 然后在下一个顶点做同样的事情并继续做，直到到达目标。 到达的第一条路径是最短路径。 可以对该算法进行许多优化，以加快速度，例如考虑吃豆人在其先前位置的位置以及它移动的方向，以便您可以在算法中获得一些启发。 我建议在每次移动时找到从每个幽灵到吃豆人的最短路径，并将幽灵朝那个方向移动。 最终距离会缩短，你将能够追上吃豆人。
另一种启发式方法可用于查找 pacman 可到达的所有直接边缘，并尝试通过幽灵覆盖尽可能多的这些顶点。 因此，我们不是将 pacman 设置为目标顶点，而是将 pacman 可立即到达的顶点设置为目标，结果将是可用的幽灵会尝试掩盖 pacman 的主要逃生路线并抓住他。
I think go for the shortest path algorithm at every move made by pacman. A very good implementation is Dijkstra's algorithm.
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.