Gulpman (Maze Game) Monster Movement

The 1982 ZX Spectrum game I cloned last year (with new code) was called Gulpman written by John A. Campbell. This clone was written without any knowledge of the internals. Over the last two weeks I’ve taken apart the original - and have a pretty much complete annotated disassembly. See my previous blog post for more information on this (including the disassembly).

You can find information about the game here http://www.worldofspectrum.org/infoseekid.cgi?id=0002175 and even play it online http://www.ciunga.it/jxspeccy/gulpmanx2.html (or actual size with instructions here http://www.ciunga.it/jxspeccy/gulpman.html). Sadly the web-emulated version is without the fantastic sound effects; download an emulator for the best experience! [Edit 7-Oct-2012: See this post about better web-based emulation]

In this post I’ll detail my understanding of the monster movement algorithm used, based on this disassembly. This is one of two relatively complex algorithms in the code - the other being the (automatic) demo player. All other functions - although long - are straightforward and relatively obvious.

As a terminology note: what I refer to as ‘monsters’ in this article are referred to by the instructions as ‘four grumpy chasers’.

Since the algorithm details are quite long, I’ve put the ‘final’ paragraphs first... (for the less-techie readers).

Movement Summary

If I had to summarise the movement algorithm it would be:

“It will always try to go toward the player, but if that fails it will step in a different direction (favouring perpendicular, i.e. 90 degrees. a right angle) repeatedly until it can either move towards the player or it is blocked from moving in that direction by something”

However, this misses out a huge amount of detail that effects real-world movement.

Conclusion

The algorithm works surprisingly well based on it’s size. You hardly ever see it get stuck (i.e. a monster hovering looking for a way to go) and it navigates around walls surprisingly well.

Part of this is helped by the maze layouts and the fact there are another three other monsters chasing you.

One case of ‘getting stuck’ is in the ’N’ or ‘U’ of the Maze ‘O’ Gulp-man maze. However, this doesn’t offer much help - since it’s very difficult to get all of the monsters stuck at the same time... (although I wouldn’t say that was impossible... just unlikely)

More Info

There are some more comments from John himself  in the emulation permission for World of Spectrum where he talks about “being pleased with the algorithm” (see http://www.worldofspectrum.org/showwrap.cgi?permit=houses/CampbellSystems.pmt ).

For real retro-interest, there was a ZX81 version as well: http://www.zx81stuff.org.uk/zx81/generated/tapeinfo/g/Gulpman.html (and click the play button to run the file).

I’d be willing to post both the cloned version and the original ZX Spectrum annotated disassembly on-line, but really need to get in contact with Mr Campbell to do this (to get copyright permission).

Algorithms in Other Games

If you are interesting in these things, it’s also worth looking at the PAC-MAN ghost behaviour which isn’t as simple as it sounds either http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior and http://www.webpacman.com/ghosts.html

There is further discussion of possible maze movement techniques here: http://www.programmersheaven.com/mb/game/165986/165986/pacman-ghost-movement/

ALGORITHM DETAILS

Monster vs. Player Speed

Part of the monster interaction is determined by the speed of the monsters.

The whole game speed is set by ‘Tempo’ which simply slows up the whole game loop by a delay. However, this does not affect the monsters algorithm in itself - except the whole game runs faster and the human needs to react quicker (and hence does effect difficulty somewhat).

The player moves every 16 game loops. The all the monsters then move at a separate pace.

This pace is set by two parameters parameters:

• the ‘Grade’ setting - to quote the instructions “the relative start speed of the [monsters]”
• Player success - to quote the instructions “every 1000 points [monsters] go a little faster”

This is a snippet from my annotated disassembly:

; reset monster speed
; this is made up of several components... grade,
L69B5: 3E 40        LD A,40h
L69B7: DD 96 A4     SUB (IX+0A4h)    ; 632A-5Ch = 62CEh = grade_number '1' (31h) to '9' (39h)
                                    ; A result will be 15 for easy and 7 for hard
L69BA: 87           ADD A            ; A=A*2, so easy is 30 and 14 is hard.
L69BB: DD 86 12     ADD (IX+12h)    ; 632A+12=Player Success. 14 at start. 0 at lowest.
                                    ; A total = 44 or 14.
L69BE: C6 08        ADD 8h            ; Give the player more advantage.
                                    ; A total = 52 or 22.
L69C0: DD 77 1F     LD (IX+1Fh),A    ; 632A+1F=monster speed, load with new calculated value


So for those of you that don’t read Z80 assembly, that is:

    monster_speed_count = ((64 - grade_number_ascii) * 2) + player_success + 8

Grade number is the ASCII value (‘grade_number_ascii’) - as per the ‘GRADE’ game setting, where ASCII ‘1’ is 49 decimal and ASCII ‘9’ is 57 decimal. T’he setting of 9’ is harder.

The player success (‘player_success’) starts at 14 and decreases by 2 (bottom 0) every 1000 points earned. So only the first 7 bonuses affect monster speed. (What I called ‘player success’ might be a bad name for this variable, but still, I’m sure you get the idea.)

This monster_speed_count is decremented until it’s zero. When it’s zero the above code is run to set the next monster run speed and the four monsters are all individually run.

Note: the monsters always run slower than the player. Based on my quick calculations that means that the monsters run at 325% slower than the player at slowest and 37.5% slower at fastest.

The equation seems logical - make the game harder based on both requested hardness and on player experience and skill, but I expect the constants in this equation were arrived at by trial and error (as is often the case).

Data Structure

Each of the four monsters have a 8-byte data structure as follows:

Byte    Action
 0    monster code - same as UDG (user defined graphic) character code
 1    default position as address in map data (least significant byte)
 2    default position as address in map data (most significant byte)
 3    monster_position as address in map data (least significant byte)
 4    monster_position as address in map data (most significant byte)
 5    what is under the monster? (e.g. an apple or a space)
 6    second choice offset if primary fails? (0=no primary/secondary, i.e. back up system off)
 7    primary offset to move in ... "Primary choice" in this case is the way we REALLY want to go towards the player!

Normal Case Algorithm

Terms used here:
    Column represents the horizontal position, i.e. left and right.
    Line represents the vertical position, i.e. up and down.

In the normal (basic) case we first try to get to the same column as the player - i.e. we follow the player left and right. After we get the same column (or the way we want to go left-or-right is blocked by a wall or another monster) we try to get the same line. If both of these are blocked then we run some ‘special-case’ algorithm which is detailed in the next section.

On the face of it this basic column-then-line method might appear naive, but consider the following:

• The playing area is wider than it is high so it’s somewhat logical to choose a column-based left-right direction first.
• The monster movement controller subroutine (function) may well run when the columns are the same if the player passes us underneath - so this then causes the line match mode to run - making the monster (try to) move up and down. Since on most mazes (and in most cases on all mazes) movement in this direction will be blocked, hence causing the special case to run.

These are well worth expanding:

1. It introduces some level of randomness into the process when the columns are the same and the player passes underneath, since the player cannot easily predict if the monster is simply going to follow the player back the other way, or the special case code takes over and it goes the other way.
2. You can see it clearly on Maze ‘O’ the GULP-MAN maze when a monster is in an open area and the player repeatedly passes left-and-right; hence the special case code is never run and column matching overrides line. However, it still doesn’t give the player very much respite in a real game with three other monsters heading towards him and the fourth getting slowly closer!

In a lot of simple maze games that just try to follow the player, the monsters get stuck behind walls (because they are taking some form of direct route to the player) and this usually results in a very boring game. Some strategy is usually required to overcome simple-follower stupidity.

Special Case Algorithm - Summary

The special case algorithm has to choose a direction to travel that is not (necessary) towards the player. As soon as it discovers these special case modes allow a move towards the direction the player was in or is blocked (by a wall or monster) it reverts to trying to chaise the payer (normal case algorithm).

The algorithm has a small feature to mix things up a bit and a slightly different behaviour if the player is on the same line.

Special Case Algorithm - Detail

So, when the direction towards the player is blocked in both line and column direction (normal case algorithm), this ‘special case’ code is run.

This piece of code (30 lines of Z80 assembler, plus two tiny tables) is relatively complex for it’s size.

First it sets up a primary direction towards the player.

The primary direction is straight forward:

1. up if the player is on a higher line
2. down if the player is on a lower line
3. right if the lines are the same and the player is to the right
4. left if the lines are the same and the player is to the left

Next it tries to move in directions from one (of two) tables. It uses a first table if the player and the monster are on the same line, or a second table if the lines are not the same. Here are the tables (with my comments and label names):

; used when the lines are the same ... we want to go up or down really ... but
; if that fails try right and left.
monster_move_offsets_1:
L672D:              DEFB E0, 20, 01, FF

; used when the lines aren't the same ... try lines then columns for movement.
monster_move_offsets_2:
L6731:              DEFB FF, 01 E0 20

Here FF means go left, 01 mean go right, E0 means go up and 20 means go down, so these could be re-written as:

monster_move_offset_1:        up, down, right, left   ; player and monster on same line
monster_move_offset_2:        left, right, up, down   ; player and monster on different lines

However, before it tries to move based on the table chosen, it swaps the first and second entries of this table. And note these tables are common for all monsters. It’s difficult to know exactly what this does without more runtime analysis, but I guess this might have several effects:

• Specific monsters don't make the same decision as the previous if they are in the same predicament.
• It also might solve 'stuck' problems for a specific monster.

After this swap, it tries each four options from the left hand table-entry to the right table-entry in turn. For the case on the same map line this will mean it will try to step up and then down first. For the case where they are on different lines, it will try to step left and right first.

If a movement in a direction succeeds it stores that direction in the ‘secondary’ direction and that’s everything completed for this time around.

There is a possible case where we cannot move in any direction - due to being surrounded by a combination of walls or monsters. In this case, the last entry in the table will be stored in the ‘secondary’ direction variable before leaving with the monster unmoved.

Special Case - Next Time the Monster Runs

The next time this monster runs (as defined by monster speed count as above), then (if we previously ran the special case algorithm) it will first try the primary direction (as defined last time we calculated this primary/secondary direction which it might be out of date but in normal cases only slightly) - this is towards where the player was when the special case started. If the primary direction works, then we go back to the normal case algorithm.

If, the primary direction is blocked, then we will try the secondary direction stored from the above processing that succeeded last time. If that doesn’t succeed (we’ve moved to a wall, or another monster is in the way) then we run the normal case algorithm (and possibly special case algorithm) again.

If the second direction does succeed then we will run this primary-then-secondary test again the next the monster runs - again and again  until the primary succeeds or the secondary is blocked.

One note about this two step special case system is that the monsters - when blocked from their objective (e.g. directly above the player but with walls in between) tend not to have more consistency in movement and don’t just hop backwards and forwards.

Phew! If you got this far, congratulations :-)