Pac-Man

From AIGPG Wiki
(Difference between revisions)
Jump to: navigation, search
(Behavior Modes: Changed section title to Architectures and moved some wording around.)
m (Architectures)
 
Line 37: Line 37:
  
 
==Architectures==
 
==Architectures==
Pac-Man uses a very simple [[finite state machine]] to control the behavior of the ghosts. The ghosts have 4 behavior states that they can be in. The ghosts spend most of their time in either "[[#scatter|scatter]]" or "[[#chase|chase]]" mode. When the player has eaten a power pill, the ghosts change to "[[#frightened|frightened]]" mode. After being eaten by Pac-Man, the ghosts switch to "[[#respawn|respawn]]" until they have returned to their base.
+
Pac-Man uses a very simple [[Finite State Machine|state machine]] to control the behavior of the ghosts. The ghosts have 4 behavior states that they can be in. The ghosts spend most of their time in either "[[#scatter|scatter]]" or "[[#chase|chase]]" mode. When the player has eaten a power pill, the ghosts change to "[[#frightened|frightened]]" mode. After being eaten by Pac-Man, the ghosts switch to "[[#respawn|respawn]]" until they have returned to their base.
  
 
They switch between chase and scatter happens on a fixed timer. The amount of time spent in each mode is different for each level with the bias being towards chase mode as the levels increase. The result of alternating between these two modes is that there is an ebb and flow to the interactions with the ghosts. This was by design as explained by creator, Tōru Iwatani.
 
They switch between chase and scatter happens on a fixed timer. The amount of time spent in each mode is different for each level with the bias being towards chase mode as the levels increase. The result of alternating between these two modes is that there is an ebb and flow to the interactions with the ghosts. This was by design as explained by creator, Tōru Iwatani.

Latest revision as of 15:04, 15 July 2011


Pac-Man
Pac-man.png
Developer: Namco
Publisher: Namco, Midway
Year: 1980
Platforms: Arcade
Genre: Maze
AI Era: Simple Hard-coded Rules

Designed by Tōru Iwatani for Namco in 1980, Pac-Man is one of the earliest, most-recognizable, and iconic arcade games. The player is in a maze alternately fleeing from and chasing 4 "ghosts".

Contents

[edit] Description of AI Behavior

The ghosts in Pac-Man act as threats requiring the player to avoid them ("chase" mode). However, when the player "eats" one of the power pills and, becomes invulnerable for a period of time, the ghosts change roles and must avoid being caught ("flee" mode). When the ghosts are caught by Pac-Man, their disembodied eyes return to their starting pen where the ghost "respawns".


[edit] Game Terms

There are some general principles about how the game works that need to be understood before one can discuss how the actual decision AI of the ghosts operates.

[edit] Tiles

There are some general rules that the ghosts follow when navigating the maze. The game space is broken up into "tiles" that the ghosts use to navigate. This is different than if they were to use a per-pixel location system.

[edit] Target Tiles

The current navigation of the ghost is based upon a "target tile" which serves as a goal for the ghost to move toward. This system is used regardless of whether the ghosts are in chase or scatter modes. Selection of the target tiles is based on the individual ghost logic (below).

[edit] Intersections

Navigation decisions are made just before a ghost reaches an intersection. The type of decision that a ghost makes is dependent on which mode it is in. When a ghost is in "frightened" mode, it simply selects a random direction prior to the intersection. In "chase" mode, however, there is more advanced decision processing.

When in the tile prior to the intersection, it looks at all the exit options from that intersection. It then measures the euclidean distance from that tile to the target tile and selects the tile that has the shortest distance. If the ghost is faced with 2 options that are the same distance from the target tile, the tie is broken by preferring directions in the following order: up, left, down, right.

Note that there is no decision made at the intersections other than how to get to the current target tile. Therefore, this phase can adequately be compared to steering behaviors.

[edit] Architectures

Pac-Man uses a very simple state machine to control the behavior of the ghosts. The ghosts have 4 behavior states that they can be in. The ghosts spend most of their time in either "scatter" or "chase" mode. When the player has eaten a power pill, the ghosts change to "frightened" mode. After being eaten by Pac-Man, the ghosts switch to "respawn" until they have returned to their base.

They switch between chase and scatter happens on a fixed timer. The amount of time spent in each mode is different for each level with the bias being towards chase mode as the levels increase. The result of alternating between these two modes is that there is an ebb and flow to the interactions with the ghosts. This was by design as explained by creator, Tōru Iwatani.

“To give the game some tension, I wanted the monsters to surround Pac Man at some stage of the game. But I felt it would be too stressful for a human being like Pac Man to be continually surrounded and hunted down. So I created the monsters’ invasions to come in waves. They’d attack and then they’d retreat. As time went by they would regroup, attack, and disperse again. It seemed more natural than having constant attack.”

The AI for the Pac-Man ghosts is a collection of very simple rules that they apply depending on which of 4 states they are in. In some of the states, each of the 4 ghosts has a ruleset that differs significantly from the others. When used in combination, however, they give the illusion of complex behavior.

[edit] Chase

The normal state for the ghosts is the "chase" behavior. Note that this term is used loosely because not all the ghosts are actually "chasing" the player. The word "chase" is used more as an identifier of the game state. Because each ghost's behavior in the "chase" state is specific to only that ghost, each will be listed separately.

[edit] Blinky

The red ghost's AI is specifically designed to be aggressive towards the player due to the fact that its target tile is set to the tile that Pac-Man is currently in. It is the only ghost that is actively pursuing the player.

Additionally, Blinky is the only ghost that changes speed throughout the course of a single level. The timing of the speed change is based on the number of (non-power-up) dots remaining. On the first level, for example, Blinky will accelerate to be as fast as Pac-Man when there are 20 dots remaining and again to be slightly faster than Pac-Man when there are only 10 dots remaining. The result of this is an increased sense of tension as the player is finishing a particular level.

These two thresholds for speed changes differ by level, happening earlier as the level number increases.

[edit] Pinky

The pink ghost's AI is designed to "feel" opposite of the red ghost's behavior. Pinky actually attempts to get out in front of Pac-Man. This is accomplished by setting the target 4 tiles ahead of Pac-Man's current location in the direction that Pac-Man is travelling. One exception to this is when Pac-Man is traveling up. Due to an overflow bug in the code, the calculation includes a left offset equal to the expected up offset.

The use of Pac-Man's expected position allows the player to exploit the navigation code for Pinky. This was most often seen in situations where Pac-Man and Pinky are in close proximity to each other. For example, if they were headed toward one another, once they are less than 4 tiles apart, the target tile is now behind Pinky. If he encounters an intersection while in this configuration, he will attempt to double-back (by turning) in order to reach the target tile.

Player's would often perform what was referred to as a "head fake" by changing directions rapidly just as Pinky was approaching an intersection. By displacing the target tile just as Pinky was doing the distance and navigation calculations, the player could often force Pinky to move in certain directions. These techniques quickly became part of advanced players' strategies.

[edit] Inky

The blue ghost uses the most complicated targeting scheme of all the ghosts. Despite being perfectly deterministic, due to the more complex nature of the calculations, Inky is actually the least predictable of the ghosts.

The location of the target tile is actually a hybrid of two calculations. In order to arrive at Inky's target tile, you must use two pieces of data:

First, in a similar manner to Pinky, extend Pac-Man's current direction out two tiles (similar to Pinky's four-tile lead) to arrive at an "offset". Second, draw a vector from Blinky's current position to this offset tile. By doubling the length of this vector, we get Inky's target tile.

Note that depending on the configuration of the actors, this target tile may be in front of Pac-Man (such as when Blinky is pursuing behind Pac-Man), behind Pac-Man (when Blinky is approaching from the front), or deflected to one side or another. Additionally, as this configuration changes, the target tile may vary rapidly. Note also that because Pac-Man's current direction is used as part of the calculation, Inky is susceptible to the "head fake" in a similar way to Pinky. Because of the inclusion of Blinky's location, however, trying to control Inky's movement is far less practical.

[edit] Clyde

The orange ghost is the least aggressive of the ghosts due to his target tile code. There are two parts to Clyde's chase calculations separated by a simple IF statement. If Clyde's location is greater than 8 tiles (Euclidean) away from Pac-Man, he uses the same targeting as Blinky (head directly towards Pac-Man). Once he is within 8 tiles, however, Clyde switches his target tile to his normal patrol corner as per his "scatter" behavior. This means that Clyde will never directly encounter the player unless the player makes a poor decision and gets between Clyde and his corner.

[edit] Scatter

In "scatter" mode, each ghost's target tile is changed to a location outside the maze. These targets are positioned with one outside each corner. The result is that each ghost will go to a different corner and, because they can't actually reach the target tile, will circle in that corner until they go back to chase mode.

Note that the ghosts are not really "scattering" from the player but merely moving in 4 different directions.

[edit] Frightened

While in "frightened" mode, the ghost chooses random directions to go when approaching each intersection. This is the only mode where the ghost is not using a target tile.

[edit] 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.

[edit] Post-Mortem

[edit] What Worked

[edit] Simple Rules Create Complex Environment

The careful construction of simple rules for the 4 ghosts created emergent behavior provided myriad gameplay scenarios. While the behaviors of the ghosts seemed complex and almost sentient, there was very little decision-making going on. Novice players felt that there was more AI happening than was actually present. Indeed, the differing rules for the ghosts made for very complex combinations of behaviors.

[edit] Waves

By alternating between "chase" and "scatter" modes, a subtle sense of tension and release was generated rather than constantly having the pressure on the player.

[edit] Personality

The individual rulesets for each ghost created a personality for that ghost. The traits of this personality were evident enough that the names of the real names of the ghosts were aligned somewhat with them. These were as follows:

  • Blinky, the ghost who follows Pac-Man, was named "Shadow"
  • Pinky, the ghost getting in front, was "Speedy" (despite the fact that he wasn't any faster)
  • Inky, the ghost who always was on the periphery, was "Bashful"
  • Clyde, the ghost who seemed to just do his own thing, was "Pokey"

This would not have worked if the rules were simply chosen randomly by each ghost. Instead, by being associated with each color, the player was able to use this knowledge to his advantage in assessing and beating the pattern.

[edit] Appearance of Cooperation

Because of the way the individual chase rules were crafted, there seemed to be an implicit cooperation between the ghosts. For example, with Blinky always following Pac-Man and Pinky mostly trying to get in front, the player often felt "boxed in". In reality, the only ghost that used the position of another ghost in its calculations was Inky who only indirectly used the location of Blinky to determine its target tile.

[edit] What Didn't Work

[edit] Predictability Leads to Exploitation

Despite the complex-looking behavior, there was no randomness involved in the AI. Even despite the fact that people were often thrown off by the seemingly random behaviors of Inky and Clyde, because the rules were simple, patterns could not only be recognized but they could be pre-determined.

These patterns were discerned and shared between the gaming community and the game quickly became "broken". The designers thought that by simply increasing the speed of the game as levels progressed, they would prevent players from "beating" the game. This however, was not the case.

Every level beyond the 21st was identical -- both in maze construction and the speed of the ghosts -- therefore, the optimal pattern to "solve" the level was the same. At that point, the game devolved into an endurance test to see how long a player could go before making a mistake.

[edit] Lessons Learned

(TODO)

[edit] Reception by Public

(TODO)


[edit] References

  1. The Pac-Man Dossier, Jamey Pittman, web,
  2. Pinky seek bug, Don Hodges, web, 2009
  3. Understanding Pac-Man Ghost Behavior, Chad Birch, GameInternals web site,


[edit] External Links

Personal tools