Earlier this year, we required a true distraction from the chaos of this world and a sad tragedy in our closer circle. What would have been more rewarding for a little recovery than indulging oneself with game theory, paying homage to Toru Iwatani‘s classic Puckman? Both my sons loved the idea and we added this work to our little cs-class. My older one was eager to learn how the math behind the ghosts works. Euclidian geometry, Pythagoras, points and vectors .. plus the strategy of choosing targets WoW! 😉 We completed the little fun endeavor using C++17 and the SDL2 library, resulting in a working nostalgic re-implementation.
At the bottom of this article I have placed a little video recording, partially demonstrating the results.
Previous Work
To implement the original Puckman game behavior like weighted tile collision, ghost algorithm, etc. – we have used the following documents for reference
- Jamey Pittman’s The Pac-Man Dossier
- Chad Birch’s Understanding Pac-Man Ghost Behavior
- Don Hodges’s Why do Pinky and Inky have different behaviors when Pac-Man is facing up?
Game Insights
Generated Media for this Article
To generate the documenting video and snapshots, I used the following command-line arguments
./bin/pacman -wwidth 672 -wheight 864 -show_fps -show_debug_gfx -show_targets -show_fps -record video/snaps/pacman-10
The above also enables the debug graphics, quite useful to document the properties of the players, i.e. the ghost’s target and movement.
You can click on the thumbnail of the snapshots (diagrams) to see them in their original size.
Game Stages, Ghost Waves and Level Specs
On the left we can see each tile, the pellets, power-pellets as well as the red-zone where ghosts can’t move up and the blue tunnel zone where ghosts are not as speedy.
Additionally we see the scatter mode targets of each ghost in each of its colors outside of the maze.
Blinky (red) starts right away in front of the ghost house, while the others are waiting for their good time to leave home. See Home Sweet Home section in Jamey Pittman’s The Pac-Man Dossier.
All level specific timings, bonus points, speeds for each occasion, pellet counter and duration of CHASE and SCATTER waves are noted in the structure game_level_spec_t.
In general, ghost have the following states and transition in-between: HOME, where they start in a level and return when eaten in PHANTOM state. CHASE, when they chase our hero using each of their character specific target. SCATTER, where they pause chasing and target each of their exterior corner. SCARED, when our hero ate a power-pellet the ghosts become blue and pick a random target. PHANTOM, when our hero caught a ghost, it is returning home only showing its eyes.
The Chase
Usually ghosts are chasing our hero and each of them has their own little secret. Each ghost has its own individual target selection. Ghosts only chose a new direction one tile ahead of an intersection. They almost never reverse direction but when changing states, e.g. CHASE to SCATTER. Naturally, they try to minimize their distance to their picked target tile.
The right diagram shows all four ghosts, each moving towards their own target, see ghost_t::set_next_target()
- Blinky targets our hero Puckman directly.
- Pinky targets 4 tiles in front of Puckman using his current direction of travel (right diagram). However, when Puckman faces up, Pinky’s target adds 4 tiles to the left of Puckman (bottom-left diagram).
- Inky is the most fancy, working hand in hand with Blinky as shown in both diagrams right and bottom-left. Inky first selects the position two tiles in front of Puckman in his current direction of travel. From there, imagine drawing a vector from Blinky’s position to this tile and then doubling the length of the vector. The tile that this extended vector ends on will be Inky’s actual target.
- Clyde is also named shy for a reason. He usually also targets Puckman directly, but getting as close as 8 tiles he starts to target his SCATTER corner.
All ghosts are working together. While Blinky seems to be the most notorious and dangerous one, Pinky cuts off Puckman’s escape route to the front of his path. Then comes Clyde, heading even further into the Puckman’s escape route and together with Pinky trying to trap our hero, running away from Blinky. Add Clyde into the mix, chasing Puckman up to 8 tiles before he shies away at the next intersection, changing his mind 😉
Altogether, a quite amusing and efficient way to generate this everlasting game play.
Note that Pinky’s target being shifted 4 tiles left of an up-facing Puckman (left diagram) is due to a bug in the original implementation, as figure by Don Hodge. You can disable this original behavior or bug by passing command-line option -bugfix for the bugfix mode.
Scattering
As hinted above, the ghosts act together and shift their behavior in waves. Our hero can relax for a little while after the CHASE sequence while they are in SCATTER mode targeting each of their corner outside of the maze as shown in the right diagram.
The SCATTER duration naturally gets less often and shorter during game play in subsequent levels.
Sisyphus alike Ghost Fate, Scared and Phantoms
By now you may realize that all state names are chosen from the perspective of our dear ghosts.
Hence in SCARED mode, its the ghosts being scared of Puckman turning blue after eating a power-pellet as our hero shall never be scare in this game at all 😉
In SCARED mode, the ghosts pick a random target to follow. In the original implementation, these are the last bits of the content of a permuted 8-bit ROM address. Since we can’t use the original ROM, we use the original permutation as a seed for the std::mt19937 pseudo RNG.
Having caught a SCARED ghost, he turns into a PHANTOM only showing his eyes and heads back home. In his home office he then gets re-materialized only to start over, continuing his sisyphean task. Indeed, this last game detail gave me the association to this ancient Greek-Mythology fate. Surely, its only futile for them when encountering the best players in the world or using the command-line option -invincible 😉
Bottom line
This little introduction can’t cover all details. Perhaps you like to have a look at the source code, exposing all details.
Some other elements were of my interest
- Inter-tile movement and speed accuracy (see Frame Sync Timing below)
- Collision by player’s weighted tile position (original) or axis-aligned bounding box (AABBox), see bugfix mode.
Further I can only recommend to read the mentioned previous work above, as they detail almost every piece of this historical classic game.
Used media data in our code is referenced in the README.
Namco hold the copyright on the original Puckman since 1980.
Further details regarding copyright and license are also referenced in the README.
Accuracy of this Implementation
We have followed the references mentioned above very closely to achieve a most accurate default mode to match the original.
However, some aspects are not fully in our control and are discussed here.
PRNG Scared Mode
The original uses a known seeding iteration, used as a memory address within the game rom. The last bits of the addressed rom byte represents the PRNG value for the ghost’s direction in scared mode.
Since the roms can’t be used, we use the PRNG value of another algorithm with same seeding sequence to preserver the periodic attrbutes at least.
Frame Sync Timing
This implementation uses the monitor’s frames per second number to approximate the sub-tile step-width for the desired tiles per frame pace.
This is achieved via Keyframe interval for animation, see keyframei_t.
Below we added measurements from pacman via commandline argument -show_fps running along the bottom longest line from collision to collision.
For each level we measured the slower first walk eating pellets and the second walk faster without pellets.
Level 1: Fields/s deviation on longest line measured 7.955 f/s to 8.000 f/s or 0.5635%
bin/pacman -no_ghosts -show_fps -level 1
[ 8,471] pacman stats: speed 0.71%, td 3515ms, fields[25.00 walked, actual 7.112/s, requested 7.100/s, diff 0.1743%], fps[draw 60.03/s, tick 56.90/s], frames[draw 211, synced 11], [fps 60, frames/field 8, fields/s 7.500000/7.100000 (diff 0.400000, 3.200001f/s, 0.938969 ms, sync 19/f), center 0.500000], [26.500000/32.500000 26/32, last[dir R, collided 1], [walked[25.000000, 25], center 25, entered 25]]
[ 11,872] pacman stats: speed 0.80%, td 3017ms, fields[24.00 walked, actual 7.955/s, requested 8.000/s, diff 0.5635%], fps[draw 59.99/s, tick 56.02/s], frames[draw 181, synced 12], [fps 60, frames/field 7, fields/s 8.571428/8.000000 (diff 0.571428, 3.999998f/s, 1.190477 ms, sync 15/f), center 0.428571], [1.428571/32.428570 1/32, last[dir L, collided 1], [walked[23.999989, 23], center 24, entered 24]]
Level 5: Fields/s deviation on longest line measured 8.772 f/s to 8.700 f/s or 0.8267%
bin/pacman -no_ghosts -show_fps -level 5
[ 8,270] pacman stats: speed 0.87%, td 2850ms, fields[25.00 walked, actual 8.772/s, requested 8.700/s, diff 0.8267%], fps[draw 60.00/s, tick 52.63/s], frames[draw 171, synced 21], [fps 60, frames/field 6, fields/s 10.000000/8.700000 (diff 1.300000, 7.800001f/s, 2.490423 ms, sync 8/f), center 0.500000], [26.500000/32.500000 26/32, last[dir R, collided 1], [walked[24.999977, 25], center 25, entered 25]]
[ 11,004] pacman stats: speed 1.00%, td 2400ms, fields[23.83 walked, actual 9.931/s, requested 10.000/s, diff 0.6945%], fps[draw 60.00/s, tick 60.00/s], frames[draw 144, synced 0], [fps 60, frames/field 6, fields/s 10.000000/10.000000 (diff 0.000000, 0.000000f/s, 0.000000 ms, sync -1/f), center 0.500000], [1.500000/32.500000 1/32, last[dir L, collided 1], [walked[23.833315, 23], center 24, entered 23]]
Below 3% deviation should be good enough for this game using >= 10% speed differences in modes.
Below 1% deviation is a great match.
Video Recording
