Retrochallenge: Hac-Man Munch Time!

Hacman and Ghosts

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.

AI strategy for Ink

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
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
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
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.


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