COMPAC
by J Dave Rogers and Colin Hogg
from ZX Computing Oct/Nov 1984


Liverpudlians JD Rogers and C Hogg have produced yet another winner with 
this definitive Pacman type game

Unlike many maze/ghost-chase type programs this one is challenging and will 
be appreciated by the connoisseur of such games. The three independent 
ghosts have more than the average amount of intelligence, and in fact even 
with the nine extra lives allowed, experienced arcade players will need many 
plays before being able to clear all of the screens.

Most of the program functions, including man-movement, are in BASIC just the 
ghost movements and screen checks are in machine code, yet the speed is 
equal to the arcade versions. There are twelve carefully designed 
full-screen-size mazes (including 'tunnels'), all in a surprisingly compact 
listing.

In attaining this compactness only two things have been left out. Once is 
'power pills', the other is continuous (dot-counting) scoring. We think the 
quality of play and other features more than make up for these. The 
addictive quality of these types of games seems to lie in 'clearing screens' 
rather than scoring points.


Using the program, playing the game
-----------------------------------

There are two sets of mazes, either of which can be chosen upon running. The 
second set are considerably harder to clear and are really intended for when 
you've become successful on the first set and are looking for a further 
challenge!

A fixed score is given for clearing each screen, and since they are graded 
in difficulty, successive screens are worth more points (see table 1). Also, 
the ghosts are programmed to be a bit less vicious on screens one and two, 
but reach their 'full-strength' from screen three onwards.

When killed you are rejuvenated, using up one life, and carry on from the 
point where you were hit. Clearing a screen also gives you an extra life, 
and there is an added bonus of four extra lives if you can get past screen 
three.

If you happen to break the program, don't press RUN or you will have to wait 
for maze decoding (see later). Always enter 'GOTO 500' as this includes a 
'clear' to erase the large arrays that are used and so drastically reduce 
loading time.

The ghosts will not follow you through tunnels. Maze 'C' in addition to 
having normal tunnels, has two 'bolt holes' which can be used as resting 
places where the ghosts can't get at you.


Storing mazes in five bit code
------------------------------

To store six, full-screen-size mazes in the usual way (as strings of 
characters) would require 132 such lines to be typed in - making a tedious 
and error-prone total of over four thousand black and white blocks to be 
entered. In this program the mazes are held in the form of a five-bit code 
(see figure 2), where each maze line (32 characters) is 'crunched' into just 
three coded elements, giving a compression ratio of almost eleven-to-one! An 
8-bit code was first considered but was awkward to type in and ambiguous, 
involving back-spacing to enter the characters needed to represent certain 
numbers, and 'chr$ N' to represent those not having a Sinclair code. 
Hexadecimal code was another possibility, but this only offered an 8-to-1 
compression ratio.


                      PATTERN IS
                    AUTOMATICALLY
                      'MIRRORED'                   THREE 5-BIT SECTIONS
                        TO LEFT                ______________^_____________
 ZX81 'PRINT'                                 /                            \
   POSITIONS: 0 1                            16                            31
              |_|_________|_________|_________|_________|_________|_________|_|
LINE OF MAZE: |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|#|_|_|_|#|_|#|_|#|_|_|_|#|_|
              | |         |         |         |         |         |         | |
                                       BINARY |0 0 1 0 0|0 1 0 1 0|1 0 0 0 1|
                                              |         |         |         |
              (ENDS ADDED             DECIMAL |    4    |   10    |   17    |
               IN LINE 930)                   |         |         |         |
                               '5-BIT' SYSTEM |   '4'   |   'A'   |   'H'   |
                                              |         |         |         |

Figure 2. Illustration shows maze storage technique described in text.


The five bit code uses numerals 0 to 9 extended through characters A to V to 
represent binary numbers up to 31. Full stops can be used instead of zeros 
and provide occasional visual landmarks for even easier typing in.

On first running the program it takes two minutes to decode the information 
to form the actual mazes. This, however, works out to be less than the extra 
time it would have taken to load the program had the mazes all been held in 
strings. So overall the time is saved, and since the program itself is made 
much shorter you also have the advantage of more reliable loading. Even more 
economical is that six extra mazes ('second set') can be obtained more or 
less for free by decoding the information for the main mazes in a different 
order. Only three program lines are needed for this (772-774).

Screen  Points  Appearance   Tunnels        Title

A (G)   500     Grey         2 (4 + H)      Easy Street.
B (H)   2,000   Stripes      3 (4 + H)      Skid Row.
C (I)   4,500   Grey         4 (4 + H)      Mr. P. Acne.
D (J)   8,000   Quilted      2 + H (4 + H)  Roundabouts.
E (K)   12,500  Grey         None (4 + H)   Claustrophobia.
F (L)   18,000  Psychedelic  2 (4 + H)      Open-Field.

Table 1. Summary of screens (brackets indicate 'Second set' screens).
         H indicates horizontal tunnel.


Concerning bug movements
------------------------

The programming of (what looks like) intelligence into the enemy's pac's' is 
not simple as it may seem, and many pages could be written on this 
interesting but sometimes frustrating subject. A particular algorithm may 
work perfectly in a given shape of maze only to fail in a slightly different 
layout. It is also advisable never to rely on oneself to be 'test pilot' 
during development, since a system that consistently outwits one person may 
be useless against somebody else who naturally tends to take different route 
decisions during play.

The common solutions, such as move towards player line then player column, 
produce 'stupid' enemy pac's that are forever getting stuck or will just 
jiggle up and down apparently unwilling to get past the slightest bend in 
the maze to catch you. Another typical behaviour is for all the pac's to 
follow the same path, in which case they are liable to stay in a 'train' 
behind the player, again offering no real challenge.

An interesting test for any pac move algorithm is a 'U' shape in the maze, 
or more accurately any construction that is topologically equivalent to a 
'U'. Take a look at some commercial/arcade mazes - U shapes are avoided, 
except at the edges. Here it doesn't matter, because the situation 
'player-under-the-U-with-pac-inside' can never arise, and it is this 
condition that can cause trouble.

The system used in this program is shown on the flowchart. It contains 
subroutines for moving in all four directions, but these are only called in 
response to a series of checks. The obvious moves directly towards player 
line and player column are tried first, and if none of these are valid, then 
scans are made for paths further afield. For compactness, the same central 
routine is used for all three pac's in turn, but information relevant to 
each pac is held in separate stores and flags (bytes are set aside for this 
at the end of the machine code rem line). The information on pack 'A' is 
first shifted into the pac move routine, the routine is executed, the pack 
is moved, then the new position and status of the pac are replaced into its 
store for use in its next move. This is then repeated for pac's 'B' and 'C'. 
Despite all three pac's using the same algorithm, they hardly ever follow 
the same paths as each other. This is because each pac is programmed to 
regard any other pac's was walls of the maze and so it will split off. In 
this way two pac's will often do a 'pincer' movement to trap you!

                            |
                            |
                            v
               +------------------------+    Figure 1. Flowchart describing the method
               |                        |              used to cause pacs to follow player.
               | IF PAC IS ON SAME LINE |
               |    COLUMN AS PLAYER    |
               |      RESET FLAG TO     |
               |        LINE MOVE       |
               |                        |
               +------------------------+
                            |
                            |
                            v
                    +---------------+
                    |               |
                    |    IS FLAG    |
             COLUMN | SET FOR LINE  | LINE
      +-------------|   OR COLUMN   |-----------+
      |             |     MOVE?     |           |
      |             |               |           |
      |             +---------------+           |
      |                                         v
      |                                 +---------------+
      |                                 |               |
      |                                 |   IS PLAYER   |
      |                           BELOW | ABOVE, BELOW, | ABOVE
      |       +-------------------------|    OR SAME    |------------------------+
      |       |                         |     LINE?     |                        |
      |       |                         |               |                        |
      |       |                         +---------------+                        |
      |       |                                 | SAME LINE                      |
      |       |                                 |                                |
      |       v                                 v                                v
      |    +------+       +------+       +------------+       +-------+       +------+
      |    |      |       |      |       |            |       |       |       |      |
      |    | TRY  |       | TRY  |  LEFT | IS PLAYER  | RIGHT | TRY   |       | TRY  |
      |    | MOVE |       | MOVE |<------| TO LEFT OR |------>| MOVE  |       | MOVE |
      |    | DOWN |       | LEFT |       |   RIGHT?   |       | RIGHT |       |  UP  |
      |    |      |       |      |       |            |       |       |       |      |
      |    +------+       +------+       +------------+       +-------+       +------+
      |       |               |                                   |              |
      |       v               v                                   v              v
      |       |               |                                   |              |
      |       +---------------+----------------+------------------+--------------+
      v                                        |
      |                                        |
      |        +-----------------+             |
      |        |                 |             v
      |        | SCAN ALONG PACS |       +------------+
      |        |  PRESENT LINE,  |    NO |            | YES
      |        |  BOTH WAYS FOR  |<------| WAS A MOVE |------> RETURN
      |        |   ACCESSES TO   |       |    MADE?   |
      |        |  PLAYERS LINE   |       |            |
      |        |                 |       +------------+
      |        +-----------------+
      |                 |
      |                 |
      |                 v
      |        +-----------------+       +------------+
      |        |                 |    NO |            | YES
      |        |   SELECT THE    |<------| WAS A MOVE |------> RETURN
      |        |  SHORTER ROUTE  |       |    MADE?   |
      |        |                 |       |            |
      |        +-----------------+       +------------+
      |                                        |
      |                                        |
      |                                        v
      |                                +----------------+
      |                                |                |
      |                                | CHANGE FLAG TO |
      |                                |   COLUMN MOVE  |
      |                                |                |
      |                                +----------------+
      |                                        |
      |                                        v
      |                                        |
      +-------------------+--------------------+
                          |
                          |
                          v
    +------+       +------------+       +-------+
    |      |       |            |       |       |
    | TRY  |  LEFT | IS PLAYER  | RIGHT | TRY   |
    | MOVE |<------| TO LEFT OR |------>| MOVE  |
    | LEFT |       |   RIGHT?   |       | RIGHT |
    |      |       |            |       |       |
    +------+       +------------+       +-------+
        |                                   |    
        |                                   |    
        +-----------------+-----------------+
                          |
                          |
                          v
                    +------------+
                    |            | YES
                    | WAS A MOVE |------> RETURN
                    |    MADE?   |
                    |            |
                    +------------+
                          | NO
                          |
                          v
               +---------------------+
               |                     |
               | SCAN PRESENT COLUMN |
               |  UP/DOWN FOR ACCESS |------> RETURN
               |  TO PLAYERS COLUMN  |
               |                     |
               +---------------------+
    
    NOTE: "Line move" means a move towards the player's line, ie up or
          down. "Column move" is to players column.


Use of RAND seed
----------------

The pac-move routine needs to know the players immediate line and column 
positions. So as not to slow down the program the 'RAND' function is used as 
an efficient means of transferring this information from the BASIC to the 
Machine Code. Changes in 'A' (across) only affect the low byte of the RAND 
seed, so this represents player column, while changes in 'D' (down) are 
multiplied by 256 and will therefore affect only the high byte, so this 
represents player line. The machine code can now go directly to the two 
fixed addresses of the RAND seed to obtain this information instead of 
messing about finding addresses in the Variables area, which is not fixed.


Typing In - IMPORTANT
---------------------

Unlike normal Rem statements, line 9999 is not optional, since it forms once 
of the 'trigger lines' used for tunnel movements (see later).

Do not attempt to alter line numbers between zero and 400 since the machine 
code causes line 90 to 'GOTO' certain preset lines.


Customising
-----------

If you find some of the mazes a strain on the eyes then you can have them 
all in 'restful grey' by changing line 840 to read 'LET A=136'.

Some people prefer the arcade type of free-running control response, i.e. if 
no keys (or more than one key) are pressed then the player continues to move 
in the same direction. This can be obtained by adding: 5 IF CODE INKEY$ + 
ABS (D+A) < 4 THEN GOTO 20

You can alter the actual control keys to those you feel most comfortable 
with by changing lines seven and ten.

To slow down the game (and add an extra effect) add '+RND' to line 50. 
Custom points 2 and 6 also slow down the game.

For desperately bad players the final figure in line 100 can be changed to 
5. This gives the advantage when turning corners to you rather than the 
ghosts, and even lets you take a breather to compose your wits by purposely 
running against a wall for a while.

A proper pause facility (for when the phone goes or you suffer a sneezing 
fit at a crucial stage of play) can be obtained by adding: 15 IF INKEY$="P" 
THEN PAUSE 4E4.

If you would prefer the player to restart at the top of the screen after 
being killed (as in arcade type) then relocate line 270 to 371 and line 280 
to 372, erasing the originals of course.

To encode your patterns of mazes into the 5-bit format you should start at 
column sixteen of each line and work right, converting each group of five 
characters into a five-bit binary number. ie dot=0, Maze wall=1. Mazes 
should be left-right symmetrical.


The Basic
---------

7-90       Players move routine.
30         If character at intended Position is anything other
           than a dot or a space then GOTO further checks
           at line 100, otherwise:
40-60      Blank out previous position, POKE player onto
           screen at new position, update S.
70-80      Update Line-Column variable (LC) then use this
           as seed for RAND (see text).
90         Calls machine code to move the three 'ghosts'
           and do screen checks, then 'goes to' one of the
           following lines:
              Normally --------- line 5
              If player has been hit by ghost --- line 300
              If screen has been cleared of dots --- line 200
110        If player hits one of the 'trigger lines' (consisting
           of CHR$ 21) above and below the maze area
           then a "tunnel" move is performed by setting D
           to either 21 or minus 21 (depending whether
           player is at top or bottom of screen). Upon re-
           entering the main loop, D now alters the palyers
           position by means of line 20 (to re-emerge from
           the opposite tunnel) and also updates 'LC' to suit
           by means of line 70.


Note
----

Only the lower trigger line is actually visible on the screen, the other one 
is within the program (line 9999) which since it is the very last thing in 
the program area of memory is effectively one line above the screen (display 
file - Refer to memory map in ZX manual). This leaves more room on screen 
for the actual game.

200-290    When a screen is cleared updates score, adds
           another life (or bonus of four lives for reaching
           screen four), pauses, does 'rollover' effect then
           prints next mazes and resets players position. In
           the unlikely (!) event of a player clearing the sixth
           screen the sequence goes back to screen one.
270-280    Resets Line-Column variable to coincide with
           players starting position.


Note
----

One is added on to LC during screens one and two, thus slightly 
disorientating the ghosts since they now 'see' the player as being one space 
to the side of his real position. This is done to make the first two screens 
slightly easier, then in screen 3 onwards the ghosts come up to 'Full 
strength'.

300-395    When player is hit takes away on life, flashes
           both the player and the life that is being used up.
           User call then returns ghosts to starting
           positions. If all lives used up ends game.
400-480    New game, resets various variables.
500        Selfsave and setting up.
630-640    Sets up arrays to hold mazes and maze data.
700-770    Storage strings, holding the data for all six mazes
           in compact '5-bit' form. Note: for greater
           readability the extreme conditions of zero and
           thirty one are represented as full stops and X's
           respectively.
800-970    Routine that decodes the data into actual mazes.
           This consists of three nested for-next loops:
              M loop - for mazes one to six.
              X loop - for items of data one to 66
           loop - extracted from each storage string.
              N loop - for bits one to five of each item.
840        Alters the characters used to build certain mazes.
           Normal value of 136 gives a grey maze.
890        Builds up each maze line 'from the centre
           outwards' and thus mirrors the maze
           symmetrically to the left and right.
920        Continues X-loop until a line of 30 characters has
           been built up, line 940 then adds 'ends' to that
           line and places it into position within the
           appropriate maze array (M$).
771        Repeatedly concatenates the string of inverse
           spaces B$ into a while screen full. Used to give
           'rollover' effect between screens.
773-774    Shifts the data in the storage strings about so
           that when decoded different shaped mazes are
           produced ('second set').


Machine code
------------

The machine code moves the three ghosts, checks for man-hit and for screen 
cleared. All addresses are in hexadecimal.

4082-40AE  Set up pacs in starting positions using data from
           the fixed stores (see later).
40AF-40BC  Scan whole screen for remaining dots, if none are
           found then return to Basic with value 200,
           which is then used as the 'GOTO' value in line
           90.
40BD-40E0  Call bug moves. Puts data from bug 1's store
           into workspace, calls pac move, then replaces
           data to store when move completed. Repeats
           this for pacs 2 and 3.
40E2-40F6  Player-hit check. The characters that are to be
           replaced behind each pac as it moves are held in
           stores, so by looking at these, if any contains the
           'player' character then player must have been hit.
           If so, jumps to routine at 40F7 which wipes out
           all the pacs, replaces them at start positions and
           then returns to Basic with value of 300, so line
           90 'goes to' player hit routine.
40F3-40F6  If player not hit, returns to Basic with value of 5,
           so line 90 continues movement loop to line 5.
4112-413F  Set working flag. Sets various bits of working
           flag (4290) according to pac position relative to
           players position. i.e. above, below, same line,
           etc.
4141-4166  Move decisions (see flowchart).
4167-416F  Try move towards player line.
4171-4175  Try move towards player column.
4177-41B9  Movement routines for all four directions. When
           called, checks if move is valid, if so does move,
           updates pac line/column and resets carry to zero,
           if not sets carry to 1.
41BA-41FD  Column scan. Scans pac column up and down to
           find horizontal access to player column. Having
           found this, calls relevant movement routine. If no
           move possible sets carry.
41FF-4259  Line scan. As for column scan but horizontally,
           plus a comparison is made between routines
           left/right and the shorter of the two is taken.
4268-end   Various stores. Information for each pac is held in
           a standardised order: pac 1, pac 2, pac 3. For
           each bug; two positions, column, line, Flag byte,
           chr$ for replacing behind.
4268-4279  Fixed stores containing start values (read only).
428C-4291  Working store holding information on current bug
           being moved.


The variables
-------------

Players Variables
A            Across movement.
D            Down/up movement.
IP           Intended position.
S            Screen position.
LC           Line/column. Represents both line and column
             position (one in high byte - *256 - the other
             in low byte) for reference by machine code.


Other variables
---------------

SC           Score.
LYF          Life remaining.
MZ           Maze number.
X            Marks start of display file in memory.
SS           The "Second set" of mazes are produced if this
             equals on, main set if zero.
S$(1 to 6)   Storage strings, containing maze data in 5-bit
             code form.
M$(1 to 6)   Maze strings, into which actual mazes are built
             up.
U$           General-purpose, also used in decoder.


Decoder variables
-----------------

K            Determines type of character used for walls of
             maze.
S            Single value extracted from storage string for
             decoding.
D            Divisor. Starts at 16 (bit-five) then reduced to 8 to
             decode bit 4, and so on down to bit 1.
U$           String into which each line of maze is built up
             before being placed into a maze array.
A            Code for character produced by decoding current
             bit.

