For my PacMan game I made a somewhat "shortest multiple path home" algorithm which works for what ever labyrinth I provide it with (within my set of rules). It also works across them tunnels.
When the level is loaded, all the path home data in every crossroad is empty (default) and once the ghosts start to explore the labyrinth, them crossroad path home information keeps getting updated every time they run into a "new" crossroad or from a different path stumble again upon their known crossroad.
According to a lot of what I've read, including the Pac-Man dossier, it would appear the ghosts target the grid directly above the ghost house "door" and use the normal movement restrictions that they normally use for normal movement.
The original pac-man didn't use path-finding or fancy AI. It just made gamers believe there is more depth to it than it actually was, but in fact it was random. As stated in Artificial Intelligence for Games/Ian Millington, John Funge.
Not sure if it's true or not, but it makes a lot of sense to me. Honestly, I don't see these behaviors that people are talking about. Red/Blinky for ex is not following the player at all times, as they say. Nobody seems to be consistently following the player, on purpose. The chance that they will follow you looks random to me. And it's just very tempting to see behavior in randomness, especially when the chances of getting chased are very high, with 4 enemies and very limited turning options, in a small space. At least in its initial implementation, the game was extremely simple. Check out the book, it's in one of the first chapters.
Knowing that pacman paths are non-random (ie, each specific level 0-255, inky, blinky, pinky, and clyde will work the exact same path for that level).
I would take this and then guess there are a few master paths that wraps around the entire
maze as a "return path" that an eyeball object takes pending where it is when pac man ate the ghost.
pacman 中的幽灵或多或少遵循可预测的模式，首先尝试在 X 或 Y 上进行匹配，直到达到目标。我一直认为这对于眼睛寻找回来的路来说是完全相同的。
The ghosts in pacman follow more or less predictable patterns in terms of trying to match on X or Y first until the goal was met. I always assumed that this was exactly the same for eyes finding their way back.
My approach is a little memory intensive (from the perspective of Pacman era), but you only need to compute once and it works for any level design (including jumps).
Label Nodes Once
When you first load a level, label all the monster lair nodes 0 (representing the distance from the lair). Proceed outward labelling connected nodes 1, nodes connected to them 2, and so on, until all nodes are labelled. (note: this even works if the lair has multiple entrances)
I'm assuming you already have objects representing each node and connections to their neighbours. Pseudo code might look something like this:
public void fillMap(List<Node> nodes) { // call passing lairNodes
int i = 0;
while(nodes.count > 0) {
// Label with distance from lair
nodes.labelAll(i++);
// Find connected unlabelled nodes
nodes = nodes
.flatMap(n -> n.neighbours)
.filter(!n.isDistanceAssigned());
}
}
Eyes Move to Neighbour with Lowest Distance Label
Once all the nodes are labelled, routing the eyes is trivial... just pick the neighbouring node with the lowest distance label (note: if multiple nodes have equal distance, it doesn't matter which is picked). Pseudo code:
x = getRelativeOppositeLatitudinalCoord()
y
origX = x
while(eyesNotInPen())
x = getRelativeOppositeLatitudinalCoordofGate()
y = getRelativeOppositeLongitudinalCoordofGate()
if (getRelativeOppositeLatitudinalCoordofGate() == 0 && move(y) == false/*assume zero is neither left or right of the the gate and false means wall is in the way */)
while (move(y) == false)
move(origX)
x = getRelativeOppositeLatitudinalCoordofGate()
else if (move(x) == false) {
move(y)
endWhile
I don't know much on how you implemented your game but, you could do the following:
Determine the eyes location relative position to the gate. i.e. Is it left above? Right below?
Then move the eyes opposite one of the two directions (such as make it move left if it is right of the gate, and below the gate) and check if there are and walls preventing you from doing so.
If there are walls preventing you from doing so then make it move opposite the other direction (for example, if the coordinates of the eyes relative to the pin is right north and it was currently moving left but there is a wall in the way make it move south.
Remember to keep checking each time to move to keep checking where the eyes are in relative to the gate and check to see when there is no latitudinal coordinate. i.e. it is only above the gate.
In the case it is only above the gate move down if there is a wall, move either left or right and keep doing this number 1 - 4 until the eyes are in the den.
I've never seen a dead end in Pacman this code will not account for dead ends.
Also, I have included a solution to when the eyes would "wobble" between a wall that spans across the origin in my pseudocode.
Some pseudocode:
x = getRelativeOppositeLatitudinalCoord()
y
origX = x
while(eyesNotInPen())
x = getRelativeOppositeLatitudinalCoordofGate()
y = getRelativeOppositeLongitudinalCoordofGate()
if (getRelativeOppositeLatitudinalCoordofGate() == 0 && move(y) == false/*assume zero is neither left or right of the the gate and false means wall is in the way */)
while (move(y) == false)
move(origX)
x = getRelativeOppositeLatitudinalCoordofGate()
else if (move(x) == false) {
move(y)
endWhile
dtb23's suggestion of just picking a random direction at each corner, and eventually you'll find the monster-hole sounds horribly ineficient.
However you could make use of its inefficient return-to-home algorithm to make the game more fun by introducing more variation in the game difficulty. You'd do this by applying one of the above approaches such as your waypoints or the flood fill, but doing so non-deterministically. So at every corner, you could generate a random number to decide whether to take the optimal way, or a random direction.
As the player progresses levels, you reduce the likelihood that a random direction is taken. This would add another lever on the overall difficulty level in addition to the level speed, ghost speed, pill-eating pause (etc). You've got more time to relax while the ghosts are just harmless eyes, but that time becomes shorter and shorter as you progress.
Short answer, not very well. :) If you alter the Pac-man maze the eyes won't necessarily come back. Some of the hacks floating around have that problem. So it's dependent on having a cooperative maze.
I would propose that the ghost stores the path he has taken from the hole to the Pacman. So as soon as the ghost dies, he can follow this stored path in the reverse direction.
This was the best source that I could find on how it actually worked.
http://gameai.com/wiki/index.php?title=Pac-Man#Respawn
When the ghosts are killed, their disembodied eyes return to their starting location. This is simply accomplished by setting the ghost's target tile to that location. The navigation uses the same rules.
It actually makes sense. Maybe not the most efficient in the world but a pretty nice way to not have to worry about another state or anything along those lines you are just changing the target.
Side note: I did not realize how awesome those pac-man programmers were they basically made an entire message system in a very small space with very limited memory ... that is amazing.
queue q
enqueue q, ghost_origin
set visited
while q has squares
p <= dequeue q
for each square s adjacent to p
if ( s not in visited ) then
add s to visited
s.returndirection <= direction from s to p
enqueue q, s
end if
next
next
这个想法是，这是一个广度优先搜索，因此每次遇到新的相邻方块 s 时，最佳路径都是通过 p 。我确实相信这是 O(N) 。
Here's an analog and pseudocode to ammoQ's flood fill idea.
queue q
enqueue q, ghost_origin
set visited
while q has squares
p <= dequeue q
for each square s adjacent to p
if ( s not in visited ) then
add s to visited
s.returndirection <= direction from s to p
enqueue q, s
end if
next
next
The idea is that it's a breadth-first search, so each time you encounter a new adjacent square s, the best path is through p. It's O(N) I do believe.
Assuming you already have the logic required for chasing pacman why not reuse that? Just change the target. Seems like it would be a lot less work than trying to create a whole new routine using the exact same logic.
How about each square having a value of distance to the center? This way for each given square you can get values of immediate neighbor squares in all possible directions. You pick the square with the lowest value and move to that square.
Values would be pre-calculated using any available algorithm.
Any simple solution that works is maintainable, reliable and performs well enough is a good solution. It sounds to me like you have already found a good solution ...
An path-finding solution is likely to be more complicated than your current solution, and hence more likely to require debugging. It will probably also be slower.
IMO, if it ain't broken, don't fix it.
EDIT
IMO, if the maze is fixed then your current solution is good / elegant code. Don't make the mistake of equating "good" or "elegant" with "clever". Simple code can also be "good" and "elegant".
If you have configurable maze levels, then maybe you should just do the pathfinding when you initially configure the mazes. Simplest would be to get the maze designer to do it by hand. I'd only bother automating this if you have a bazillion mazes ... or users can design them.
(Aside: if the routes are configured by hand, the maze designer could make a level more interesting by using suboptimal routes ... )
In the original Pacman the Ghost found the yellow pill eater by his "smell" he would leave a trace on the map, the ghost would wander around randomly until they found the smell, then they would simply follow the smell path which lead them directly to the player. Each time Pacman moved, the "smell values" would get decreased by 1.
Now, a simple way to reverse the whole process would be to have a "pyramid of ghost smell", which has its highest point at the center of the map, then the ghost just move in the direction of this smell.
Actually, I'd say your approach is a pretty awesome solution, with almost zero-run time cost compared to any sort of pathfinding.
If you need it to generalise to arbitrary maps, you could use any pathfinding algorithm - breadth-first search is simple to implement, for example - and use that to calculate which directions to encode at each of the corners, before the game is run.
EDIT (11th August 2010): I was just referred to a very detailed page on the Pacman system: The Pac-Man Dossier, and since I have the accepted answer here, I felt I should update it. The article doesn't seem to cover the act of returning to the monster house explicitly but it states that the direct pathfinding in Pac-Man is a case of the following:
continue moving towards the next intersection (although this is essentially a special case of 'when given a choice, choose the direction that doesn't involve reversing your direction, as seen in the next step);
at the intersection, look at the adjacent exit squares, except the one you just came from;
picking one which is nearest the goal. If more than one is equally near the goal, pick the first valid direction in this order: up, left, down, right.
I've solved this problem for generic levels that way: Before the level starts, I do some kind of "flood fill" from the monster hole; every tile of the maze that isn't a wall gets a number that says how far it is away from the hole. So when the eyes are on a tile with a distance of 68, they look which of the neighbouring tiles has a distance of 67; that's the way to go then.
发布评论
评论（23）
对于我的 PacMan 游戏，我做了一个有点“
最短多路径回家< /a>”算法适用于我提供的任何迷宫（在我的规则集内）。它也适用于穿过隧道。加载关卡后，每个十字路口的所有
路径家乡数据都是空的（默认），一旦幽灵开始探索迷宫，他们的十字路口路径家乡信息就会不断获取每次他们遇到“新”十字路口或从不同的路径再次绊倒他们已知的十字路口时都会更新。For my PacMan game I made a somewhat "
shortest multiple path home" algorithm which works for what ever labyrinth I provide it with (within my set of rules). It also works across them tunnels.When the level is loaded, all the
path home data in every crossroadis empty (default) and once the ghosts start to explore the labyrinth, themcrossroad path home informationkeeps getting updated every time they run into a "new" crossroad or from a different path stumble again upon their known crossroad.根据我读过的很多内容，包括吃豆人档案，鬼魂似乎瞄准了鬼屋“门”正上方的网格，并使用了它们通常用于正常移动的正常移动限制。
According to a lot of what I've read, including the Pac-Man dossier, it would appear the ghosts target the grid directly above the ghost house "door" and use the normal movement restrictions that they normally use for normal movement.
最初的吃豆人没有使用寻路或花哨的人工智能。它只是让玩家相信它比实际更有深度，但事实上它是随机的。正如《游戏人工智能》/Ian Millington、John Funge 中所述。
不确定这是否属实，但这对我来说很有意义。老实说，我没有看到人们谈论的这些行为。正如他们所说，前任的 Red/Blinky 并不总是跟随玩家。似乎没有人故意持续跟踪玩家。在我看来，他们跟随你的机会是随机的。看到随机行为是非常诱人的，特别是当被追赶的机会非常高、有 4 个敌人、转弯选项非常有限、空间狭小时。至少在最初的实现中，游戏非常简单。看看这本书，它在第一章中。
The original pac-man didn't use path-finding or fancy AI. It just made gamers believe there is more depth to it than it actually was, but in fact it was random. As stated in Artificial Intelligence for Games/Ian Millington, John Funge.
Not sure if it's true or not, but it makes a lot of sense to me. Honestly, I don't see these behaviors that people are talking about. Red/Blinky for ex is not following the player at all times, as they say. Nobody seems to be consistently following the player, on purpose. The chance that they will follow you looks random to me. And it's just very tempting to see behavior in randomness, especially when the chances of getting chased are very high, with 4 enemies and very limited turning options, in a small space. At least in its initial implementation, the game was extremely simple. Check out the book, it's in one of the first chapters.
知道 pacman 路径是非随机的（即，每个特定级别 0-255、inky、blinky、pinky 和 clyde 将在该级别使用完全相同的路径）。
我会接受这个，然后猜测有一些主路径环绕整个
迷宫作为“返回路径”，当吃豆人吃掉鬼魂时，眼球对象会选择迷宫。
Knowing that pacman paths are non-random (ie, each specific level 0-255, inky, blinky, pinky, and clyde will work the exact same path for that level).
I would take this and then guess there are a few master paths that wraps around the entire
maze as a "return path" that an eyeball object takes pending where it is when pac man ate the ghost.
pacman 中的幽灵或多或少遵循可预测的模式，首先尝试在 X 或 Y 上进行匹配，直到达到目标。我一直认为这对于眼睛寻找回来的路来说是完全相同的。
The ghosts in pacman follow more or less predictable patterns in terms of trying to match on X or Y first until the goal was met. I always assumed that this was exactly the same for eyes finding their way back.
节点列表中最近的节点
享受吧！
nearest node in your node list
Enjoy!
我的方法有点占用内存（从吃豆人时代的角度来看），但你只需要计算一次，它适用于任何关卡设计（包括跳跃）。
标记节点一次
当您第一次加载关卡时，将所有怪物巢穴节点标记为 0（代表距巢穴的距离）。继续向外标记连接的节点 1，连接到它们的节点 2，依此类推，直到所有节点都被标记。 （注意：如果巢穴有多个入口，这甚至可以工作）
我假设您已经拥有代表每个节点以及与其邻居的连接的对象。伪代码可能如下所示：
眼睛移动到具有最小距离标签的邻居
一旦标记了所有节点，路由眼睛就很简单了......只需选择距离最近的邻居节点标签（注意：如果多个节点距离相等，则选择哪个节点并不重要）。伪代码：
完全标记示例
My approach is a little memory intensive (from the perspective of Pacman era), but you only need to compute once and it works for any level design (including jumps).
Label Nodes Once
When you first load a level, label all the monster lair nodes 0 (representing the distance from the lair). Proceed outward labelling connected nodes 1, nodes connected to them 2, and so on, until all nodes are labelled. (note: this even works if the lair has multiple entrances)
I'm assuming you already have objects representing each node and connections to their neighbours. Pseudo code might look something like this:
Eyes Move to Neighbour with Lowest Distance Label
Once all the nodes are labelled, routing the eyes is trivial... just pick the neighbouring node with the lowest distance label (note: if multiple nodes have equal distance, it doesn't matter which is picked). Pseudo code:
Fully Labelled Example
我不太了解你如何实现你的游戏，但是，你可以执行以下操作：
，我在我的伪
I don't know much on how you implemented your game but, you could do the following:
Some pseudocode:
dtb23 建议在每个角落随机选择一个方向，最终你会发现怪物洞听起来非常低效。
然而，您可以利用其低效的返航算法，通过在游戏难度中引入更多变化来使游戏变得更有趣。您可以通过应用上述方法之一（例如路径点或洪水填充）来实现此目的，但这样做是不确定的。所以在每个拐角处，你都可以生成一个随机数来决定是走最优路线，还是随机方向。
随着玩家升级，您会降低随机方向的可能性。除了关卡速度、幽灵速度、吃药暂停等之外，这将为整体难度级别增加另一个杠杆。当鬼魂只是无害的眼睛时，你有更多的时间放松，但随着你的进步，时间会变得越来越短。
dtb23's suggestion of just picking a random direction at each corner, and eventually you'll find the monster-hole sounds horribly ineficient.
However you could make use of its inefficient return-to-home algorithm to make the game more fun by introducing more variation in the game difficulty. You'd do this by applying one of the above approaches such as your waypoints or the flood fill, but doing so non-deterministically. So at every corner, you could generate a random number to decide whether to take the optimal way, or a random direction.
As the player progresses levels, you reduce the likelihood that a random direction is taken. This would add another lever on the overall difficulty level in addition to the level speed, ghost speed, pill-eating pause (etc). You've got more time to relax while the ghosts are just harmless eyes, but that time becomes shorter and shorter as you progress.
简短的回答，不太好。 :) 如果你改变了吃豆人迷宫，眼睛不一定会回来。一些流行的黑客有这个问题。所以这取决于有一个合作的迷宫。
Short answer, not very well. :) If you alter the Pac-man maze the eyes won't necessarily come back. Some of the hacks floating around have that problem. So it's dependent on having a cooperative maze.
我建议幽灵存储他从洞到吃豆人的路径。所以一旦鬼魂死了，他就可以沿着这条存储的路径反向行驶。
I would propose that the ghost stores the path he has taken from the hole to the Pacman. So as soon as the ghost dies, he can follow this stored path in the reverse direction.
这是我能找到的关于它实际工作原理的最佳来源。
http://gameai.com/wiki/index.php?title=Pac -Man#Respawn
当鬼魂被杀死时，他们脱离实体的眼睛会回到原来的位置。这只需将幽灵的目标图块设置到该位置即可完成。导航使用相同的规则。
这实际上是有道理的。也许不是世界上最有效的，但这是一种非常好的方法，不必担心另一个状态或任何类似的事情，你只是改变目标。
旁注：我没有意识到那些吃豆人程序员有多棒，他们基本上在非常小的空间和非常有限的内存中创建了整个消息系统......这太棒了。
This was the best source that I could find on how it actually worked.
http://gameai.com/wiki/index.php?title=Pac-Man#Respawn
When the ghosts are killed, their disembodied eyes return to their starting location. This is simply accomplished by setting the ghost's target tile to that location. The navigation uses the same rules.
It actually makes sense. Maybe not the most efficient in the world but a pretty nice way to not have to worry about another state or anything along those lines you are just changing the target.
Side note: I did not realize how awesome those pac-man programmers were they basically made an entire message system in a very small space with very limited memory ... that is amazing.
我认为你的解决方案是正确的问题，比这更简单，是使新版本更“现实”，鬼眼可以穿过墙壁=）
I think your solution is right for the problem, simpler than that, is to make a new version more "realistic" where ghost eyes can go through walls =)
这是 ammoQ 的洪水填充想法的模拟和伪代码。
这个想法是，这是一个广度优先搜索，因此每次遇到新的相邻方块 s 时，最佳路径都是通过 p 。我确实相信这是 O(N) 。
Here's an analog and pseudocode to ammoQ's flood fill idea.
The idea is that it's a breadth-first search, so each time you encounter a new adjacent square s, the best path is through p. It's O(N) I do believe.
假设您已经拥有追逐 pacman 所需的逻辑，为什么不重用它呢？只是改变目标。看起来这比尝试使用完全相同的逻辑创建一个全新的例程要少得多。
Assuming you already have the logic required for chasing pacman why not reuse that? Just change the target. Seems like it would be a lot less work than trying to create a whole new routine using the exact same logic.
这是一个寻路问题。对于流行的算法，请参见 http://wiki.gamedev.net/index.php/A *。
It's a pathfinding problem. For a popular algorithm, see http://wiki.gamedev.net/index.php/A*.
每个正方形都有一个到中心的距离值怎么样？这样，对于每个给定的方格，您可以获得所有可能方向上紧邻方格的值。您选择具有最低值的方格并移动到该方格。
将使用任何可用的算法预先计算值。
How about each square having a value of distance to the center? This way for each given square you can get values of immediate neighbor squares in all possible directions. You pick the square with the lowest value and move to that square.
Values would be pre-calculated using any available algorithm.
任何有效、可维护、可靠且性能足够好的简单解决方案都是一个好的解决方案。在我看来，您已经找到了一个很好的解决方案......
路径查找解决方案可能比您当前的解决方案更复杂，因此更有可能需要调试。它可能也会更慢。
IMO，如果它没有坏，就不要修理它。
编辑
IMO，如果迷宫已修复，那么您当前的解决方案是良好/优雅的代码。不要错误地将“好”或“优雅”等同于“聪明”。简单的代码也可以“好”、“优雅”。
如果您有可配置的迷宫级别，那么也许您应该在最初配置迷宫时进行寻路。最简单的方法是让迷宫设计师手工完成。如果你有无数的迷宫，或者用户可以设计它们，我只会费心将其自动化。
（旁白：如果路线是手动配置的，迷宫设计者可以通过使用次优路线使关卡变得更有趣......）
Any simple solution that works is maintainable, reliable and performs well enough is a good solution. It sounds to me like you have already found a good solution ...
An path-finding solution is likely to be more complicated than your current solution, and hence more likely to require debugging. It will probably also be slower.
IMO, if it ain't broken, don't fix it.
EDIT
IMO, if the maze is fixed then your current solution is good / elegant code. Don't make the mistake of equating "good" or "elegant" with "clever". Simple code can also be "good" and "elegant".
If you have configurable maze levels, then maybe you should just do the pathfinding when you initially configure the mazes. Simplest would be to get the maze designer to do it by hand. I'd only bother automating this if you have a bazillion mazes ... or users can design them.
(Aside: if the routes are configured by hand, the maze designer could make a level more interesting by using suboptimal routes ... )
在最初的《吃豆人》中，幽灵通过他的“气味”找到了黄色的吃药丸的人，他会在地图上留下痕迹，幽灵会随机徘徊，直到发现气味，然后他们会简单地沿着气味路径直接到达玩家。吃豆人每次移动，“气味值”都会减少 1。
现在，扭转整个过程的一个简单方法是建立一个“幽灵气味金字塔”，其最高点位于地图的中心，然后鬼魂就朝着这个气味的方向移动。
In the original Pacman the Ghost found the yellow pill eater by his "smell" he would leave a trace on the map, the ghost would wander around randomly until they found the smell, then they would simply follow the smell path which lead them directly to the player. Each time Pacman moved, the "smell values" would get decreased by 1.
Now, a simple way to reverse the whole process would be to have a "pyramid of ghost smell", which has its highest point at the center of the map, then the ghost just move in the direction of this smell.
您应该看一下寻路算法，例如 Dijsktra 算法 或 A* 算法。这就是您的问题：图形/路径问题。
You should take a look a pathfindings algorithm, like Dijsktra's Algorithm or A* algorithm. This is what your problem is : a graph/path problem.
对于更传统的寻路算法的替代方案，您可以查看（适当命名！）吃豆人气味反物体图案。
你可以在启动时在迷宫周围散布怪物洞的气味，并让眼睛跟随它回家。
一旦气味设置好，运行时间成本就非常低。
编辑：遗憾的是维基百科文章已被删除，因此WayBack 机器来救援...
For an alternative to more traditional pathfinding algorithms, you could take a look at the (appropriately-named!) Pac-Man Scent Antiobject pattern.
You could diffuse monster-hole-scent around the maze at startup and have the eyes follow it home.
Once the smell is set up, runtime cost is very low.
Edit: sadly the wikipedia article has been deleted, so WayBack Machine to the rescue...
实际上，我想说你的方法是一个非常棒的解决方案，与任何类型的寻路相比，运行时间成本几乎为零。
如果您需要它泛化到任意地图，您可以使用任何寻路算法（例如，广度优先搜索很容易实现），并在游戏运行之前使用它来计算在每个角处编码的方向。
编辑（2010 年 8 月 11 日）：我刚刚提到了 Pacman 系统上一个非常详细的页面：吃豆人档案，既然我在这里有了公认的答案，我觉得我应该更新它。这篇文章似乎没有明确介绍返回怪物屋的行为，但它指出吃豆人中的直接寻路是以下情况：
Actually, I'd say your approach is a pretty awesome solution, with almost zero-run time cost compared to any sort of pathfinding.
If you need it to generalise to arbitrary maps, you could use any pathfinding algorithm - breadth-first search is simple to implement, for example - and use that to calculate which directions to encode at each of the corners, before the game is run.
EDIT (11th August 2010): I was just referred to a very detailed page on the Pacman system: The Pac-Man Dossier, and since I have the accepted answer here, I felt I should update it. The article doesn't seem to cover the act of returning to the monster house explicitly but it states that the direct pathfinding in Pac-Man is a case of the following:
我已经通过这种方式解决了通用关卡的这个问题：在关卡开始之前，我从怪物洞中进行某种“洪水填充”；迷宫中除墙之外的每一块瓷砖都有一个数字，表示它距洞有多远。因此，当眼睛注视距离为 68 的图块时，它们会查看相邻图块中哪一个距离为 67；那就这样吧。
I've solved this problem for generic levels that way: Before the level starts, I do some kind of "flood fill" from the monster hole; every tile of the maze that isn't a wall gets a number that says how far it is away from the hole. So when the eyes are on a tile with a distance of 68, they look which of the neighbouring tiles has a distance of 67; that's the way to go then.