游戏邦在:
杂志专栏:
gamerboom.com订阅到鲜果订阅到抓虾google reader订阅到有道订阅到QQ邮箱订阅到帮看

分享《吃豆人》制作档案第三章:寻径逻辑

发布时间:2013-12-11 17:10:05 Tags:,,,

作者:Jamey Pittman

我们得看看鬼如何在迷宫中移动和追击目标。本章节中描述的所有寻径逻辑都是四鬼共有的——在理解它们之间的区别以前,先研究它们的共性是非常重要的。我们先看看游戏如何追踪吃豆人和这四只鬼的位置。我们把可见的游戏屏幕当成一个正方形网格,每个格子边长为8像素。屏幕的实际像素是224 x 288,所以按8像素划分,就得到了一个由28 x 36个贴图组成的网格。(请点击此处阅读本文第一章第二章第四章、第五章

Tiles(from home.comcast.net)

Tiles(from home.comcast.net)

每一个贴图要么在合法区域,要么在死亡区域。在上图中,合法区域是灰色贴图组成的部分;其他贴图都是死亡区域。吃豆人和鬼只在合法区域内移动。各个中心有一点点的贴图表示它是一个正好8像素的贴图——这对于在游戏中估计距离是非常有用的。

我在什么贴图中?

随着角色在迷宫中移动,游戏会时时记录被占用的贴图。一个角色一次只能占用一个贴图,尽管从图像上看已经复盖到周围的贴图上了。角色的移动精确到像素级,所以它们通常不会直接在贴图的中心。观察以下例子:

Tile Move 2(from home.comcast.net)

Tile Move 2(from home.comcast.net)

上图显示的是,透明的红色鬼在合法区域中从左到右沿着一行贴图移动。在第一帧中,它占用的贴图(显示为亮红色)更靠近图的左侧。鬼的有些图像没有在贴图上并不重要——重要的是,这只鬼的中心点在贴图上。在第二帧,它的中心点已经移动到下一张贴图的右边了,它占用的贴图也相应地更新了。这只鬼继续移动,直到第六帧,它的中心点现在已经移到下一个贴图中了。

贴图的深层概念对于理解鬼的寻径逻辑是必须的,因为它只关心角色所占用的贴图——而不是它在这个贴图上的像素位置。对于这种逻辑性常规,这五个角色看起都非常相像,如下图所示。每个角色都是由它当前占用的贴图和它的当前移动方向定义的。角色之间的距离也是按贴图计算的(游戏邦注:比如,粉色鬼在水平上与吃豆人相距5个贴图,在竖直上相距1个贴图)。

Tile Game(from home.cast.net)

Tile Game(from home.cast.net)

穿过

《吃豆人》发布不久后,玩家当中开始传言,偶尔可以看到吃豆人直接穿过鬼而不受伤。这个传言是完全真实的,毕竟大部多资深《吃豆人》玩家都可以证实它。如果你玩这款游戏玩得够久,你最终会看到吃豆人撞上鬼却毫发无伤地出现在另一边——这种现象并不经常发生,所以当发生时就好好享受一下吧!有些玩家甚至在自己的模式中考虑到了这种神秘的“穿过”概率。

这种现象产生的根源在于,游戏检测吃豆人和四只鬼的碰撞的方法。任何时候吃豆人与鬼占用相同的一个贴图时,游戏总是判定是吃豆人撞上鬼,然后玩家损失一条命。是鬼移动到吃豆人占用的贴图上还是吃豆人移动到鬼占用的贴图上,并不重要——反正这两种情况的结果是一样的。对于处理游戏99%的时间的碰撞,这种逻辑已经够用了,但它没有考虑到一种非常特殊的情况:

Pass thru Bug(from home.comcast.net)

Pass thru Bug(from home.comcast.net)

上图显示的是产生这种特殊情况的必要条件。上排的五个相邻帧显示了Blinky鬼和吃豆人互相穿过。下排的帧用它们当前占用的贴图和它们的中心点的像素位置来表现相同的情景。吃豆人和鬼正好处于一个导致它们供销社交换贴图的位置和速度。换句话说,吃豆人的中心点向上移动到鬼的贴图,而鬼的中心点向下移动到吃豆人的贴图,二者的速度是相同的,导致它们穿过对方,游戏却没有检测到碰撞。注意,从上排帧看,吃豆人的原来位置是在第四帧的贴图的边缘;从下排帧看,这仍然被认为是在贴图的内部,但向上多移动1像素就会使它占用下一个贴图的边缘。吃豆人和鬼在第五帧时互换贴图,吃豆人可以继续它的愉快旅程,因为它没有被“撞上”鬼(即与鬼共享贴图)!

目标贴图

在追击模式或分散模式中,鬼总是试图达到屏幕上或(屏幕外)的“目标贴图”。所谓的目标贴图是指鬼在任何时刻都企图占用的贴图。这个贴图可以是固定的,也可以经常变化。例如,当鬼分散到屏幕到迷官的角落时,各个鬼都希望达到最接近它的“据点”角落的固定的目标贴图。在追击模式时,这个目标贴图通常(但不总是)与吃豆人当前占据的贴图有关。尽管可能一开始不明显,但追击模式和分散模式之间的唯一区别就是它的目标贴图所在的地方不同。而两种模式使用的寻径逻辑是一样的。

向前看

当鬼在迷宫中移动时,它总是想着下一步要走哪里。无论何时鬼进入一个新贴图,它就会沿着当前移动方向看到下一个贴图,然后决定当它到那个贴图时要走哪条路。当它到达那个贴图时,它会根据它之前预测的贴图改变它的前进方向。然后再重复这个决策过程,即沿着新方向看下一个贴图,再决定走哪条路。

当鬼看到下一个贴图时,它必须考虑这个贴图的可能出口,以决定往哪个方向走。在下图中,红鬼已经达到贴图A,正在由右向左移动。它立即向前看到贴图B(沿着前进方向的下一个贴图)。每个贴图都有四个可能的出口:右、左、上和下。对于贴图B,上和下出品被墙阻挡了,所以不能作为潜在的出口来考虑。右出口也不用考虑,因为它只能把鬼再次带回贴图A,而鬼是永远不会自动反向的。这样,贴图B的的四个可能出口中就只能选择左出口了。

AI Simple 2(from home.comcast.net)

AI Simple 2(from home.comcast.net)

这个例子清楚地表明,鬼只有一条合法的路可以前进。因此,我们不必关心它的目标贴图在哪里。游戏中位于合法区域的大部分贴图都与此类似,但当鬼到达一个具有更多潜在出口的贴图时,情况就变得更意思了。

十字路口

当鬼到达十字路口的前一贴图时,它必须在这三个方向中选择出口。思考以下例子:

Intersect ALL(from home.comcast.net)

Intersect ALL(from home.comcast.net)

在上图的左半图中,红鬼已经达到贴图A,正在寻找它的目标(表示为绿色贴图)。沿着当前方向,它立即看到下一个贴图。在这个例子中,那个贴图是一个十字路口。因为这个路口贴图的四个出口都没有被墙挡住,所以除了反向出口(下)不能选,还有三个出口可以走。鬼把十字路口的三个方向的第一个贴图选为“测试贴图”(游戏邦注:在图中用虚线框中的贴图)。在上图中间,鬼把这三线贴图和目标贴图之间作三角流量,找到距离目标最近的贴图,就是鬼的前进方向。在这个例子中,右边的测试贴图距离目标最近,所以鬼相应地选择它作为前进方向。

有时候,鬼会遇到两个与目标距离相等的测试贴图。在下图所示的例子中,红鬼必须在向下或向左之间作选择。不幸的是,两个测试贴图与目标(左上角的贴图)距离相等。为了解决这个问题,鬼会按上、左、下、右的顺序选择方向。上是最优先的方向,右是最末的方向。因此,图中的鬼会选择向左走,因为左的优先级比下高。尽管这对人来说,向下走显然是更好的选择,但鬼没有人那么聪明。它们不可能向前看到那么多个贴图,所以,它们自然无法意识到这两个选择之间的差异。

Tie Break ALL(from home.comcast.net)

Tie Break ALL(from home.comcast.net)

固定目标贴图

在分散模式中,每只鬼都有一个固定的目标贴图。下图显示的是四只鬼在分散模式中的各自目标的物理位置(目标与鬼的颜色相对应)。注意,各个目标贴图都在死亡区域,所以鬼是不可能到达的。这导致各只鬼朝着迷宫的角落前进,因为那是最接近各自目标的地方,然后在这个角落绕圈直到出现亲的的模式变化。这就是分散模式的真相。鬼在迷宫中有一个“最爱的角落”的唯一原因就是,固定的目标贴图在它永远达不到的位置。

当鬼被吃豆人吃掉时,游戏就会使用额外的固定目标贴图,它的没有身体的眼睛必须回到迷宫中心的鬼屋。这个目标就直接落在鬼屋“门口”的左边,在下图中用绿色贴图表示。

Scatter(from home.comcast.net)

Scatter(from home.comcast.net)

本文为游戏邦/gamerboom.com编译,拒绝任何不保留版权的转载,如需转载请联系:游戏邦

The Pac-Man Dossier

by Jamey Pittman

CHAPTER 3:

Maze Logic 101

We need to take a look at how ghosts are able to move through the maze in pursuit of a goal. All pathfinding logic described in this chapter is shared by the four ghosts—it is important to understand what they have in common before we get into what makes them different. Before we proceed, let’s see how the game tracks the location of Pac-Man and the four ghosts (herein referred to as actors for brevity’s sake). The visible game screen should be thought of as a regular grid of tiles, each eight pixels square. The actual pixel dimensions of the screen are 224 x 288, so dividing each value by eight yields a grid that is 28 x 36 tiles in size:

Each tile is either in legal space or dead space. In the picture above, legal space is shown as the gray-colored tiles; all other tiles are considered dead space. Actors only travel between the tiles in legal space. Each dot sits in the center of a tile, meaning they are exactly eight pixels (one tile) apart—this is useful for estimating distances during gameplay.

What Tile Am I In?

As the actors move through the maze, the game keeps track of the tile each one occupies. An actor is only associated with a single tile at a time, although its graphic will overlap into the surrounding tiles. The location of the actor’s center point is what determines the tile it occupies at any given time. As the actors can move at pixel-level precision, they are often not centered directly on top of the tile they are in. Consider the following example:

The transparent red ghost is moving left-to-right across a row of tiles in legal space. In frame one, its occupied tile (shown in bright red) is near the left side of the picture. It does not matter that some of the ghost’s graphic is not in the tile—what matters is that the ghost’s center point is in the tile. By frame two, it has moved far enough for its center point to be in the adjacent tile to the right and its occupied tile is updated accordingly. The ghost continues to be associated with the same tile until frame six where its center point has now crossed over into the next one.

The underlying concept of tiles is essential for understanding the ghosts’ pathfinding logic as it only cares about the tile an actor occupies—not its per-pixel location within that tile. To the logic routines, the five actors look very much like the picture below. Each actor is defined by the tile it presently occupies along with its current direction of travel. Distances between actors are also measured in tiles (the pink ghost is five tiles away from Pac-Man horizontally and one tile away vertically, for example).

Just Passing Through

It wasn’t too long after the release of Pac-Man when word began to spread of players occasionally passing straight through a ghost unharmed, seemingly at random. This rumor turned out to be completely true as most die-hard Pac-Man players can attest. If you play the game long enough, you will eventually see Pac-Man run into one of the ghosts and come out unscathed on the other side—it doesn’t happen very often so enjoy it when it does! Some players have even gone so far as to incorporate this mysterious pass-through oddity into their patterns.

The root cause of this elusive peculiarity lies in the way the game detects collisions between Pac-Man and the four ghosts. Any time Pac-Man occupies the same tile as a ghost, he is considered to have collided with that ghost and a life is lost. It is irrelevant whether the ghost moved into Pac-Man’s tile or Pac-Man into the ghost’s—the result is the same either way. This logic proves sufficient for handling collisions more than 99% of the time during gameplay, but does not account for one very special case:

The above picture illustrates the conditions necessary to produce this curious behavior. There are five consecutive frames showing Blinky and Pac-Man passing through each other. Below each frame is the same scene represented by the tiles they currently occupy and the per-pixel location of their center points. Pac-Man and Blinky are at just the right position and speed relative to one another to cause them to swap tiles with each other simultaneously. In other words, Pac-Man’s center point moves upwards into Blinky’s tile in the same 1/60th of a second that Blinky’s center point moves downwards into Pac-Man’s tile, resulting in them moving past each other without colliding. Note that Pac-Man’s origin point is centered on the top edge of his tile in frame four; this is still considered to be inside the bottom tile, but moving up one more pixel will push him over the edge into the next one. Pac-Man and Blinky have now swapped tiles with each other in frame five, and Pac-Man can go on his merry way because he never “collided” (i.e., shared the same tile) with Blinky at all! Click on the YouTube video below to see an example of the pass-through bug (it happens 40 seconds after playback begins):

Target Tiles

Whenever a ghost is in chase or scatter mode, it is trying to reach a target tile somewhere on (or off) the screen. A target tile is merely a way to describe the tile a ghost would like to occupy at any given moment. This tile can be fixed in place or change location frequently. Whenever the ghosts scatter to the corners of the maze, for example, each ghost is striving to reach a fixed target tile located somewhere near its home corner. In chase mode, the target tile is usually (but not always) related to Pac-Man’s current tile which changes often. Although it may not be obvious at first, the only difference between chase and scatter mode to a ghost is where its target tile is located. The same pathfinding logic applies in either case.

Looking Ahead

Ghosts are always thinking one step into the future as they move through the maze. Whenever a ghost enters a new tile, it looks ahead to the next tile along its current direction of travel and decides which way it will go when it gets there. When it eventually reaches that tile, it will change its direction of travel to whatever it had decided on a tile beforehand. The process is then repeated, looking ahead into the next tile along its new direction of travel and making its next decision on which way to go.

When a ghost looks ahead into the upcoming tile, it must examine the possible exits from that tile to determine a way to proceed. In the picture below, the red ghost has just arrived at tile A and is moving right-to-left. It immediately looks ahead to tile B (the next tile along its direction of travel). Each tile has four potential exits to be considered: right, left, up, and down. In the case of tile B, the up and down exits are blocked by walls and must be discarded as potential candidates. The right exit is also discounted because it would only take the ghost back to tile A again, and ghosts never voluntarily reverse direction. With three of the four possible exits eliminated from tile B, moving left is the only remaining choice.

This example is the most simple to explain as the ghost has but one way it can legally move. As such, we did not have to worry about where its target tile was located. The majority of game tiles in legal space are similar to this one, but things get more interesting when a ghost approaches a tile with more potential exits to choose from.

Intersections

When a ghost arrives one tile away from an upcoming intersection, it must choose between several possible directions in which to proceed. Consider the following example:

In the first picture, the red ghost has just reached tile A and is seeking its target (shown as the green tile). It immediately looks ahead to the subsequent tile along its present direction of travel (up). In this case, that tile is a four-way intersection. As this intersection tile has no walls blocking off any of the exits, the ghost can only discard his reverse direction (down), leaving three exits open for travel. It looks one tile beyond the intersection in each of the three remaining directions, collecting “test tiles” (shown as the tiles with dashed, white lines). In the middle picture, the ghost triangulates the distance from each of these test tiles to its target tile. Whichever direction’s test tile has the shortest distance to the target becomes the direction the ghost will take upon reaching the intersection tile. In this case, the right test tile has the shortest distance to the target, and the ghost updates its chosen direction for the intersection tile accordingly.

Sometimes a ghost is presented with two or more test tiles that have the same distance to the target tile. In the example below, the red ghost must choose between moving down or left at the upcoming intersection tile. Unfortunately, both test tiles have the same distance to the target (bottom left). To break the tie, the ghost prefers directions in this order: up, left, down, right. Up is the most preferred direction; right is the least. Therefore, the ghost chooses to go left at the intersection because left precedes down in the preference list. Although it may seem obvious to a person that going down was the better choice to reach the target, ghosts are not that smart. They cannot see more than a few tiles ahead and, as a consequence, cannot recognize the disparity between these two options.

Fixed Target Tiles

Each ghost has a fixed target tile it tries to reach while in scatter mode. The picture below shows the physical location of the scatter mode targets used by each ghost (matched to each ghost’s color scheme). Notice each target tile is in dead space above or below the actual maze making them impossible for the ghosts to reach. This results in each ghost heading toward the corner of the maze nearest its respective scatter target and then making circles around this area until another mode change occurs. That’s all scatter mode really is. The only reason a ghost has a “favorite corner” of the maze at all is due to the location of a fixed target tile it will never reach.

An additional fixed target tile is employed whenever a ghost is eaten by Pac-Man and its disembodied eyes need to return to the ghost house in the center of the maze. This target is located directly above the left side of the “door” to the ghost house and is shown in the picture below as the green tile.(source:home.comcast)


上一篇:

下一篇: