Why do Pinky and Inky have different behaviors when Pac-Man is facing up?By Don Hodges, December 30, 2008 Page last updated 8/14/2015
In the videogame Pac-Man (and in many of its sequels and clones), it has been previously established that the ghosts, Pinky and Inky, track Pac-Man by examining the direction he is facing and use that information as part of their determination of their respective targets. For example, Pinky usually targets the location four tiles in front of Pac-Man's location. However, if Pac-Man is facing up, this location becomes four up and four to the left of Pac-Man's location. Inky has a similar change in his targeting when Pac-Man is facing up. Why do Pinky and Inky have different behaviors when Pac-Man is facing up? The short answer is, in my opinion, because of a programming bug. Here is the evidence. Pac-man codes directions in at least two different ways. One way that Pac-man codes directions is by using a single byte integer with the following codes: Right = 0, Down = 1, Left = 2, and Up = 3. Another way Pac-man codes directions is by using a two-bytes pair, to create a directional vector, in the following manner. All values are in hexadecimal are preceded by the # sign, and can be viewed in memory locations #32FF through #3306. Right = (#FF, 00) Down = (00, 01) Left = (01, 00) Up = (00, #FF)
#FF (decimal 255) is being used as negative 1, for 8-bit Z80 math. Consider this example:
Coded tile locations are (XX, YY) in hexadecimal values. Suppose that Pac-Man is on tile (#26, #2F). The game would compute the tile locations of each of the four tiles surrounding this location by adding the two-byte directional vector values to the original location. To compute the grid location of the tile to the right of Pac-man, add the two-byte code for Right (#FF,00) to (#26,#2F). Since FF is treated as negative 1, the result is (#25,#2F), which is the tile to the right of Pac-man's location. To compute the grid location of the tile below Pac-man, add the two-byte code for Down (00,01) to (#26,#2F). The result is (#26,#30), which is the tile directly below Pac-man's location. To compute the grid location of the tile to the left of Pac-man, add the two-byte code for Left (01,00) to (#26,#2F). The result is (#27,#2F), which is the tile to the left of Pac-man's location. To compute the grid location of the tile above Pac-man, add the two-byte code for Up (00,#FF) to (#26,#2F). Since FF is treated as negative 1, the result is (#26,#2E), which is the tile directly above Pac-man's location. This all works correctly when we are dealing with single unit differences, and when these differences are computed separately, which is the only correct way to handle this arithmetic when it has negative numbers. For example, at code location #2000, there is a subroutine which does this function correctly: 2000 FD7E00 LD A,(IY+#00) ; load A with Y position 2003 DD8600 ADD A,(IX+#00) ; add Y direction vector 2006 6F LD L,A ; store result into L 2007 FD7E01 LD A,(IY+#01) ; load A with X position 200A DD8601 ADD A,(IX+#01) ; add X direction vector 200D 67 LD H,A ; store result into H 200E C9 RET ; return The above subroutine is used to load HL (a two-byte Z80 register pair) with a new tile position given a tile position in the IY register and a direction vector in the IX register. It works correctly because the two vectors' X and Y additions are handled separately. A problem arises when the game tries to compute, for example, the target for Pinky. The game code specifies that Pinky's target is four tiles in front of Pac-man's location, based on the way Pac-man is facing. To compute this tile, the code takes Pac-man's directional vector and adds it to itself, giving two times the original. Then it doubles this result, giving four times the original value. The problem is that the vectors' X and Y values are not added separately; they are added at the same time with a 2-byte register pair. The bug appears when the Up vector is computed. Pac-Man Z80 assembly code follows, highlighted code is buggy:
; Pac-Man Pinky targeting subroutine 278E ED5B394D LD DE,(#4D39) ; load DE with Pac-man's position 2792 2A1C4D LD HL,(#4D1C) ; load HL with Pac-man's direction vector 2795 29 ADD HL, HL ; double Pac-man's direction vector 2796 29 ADD HL, HL ; quadruple Pac-man's direction vector 2797 19 ADD HL, DE ; add result to Pac-Man's position to give target
The following tables shows the results of the above subroutine:
[The code for Inky's targeting is similar, but only doubles the vector instead of quadrupling. Inky's AI also factors in Blinky's position for a more complicated targeting mechanism.] HL is a two-byte Z80 register pair. At line #2792, H is loaded with the X part of the vector, and L is loaded with the Y part of the vector. When the vector for facing Right is considered, HL contains #FF00. The instructions at #2795 adds this value to itself, which results in HL containing #FE00, with the carry flag set because of the integer overflow of H which has been discarded. But the program ignores the carry flag and only uses the numerical result, which happens to work correctly as a coded -2 value. When doubled again at line #2796, the result in HL becomes #FC00, which is a correctly coded value for -4, again discarding the overflow and ignoring that the carry flag was set. When this result is added to the Pac-Man's location in the final line, the carry flag is set again because of the overflow, which is once again ignored by the program. The desired result is achieved: the new target is 4 tiles to the right of Pac-man. The Bug in ActionHowever, when the vector for facing Up is considered, HL is loaded with #00FF at line #2792. When it is doubled on the next line, HL then contains #01FE. Instead of the overflow being dropped, as it was when facing Right, the Y-axis negative number doubling overflow rolls into the X-axis value, causing the vector to become corrupted and move not only two up, but also two to the left when added to the position in the last line, which is also bugged. When doubled again, the result in HL becomes #03FC, which when added to the position gives a new location of four up and four to the left, instead of the expected four up.
I believe this is a bug, and not intentional, because the same command is being used for all four directions. In other words, the code is not running a different subroutine when the direction UP is encountered, yet UP gives a different, unexpected result than the three other directions. Given the low-level nature of this problem, I have a doubt that even the original programmers were aware of it. If they were aware of it, then it follows that they chose to ignore it and leave it as it is. Somehow, I doubt that they would have left it this way if they were aware of it. A FixAn possible fix would be to add HL as separate bytes, and ignore all overflow. This does not appear to be possible within the confines of the original code space, so a new subroutine is created in an unused area of memory. Original buggy code: 2795 29 ADD HL, HL ; double Pac-man's direction vector 2796 29 ADD HL, HL ; quadruple Pac-man's direction vector 2797 19 ADD HL, DE ; add result to Pac-Man's position to give target Fixed code: 2795 CD F0 2F CALL #2FF0 ; add 4x dir. vector to Pac's position ... 2FF0 7C LD A, H ; load Pac-man's X directional vector 2FF1 87 ADD A, A ; double it 2FF2 87 ADD A, A ; quadruple 2FF3 82 ADD A, D ; add to Pac-Man's X position 2FF4 67 LD H, A ; store 2FF5 7D LD A, L ; load Pac-man's Y directional vector 2FF6 87 ADD A, A ; double it 2FF7 87 ADD A, A ; quadruple 2FF8 83 ADD A, E ; add to Pac-Man's Y position 2FF9 6F LD L, A ; store 2FFA C9 RET ; return 2FFB CA FC ; checksum fixes This code has been tested and does work. Obviously, some existing maze patterns will no longer work as they did before, as Pinky now tracks Pac-man's UP direction in the same way as the other three directions. There is also the similar problem that Inky has in his tracking algorithm. Original buggy code: 27D6 29 ADD HL, HL ; HL := HL * 2 [gives wrong result when pacman facing up] 27D7 19 ADD HL, DE ; add result to pac position 27D8 7D LD A, L ; load A with computed Y position
My fixed code is posted below: 27D6 CD E0 2F CALL #2FE0 ; call new sub to fix inky AI ... 2FE0 7C LD A, H ; load Pac-man's X directional vector 2FE1 87 ADD A, A ; double it 2FE2 82 ADD A, D ; add to Pac-Man's X position 2FE3 67 LD H, A ; store 2FE4 7D LD A, L ; load Pac-man's Y directional vector 2FE5 87 ADD A, A ; double it 2FE6 83 ADD A, E ; add to Pac-Man's Y position ; (no need to store, A is used on return) 27E7 C9 RET ; return to 27D9 27E8 AC ; even # checksum fix 27E9 FB ; odd # checksum fix Updated: 5/1/2015. I had the checksums backwards. Sorry about that. It has been fixed. Thanks for Bill Krick for pointing this out. Added the code for Inky's fix.
|
| In accordance with Title 17 U.S.C. Section 107, some of the material on this site is distributed without profit to those who have expressed a prior interest in receiving the included information for research and educational purposes. For more information go to: http://www.law.cornell.edu/uscode/17/107.shtml. If you wish to use copyrighted material from this site for purposes of your own that go beyond 'fair use', you must obtain permission from the copyright owner. |
|
|
|
|
|
|
