Retrochallenge: Hac-Man Munch Time!Posted: July 30, 2012
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.