Software

Video Generation
Video is generated by sending an video line intensity signal varying from 0.3V to 1.0V and a sync pulse which marks the end of every line and every field (half frame). During the lines that we are drawing, the video signal is very busy and nothing else is happening. On the lines before and after this, we are allowed to work on game computation. The basics of the the signal generation is covered here (http://instruct1.cit.cornell.edu/courses/ee476/video/index.html). We will now discuss the major parts that were handled differently. The following code is taken from the latest Mega32 version of video code available at the above website:

BST @0, [7..0]
IN R30,0x12
BLD R30, 6
nop
OUT 0x12,R30


This code sets PORTD.6 to bits 7 through 0 of the register parameter @0. This code preserves all the other bits of port D and takes a total of 5 * 8 = 40 cycles to output the contents of one register in big-endian order. Our blasting code:

OUT PORTB, @0
LSR @0
...
OUT PORTB, @0
LSR @0
OUT PORTB, @0
LSR @0


This code sets all of port B to the contents of register @0 and shifts the contents to the right one by one so that PORTB.0 is assigned each bit once. This code destroys all bits of port B even though only PORTB.0 is being used to output the register but takes merely 2 * 8 = 16 cycles to execute. Note that the register is being blasted out in LITTLE-endian order. Due to output current constraints on pins PORTB.[5-7] (only 500 mA allowed) we needed to shift the register output through PORTB.0. The main effect of this little-endian order storage is that bitmaps must be stored in the reverse order that they appear on the screen and shifting a byte to the left will shift the image to the right and vice-versa.
e.g. 0b00001111 will display 11110000 on the screen

The Pac-Man drawing is stored in external memory to keep the load time of screen registers constant. Since our raster wouldn't fit in the internal memory of the AT90S8515 and each load and store with external memory takes 3 cycles instead of 2, we need to put the whole screen in external memory to prevent image skewing. Specifically, the image would be quick to load and shifted left on the screen when loading from internal ram and then slower to load and shifted to the right when loading from external ram.

The width of our raster is 22 registers (176 pixels) wide. This is just good enough at 8Mhz to provide a well centered picture that maximizes the space available. The fact that 22 is not a power of 2 will require us to do binary multiplication instead of simple shifting when calculating screen coordinates. And since the AT90S8515 doesn't have a built-in multiplier like the ATMEGA162, we need to do a software multiply which take 15 cycles. More on that later.

Drawing Basics
Above we described the hardware interface to output the pixels to screen. Now we give some background on how we handle the drawing of maps and sprites. The screen is stored directly to an array of size 22 (176 pixels) * 200 (lines) = 4400 bytes large. This array stores 1s and 0s which are output straight to the screen. If you didn't know where a wall was or where a sprite was, you can't really tell what is what if I were to give you a random byte and say the 5th bit is high. This was also a problem with drawing Pac-Man and having him respect his boundaries. We started with walls set up on the boundaries of the drawing and Pac-Man represented as a dot that zoomed around. It was very apparent to a person what was Pac-Man and what was a wall. < insert dot pac man and wall picture> But since there is no internal machine vision algorithm at work in our program, we need something else to help our program distinguish which 1 bit is a wall and which 1 bit is Pac-Man. So we introduced another array of the same size except that this array only holds a picture of the walls of the screen. Thus, everytime dot Pac-Man is moved, we look up the next pixel (in the direction he is going) in the walls array to see if he will be stopped by a wall.

This implementation has only a marginal benefit over the original wall and dot Pac-Man implementation since the walls array holds exactly the same picture of the wall as the orginal screen array did. However, when Pac-Man is a sprite, we need to make sure that the walls contain the whole sprite and not just the position of Pac-Man, which we take to be somewhere in the middle of his sprite. From the Commodore 64 screenshots, we determined that Pac-Man and the ghosts can be drawn as 8x11 pixel bitmaps and the position pixel (the x, y coordinate that we keep track of) of each drawing is near the middle of the bitmap as shown below.


        4
     /-----\

    0       4
   0///////////////////
 /  / 0 0 0 0 0 0 0 0 /
 |  / 0 0 0 0 0 0 0 0 /
5|  / 0 0 0 0 0 0 0 0 /
 |  / 0 0 0 0 0 0 0 0 /
 \ 5/ 0 0 0 0 0 0 0 0 /
    / 0 0 0 0 * 0 0 0 /
    / 0 0 0 0 0 0 0 0 /-7 \
    / 0 0 0 0 0 0 0 0 /   |
    / 0 0 0 0 0 0 0 0 /   |-6
    / 0 0 0 0 0 0 0 0 /   |
    / 0 0 0 0 0 0 0 0 /   |
    / x x x x x x x x /   /
    ///////////////////-1
               -4    -1

                \---/
                 -3


From this very ghetto drawing you can see the distances between the wall seen on the screen and the position pixel (All this is based on where you pick the position pixel to be). There is an extra line at the very bottom between the bitmap and wall below, this is simply an extra line excluded from all bitmaps because it is the same blank empty line for all bitmaps. You can think of it as the bitmaps being 8x12 instead of 8x11. So for example, if there was a vertical wall at x-coordinate 50 and a sprite was approaching from the left, the sprite would need to be stopped once its position pixel's x-coordinate was at 50 - 3 = 47. Similarly, if the sprite were approaching from the right, it would need to stop at 50 + 4 = 54, otherwise the sprite would crash right through the wall.

Knowing this, the wall array becomes extremely useful. Instead of storing the same wall that we see visually on screen, we store the modified wall that the sprite's position pixel must respect. So for the same box visualized above, the associated walls box would be in
#:

        4
     /-----\

    0       4
   0///////////////////
 /  / 0 0 0 0 0 0 0 0 /
 |  / 0 0 0 0 0 0 0 0 /
5|  / 0 0 0 0 0 0 0 0 /
 |  / 0 0 0 0 0 0 0 0 /
 \ 5/ 0 0 0 ##### 0 0 /
    / 0 0 0 # * # 0 0 /
    / 0 0 0 ##### 0 0 /-7 \
    / 0 0 0 0 0 0 0 0 /   |
    / 0 0 0 0 0 0 0 0 /   |-6
    / 0 0 0 0 0 0 0 0 /   |
    / 0 0 0 0 0 0 0 0 /   |
    / x x x x x x x x /   /
    ///////////////////-1
               -4    -1

                \---/
                 -3


It doesn't look like that sprite has anywhere to go now but this is just an example case. The same idea works for boxes where the sprite is outside. But in this case, the walls array will need a picture of the box which is expanded outward. In truth, both an inner wall and an outer can be drawn but since Pac-Man will never be inside a box, we didn't do that. Now that the drawing background is done, we will cover the map drawing.

Map Drawing
The map does not ever change once drawn so we drew the map onto the screen array and the modified map onto the walls array before the TV signals were generated. Due to the extensive access of external memory, drawing the map while the video signal code was executed would have caused much jitter. There are two subroutines,
drawhorz and drawvert, which draw horizontal and vertical lines in a specified array starting and ending at two points. Below is an example of drawing a box in the screen array and its equivalent box in the walls array:

; screen box 13         ; walls box 13
LDI horzPT, 85          LDI horzPT, 85 - 6
LDI start, 102          LDI start, 102 - 1 - 3
LDI end, 107            LDI end, 107 + 1 + 4
RCALL drawhorz          RCALL drawhorz

LDI horzPT, 104         LDI horzPT, 104 + 5
RCALL drawhorz          RCALL drawhorz

LDI vertPT, 101         LDI vertPT, 101 - 3
LDI start, 86           LDI start, 86 - 1 - 6
LDI end, 103            LDI end, 103 + 1 + 5
RCALL drawvert          RCALL drawvert

LDI vertPT, 108         LDI vertPT, 108 + 4
RCALL drawvert          RCALL drawvert


Note that there are some +1 and -1 distributed throughout the walls code. This is because the screen box has rounded edges but the walls box should not.

Pills Drawing
Pills are drawn as two length 2 horizontal lines stacked on each other. The two subroutines
drawhorzpills and drawvertpills draw a row or a column of a specified number of pills starting at a specified point.

Pills provided another challenge for us: we need to detect when Pac-Man collides with a pill but also detect when Pac-Man ALMOST eats a pill but veers away at the last second. As with the walls, we define collision as the case when the position pixel of a sprite actually overlaps with a pill pixel. Also, we must make sure that ghosts do not eat pills. In all cases, we must make sure that a pill, if not already eaten, is redrawn on the screen even when it is erased by a passing sprite. This collision detection and redraw requires us to make yet another array of the same size as the screen. In this new array, we draw all the pills, just as they appear in the screen array. When a sprite moves, we check the pill array to see if it erases a pill accidentally and force a redraw of a pill if necessary. We also check to see if Pac-Man collided with the pill and erase the pill from the screen and pill array if that happens. Two subroutines,
killpillhorz and killpillvert, erase a pill from the screen and pill array depending on the direction in which Pac-Man approaches the pill. The pillsleft counter is also updated when a pill is killed.


Sprite Drawing
8x11 Sprites are relatively large bitmaps to draw at 8Mhz. Since we only have 508 cycles per line including the sync generation code to do game processing, we needed to split the erasing and drawing of sprites into two line's worth of code each. The first line would erase/draw the first half of the sprite and the second line would erase/draw the second half. The subroutine
dohalfbmp handles this. It take several parameters such as which bitmap to process, whether it is erasing or drawing, and which half to process.

At the end of each frame, each sprite is erased from the screen. Then a subroutine called
pollandupdate is run that polls the buttons for a legal change in Pac-Man's direction. Pac-Man's position is updated and the ghost AI is run to change the position of the ghosts. If Pac-Man new position takes him over a pill, the appropriate killpill subroutine is run to remove the pill. If Pac-Man has been hit by a ghost, special code is run to update his death status (shock, dissolving, pause). After pollandupdate, each sprite, if appropriate, is redrawn on the screen in time for the next frame.


Game Initialization
After the map is drawn, the
drawhorzpills and drawvertpills subroutines are run to seed the map with pills. The initial positions and directions of the sprites are set in the subroutine go_to_starting_positions. Various counters and flags are also set at this time. They are:

-
death counter: stays at zero until Pac-Man is hit, then counts up and different intervals signal the different phases of death for Pac-Man (shock, dissolving, pause)

-
mod3 counter: a mod-3 counter which keeps track of the current animation phase Pac-Man is in

-
ghostcntr: a counter which keeps track of the current animation phase the ghosts are in

-
pillsleft: a 16-bit counter which keeps track of how many pills are left of the initial 260

-
startgame: a flag which signals whether the game has started or if we're waiting for start


Some Miscellaneous Subroutines
-
check(x)side: replace x with a direction, checks if there is a wall in that direction next to a specified pixel

-
xy_to_pointermask: translates a pixel (x and y coordinate) to a pointer offset which points to the byte containing the pixel and a single pixel mask which masks the position of the pixel in that byte. As mentioned in the beginning, the raster is 22 bytes wide meaning that to get the byte pointer you must divide the x coordinate by 8 (easy) and multiply the y coordinate by 22 (must be done in software).