Game Overview
The objective is to navigate Pac-Man through a map, collecting all 260 pills and 4 megapills while avoiding the four enemy ghosts chasing him. The game begins upon pushing the start buttons. Pac-Man continues moving in the direction you press, assuming that direction is legal and does not try to push Pac-Man through a wall. For every pill collected earns the player 10 points. Megapills are worth 50 points. Upon eating a megapill, Pac-Man will become Mega Pac-Man for a short period of time and be able to eat ghosts. A player will lose a life if he comes in contact with a ghost while he is regular Pac-Man and the game will restart, minus the pills already collected. A player will only have two lives.

Game Design
Using the VICE Versatile Commodore Emulator v1.11 and Pac-Man by Atari (c) 1983, we ran Pac-Man and collected many screenshots which we then ran through MS Paint to determine sprite and map details at the pixel level. We then tried to emulate the behavior of the game as closely as possible. A screenshot and blown up sample are shown below.

Hardware
Pac-Man runs off an Atmel AT90S8515 chip running at 8MHz with external memory. Two output pins are connected to a Digital-to-Analog Converter (DAC) to the composite video input of a television. Limited to 8Mhz, the microcontroller outputs a non-interlaced picture of 176 (W) x 200 (H) pixel resolution. Our MCU, memory, and memory latch are all mounted on an STK-200 development board which enabled a transparent hardware interface with the external memory.

Software
This entire project was written in AT90S8515 assembly (yes, our programmer was quite insane when he thought to do this) for speed and greater control execution time. Our program's video generation code is simply a very tightly optimized AT90S8515 assembly version of Professor Land's optimized Mega32 video code available here. All tasks are performed within the one interrupt routine that generates a sync pulse at regular intervals. Lines that are not being used to blast registers to the screen are used instead to update the game state with the various subroutines. Care must be taken to divide work up between lines so that the sync generator is able to produce its signal at the required times. For smooth, un-interlaced playback, sprite placement is updated a maximum of every other field (i.e. every frame) which gives us an effective refresh rate of 30 frames per second.

Trade-Offs
With the map and pills and positions of Pac-Man and the ghosts, we needed external memory. At the time of our project conception, the AT90S8515 was the only chip available from Atmel that would support external ram natively. We needed built-in support of ram and since the faster ATMEGA8515 and ATMEGA162 chips were unavailable until just the weekend before this project was due, we had to go with the AT90S8515 and its 8Mhz speed limit. Using the either the Mega8515 or Mega162, we would have been able to generate a much tighter raster horizontally, outputting at least 256 pixels across (32 registers) and possibly using interlaced code to provide 400 pixels down.

Due to limitations on the number of available pins because of external ram interfacing, we initially had to use the push buttons provided by the STK-200 as our directional buttons instead of implementing a game controller. Later on we moved the buttons offboard to a more intuitive directional configuration.