|
Bride of Kill ScreenThe Journey to
Find, Analyze, and Fix Ms. Pac-Man’s
Kill Screens Ms. Pac-Man has a series of kill screens. The first seems to occur on level 134, where very strange things start to happen. Apparently there is a chance on a real arcade machine that this bug will not cause any problems, but I cannot seem to arrive on this level in MAME without something very weird happening. Apparently, MAME is not emulating the arcade machine 100% exactly.
The Problem
The first step is to search the
Internet to see if this answer
has already been found. We find
a lot of good work has been done
and a
complete disassembly of Ms. Pac-Man at Scott Lawrence’s web site
http://umlautllama.com/projects/pacdocs/mspac/mspac.asm.
Ms. Pac-Man shares a great deal
of code with the original Pac-Man, so the
previous work we did
on Pac-Man may help here as
well. We need to know that levels on Ms. Pac-Man are stored with a starting value of zero. In other words, the first level that we play (cherry) is treated as level zero by the game. The second level (strawberry) is counted as level 1 by the game, and so on. In order to understand what happens at level 134, the upside down screen, we need to examine the memory locations of the screen elements. Luckily this has already been done by Bart Grantham - see http://www.bartgrantham.com/projects/mspacman/sprite-RAM.html . The color memory grid has been overlaid with the 1st screen, and rectangles drawn around key squares, to show the following:
It turns out there is a subroutine which sets bit 6 in the color grid of certain screen locations on the first three levels. This color bit is ignored when actually coloring the grid, so it is invisible onscreen. However, when a ghost encounters one of these specially painted areas, he slows down. This is used to slow down the ghosts when they use the tunnels on these levels. So, why are there four squares painted this way at the top of the screen? The answer to this question turns out to also serve a clue as to why the kill screens occur. It is because of the way the subroutine, which paints these values, was written. Let's have a look at it. 95C3 3A 13 4E LD A,(#4E13) ; Load A with current level number 95C6 FE 03 CP #03 ; Is A < #03 ? 95C8 F2 34 25 JP P,#2534 ; No, jump back to program 95CB 21 DF 95 LD HL,#95DF ; Yes, load HL with start of table data address 95CE CD BD 94 CALL #94BD ; Load BC with either #95DF or #95E1 depending on the level 95D1 21 00 44 LD HL,#4400 ; Load HL with start of color memory 95D4 0A LD A,(BC) ; Load A with the table data 95D5 03 INC BC ; Set BC to next value in table 95D6 A7 AND A ; Is A == 0 ? 95D7 CA 34 25 JP Z,#2534 ; Yes, jump back to program 95DA D7 RST #10 ; No, load A with table value of (HL + A) and load HL with HL + A 95DB CB F6 SET 6,(HL) ; Sets bit 6 of HL - make tunnel slow for ghosts 95DD 18 F5 JR #95D4 ; Loop back and do again 95DF 3D 8B ; #83BD Pointer to table for tunnel data for levels 1 and 2 95E1 28 8E ; #8E28 Pointer to table for tunnel data for level 3 8B3D 49 09 17 09 17 09 0E E0 E0 E0 29 09 17 09 17 09 00 00 ; data for level 1 and 2 8E28 42 16 0A 16 0A 16 0A 20 30 20 20 DE E0 22 20 20 20 20 16 0A 16 16 00 00 ; data for level 3 This subroutine also calls two other subroutines. The first one is called in the fifth line of code above, CALL #94BD. We will examine the details of that subroutine later. For now, just know that it is supposed to return the BC register with either #95DF if the level is 1 or 2, or #95E1 if the level is 3. These two values are themselves pointers to the beginning of the data tables that are used to set the color bits seen in the screen shot above. The second subroutine is used to load A with the data from the table and also set the HL pointer to the next data table element. So for levels 1 and 2, HL starts at #4400 and then gets incremented by the values in the table starting at #8B3D. Thus, HL changes during the subroutine to #4400 + #49 = #4449, then #4449 + #09 = #4452, then #4452 + #17 = #4469, and so on. Refer to the diagram above to see where these values land, you will see they are all in the tunnels on the right side of the screen. One problem with this subroutine is that the next data value can be a maximum of #FF (255 decimal) screen elements from the previous one. So, when the last tunnel on the right side of the screen at #4492 has been drawn, there is no way to jump directly to the next one that should be drawn on the left side at #4769, because it is #2D7 (727 decimal) bytes higher. So, the programmers had the subroutine draw four intermediate placeholders at the top of the screen, which will never be encountered by a ghost, in order to get to the left side of the screen to continue drawing the remaining six data elements for the tunnel. Another problem with this subroutine, as we shall see, is that it relies on encountering a data element of #00 to signal and end to the routine. The Bug for levels 132, 133, 139-141A close look at the subroutine reveals the source of the problem: 95C3 3A 13 4E LD A,(#4E13) ; Load A with current level number
95C6 FE 03 CP #03 ; Is A < #03 ?
95C8 F2 34 25 JP P,#2534 ; No, jump back to program
95CB 21 DF 95 LD HL,#95DF ; Yes, load HL with start of table data address
The highlighted statement above is testing the wrong condition to see if the comparison to #03 in the line above is true or not. It is testing whether the result sets the positive flag, instead of checking the carry flag which would result in the correct behavior. In the binary number system used on this Z80 CPU, any number that #80 (128 decimal) through #FF (255 decimal) can be considered negative when tested for. When the game level is above #83 (131 decimal), this faulty coding results in the wrong answer for the comparison and the program then jumps to the subroutine which is only supposed to be used on levels 1, 2, and 3. Remember that the game counts game levels as one less than we do. So when the player reaches level 132, this is counted by the game as 131 (#83 hexadecimal). This causes a chain reaction for the subroutine which is expecting only levels 1, 2 and 3. When this level is run through, the following statement gives a wrong result: 95CE CD BD 94 CALL #94BD ; Load BC with either #95DF or #95E1 depending on the level On levels #83, #84, #8A, #8B, and #8C (131, 132, 138, 139, 140, decimal, actually boards 132, 133, 139, 140, and 141), BC gets loaded with #CC0A. This is garbage output which points to an area of memory which is not supposed to be used for this function. CC0A: 35 09 3F 00 00 As it turns out, the result of the bug on this level is very minor, and only an extremely observant player would even notice it. The following memories get written with the "slow ghost" bit: #4400 + #35 =
#4435 At this point, the subroutine encounters #00, which is its stop code, so it is done. However, it has written a "slow ghost" bit to screen element #447D, which is located just underneath the energizer in the lower right corner.
Below is a Youtube video showing the ghosts slowing down on level 132 when they pass under the energizer. I used MAME to warp to level 132 and then turned on the invincibility cheat to allow the viewer to clearly see the ghosts' behavior.
Level 134The next observation is made when the game reaches level #85 (133 decimal, board 134). This is the level that is usually regarded as the first possible kill screen. Let's observe what happens here. Remember that the game counts game levels as one less than we do. So when the player reaches level 134, this is counted by the game as 133 (#85 hexadecimal). This causes a chain reaction for the subroutine which is expecting only levels 1, 2 and 3. When this level is run through, the following statement gives a wrong result: 95CE CD BD 94 CALL #94BD ; Load BC with either #95DF or #95E1 depending on the level On levels #85 through #89 (133 through 137 decimal, actually boards 134 through 138), BC gets loaded with #FE78 This is garbage output which points to an area of memory which is not supposed to be used for this function. FE78: 7F 7F 7F 7F 7F 7F 7F 7F C9 C9 C9 C9 C9 C9 C9 C9 FE88: C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 FE98: C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 FEA8: C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 FEB8: C9 C9 C9 C9 C9 C9 C9 C9 00 00 00 00 00 00 00 00 The following memories get written with the "slow ghost" bit: #447F, #44FE, #457D, #45FC, #467B, #46FA, #4779, #47F8 <--- LAST OF VIDEO COLOR MEMORY #48C1, #498A, #4A53, #4B1C, #4BE5, #4CAE, #4D77, #4E40, #4F09, #4FD2, #509B, #5164 <--- PINKY GETS DRAWN #522D, #52F6, #53BF, #5488, #5551, #561A, #56E3, #57AC, #5875, #593E, #5A07, #5AD0, #5B99, #5C62 <--- PINKY TURNS RED #5D2B <-- Screen Turns upside down #5DF4, #5EBD, #5F86, #604F, #6118, #61E1, #62AA, #6373, #643C, #6505, #65CE, #6697, #6760, #6829, #68F2, #69BB, #6A84, #6B4D, #6C16, #6CDF, #6DA8, #6E71, #6F3A, #7003, #70CC, #7195, #725E, #7327, #73F0, #74B9, #7582, #764B, #7714, #77DD, #78A6, #796F, #7A38 At this point, the subroutine encounters #00, which is its stop code, so it is done. However, it has written a "slow ghost" bit to many random screen positions, and it also starts overwriting memory locations which lie way beyond the screen memory locations. I have added some descriptions of events that I notice when running the game on this level step by step, using a debug build of MAME. Level 142On level #8D (141 decimal, actually board 142), BC gets loaded with #F303 This is also garbage output which points to an area of memory which is not supposed to be used for this function either. F303: EF EF EF EF EF EF EF EF EF EF EF EF EF EF EF EF F313: EF EF EF EF EF EF EF EF EF EF EF EF EF EF EF EF F323: EF EF EF EF EF EF EF EF EF EF EF EF EF EF EF EF F333: EF EF EF EF EF EF EF EF EF EF EF EF EF FF FF FF F343: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF F353: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF F363: FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF F373: FF FF FF FF FF FF FF FF FF FF FF FF FF C9 C9 C9 F383: C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 F393: C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 F3A3: C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 F3B3: C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 C9 00 00 00 This results in various memories from #44EF through #EEF3 getting written to with the "slow ghost" bit set. At this point, the subroutine encounters #00, which is its stop code, so it is done. However, it has written a "slow ghost" bit to many random screen positions, and it also overwrites memory locations which lie way beyond the screen memory locations. This ultimately causes the game's watchdog to detect an error and cause the game to reset. It is possible the game resets even before this subroutine is finished executing. The Fix, Part 1The next step is
to fix the code so that this
behavior does not occur starting
on level 131. ; level 141 mspac fix ; HACK9 ;0a90 c3960f jp #0f96 ;0a93 00 nop … ; level 141 mspac fix ; HACK9 ;0f96 3a134e ld a,(#4e13) ; board number ;0f99 3c inc a ;0f9a f37b cp #7b ; compare to bad board point ;0f9c 2002 jr nz,#0fa0 ; don't store if out of range ;0f9e d608 sub #08 ; loop around for all 8 boards ;0fa0 32134e ld (#4e13),a ; store the level number ;0fa3 c3940a jp #0a94 ; return What does this
fix do? It overwrites the
program that increases the
game’s level with a jump command
(called a ‘hook’) that takes it
out to a new subroutine that has
been written and placed in some
unused memory. This subroutine
really has nothing directly to
do with the bug we are observing
here. It
checks the value of the level
right after it has been
increased after a level is
completed. If the level is #7B
(123 decimal), the result
reduced by 8 before being
written back to memory. Then it
jumps back to the original
program. The result is the game
stays forever between game level
#73 (115 decimal, the 116th
board) and #7A (122 decimal, the
123rd board). Another hack
which bypasses the self-test
must also be employed with this
one, or else the checksum
routines that are run when the
game powers on will detect a
problem and refuse to run the
game. Original Code: 95C8 F2 34 25 JP P,#2534 ; No, jump back to program Part of the fix will change the code to read this way: Fixed Code: 95C8 D2 34 25 JP NC,#2534 ; No, jump back to program So this fix is implemented by changing a single byte of code, to test for a carry flag instead of the incorrect negative flag. Once implemented with a MAME cheat, levels 132 through 140 are correctly computed by the above subroutine and the initial part of our puzzle has been solved. These levels are now playable as regular levels with no chance of strange behavior. A New Problem EmergesHowever, level #8D (141 decimal, board 142) is still broken, but now does not cause the game to reset like it did before.
Without getting into specifics, the program is encountering a bug which causes the wrong maze to be drawn. Remember the subroutine above that we said we would look at later? Here it is: 94BD 3A 13 4E LD A,(#4E13) ; Load A with level number 94C0 E5 PUSH HL ; Save HL 94C1 FE 0D CP #0D ; Is level number >= #0D (13 decimal) ? 94C3 F2 D4 94 JP P,#94D4 ; Yes, jump to subroutine to makes the result in A become between #5 and #C 94C6 21 DF 94 LD HL,#94DF ; No, load HL with map order table 94C9 D7 RST #10 ; A now contains the map number 94CA E1 POP HL ; Get HL that was saved earlier 94CB 87 ADD A,A ; A = A*2 94CC 4F LD C,A ; Load C with A 94CD 06 00 LD B,#00 ; Load B with #00 94CF 09 ADD HL,BC ; Add this value into HL 94D0 4E LD C,(HL) ; Load C with table value from HL 94D1 23 INC HL ; Next table value 94D2 46 LD B,(HL) ; Load B with table value from HL 94D3 C9 RET ; Return 94D4 D6 0D SUB #0D ; Subtract #0D (13 decimal) from A 94D6 D6 08 SUB #08 ; Subtract #08 from A. Is A >= 0 ? 94D8 F2 D6 94 JP P,#94D6 ; Yes, then repeat previous subtraction 94DB C6 0D ADD A,#0D ; No, add #0D (13 decimal) back into A 94DD 18 E7 JR #94C6 ; Return to program This subroutine is supposed to load BC with a value based on the level and the value already loaded into HL. The first thing that it does is check to see if the level is greater than or equal to #0D (13 decimal). If it is, the program branches to a small subroutine to make the value between 5 and #0C (12 decimal). This is what is supposed to keep the game cycling between the 3rd and 4th mazes, which appear on levels 6 through 13. The Fix, Part 2The problem with this subroutine is the same as the problem we encountered in the previous section. The program is using the wrong flag to check for the comparisons, using the positive flag instead of the carry flag. Original Code: 94C3 F2 D4 94 JP P,#94D4 ; Yes, jump to subroutine to makes the result in A become between 0 and #0D ... 94D8 F2 D6 94 JP P,#94D6 ; Yes, then repeat previous subtraction We can fix these problems in exactly the same way that we fixed the previous one. We change code to check for carry instead of positive: Fixed Code: 94C3 D2 D4 94 JP NC,#94D4 ; Yes, jump to subroutine to makes the result in A become between 0 and #0D ... 94D8 D2 D6 94 JP NC,#94D6 ; Yes, then repeat previous subtraction Once we set up a MAME cheat with these fixes, the game becomes playable for boards 142 and beyond. Another Problem EmergesIt is apparent that another bug is still present, related to the color of the maze. Below is a montage of a few screen shots of color combinations that are encountered at various levels above 150. The have seemingly random colors for the maze and dots. Some mazes and dots are even invisible. Also, when played, some of these mazes have bit 6 set for the entire maze, making the ghosts run at a slow speed throughout, as if they were always in a tunnel on level 1.
An example of the slow ghosts can be seen in the following Youtube video, where level 242 is played under this partial bugfix.
After looking around we find the code that controls the color of the mazes: 9590 3A 13 4E LD A,(#4E13) ; Load A with board number 9593 FE 15 CP #15 ; Is this board >= #15 (21 decimal) ? 9595 F2 A3 95 JP P, #95A3 ; Yes, go and bring it back down to a number between #5 and #14 9598 4F LD C,A ; Load C with A 9599 06 00 LD B,#00 ; Load B with zero 959B 21 AE 95 LD HL,#95AE ; load HL with map color table 959E 09 ADD HL,BC ; Add the offset computed from level 959F 7E LD A,(HL) ; A now contains the maze color 95A0 C3 E1 24 JP #24E1 ; Jump back to program 95A3 D6 15 SUB #15 ; Subtract #15 from A 95A5 D6 10 SUB #10 ; Subtract #10 from A 95A7 F2 A5 95 JP P,#95A5 ; Did A just go negative? No, loop again and subtract another #10 95AA C6 15 ADD A,#15 ; Yes, Add #15 back into A 95AC 18 EA JR #9598 ; Return The Fix, Part 3The problem with this subroutine is the same as the ones previously encountered. The problem is with the following two lines of code: Original Code: 9595 F2 A3 95 JP P,#95A3 ; Yes, go and bring it back down to a number between #0 and #14 ... 95A7 F2 A5 95 JP P,#95A5 ; Did we just go negative? No, loop again and subtract another #10 We can fix the code the same way as we did in the previous sections. Fixed Code: 9595 D2 A3 95 JP NC,#95A3 ; Yes, go and bring it back down to a number between #0 and #14 ... 95A7 D2 A5 95 JP NC,#95A5 ; Did we just go negative? No, loop again and subtract another #10 After applying a MAME cheat with all of the above fixes, the game is now playable, but only up to level 255, where we encounter Ms. Pac-Man's version of the split-screen level. Ms. Pac-Man's Split Screen and Fix
Now we have to go after Ms. Pac-Man's split screen bug, which as it turns out is simpler than Pac-Man's split screen, because the game only needs to ever draw up to seven fruit. Let's have a look at it: Original Code: 2BF0 3A 13 4E LD A,(#4E13) ; Load A with level number 2BF3 3C INC A ; Increment 2BF4 C3 93 87 JP #8793 ; Jump to new subroutine to check for levels above 7 ... 8793 FE 08 CP #08 ; Is A >= #08 ? 8795 DA F9 2B JP C,#2BF9 ; No, return 8798 3E 07 LD A,#07 ; Yes set A := #07 879A C3 F9 2B JP #2BF9 ; Return The problem with this subroutine is the same problem that Pac-Man has: it increments the level first, then checks to see if it is 8 or higher. When level #FF (255 decimal, board number 256) is reached, it gets incremented and wraps around to zero, which is a value for the level that the subroutine which draws the fruit is not expecting. This causes the same chain reaction that Pac-Man has where 256 fruit plus 7 blank spaces are drawn to the screen. We can use a fix very similar, but simpler, to the one that we developed for Pac Man's split screen. Fixed Code: 2BF0 3A 13 4E LD A,(#4E13) ; Load A with level number 2BF3 C3 93 87 JP #8793 ; Jump and check if level is too high ... 2BF8 3C INC A ; Increment it only when 0 through 6 ... 8793 FE 07 CP #07 ; Is A >= #07 ? 8795 DA F8 2B JP C,#2BF8 ; No, it is 0 through 6, return, and add 1 8798 3E 07 LD A,#07 ; Yes, set A := #07 879A C3 F9 2B JP #2BF9 ; Return and don't add 1 So we only add 1 to the level if it between 0 and 6. Otherwise, we set the level to 7, and Ms. Pac-Man's split screen is fixed. Checksum Fixes and Final Cheat CodesThe last thing that needs to be done is to fix the power-on checksum routine so that this change can be made without causing a memory error. Instead of creating or using another hack to bypass the self-tests, we will add offsets to the end of the memory bank #2000-#2FFF to make the checksums add up properly. The total patch
is made by changing 11
bytes of the original code, plus
two bytes for the checksum fix. :mspacman:A0600000:2BF3:00C39387:FFFFFFFF:Fix All Level Bugs :mspacman:A0010000:2BF8:0000003C:FFFFFFFF:Fix All Level Bugs (2/9) :mspacman:A0110000:2FFC:0000FA5B:FFFFFFFF:Fix All Level Bugs (3/9) :mspacman:A0610000:8794:0007DAF8:FFFFFFFF:Fix All Level Bugs (4/9) :mspacman:A0010000:94C3:000000D2:FFFFFFFF:Fix All Level Bugs (5/9) :mspacman:A0010000:94D8:000000D2:FFFFFFFF:Fix All Level Bugs (6/9) :mspacman:A0010000:9595:000000D2:FFFFFFFF:Fix All Level Bugs (7/9) :mspacman:A0010000:95A7:000000D2:FFFFFFFF:Fix All Level Bugs (8/9) :mspacman:A0010000:95C8:000000D2:FFFFFFFF:Fix All Level Bugs (9/9) Learn more about
cheat codes in MAME at
http://cheat.retrogames.com
Thoughts & CommentsSloppy programming causes bugs. In this case, it seems whoever wrote the extended code for Ms. Pac-Man didn't know the first thing about basic Z80 assembly language. The split-screen part is understandable, because it is a legacy from the Pac-Man code. [update 2/6/2017: I retract the original statements that are strikethrough. The creators of the Ms Pac Man game, General Computer Corporation, worked extremely hard on an incredible expansion for the original Pac Man. They were able to reverse engineer the code to Pac Man with relatively primitive tools, at least compared to today's standards. The story of its creation is great and can be viewed here: https://www.youtube.com/watch?v=rhM8NAMW_VQ ] I still don't know why the bug sometimes occurs on a real arcade machine and sometimes not. Some discussions have put the chances of the bug causing problems at about 1 in 3 for each of the levels from 134 to 138. It may have something to do with the fact that the first subroutine only sets one bit of the memories. Perhaps some have a chance of already having that bit set, which makes the program in effect do nothing when it writes to those particular locations. Who knows?
Coming next: A fix for Galaga and an explanation of Defender's extra life bonanza at 990,000 points. Updated 9/7/2009 - Fixed some mistakes, thanks to some excellent feedback from someone named Chupo from Hrvatska (Croatia). Thanks, Chupo! Updated 10/8/2011 - Fixed a spelling typo.Thanks to commenter Blitz. Updated 2/6/2017 |
| 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. |
|
|
|
|
|
|
