Retrochallenged: HacMan—Mazes and Motion

HacMan program listing, featuring the background object array

For the past month I’ve been working on a Pac-Man clone that I originally wrote back in 1981.  I lost the source, so I’ve had to recreate everything as I’ve gone.  But one technique hasn’t changed:  When I had the idea for the game, I already learned how to get our terminals to move the cursor about the screen and draw characters on them, but one problem stumped me for a long time in 1981:  How do I get my game code to know what’s on the screen?

How can I have a game with spaceships, enemy saucers, and ghosts on the screen, recognizing each other’s existence and interacting with the player?  From the time I first saw Pac-Man in an arcade, I wanted to replicate it.  But how?

Back then (and even to this day, for the VT-100), there was no command, no escape sequence, that would take in row/column coordinates and return the ASCII value of the character painted on the screen on that location.  Nothing at all.

I’m not sure how I came up with the solution, but I thought of something that my peers considered elegant at the time, a technique that’s just the way I remember it back then, the one thing in my program that still dates to 1981.

Look at this code snippet:

2895 ! *** Gamefield string definition ***
2950 DIM GFL$(22%)     ! GFL$ = Gamefield drawn on screen
2960 DIM GFL%(80%,24%) ! GFL%(x,y) = Gamefield object detection
3000 GFL$(1) = "lqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqk"
3010 GFL$(2) = "x O........ .............. .............  ............ ..... ...... .......O x"
3020 GFL$(3) = "x                                                                            x"
3030 GFL$(4) = "x .lqqqqqu. tqqqqqqqqqqqu. tqqqqqqqqqqu. tqqqqqqqqqqu. tqqqu. tqqu. tqqqqqk. x"
3040 GFL$(5) = "x .x ...... .............. ........ .... .... ........ ...... ..... ..... x. x"
3050 GFL$(6) = "x .x                                                                      x. x"

You’ve seen the GFL$ string array before;  it contains the playfield.  Note the GFL% 80×24 integer array.  More code:

10115 !Initialize background maze collision detect array
10120 MAXDOT%=0% \ FOR IY%=2% TO 23% \ FOR IX%=1% TO 79%
10130 GFL%(IX%,IY%)=ASCII(MID(GFL$(IY%-1%),IX%,1%))
10141 !Count up total dots including 4 power pills
10200 !Draw maze and score display
10210 PRINT FNCL$+FNLD$ ! Clear screen and alt character set
10220 GOSUB 19010\GOSUB 19050 ! Print score and level
10250 PRINT FNHM$;! Home cursor
10260 PRINT\FOR I%=1% TO 22%\PRINT GFL$(I%)\NEXT I%

At this point, we go through the playfield string array one line at a time, and we fill the GFL% integer array with the ASCII value of each character making up the playfield.  Along the way, we count the dots and the pills to get a maximum count that the game uses to determine when  the level is complete.  (That makes it easier to change the maze during development.)

LInes 10210 through 10260 actually draw the maze on the screen.  But the real logic is in the GFL% array—this array has the information that Hac-Man and the ghosts will use to navigate as they twist, turn and eat their way through the game.

This was the most important idea I had in 1981, and the one that made the game possible.

In this era’s revision of my program, I put a lot more thought and a lot more logic into a great many tables and data structures that govern how the actors move in the maze.  (That’s how last Friday’s blog update turned into this Friday’s…) 

I wanted to make the logic as general as I could, which in BASIC is something of an oxymoron, but I think I did much better than I did in 1981,  Here’s how my object detection routines work:

Hacman Direction Diagram

There are four, and only four directions for any sprite to take, starting from leftward motion—direction 1—going clockwise, up (2), right (3) and down (4), and they are numbered and indexed in various tables and arrays, beginning at the input detection logic and continuing all the way to the ghost AI routines.

(On the screen, you may notice a debugging message at the top saying “X,Y,Dir”.  The coordinates are right but the direction is wrong:  I changed the direction numbering scheme after I took the screenshot—the old scheme I first used would have made the ghost AI routines nearly impossible to write.)

The master list of sprite coordinates—SPX%, SPY%, SDR%—contain location and current direction for the player and the ghosts (and the inanimate, unmoving fruits.)  There are also arrays for starting location and direction.

There is a object detection array CX% and CY%, illustrated by the green highlights.  The function FNOBJ% will return a value given the current position of a sprite, and the direction it is moving in.   This is used by the player sprite to detect dots and pills. 

And there is a movement array DX% and DY% which returns the proper direction XY vector given the numerical direction.  There’s even a reverse direction array that the program uses in certain circumstances, such as when a pill is eaten and the ghosts reverse direction.

Wall detection logic is simple: FNOBJ% checks the two coordinates in the direction the sprite is moving. If either of the two coordinates is not a space, a dot or a pill, it is considered a wall. This made it possible for me to make the maze look nicer with VT-100 drawing characters that I didn’t have in the original.

There is special-case code for the tunnel that connects the left and right sides of the maze.

The background object detection array is altered in one circumstance:  When Hac-Man eats dots, or one of the pills, the corresponding object is erased from the array and is replaced by the ASCII code for space, 32, which the game treats as empty, movable space.  So, the array saves the game state during play until the level is complete.

The background object array also has one important purpose I forgot to mention in my first draft:  Ghosts ignore dots and pills, but as they move through the maze, those dots and pills are the background that has to be preserved and redrawn.  (In 1981, multiplane sprite graphics were something I had only heard of.  They were also in machines I could never afford.)

Checking for collisions between sprites, between Hac-Man and a ghost, or a fruit, is much simpler;  the original game, and my remake, uses a Euclidean distance formula of the sort taught in basic high school geometry.  If Hac-Man and a ghost meet, their mutual distance will be zero and the ghost had better be edible.  Either way, the code to handle that is under the sprite collision section.

Next up, the ghost AI.   The most important part of the game.  The part that makes Hac-Man, Hac-Man.  We’re nearly there.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s