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