{"id":1065,"date":"2022-05-31T18:04:34","date_gmt":"2022-05-31T22:04:34","guid":{"rendered":"https:\/\/jausoft.com\/blog\/?p=1065"},"modified":"2023-10-09T06:55:09","modified_gmt":"2023-10-09T10:55:09","slug":"chase-scatter-and-phantoms-sisyphus-alike-ghost-fate","status":"publish","type":"post","link":"https:\/\/jausoft.com\/blog\/2022\/05\/31\/chase-scatter-and-phantoms-sisyphus-alike-ghost-fate\/","title":{"rendered":"Chase, Scatter and Phantoms &#8211; Sisyphus alike Ghost Fate"},"content":{"rendered":"<p>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 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Toru_Iwatani\">Toru Iwatani<\/a>&#8216;s classic <a href=\"https:\/\/en.wikipedia.org\/wiki\/Pac-Man\">Puckman<\/a>? Both my sons loved the idea and we added this work to our little <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/\">cs-class<\/a>. My older one was eager to learn how the math behind the ghosts works. <a href=\"https:\/\/en.wikipedia.org\/wiki\/Euclidean_geometry\">Euclidian geometry<\/a>, <a href=\"https:\/\/en.wikipedia.org\/wiki\/Pythagorean_theorem\">Pythagoras<\/a>, points and vectors .. plus the strategy of choosing targets <em>WoW!<\/em> \ud83d\ude09 We completed the little fun endeavor using C++17 and the <a href=\"https:\/\/www.libsdl.org\/\">SDL2 library<\/a>, resulting in a <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/pacman.git\/about\/\">working nostalgic re-implementation<\/a>.<\/p>\n<p>At the bottom of this article <a href=\"#video-recording\">I have placed a little video recording<\/a>, partially demonstrating the results.<!--more--><\/p>\n<h2 id=\"previous-work\">Previous Work<\/h2>\n<p>To implement the original Puckman game behavior like weighted tile collision, ghost algorithm, etc. &#8211; we have used the following documents for reference<\/p>\n<ul>\n<li>Jamey Pittman&#8217;s <a href=\"https:\/\/www.gamedeveloper.com\/design\/the-pac-man-dossier\">The Pac-Man Dossier<\/a><\/li>\n<li>Chad Birch&#8217;s <a href=\"https:\/\/gameinternals.com\/understanding-pac-man-ghost-behavior\">Understanding Pac-Man Ghost Behavior<\/a><\/li>\n<li>Don Hodges&#8217;s <a href=\"http:\/\/donhodges.com\/pacman_pinky_explanation.htm\">Why do Pinky and Inky have different behaviors when Pac-Man is facing up?<\/a><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h2>Game Insights<\/h2>\n<h3>Generated Media for this Article<\/h3>\n<p>To generate the documenting video and snapshots, I used the following command-line arguments<\/p>\n<pre>.\/bin\/pacman -wwidth 672 -wheight 864 -show_fps -show_debug_gfx -show_targets -show_fps -record video\/snaps\/pacman-10<\/pre>\n<p>The above also enables the debug graphics, quite useful to document the properties of the players, i.e. the ghost&#8217;s target and movement.<\/p>\n<p>You can click on the thumbnail of the snapshots (diagrams) to see them in their original size.<\/p>\n<h3>Game Stages, Ghost Waves and Level Specs<\/h3>\n<p><a href=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-01-start.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignleft wp-image-1076 size-medium\" src=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-01-start-233x300.png\" alt=\"Diagram 1\" width=\"233\" height=\"300\" srcset=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-01-start-233x300.png 233w, https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-01-start.png 672w\" sizes=\"auto, (max-width: 233px) 100vw, 233px\" \/><\/a><\/p>\n<p>On the left we can see each tile, the pellets, power-pellets as well as the red-zone where ghosts can&#8217;t move up and the blue tunnel zone where ghosts are not as speedy.<\/p>\n<p>Additionally we see the scatter mode targets of each ghost in each of its colors outside of the maze.<\/p>\n<p>Blinky (red) starts right away in front of the ghost house, while the others are waiting for their good time to leave home. See <em>Home Sweet Home<\/em> section in Jamey Pittman&#8217;s <a href=\"https:\/\/www.gamedeveloper.com\/design\/the-pac-man-dossier\">The Pac-Man Dossier<\/a>.<\/p>\n<p>All level specific timings, bonus points, speeds for each occasion, pellet counter and duration of <em>CHASE<\/em> and <em>SCATTER<\/em> waves are noted in the structure <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/pacman.git\/tree\/src\/game.cpp#n126\">game_level_spec_t<\/a>.<\/p>\n<p>In general, ghost have the following states and transition in-between: <em>HOME<\/em>, where they start in a level and return when eaten in <em>PHANTOM<\/em> state. <em>CHASE<\/em>, when they chase our hero using each of their character specific target. <em>SCATTER<\/em>, where they pause chasing and target each of their exterior corner. <em>SCARED<\/em>, when our hero ate a power-pellet the ghosts become blue and pick a random target. <em>PHANTOM<\/em>, when our hero caught a ghost, it is returning home only showing its eyes.<\/p>\n<h3>The Chase<\/h3>\n<p>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. <em>CHASE<\/em> to <em>SCATTER. <\/em>Naturally, they try to minimize their distance to their picked target tile.<\/p>\n<p><a href=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-02-chase01.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignright wp-image-1103 size-medium\" src=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-02-chase01-233x300.png\" alt=\"\" width=\"233\" height=\"300\" srcset=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-02-chase01-233x300.png 233w, https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-02-chase01.png 672w\" sizes=\"auto, (max-width: 233px) 100vw, 233px\" \/><\/a>The right diagram shows all four ghosts, each moving towards their own target, see <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/pacman.git\/tree\/src\/ghost.cpp#n142\">ghost_t::set_next_target()<\/a><\/p>\n<ul>\n<li>Blinky targets our hero Puckman directly.<\/li>\n<li>Pinky targets 4 tiles in front of Puckman using his current direction of travel (right diagram). However, when Puckman faces up, Pinky&#8217;s target adds 4 tiles to the left of Puckman (bottom-left diagram).<\/li>\n<li>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&#8217;s position to this tile and then doubling the length of the vector. The tile that this extended vector ends on will be Inky&#8217;s actual target.<\/li>\n<li>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 <em>SCATTER<\/em> corner.<\/li>\n<\/ul>\n<p><a href=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-02-chase04.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignleft wp-image-1068 size-medium\" src=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-02-chase04-233x300.png\" alt=\"\" width=\"233\" height=\"300\" srcset=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-02-chase04-233x300.png 233w, https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-02-chase04.png 672w\" sizes=\"auto, (max-width: 233px) 100vw, 233px\" \/><\/a>All ghosts are working together. While Blinky seems to be the most notorious and dangerous one, Pinky cuts off Puckman&#8217;s escape route to the front of his path.\u00a0 Then comes Clyde, heading even further into the Puckman&#8217;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 \ud83d\ude09<\/p>\n<p>Altogether, a quite amusing and efficient way to generate this everlasting game play.<\/p>\n<p>Note that Pinky&#8217;s target being shifted 4 tiles left of an up-facing Puckman (left diagram) is due to a bug in the original implementation, <a href=\"http:\/\/donhodges.com\/pacman_pinky_explanation.htm\">as figure by Don Hodge<\/a>. You can disable this original behavior or bug by passing command-line option <em><code>-bugfix<\/code><\/em> for the <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/pacman.git\/about\/#bugfix-mode\">bugfix mode<\/a>.<\/p>\n<p>&nbsp;<\/p>\n<h3>Scattering<\/h3>\n<p><a href=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-03-scatter01.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignright wp-image-1070 size-medium\" src=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-03-scatter01-233x300.png\" alt=\"\" width=\"233\" height=\"300\" srcset=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-03-scatter01-233x300.png 233w, https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-03-scatter01.png 672w\" sizes=\"auto, (max-width: 233px) 100vw, 233px\" \/><\/a>As hinted above, the ghosts act together and shift their behavior in waves. Our hero can relax for a little while after the <em>CHASE<\/em> sequence while they are in <em>SCATTER<\/em> mode targeting each of their corner outside of the maze as shown in the right diagram.<\/p>\n<p>The <em>SCATTER<\/em> duration naturally gets less often and shorter during game play in <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/pacman.git\/tree\/src\/game.cpp#n126\">subsequent levels<\/a>.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<h3><em><a href=\"https:\/\/en.wikipedia.org\/wiki\/Sisyphus\">Sisyphus<\/a> alike Ghost Fate, Scared and Phantoms<\/em><\/h3>\n<p><a href=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-05-fright01.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignleft wp-image-1071 size-medium\" src=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-05-fright01-233x300.png\" alt=\"\" width=\"233\" height=\"300\" srcset=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-05-fright01-233x300.png 233w, https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-05-fright01.png 672w\" sizes=\"auto, (max-width: 233px) 100vw, 233px\" \/><\/a>By now you may realize that all state names are chosen from the perspective of our dear ghosts.<\/p>\n<p>Hence in <em>SCARED<\/em> 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 \ud83d\ude09<\/p>\n<p>In <em>SCARED<\/em> 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 <em>ROM<\/em> address. Since we can&#8217;t use the original <em>ROM<\/em>, we use the <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/pacman.git\/tree\/include\/pacman\/utils.hpp#n350\">original permutation as a seed for the <em>std::mt19937<\/em> pseudo <em>RNG<\/em>.<\/a><code><\/code><\/p>\n<p><a href=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-05-fright03.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignright wp-image-1073 size-medium\" src=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-05-fright03-233x300.png\" alt=\"\" width=\"233\" height=\"300\" srcset=\"https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-05-fright03-233x300.png 233w, https:\/\/jausoft.com\/blog\/wp-content\/uploads\/2022\/05\/pacman-10-05-fright03.png 672w\" sizes=\"auto, (max-width: 233px) 100vw, 233px\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<p>Having caught a <em>SCARED<\/em> ghost, he turns into a <em>PHANTOM<\/em> only showing his eyes and heads back home. In his <em>home office<\/em> 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 <em><code>-invincible<\/code> \ud83d\ude09<\/em><\/p>\n<p>&nbsp;<\/p>\n<h3>Bottom line<\/h3>\n<p>This little introduction can&#8217;t cover all details. Perhaps you like to have a look <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/pacman.git\/about\/\">at the source code<\/a>, exposing all details.<\/p>\n<p>Some other elements were of my interest<\/p>\n<ul>\n<li>Inter-tile movement and speed accuracy (see <em>Frame Sync Timing <\/em>below)<\/li>\n<li>Collision by player&#8217;s weighted tile position (original) or axis-aligned bounding box (AABBox), see <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/pacman.git\/about\/#bugfix-mode\">bugfix mode<\/a>.<\/li>\n<\/ul>\n<p>Further I can only recommend to read the <a href=\"#previous-work\">mentioned previous work above<\/a>, as they detail almost every piece of this historical classic game.<\/p>\n<p>Used media data in our code is <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/pacman.git\/about\/#media-data\">referenced in the README<\/a>.<\/p>\n<p>Namco hold the copyright on the original <em>Puckman<\/em> since 1980.<\/p>\n<p>Further details regarding copyright and license are also <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/pacman.git\/about\/#license-and-copyrights\">referenced in the README<\/a>.<\/p>\n<h2>Accuracy of this Implementation<\/h2>\n<p>We have followed <a href=\"#previous-work\">the references mentioned above<\/a> very closely to achieve a most accurate default mode to match the original.<\/p>\n<p>However, some aspects are not fully in our control and are discussed here.<\/p>\n<h3 id=\"prng-scared-mode\">PRNG Scared Mode<\/h3>\n<p>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&#8217;s direction in scared mode.<\/p>\n<p>Since the roms can&#8217;t be used, we use the PRNG value of another algorithm with same seeding sequence to preserver the periodic attrbutes at least.<\/p>\n<h3 id=\"frame-sync-timing\">Frame Sync Timing<\/h3>\n<p>This implementation uses the monitor&#8217;s frames per second number to approximate the sub-tile step-width for the desired tiles per frame pace.<\/p>\n<p>This is achieved via Keyframe interval for animation, see <a href=\"https:\/\/jausoft.com\/cgit\/cs_class\/pacman.git\/tree\/include\/pacman\/utils.hpp#n96\">keyframei_t<\/a>.<\/p>\n<p>Below we added measurements from pacman via commandline argument <code>-show_fps<\/code> running along the bottom longest line from collision to collision.<\/p>\n<p>For each level we measured the slower first walk eating pellets and the second walk faster without pellets.<\/p>\n<p>Level 1: Fields\/s deviation on longest line measured 7.955 f\/s to 8.000 f\/s or 0.5635%<\/p>\n<pre class=\"{.sh}\"><code>bin\/pacman -no_ghosts -show_fps -level 1\r\n\r\n[    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]]\r\n\r\n[   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]]\r\n<\/code><\/pre>\n<p>Level 5: Fields\/s deviation on longest line measured 8.772 f\/s to 8.700 f\/s or 0.8267%<\/p>\n<pre class=\"{.sh}\"><code>bin\/pacman -no_ghosts -show_fps -level 5\r\n\r\n[    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]]\r\n\r\n[   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]]\r\n<\/code><\/pre>\n<p>Below 3% deviation should be good enough for this game using &gt;= 10% speed differences in modes.<\/p>\n<p>Below 1% deviation is a great match.<\/p>\n<h2 id=\"video-recording\">Video Recording<\/h2>\n<div style=\"width: 640px;\" class=\"wp-video\"><video class=\"wp-video-shortcode\" id=\"video-1065-1\" width=\"640\" height=\"360\" preload=\"metadata\" controls=\"controls\"><source type=\"video\/mp4\" src=\"https:\/\/jausoft.com\/Files\/media\/20220531-pacman-10.mp4?_=1\" \/><a href=\"https:\/\/jausoft.com\/Files\/media\/20220531-pacman-10.mp4\">https:\/\/jausoft.com\/Files\/media\/20220531-pacman-10.mp4<\/a><\/video><\/div>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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&#8216;s classic Puckman? Both my sons loved the idea and we added this&hellip; <a class=\"more-link\" href=\"https:\/\/jausoft.com\/blog\/2022\/05\/31\/chase-scatter-and-phantoms-sisyphus-alike-ghost-fate\/\">Continue reading <span class=\"screen-reader-text\">Chase, Scatter and Phantoms &#8211; Sisyphus alike Ghost Fate<\/span> <span class=\"meta-nav\" aria-hidden=\"true\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[59,3,58,1],"tags":[51,64,65,66,67],"class_list":["post-1065","post","type-post","status-publish","format-standard","hentry","category-c-language","category-computer-stuff","category-computer-languages","category-uncategorized","tag-c","tag-game-theory","tag-puckman","tag-sdl","tag-toru-iwatani"],"_links":{"self":[{"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/posts\/1065","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/comments?post=1065"}],"version-history":[{"count":48,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/posts\/1065\/revisions"}],"predecessor-version":[{"id":1125,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/posts\/1065\/revisions\/1125"}],"wp:attachment":[{"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/media?parent=1065"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/categories?post=1065"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jausoft.com\/blog\/wp-json\/wp\/v2\/tags?post=1065"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}