Hac-Man Won the Retrochallenge!

I’ve won the Summer 2012 Retrochallenge!!

Hac-Man is a clone and a recreation of a game I originally wrote on my high school’s minicomputer 30 years ago.  I’m delighted that I was able to get back into retrocomputing, considering I had to throw out almost all of my old computer and electronics history. 

Though I’m very much future-focused (and sometimes depressed for it), I always loved reading old technical books and magazines and  I love it more so when I can run old software and old operating systems like DEC RSTS/E.  I am not done with my retro explorations—I have a whole file share on my home server with hundreds of megabytes of nothing but emulators and system images, most of which I haven’t even had time to yet touch.  (It was this system that hosted the RSTS/E instance from which I developed the game, since I could work on it at my desk and at my laptop during lunch breaks.)

Hac-Man the game is completely finished now;  I’ve thought about making it available to download as a complete system, but it’s hard to do as there are very few terminal emulators that will work for Hac-Man, other than TeraTerm.   Kermit 95 is another possibility for a terminal emulator—it has recently been open-sourced—but from reading about the code, it sounds like quite a fixer-upper that I know I won’t have the time for.

I’d like to recreate my game in QuickBasic.  QB64 seems to be a very ingenious, well-developed reinvention of this classic BASIC interpreter and compiler.   I could create a very nice looking, if retro, Hac-Man, and this is what I’ll probably do if I ever have time.

The final tally:  Hac-Man is contained in two RSTS/E BASIC-PLUS programs, each of them weighing in at 20K and 400 lines each, and I spent roughly 50 hours in July working on the project.

Here’s the final, final video:

This’ll be my last retro entry for a little while, as I am forced back to the present by SATV and Microsoft.

Retrochallenge: Closing thoughts and a video

I’m a bit too exhausted to write the long post-mortem I had planned for the project.  I got enough of it done to show, but not enough to be a complete game;  the real world won’t let me take any more time on this project.

But it’s been a lot of fun.  RSTS/E is as linked to BASIC as Unix is to C.  Considering the limitations of BASIC, it’s amazing that so many of the system utilities were written in that language.  RSTS will never be a good host for arcade games, but we made it do in 1981. 

I’d like to give a hat tip to my old classmates in the Salem High computer lab:  Randy Moisan, Chris Haight, John Orlowski, Dave Irish, Peter Georgelas, and our department head Thomas Risoldi.  Thanks for the start in this crazy business.

Retrochallenge: The last few details of Hac-Man

There are just a few details left to explain. When I first thought of recreating my old BASIC game, I’d planned to have some bells and whistles like a high-score screen and an attract mode like in a real arcade game.

Very late in development, I ran out of time and memory to include all this in one executable, and I wasn’t sure if I would have a complete game for the contest. 

Fortunately, fate went in the other direction;  Hac-Man will have a front end with animation, a help screen and high scores.  It will also have the “halftime show” that was in the original game—and in my original clone.

RSTS/E BASIC, like most BASICS, has a mechanism for starting other programs from within a program:  The CHAIN statement.

23050 IF NOT DEBUG% THEN CHAIN "HACMAN.BAC" 9000

This code, if I’m not debugging will call HACMAN.BAC and start it at line 9000.  The .BAC extension indicates a compiled program;  CHAIN will fall back to the uncompiled program if the compiled program isn’t found, so it’s recommended practice to always specify .BAC.

(The DEBUG% variable is not part of RSTS/E BASIC, but is my own convention I’ve used for debugging in all my code.)

OK, but how do we pass information from one program to another.  This line of code is run in the Hac-Man game engine when the player loses the game.  The program should then pass the score back to the front end so it can be included in the high score list if possible.

RSTS/E has a feature it calls “core common”.  This is a 128-byte area that the operating system keeps for each job, and it is shared amongst all the processes in each job.   The RSTS/E command processor uses core common to pass parameters to system programs from the command line.

23010 GM$="HACMAN"+CVTF$(SCORE)+SPACE$(12-LEN(CVTF$(0)))+CVT%$(LEV%)+CVT%$(PLAY%)
23020 XX$=SYS(CHR$(8%))

We construct a string to pass back to our front end.  The first characters of the string are “HACMAN”, our magic signature that the other program uses to verify that it’s valid.

Next, the function CVTF$(SCORE) adds the score as a binary string.  Some explanation:  In RSTS/E, BASIC can use either 2-word floating point or 4-word floating point values, determined at system generation.  I generated my own RSTS/E system but I don’t remember which option I selected.  (And in the era of emulation, there’s no saying I could not generate a system with 4-word FP.) 

The string fragment SPACES$(12-LEN(CVTF$(0 ))) accounts for this possibility;  it pads the string with spaces for the next two values.

CVT%$(LEV%) and CVT%(PLAY%) convert these integers to binary;  integers are always 2 bytes so this is straightforward.

Here is the corresponding code on the front end:

8500 GM$=SYS(CHR$(7%)) ! Get string from core common
8509 !Validate string
8510 IF LEFT(GM$,6)<>"HACMAN" GOTO 1000 ! If no score passed, resume attract loop
8520 SCORE=CVT$F(MID(GM$,7,LEN(CVTF$(0))))
8530 LEV%=CVT$%(MID(GM$,12,2))

This code is called from the Hac-Man game engine at game over.  Line 8500 retrieves the string from core common.  Line 8510 checks for a “HACMAN” signature that indicates a valid code.  Line 8520 retrieves the score, and 8530 retrieves the ending level.

One last aside, this on memory:  I had forgotten how little memory I had on RSTS.  The memory in the BASIC interpreter, and the memory in my TECO screen editor more or less tracked together.  The biggest program I could get in both the editor, and BASIC was about 19,000 bytes, just less than 20K.

That included white space.  It isn’t free here, and that will surprise a lot of modern developers.

Several times, I had to back out of programming changes and refactor my code.  Hac-Man likely represents the most complex programming in RSTS/E.  In 1981, I was complimented on my work by a DEC field service engineer (“Wow, is that Pac-Man!?”) who told us that was the most ingenious program he had ever seen.

It is as good as I can possibly get it.

Next:  Closing words, and a video.

Retrochallenge: Hac-Man Munch Time!

After a month at recreating this old game, I have the AI kinda-sorta working.  Here’s how it’s supposed to work.

First, I must explain that the original game had no AI.  All we learned in those days about AI was in two lines of BASIC that were in virtually every book on BASIC, including the seminal work 101 BASIC Computer Games.  There were many such books up through the mid-80s.

10 Z=INT(RND(0)*10000)
20 D=SQR((X2-X1)*2+(Y2-Y1)*2)

Line 10 computes a pseudo-random number (which will be the same number every time it runs unless I include a RANDOMIZE statement).  Line 20 is a very familiar Euclidean distance formula.

That was it.  That was our AI in almost all of the computer games I and my classmates wrote in those days, and indeed in all of the innumerable collections of BASIC games published in print.

I wanted to do better this time around.   My strategy was inspired by a discussion of the AI of a certain popular game.  I couldn’t copy it as is, but I did take to heart its important lesson:  One can assemble simple behaviors and simple code to make our ghosts have reasonable smarts.

All of the ghosts share AI code;  each ghost has target coordinates that it prefers to go to.  It will take a direction to these coordinates first, if it can.  If not, it will continue in the same direction it’s heading, in hopes of finding a cross-corridor.

If the ghost finds itself blocked, it will then try moving to its left, and then to its right.  Here’s a diagram of how it works for Ink, the “fast” ghost that is most like the red ghost in the original game.

The other ghosts have different strategies:  Blink tries to move in front of the player.  Pink tries to block the player from behind, and, Sal, the fourth ghost, prefers to hide in a corner.

When the player eats a power pill, the ghosts only have one strategy—to get away from the player as fast as possible.

In testing, I found the ghosts to move very fast in relation to the player, so I added a counter to slow the ghosts down.  Currently, the ghosts move one cycle for every five cycles through the game loop. 

Here’s the annotated code:

12198 !Ghost movement routine
12200 FOR I%=GHOST% TO MAXGH%
12201 !Apply a delay count before moving ghost;  skip moving if delay timer not expired
12210 SV%(I%)=SV%(I%)-1\IF SV%(I%)>0 THEN 13480 ELSE SV%(I%)=VEL%
12220 IF NOT FNGHB%(SPX%(I%),SPY%(I%)) THEN 12300

Line 12200 starts a FOR loop to iterate through the four ghosts.  Line 12210 applies the delay counter.  Line 12220 calls a function, FNGHB%, that detects if the ghost is in its box.

12229 !If in ghost box, move ghost up through door
12230 IF SSTAT%(I%) THEN 13400 !If in box and eatable, do not move!
12240 SDR%(I%)=2\GOTO 13350 !End ghost box exit AI

If the ghost is in its box, it does one of two things:  If it is eatable, the ghost stays exactly where it is and does not try to leave the box.  If it’s normal, it will move up through the exit door (which I’ve made wide to simplify the AI).  SDR% is an array with direction data for all the moving sprites in the game, including ghosts.

12300 IF NOT SSTAT%(I%) THEN 12330 !Skip if not eatable
12301 !Same strategy for eatable mode for all ghosts
12302 !Preferred: Move away from Hac-Man
12310 GP%=REV%(FNDIR%(I%,SPX%(0),SPY%(0)))
12320 GOTO 13200

If the ghost is roaming the maze and it is eatable, its only strategy is to get away.  Line 12310 gets the reverse of the current direction of Hac-Man.

12323 !Per-ghost target calculations
12330 ON (I%-GHOST%)+1 GOSUB 12400,12500,12600,12900
12340 IF DEBUG% THEN XX$=FNSP$(SPDEAD%,PX%,PY%) !Indicate target square in debug
12350 GP%=FNDIR%(I%,PX%,PY%)

Otherwise, the target square for each ghost is calculated.  Line 12340 is some debugging code to display the target square on the playfield.  Line 12350 calculates the direction to the target square.

12398 !Ink: Head directly for Hac-Man
12400 PX%=SPX%(0)\PY%=SPY%(0%)\RETURN
12498 !Blink:  Head in front of Hac-Man
12500 PX%=SPX%(0)+DX%(SDR%(0))*2\PY%=SPY%(0)+DY%(SDR%(0))*2\RETURN
12598 !Pink: Goes behind Hac-Man
12600 PX%=DX%(SDR%(0))+DX%(SDR%(7))\PY%=DY%(SDR%(0))+DY%(SDR%(7))\RETURN
12895 !Sal: Go for Hac-Man if far, hide when close
12900 SD=FNDIST(I%,0)\IF SD>8 THEN PX%=SPX%(0)\PY%=SPY%(0)\RETURN
12920 PX%=70%\PY%=5\RETURN !Sal's corner is in upper right

Each ghost’s target square is calculated here.  This code was much shorter than I thought it would be.  Line 12400 handles Ink’s AI.  Blink is handled at line 12500.  Pink is at line 12600.  Sal is slightly more complicated:  If he’s far away (greater than 8 characters) from Hac-Man, he’ll head towards him, but when he gets closer, he’ll run and hide to the upper right corner.

13195 !Select direction:  Priority is Preferred (calculated), straight-ahead, sprite left, sprite right
13200 DIM G%(3)
13210 G%(0)=GP%\G%(1)=SDR%(I%)\G%(2)=FNRLD%(SDR%(I%),-1)\G%(3)=FNRLD%(SDR%(I%),1)
13220 IX%=0
13230 GD%=FNOBJ%(G%(IX%),SPX%(I%),SPY%(I%)) !Check each direction if clear
13240 IF GD%=4 OR GD%=5 THEN XX$=FNTUN$(I%,GD%)\GOTO 13460
13250 IF GD%<=2 THEN SDR%(I%)=G%(IX%)\GOTO 13350
13260 IF IX%<=2 THEN IX%=IX%+1\GOTO 13230
13270 IF DEBUG% THEN PRINT FNNC$;"NO DIRECTION FOUND-G,GD,IX,I";\MAT PRINT G%\PRINT IX%;I%\stop
13350 XX$=FNRD$(SPX%(I%),SPY%(I%))
13440 SPX%(I%)=SPX%(I%)+DX%(SDR%(I%))\SPY%(I%)=SPY%(I%)+DY%(SDR%(I%))
13450 IF NOT SSTAT%(I%) THEN IS%=I% ELSE IS%=9 ! Draw ghost sprite or eatable sprite
13460 XX$=FNSP$(IS%,SPX%(I%),SPY%(I%))
13480 NEXT I% !End AI routine

To make it easier on me, I used another array, G%, to hold the possible directions a ghost would take.  Again, the ghost moves in this order:  1) preferred direction, 2) current direction or straight ahead, 3) left turn, 4) right turn.

Lines 13220 through 13260 form the direction determining loop.  Line 13230 call the background object detection function FNOBJ%.  Line 13240 has special-case code and calls another special function FNTUN$ for the tunnel, which the ghosts will take.  If FNOBJ% returns 0 (empty space), 1 (dot) or 2 (pill), the direction is good and the ghost will take that, in line 13250.

Otherwise, the code tries the next direction from G%.  Line 13270 is debugging code that triggers if the four choices in G% are exhausted.  (There are no blind alleys in the maze.  There should not be.)

Once the ghost has a direction the rest is straightforward.  Line 13350 erases the ghost in its old location.  Line 13440 updates the ghost’s coordinates.  Line 13450 accounts for the ghost’s normal sprite or eatable sprite and line 13460 draws the sprite.  Finally, line 13480 ends the main FOR loop for the ghost AI.

With that, the major work behind Hac-Man is finished.

I only have a few more posts left before the end.  I’ll cover the last technical details in the next post.  My last post will have a video, my closing thoughts, and a dedication to close out the July Retrochallenge.