Steve Marsden originally worked fur Hewson in 1984, where he produced Technician Ted. He then moved to BT, where he produced Costa Capers in mid 1985. City Slicker came next in 1986 for Hewson.
In early 1987 Steve moved to Gremlin Graphics and produced Final Matrix, the 1997 Christmas compendium. April 1988 saw the release of Blood Brothers for Gremlin. More recently, Steve finished 4x4 Off-road Racing for US Gold.
During the four years of programming, Steve has worked with Dave Cooke. Before he started programming, he made silicon chips. Steve Marsden is a pilot.
In a program such as a game or a utility with a moving pointer driven by a mouse/tracker ball, there will be some form of detection routine if the moving objects interact in some way. If the detection routine is a good one, then the results on the screen will be visually more pleasing. We've all played games where you are frantically trying to move your main character away from a hostile alien, only to be killed off by another which looks to be a good two inches from the main character.
It can be extremely difficult to come up with an algorithm which doesn't take up hours of execution time and still leave an acceptable collision detection system. At the end of the day therefore it is all down to how much - or how little - time the programmer can allow for the detection routine. At the end of this article, I have written a small routine which gives the ultimate in detection - pixel detection. Like your computer teachers always say - "A computer can do anything you program it to do!" This is also the case when designing detection routines. Most programmers go for the first method I will describe - Box detection.
Virtually every sprite that has eve been drawn, starts out life as a rectangular array of bytes. The array of bytes is then transformed into a super duper spacecraft or other graphic with a suitable editing package and the resulting data is called a sprite frame. To move this sprite around the screen, the animation routine will simply output the rectangular array to various positions on the screen map. Now unless we draw a rectangular box shape which perfectly lines up with the edges of the array of bytes making up the sprite, then the odd corner of the array will consist of fresh air or nothingness (Fig 1).
However, we don't usually set up a rectangular array of say 10 characters by 10 characters in size and only draw a 2 x 2 character shape. Moreover we select a suitable size of rectangle so that we more or less fill the rectangle with only a few bare corners showing. This factor allows us to use a mathematical form of detection known as box detection.
Normally, a sprite will have a few important variables associated with it. These are at the very least an X co-ordinate, Y co-ordinate and possibly variables telling us how wide the sprite is and also how it is. Now it is quite an easy matter from this information about a sprite to determine whether an overlap has occurred between two sprite rectangles with a little elementary maths.
if all law sprites were boxes or rectangles, then this method would be infallible. The truth is, however, that our sprites have corners missing as in Fig. 1. Suppose two sprites are overlapping by their corners, the routine above will sense that they are overlapping - but on the screen we would not see an overlap the pixel meeting pixel sense. To us, it would seem that the two sprites were miles apart but they still detected each other. What is required then is a routine which actually determines pixel to pixel collisions.
The Hewson game Technician Ted used pixel detection and made it possible to use the feature extensively in its gameplay. The main character could literally walk up to a hostile sprite until his nose was only one pixel away from death. This sounds quite a complicated feat on the surface, but in reality it is so easy - the logical instruction 'AND' does it all for you.
Just think about it at the lowest level. A sprite is data and the screen is also data - just numbers. To draw a sprite onto a screen really means that we are taking one byte of data from one place and mixing it with another byte of data in another place and then storing the new data byte in the screen memory. Remember the truth table for the logical AND instruction:
| A | B | C |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Column A is one bit of data while column B is another bit of data. If we assume that a pixel is a '1' or a set bit in a byte then an overlap in logic terms means the case when A = B = l. The column C in this case produces a '1' when both A and B are '1'.
This shows clearly how we can use the AND to create a pixel detection system. The example program below uses an AND instruction in the detection routine but it does seem to be buried under a lot of other instructions - this is because a few other considerations have sometimes to be applied such as outputting the sprite to the screen. For the more technically minded out there, I have used and XOR type of output routine which combines the pixel detection as well.
A pixel detection system does not give any other information apart from telling us that an overlap has occurred. For example, a collision might occur between two sprites and a background feature such as a wall. The sprite to sprite collision might be acceptable - a friendly character perhaps - but the pixel detection cannot differentiate between pixels. A pixel could belong to a wall, a frog, a power pill, but the routine does not know where it originated from. This is why pixel detection can grow to very complicated lengths and as such it is why programmers usually shy away from it.
Preferably type in the source code into an assembler and produce the program that way. Fro those who haven't got an assembler (earn yourself a slapped wrist!), type in this BASIC program and input the decimal numbers from the listing supplied.
10 FOR N=32768 TO 33159 20 INPUT (N);"-";A 30 POKE N,A 40 PRINT N;" ";A 50 NEXT N
To run the program, do a RANDOMIZE USR 32768 and just watch what happens - hopefully a starry background with 6 square shapes moving around it. To return to BASIC press the SPACE bar. Poke the addresses 32792 and 32824 with any number from 1 to 6 to determine how many of the square shape you want.
Once the program has been entered, to save the machine code type in SAVE "detect" CODE 32768,391.
ORG 08000H
NO_SHAPES: EQU 6
DETECT_DEMO:
LD A,1 ; set the border to blue
OUT (£FE),A
LD HL,£4000 ; clear the pixel screen
LD DE,£4001
LD BC,£17FF
LD (HL),L
LDIR
CALL DRAW_STARS ; draw in the background and borders
LD IX,BLOB_VARS ; set up IX to point to the first set
LD B,NO_BLOBS ; of shape variables and make B equal
; to the number of shapes we want
INIT_LOOP:
PUSH BC ; preserve B - the counter
LD D,(IX+1) ; set up DE with the X and Y coords
LD E,(IX+0) ; of the shape
CALL DRAW_BLOB ; draw it to the screen
LD C,4
ADD IX,BC ; make IX point to the next shape
POP BC ; restore B
DJNZ INIT_LOOP ; loop back to draw in the rest of
; the shapes
MAIN_LOOP: ; synchronise the output loop with a
LD BC,1900 ; HALT and set up BC for the flicker
DELAY: DEC BC ; reducing counter
BIT 7,B ; if BC has not gone negative then go
JR Z,DELAY ; back (1901 times)
LD IX,BLOB_VARS ; initialise IX to the shape variable
LD B,NO_BLOBS ; list and B as a counter to the
BLOB_LOOP: ; number of shapes required
PUSH BC ; save the counter
CALL OUTPUT_BLOB ; CALL the main shape output and test
; routine
CALL NC,CHANGE_DIR ; NO CARRY from OUTPUT_BLOB
; means that collision has occurred so we
; CALL CHANGE_DIR to make the shape
LD BC,4 ; rebound
ADD IX,BC ; move IX on to the next set of shape
POP BC ; variables and restore B
DJNZ BLOB_LOOP ; loop back as required
LD A,£7F ; set A to the keyboard half row
IN A,(£FE) ; B-SPACE and read it
RRA ; check Bit 0 (SPACE)
JR C,MAIN_LOOP ; jump back if not pressed
RET ; else return to BASIC
CHANGE_DIR:
CALL DIR10 ; CALL DIR10 to get a random value of
LD (IX+2),A ; 0,1,-1 into the accumulator. Store
LD C,A ; it in the X movement variable
; (IX+2) and also temporarily in C
CALL DIR10 ; do the same for the Y movement
OR C ; variable and then OR it with C
; if the X and Y movement variables
JR Z,CHANGE_DIR ; are both zero then the shape would
; not move so jump back to CHANGE_DIR
RET ; then return
DIR10: CALL RAND_NUM ; get an 8-bit random number
CP 96
JR NC,DIR20 ; jump if A>96
LD A,-1 ; if A is 0-95, then make A=-1
RET
DIR20: CP 160
JR C,DIR30 ; jump if A<160
LD A,1 ; if A>160 then make A=1
RET
DIR30: XOR A ; if 96<=A<160 then make A=0
RET
DRAW_STARS:
LD BC,£FFBF ; make BC = counter values
LD DE,0 ; DE = screen top left coordinates
ST10: CALL PLOT ; plot at DE
INC E ; stEp along a pixel
DJNZ ST10 ; and repeat for 255 times
LD B,C ; make B = 191
ST20: CALL PLOT ; plot at top right corner
INC D ; and step down the screen 191 times
DJNZ ST20
DEC B ; decrement B to make it = 255
ST30: CALL PLOT ; plot at bottom right corner
DEC D ; step from right to left
DJNZ ST30 ; for 255 times
LD B,C ; make B = 191
ST40: CALL PLOT ; plot at bottom left corner
DEC D ; and step up the left edge of the
DJNZ ST40 ; screen for 191 times
INC B ; make BC = 447
ST50: PUSH BC ; save it
CALL Y_RAND_NUM ; get random number from 0-191
LD D,A ; put it in D
CALL RAND_NUM ; now get one from 0-255
LD E,A ; and put it in E
CALL PLOT_ADDR ; now plot at this random coordinate
OR (HL) ; by OR'ing with the screen
LD (HL),A ; pointed at by HL
POP BC ; restore the counter
DEC BC ; decrement it and loop back for 448
BIT 7,B ; times (until BC goes negative)
JR Z,ST50
RET
OUTPUT_BLOB:
LD D,(IX+1) ; set up DE from the shape coordinate
LD E,(IX+0) ; variables
CALL DRAW_BLOB ; rub out the blob from its present
; position
LD A,(IX+2) ; now add in the X movement variable
ADD A,E ; to the X coordinate and put in E
LD E,A
LD A,(IX+3) ; do the same with the Y movement
ADD A,D ; variable but put it in D
LD D,A
CALL DRAW_BLOB ; draw in the shape at the new moved
; position
JR C,PUT_BACK ; if there was a CARRY, then the new
; position has hit a pixel so jump
; to PUT_BACK and don't move
LD (IX+1),D ; if the new position was OK then
LD (IX+0),E ; store the new X and Y coordinates
SCF ; and set the CARRY before returning
RET ; to signal - MOVE SUCCESSFUL
PUT_BACK:
CALL DRAW_BLOB ; rub out the moved shape
LD D,(IX+1)
LD E,(IX+0) ; Y position
CALL DRAW_BLOB ; and re-draw the shape at its first
AND A ; position, CLEAR the carry flag
RET ; before returning to signal - MOVE
; UNSUCCESSFUL
DRAW_BLOB:
PUSH DE ; save DE
CALL PLOT_ADDR ; calculate the screen address at
; which to draw the shape (from DE)
LD DE,SHAPE ; make DE point to the shape data
EX AF,AF' ; clear the alternative carry flag
AND A
EX AF,AF'
LD B,8 ; there are 8 pixel rows in the shape
BLOB10: PUSH BC ; save the counter
PUSH DE ; ... and the shape pointer
LD B,C ; B = C = X pixel position (1 - 8)
LD A,(DE) ; get the shape data byte
LD D,A ; put it in DE (E = 0)
LD E,0
BLOB20: SRL D ; rotate DE as required to bring the
; shape data into the correct place
DJNZ BLOB20 ; for outputting to the screen
; The detection and output stage
LD A,D ; get the leftmost byte of data and
LD (HL) ; logically XOR it with the screen
LD (HL),A ; data then store it in the screen
AND D ; mask off the bits we have just put
CP D ; in and check to see that they are
; the same - Zero flag set
JR Z,BLOB30 ; jump if the same - no collision
EX AF,AF' ; set the alternative carry flag to
SCF ; indicate that a collision has in
EX AF,AF' ; fact occurred
BLOB30: INC HL ; step on the screen point across
LD A,E ; the screen and now treat the right
XOR (HL) ; most byte of shape data in the same
LD (HL),A ; way - XORing to the screen, masking
AND E ; the bits we are interested in and
CP E ; comparing to check that they are
JR Z,BLOB40 ; the same - jumping if they are
EX AF,AF' ; as before, set the alternative
SCF ; carry flag if a collision has
EX AF,AF' ; occurred
BLOB40: DEC HL ; step the screen pointer back to its
INC H ; first place and increment it down
LD A,H ; the screen
AND 7 ; if within the same character cell
JR NZ,BLOB50 ; then jump
LD A,L ; else add 32 to the low byte of the
ADD A,£20 ; screen pointer
LD L,A
JR C,BLOB50 ; if transition across a screen
; 'third' has been made then jump
LD A,H ; else subtract 8 off the pointer
SUB 8 ; high byte
LD H,A
BLOB50: POP DE ; restore the shape pointer
POP BC ; and the 8 pixel row counter
INC DE ; increment the shape pointer
DJNZ BLOB10 ; and decrement the counter
EX AF,AF' ; make the alternative carry flag
POP DE ; available to the CALLing routine
RET ; restore DE and return
PLOT:
PUSH BC ; save registers from corruption
PUSH DE
CALL PLOT_ADDR ; calculate the screen plot address
OR (HL) ; and OR in the pixel to
LD (HL),A ; the screen
POP DE
POP BC ; restore registers and return
RET
PLOT_ADDR:
LD A,D ; check the Y coordinate range to see
CP 192 ; that it is not off the screen
RET NC ; return if it is
AND £C0 ; put the screen 'third' bits into
RRA ; bits 3 and 4 with a 010 in bit
SCF ; positions 5, 6 and 7
RRA
RRA
XOR D ; merge in the bits 0, 1, and 2 from
AND £F8 ; the Y coordinate
XOR D
LD H,A ; and store in H
LD A,E ; move the top 5 bits of the X co-
RLCA ; ordinate into bits 0, 1, 2 and 6, 7
RLCA
RLCA
XOR D ; merge in bits 3, 4 and 5 from the
AND £C7 ; Y coordinate
XOR D
RLCA ; rotate the byte twice more and
RLCA ; hey presto we have
LD L,A ; the low byte of the screen address
LD A,E ; get the three lower bits of the X
AND 7 ; coordinate and increment them to
INC A ; give the range 1 - 8
LD B,A ; copy it to B and C
LD C,A
LD A,1 ; set bit 0 of A
PLOT10: RRCA ; rotate it so that the set bit is
DJNZ PLOT10 ; in the correct place before
RET ; returning
Y_RAND:
CALL RAND_NUM ; get an 8-bit random number and
CP 192 ; check to see that it is less than
JR NC,Y_RAND_NUM ; 192. Jump back if it isn't until
RET ; we get a valid number less than 192
RAND_NUM:
LD HL,(SEED_POINTER) ; the random number is obtained by
INC HL ; poking the Spectrum ROM from £0000
LD A,H ; to £4000
AND £3F ; the pointer to the ROM address is
LD H,A ; incremented each time we call the
LD (SEED_POINTER),HL ; random number routine and the
LD A,(HL) ; accumulator is loaded with the
RET ; current pointer value before
; returning
; this is the 8 bytes of shape data
SHAPE: BYTE £FF,£81,£81,£9F,£80,£81,£81,£FF
; the random number pointer
SEED_POINTER:
WORD 2000
; initial values for the 6 shape
; variables
BLOB_VARS:
WORD £3010,£FF01
WORD £0950,£00FF
WORD £0960,£0101
WORD £9F70,£FF00
WORD £9F80,£00FF
WORD £7F10,£00FF
62 1 211 254 33 0 64 17 1 64 1 255 23 117 237 176 205 116 128 221 33 111 129 6 6 197 221 86 1 221 94 0 205 217 128 14 4 221 9 193 16 239 118 1 108 7 11 203 120 40 251 221 33 111 129 6 6 197 205 171 128 21 80 128 1 4 0 221 9 193 16 241 62 127 219 254 31 56 219 201 205 97 128 221 119 2 79 205 97 128 221 119 3 177 40 240 201 205 88 129 254 96 48 3 62 255 201 254 160 56 3 62 1 201 175 201 1 191 255 17 0 0 205 32 129 28 16 250 65 205 32 129 20 16 250 5 250 32 129 29 16 250 65 205 32 129 21 16 250 4 197 205 80 129 87 205 88 129 95 205 42 129 182 119 193 11 203 120 40 236 201 221 86 1 221 94 0 205 217 128 221 126 2 131 95 221 126 3 130 87 205 217 128 56 8 221 114 1 221 115 0 55 201 205 217 128 221 86 1 221 94 0 205 217 128 167 201 213 205 42 129 17 101 129 8 167 8 6 8 197 213 65 26 87 30 0 203 58 203 27 16 250 122 173 119 162 186 40 3 8 55 8 35 123 174 119 163 187 40 3 8 55 8 43 36 124 230 7 32 10 125 198 32 111 56 4 127 214 8 103 209 193 19 16 200 8 209 201 197 213 205 42 129 182 119 209 193 201 122 254 192 208 230 192 31 55 31 31 170 230 248 170 103 123 7 7 7 170 230 199 170 7 7 111 123 230 7 60 71 79 62 1 15 16 253 201 205 88 129 254 197 48 249 201 42 109 129 35 124 230 63 103 34 109 129 126 201 255 129 129 159 128 129 129 255 208 7 16 48 1 255 80 9 255 0 96 9 1 1 112 159 0 255 128 159 255 0 16 127 255 0