Pac-Man

From AIGPG Wiki
(Difference between revisions)
Jump to: navigation, search
m
m (hooked up image)
Line 5: Line 5:
 
{{GameInfoBox
 
{{GameInfoBox
 
|gametitle=Pac-Man
 
|gametitle=Pac-Man
|imagefile=http://upload.wikimedia.org/wikipedia/en/5/59/Pac-man.png
+
|imagefile=Pac-man.png
 
|developer=Namco
 
|developer=Namco
 
|publisher=Namco, Midway
 
|publisher=Namco, Midway
Line 90: Line 90:
  
 
==Reception by Public==
 
==Reception by Public==
 
+
(TODO)
  
 
==References==
 
==References==

Revision as of 08:38, 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

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).


Architectures

The AI for the Pac-Man ghosts is a collection of very simple rules. Each of the 4 ghosts has their own ruleset that differs significantly from the others. When used in combination, however, they give the illusion of complex behavior. Because each ghost's behavior is specific to only that ghost, each will be listed separately.

Navigation

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.

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.

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 flee modes. Selection of the target tiles is based on the individual ghost logic (below).

Intersections

Navigation decisions are made just before a ghost reaches an intersection. 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.

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.

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.

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.

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.

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.

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 "flee" 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.

Flee

When the player eats one of the "power pills", the ghosts change into "flee" mode. When this happens, 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 "fleeing" from the player but merely scattering in 4 different directions. Another result of this is that, as time passes and the ghosts move apart during "flee mode", it is more difficult for the player to reach all 4 of them.

Post-Mortem

What Worked

Simple Rules Create Complex Environment

The careful construction of simple rules for the 4 ghosts provided myriad gameplay scenarios.

What Didn't Work

Predictability Leads to Exploitation

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. However, as these patterns were discerned and shared between the gaming community, 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.

Lessons Learned

(TODO)

Reception by Public

(TODO)

References

  1. The Pac-Man Dossier, Jamey Pittman, web,
  2. Pinky seek bug, Don Hodges, web, 2009


External Links

Wikipedia:Pac-Man

The History of Pac-Man

Understanding Pac-Man Ghost Behavior

Personal tools