Pac-Man Emulator

Introduction

Ever since discovering the Pac-Man arcade machine was Z80-based, I’d wondered if the same code could be adapted to run on the SAM. I knew the sound and video hardware was very different, but the core code should still work — shouldn’t it?

Hardware Analysis

Before coding anything we need to compare the arcade hardware to SAM, to decide how best to handle the differences. A quick Google for “pacman hardware” brings up a number of helpful sites detailing memory map, graphics formats, etc. The MAME project, being primarily a documentation project, is also an excellent source of hardware information.

CPU

Arcade: 3.072MHz Z80A, 60Hz display interrupts
SAM: 6MHz Z80B, 50Hz display interrupts

On paper the SAM is almost twice as fast, but memory contention eats away some of that lead. Even assuming the arcade CPU is busy most of the time, we should still have up to half of each frame to do our own processing. By hooking the ROM interrupt handler we can get regular control to perform our emulation functions, before passing control back to the original handler.

The interrupt frequency is tied to the vertical refresh rate of the display and determines the running speed of the game. The 60Hz arcade frequency is very difficult to achieve on the SAM, particularly since we only have control for part of each frame. This leaves us using SAM’s native 50Hz frequency, which reduces the running speed by around 17%.

The arcade ROM code will be running natively on SAM’s CPU, but I plan on doing as much of the remaining work using knowledge of the hardware only. An easier port of the game could be done by patching a selection of subroutines in the ROM, but I wanted to keep it as close to a traditional emulator as possible, just for the challenge! It also means other games written for the same hardware should run with relatively few changes.

Video

Arcade: 224x288 in two sprite layers, 32 colours (fixed)
SAM: 256x192, 16 colours (mode 4) from palette of 128

Despite the similar specifications, the video hardware is almost completely different. Rather than using a traditional bitmapped display, the arcade display is composed of a background layer of character tiles overlayed by 6 floating sprites. The display is 2K in size and based at address &4000, with 1K each for characters and attributes.

The character layer uses a grid of 28x36 tiles, each 8x8 pixels in size. Each has a byte for the character number and an attribute byte for colour information. The actual character graphics are stored as a 2-bit images, with the attribute byte determining the palette colours used (more on that below).

The character display layout is quite unusual, and worth describing in a little more detail. The first two rows (each 32 bytes) are used for the fruit/credit display at the bottom. The next 28 rows are rotated columns from the main display, ordered from right to left. The final two rows are used for the score display at the top of the screen. Despite the main display width being 28 characters, the first and last two rows are 32 characters wide. These 4 outer columns only exist for the 2 lines at the top and bottom of the screen, and are not part of the visible display. Using 32-byte strips of memory makes dealing with the display much easier, and should also help with our own emulation.

Displayed above the character layer are eight sprites, each 16x16 pixels in size. They can be positioned anywhere on the display with pixel accuracy, and since they can’t be disabled, they’re positioned in hidden columns of the screen when not needed. Each has a sprite number, colour index, and bits to determine whether the sprite should be flipped vertically and/or horizontally. Like the character graphics, the sprites are stored as 2-bit images, with black being taken as transparent so you can see through to the character layer.

Like the rest of the video details, the palette situation is not straight-forward either! There is a master palette of 32 colours, stored in a PROM on the main board. Rather than referencing this table directly with a 5-bit value, the video uses a list of sub-palettes, each referencing 4 colours from the master palette. The colour value used by each character/sprite is actually a sub-palette number, allowing up to 4 colours to be used for each.

The image below shows all the characters (top-half) and sprites (bottom-half) available on a standard Pac-Man board. Since the colours for each are determined at display time, I’ve used an artificial palette of black, red, blue and white:

Pac-Man Arcade Graphics

Looking to the SAM version, the first problem is that our display is too small hold the full arcade image, even rotated. We will need some way to scale or clip the image to fit - something to worry about in the implementation.

The arcade colour requirements mean that SAM’s mode 4 is the only realistic option. We also need to cut the number of colours in half to fit SAM’s 16 entry CLUT, perhaps by sharing similar colours where possible.

Another colour issue is the fact that any character or sprite could use any sub-palette, so we might need to colour the sprites when needed, or build every combination from the sub-palettes available.

Sound

Arcade: 3 mono voices, 16 volume levels, any frequency, choice of 8 pre-defined waveforms.
SAM: 6 stereo voices, 16 volume levels, 31Hz-7.8KHz, square wave only.

SAM has no problem matching the 3 voices and 16 volume levels needed, but we can’t handle the custom waveforms used by the arcade version. There’s a choice of 8 voice sounds, giving different instrument sounds such as smooth bass lines or trill notes for sound effects. The SAM’s SAA 1099 chip lacks the same level of control, so the best we can do is play notes at the correct volume and frequency.

Input

Arcade: Memory-mapped I/O ports at &5000 and &5040 for control and coin/start inputs.
SAM: I/O port &FE for the full keyboard matrix, including joystick ports.

The main difference here is the use of memory-mapped ports instead of traditional I/O ports. When a memory-mapped location is read the external hardware provides the result, as if an IN instruction was used. This actually makes our job easier as real I/O usage would require code patches to intercept the read and supply our own result.

To support the correct input functionality we need to update the following locations with appropriate port values:

        +--------+-------+-------+---------+-------+--------+-------+-----+
 &5000: | credit | coin2 | coin1 | advance | down  | right  | left  | up  |
        +--------+-------+-------+---------+-------+--------+-------+-----+

        +---------+--------+--------+------+-------+--------+-------+-----+
 &5040: | upright | start2 | start1 | test | down2 | right2 | left2 | up2 |
        +---------+--------+--------+------+-------+--------+-------+-----+

ROM Testing

With a better idea of what we’re dealing with we can move on to the original game code.

The arcade ROMs are not legally available for download, but they can be extracted from commercial emulators such as the Microsoft Arcade Pocket Pack. A few minutes with a hex editor gave the ROM file I needed, and as a bonus, it was the original Namco ROM with the copy-protection disabled (more on that later).

In Pac-Man’s 64K address space, the first 16K is ROM code and the next 16K is RAM, leaving the upper 32K unmapped. The RAM block includes the display, a number of memory mapped I/O ports, and regular workspace areas. The sound/graphics ROMs and colour PROMs are not present in mapped memory, accessible to the sound and video hardware only.

Test 1

As a simple first test we set up the required address space configuration and run the ROM completely unmodified, just to see what happens. After loading the Pac-Man ROM at BASIC address &10000 (page 3), the following code does just that:

        di
        ld  a,%10100011   ; ROM0 off, page 3 (write-protected)
        out (lmpr),a      ; set lower memory paging
        jp  0             ; execute Pac-Man ROM

The differences in video hardware mean nothing is actually seen on screen when the test is run. Entering the debugger does show that ROM code is still executing, with no obvious signs of having crashed - a good enough start.

Test 2

As a temporary workaround to the display differences, we can point SAM’s display at the memory holding the arcade display (&4000). Any display changes will then shown up as patterns on the SAM display. Mode 2 is also ideal for this as the 32-byte width matches the arcade display column height. The mode also benefits from having the scanlines stored sequentially, so the display lines are shown in the correct order, with the character and attribute data in distinct blocks.

The updated test code also needs to fill SAM’s mode 2 attributes with a suitable value, so the display data is visible (&07 gives white on black):

        di                ; no interrupts before we modifying paging
        
        ld  a,%10100011   ; ROM0 off, page 3 (write-protected)
        out (lmpr),a      ; set lower memory paging
        ld  a,%00100100   ; mode 2, page 4 (at #4000, from above)
        out (vmpr),a      ; set video mode and paging
        
        ld  hl,#6000      ; start of arcade display
        ld  bc,#1807      ; 24 blocks of 256, attr of 07
loop:   ld  (hl),c        ; fill attributes
        inc l
        jr  nz,loop       ; complete block of 256
        inc h
        djnz loop         ; complete 24 blocks
        
        jp  0             ; execute Pac-Man ROM

Executing the code above clearly shows the ROM startup sequence, with the display memory being tested in 1K blocks (1/6th of our mode 2 display height). On a real arcade machine this is seen as a rapidly changing pattern of characters and colours, before the normal menu attract sequence begins.

Unfortunately, the test ends with static display image, apparently never reaching the attract mode. Peeking the character display memory reveals the test mode text, which explains why it isn’t changing! The images below show the SAM and arcade displays at the test screen:

Test Screen (SAM)

Test Screen (Arcade)

If you tilt your head to the left by 90° you should see SAM display patterns corresponding to the 5 lines of text on the arcade display.

The narrow lines in the top 1/6th of the display are from the value &20, which is the ASCII value for the space characters that fill most of the test display. The thicker bands below it are from the value &0F, which is the character attribute value used to give white text on a black background.

Test 3

For us to move past the test screen we must ensure the Test DIP switch is inactive during startup. This is part of the memory-mapped port at address &5000, and the bit itself is active when low. In theory, pre-setting the value of this port should fix the problem, but it doesn’t. When stuck at the test screen again, peeking the DIP location shows it had been cleared by something!

Stepping through the startup sequence revealed that the memory test clearing all the DIP memory locations, activating all features - the cause of our problem. On the arcade machine the DIP switches are read-only memory-mapped I/O ports, unaffected by RAM writes, but on the SAM they’re regular read-write RAM locations.

Crippling the memory test exposes yet another problem affecting the DIP switch value. The same location at &5000 is a write-only memory-mapped port used to control whether external interrupts are enabled. Fortunately, this is not needed when running on the SAM so we can safely change the interrupt writes to an unused RAM location at &5001.

With these ROM tweaks in place, the mode 2 display shows enough to indicate the attract sequence and demo mode are running normally. We’re now ready to start on the hardware emulation!

Implementation

Video

The first problem to tackle is the SAM display being too small to hold the entire arcade image. Fortunately I’d already solved this in my own Pac-Man clone, written back in 1994. Using 6x6 pixel cells instead of 8x8 fits the maze to the SAM height almost perfectly. It does mean the two lines at both the top and bottom of the display (used for score and fruit) need to be moved, but since the display is stored as characters this is relatively easy to do.

Scaling down the arcade graphics is the next problem, and my attempts to do automatic scaling gave poor results. Another option is to drop 1/4 of the pixels in both X and Y directions, but a few tests showed that didn’t work very well either, particularly when displaying text. I settled on redrawing the graphics by hand, as I did for my old program. I’d need to cover all the arcade sprites shown in the first image above.

Matching colours from the arcade to SAM is relatively easy, with a little help from Paint Shop Pro. I started with a SimCoupe screenshot from SAM BASIC showing all palette colours, using a simple PALETTE 0,n LINE n loop with values from 1 to 127. This was loaded into PSP to give the full SAM palette, which was then saved to a .pal file. In MAME I saved a screenshot showing as many graphics as possible, to give a wide selection of arcade colours. Finally, I loaded this image into PSP and imported the .pal file to convert the screen to the nearest SAM colours. There were still more than 16 unique colours used, but some were similar enough to share a single SAM colour.

Still in Paint Shop Pro, I drew the full character and sprite sets needed to match the arcade versions. Here’s the completed set:

Pac-Man SAM Graphics

To match the original hardware perfectly we’d need to support the full palette and sub-palette function to colour sprites on-the-fly. In reality this is rarely needed as almost all the sprites use the same colours each time. This knowledge, coupled with the fact that we’re already using re-drawn sprites, means we can pre-colour virtually everything to dramatically reduce the sprite drawing work.

Exceptions to the pre-colouring include the ghost sprites and text characters. The arcade version uses a single sprite for the ghosts with a change in attribute value to give different colours. The flashing scared ghosts, returning eyes, and coloured text are all implemented using the same method and also need to be stored separately.

Additional sprite exceptions are needed for the sprite mirroring feature, used to create the left/up versions of Pac-Man from the right/down sprites. All these exceptions will be handled by the sprite drawing code, using additional checks when the affected sprite numbers are drawn, substituting the alternatives as required.

For true floating sprite support on SAM’s bitmapped screen we need to preserve the character image under each sprite. The drawing process will restore the image data under the old sprites, saves the data under the new positions, before drawing the new sprites (correctly masked for transparency). Doing this for all 6 sprites takes roughly 1/2 of each frame, and unavoidably leads us to be drawing at the TV raster position. To avoid ugly shearing artefacts we need to using double-buffering, with everything drawn to a back-buffer we flip to show at the start of the next frame.

Changes to the sprite settings are easily spotted as there is only a small amount of data stored in fixed locations. The character data locations are also fixed but there is 2K of data to compare each frame! The scanning code is going to need to be as fast as possible.

As it happens, very few changes are made to the character layer each game frame. The main changes to the data area are for dots that disappear as Pac-Man eats them, and for the updated score. Attribute changes are used to flash the power pills by toggling their colour every 10 frames.

Since most bytes will remain unchanged it made sense to optimise for the ‘same’ case, even if it meant a speed penalty when changes were detected. The best solution I could think of was an unrolled loop to scan a full display row, using 32 (well, 31 and a bit) repeated blocks of the following code:

        ld  a,(de)   ; fetch display display byte   7
        cp  (hl)     ; compare to our copy          7
        ret nz       ; return if changed            5/11
        inc e        ; next arcade character        4
        inc l        ; next copy character          4

The code avoids expensive conditional jumps, using a cheaper conditional return instead, which takes only 5 tstates if the condition is not met (as is the case most of the time). It takes 27 tstates plus contention for each full comparison, which seems pretty good.

The compare function called expecting it to return when a change is found. The location of the change is still held in DE, which is then used by the drawing function to update the changed character. Once drawn, the function calculates the point in the compare code where it was up to and resumes scanning for changes. If no changes are found the function pops the return address off the stack and returns back to the parent, having completed the scan.

Even with an optimial scanning routine it’s still taking too much of our valuable execution time each frame. With so little changing it wouldn’t hurt to scan for changes in strips, reducing the amount of scanning done each frame. At worst a change will be visible a few frames after it was made, and in the case of an eaten dot the Pac-Man sprite will already be obscuring it for most of that time.

To further reduce the work we can avoid scanning the attribute later altogether. Character data and attribute changes are typically made at the same time, and we already pick up the corresponding attribute value when the changed character is drawn.

As with the sprite optimisation short-cuts, there are some special cases for the character handling. As we’re no longer scanning the attributes we won’t see the changes made to make the power-pills flash. As a work-around we can monitor the static locations used for the attributes, invalidating the saved copy of the character data when a change is detected. The normal character data scan will pick up on the change and draw the updated flashing state. As well as the 4 positions on the main maze, there are two additional screen locations used on the attract screen we must monitor.

Character attributes are also used to flash the maze blue/white at the end of each completed screen. This is easily detected by watching for specific attribute values used for the top-left corner of the maze. Rather than implement the flash by invalidating the whole screen (very slow!) we alter the SAM palette colour used only for the maze blue.

The final piece of the character layer implementation is to re-position the missing top/bottom lines. This is done by selectively repositioning characters at the point they’re draw, with the same character drawing code used as normal. In a similar layout to my old game I positioned the lives and fruits at the bottom edges of the main maze. The scores are shown at the top edges, close to the positions used in the arcade.

With the character and sprite implementations in place we can now see the attract mode running in all its glory! Curiously, when starting the ROMs the attract screen is the first thing seen, with no sign of the memory tests. This turns out to be because interrupts remain disabled during the memory tests so our code is never called.

Sound

To generate the correct tone for each channel we need to convert from a frequency value in Hz to the octave/note values used by SAM’s SAA 1099 sound chip. The following formula describes the relationship between the values:

    freq = (15625 * 2<sup>octave</sup>) / (511-note)

The calculations required to determine the note and octave values given a frequency isn’t trivial and would eat into our valuable frame time. Using a pre-calculated look-up table of values is better and faster option. I chose to use a 16K table containing 8192 entries, with the closest values determined in advance using a Perl script.

The arcade covers a wider range of frequencies and we have little choice but to clip them at both ends of the range. There is also a special case frequency of zero to handle, which is used to silence a voice without altering the volume. If we see this value we can set the SAM volume to zero to give the same effect.

Knowing that pairs of SAA channels share a single register to hold two nybbles of octave data, it makes sense to use SAA channels 0, 2 and 4 for the three arcade channels. That way we can write the octave value for the arcade voice immediately, without needing to combine two octave values.

The sound conversion process above provides a good approximation of the arcade sound. However, during play-testing I noticed the frequency of the eating-ghost sound was far too low. Since the voice frequency was correct, the waveform sample data must be stored at a lower base frequency than the others. After a little experimentation I found multiplying this waveform frequency by 8 (increasing it by 3 octaves) corrected it. This adjustment is made whenever the affected waveform is used.

Input

After the earlier complications, the input implementation is refreshingly simple. We take selected bits from SAM’s keyboard ports and combine them to form to the arcade port values.

To keep with the key mappings used by other arcade emulators I used the following:

Copy protection

Some versions of the Pac-Man* arcade machine include a copy-protection mechanism designed to make bootlegging more difficult. It consists of an add-on board addressed using port &0, which accepts a byte value to present on the bus at interrupt time. With the machine normally running in IM 2, this byte forms the low byte of the IM 2 handler look-up address. If the protection hardware is missing, the wrong interrupt handler address is formed and the machine crashes.

To further confuse bootleggers, the IM 1 handler at &0038 contains dummy code! It disables external interrupts by writing zero to &5000, clears the coin counter at &5007, then loops back round to the start of the handler. Interrupts are already disabled by the time the IM handler is called, giving no way to exit the loop. Detecting an apparent hang, the hardware watchdog timer soon kicks in to reboot the board.

For the code to run on the SAM we must remove this protection mechanism. The simplest solution is to switch to using IM 1, and replace the dummy IM 1 handler with our own code to perform the original IM 2 functionality. IM 1 doesn’t use the I register, giving a handy storage location for the bus value normally written to port &00. By changing instances of OUT (&00),A to LD I,A in the code (both are 2-byte instructions) we preserve the port &00 value for later use.

To locate the correct handler we perform the original IM 2 lookup manually, using the port &00 value from I and the normal Pac-Man I value of &3f:

        ld  a,i      ; bus value originally written to port #00
        ld  l,a      ; vector table offset
        ld  h,#3f    ; normal I value, for vector table
        ld  a,(hl)   ; fetch handler low
        inc hl
        ld  h,(hl)   ; fetch handler high
        ld  l,a
        jp  (hl)     ; jump to interrupt handler

With this code in place we can now run the Midway ROM set, as found in the US version of the machine. The Midway set also includes different ghost names, and a 2-character change of game name from PuckMan to Pac-Man, over worries part of the original name could be scratched away to read something obscene!

Final Tweaks

A minor issue that puzzled me for a few days was that the routes the ghosts took in the demo mode were not quite right in my emulation. Suspecting a CPU bug in SimCoupe, the program was checked on a real SAM, with the same result.

I then feared subtle differences in the Z80 chips used, perhaps with the refresh register used for some pseudo randomness. Searching the ROM code for uses of the refresh register showed up nothing, so I got in touch with Pac-Man guru David Widel to ask for advice. He pointed me at the random function in the ROM, used by scared ghosts to make route decisions, which sourced values from the ROM code itself. As I was modifying the ROM to patch in my code, different values would be seen in some locations compared to the original version.

I changed my start-up code to keep a clean copy of the ROM before patching it, with an additional change to get the random function to source from this copy instead. Once in place the ghost routes were fixed and I could finally sleep at night!

Other Games

As well as running the original Namco and Midway versions of Pac-Man, a number of bootleg versions will also run. One of the more customised bootlegs is Hangly Man (apparently “Hungry Man” in Engrish. It features multiple maze layouts, some without inner walls. The maze also turns invisible at set points throughout the game! Here are the first and third screens:

Hangly Man (cherry)

Hangly Man (orange)

Bootlegs that use different sprites will run, but use our pre-scaled SAM versions instead. Our pre-coloured graphics also mean differences in colour PROMs will not show up in our version. Pac-Man Plus uses encrypted ROMs that are decoded in hardware, will not work either.

A more exciting prospect is to run other games that use the same hardware platform, such as Pengo. It should be possible to modify the patching locations and re-draw the graphics set to give a fully working version, but I’ve left that as an exercise for the reader ;-)

Summary

Despite cutting a few corners for speed reasons, I achieved most of what I set out to do, and am quite pleased with the result. I hope I’ve covered most details people would find interesting, but if I’ve missed anything, please contact me using the address below.

A disk image of the final program (minus ROMs) is available on the Pac-Man Emulator page of my web-site. As a special treat for SAM Revival readers you can also download the fully commented source code, ahead of it being announced on the sam-users list.