## Sunday, 29 May 2016

### Divide and Conquer Line Algorithm for the ZX Spectrum

While attempting to write a game in 256 bytes I needed a routine to draw lines, but Bresenham's line algorithm weighs in at approx ~120 bytes. The only suitable alternative I'm aware of is recursive divide and conquer: divide a line into two smaller lines and call the draw routine with each in turn:

``````/* Draw a line from (ax,ay) to (bx,by) */

int draw ( ax, ay, bx, by )
{
int midx, midy;
midx = ( ax+bx ) / 2;
midy = ( ay+by ) / 2;
if ( midx != ax && midy != ay )
{
draw( midx, midy, ax, ay );
draw( bx, by, midx, midy );
plot( midx, midy );
}
}
``````

This is significantly smaller thank Bresenham's, 32 byte of Z80. However, there are a couple of compromises: it's slower and the lines aren't perfect because the rounding errors accumulate.

``````; draw lines using recursive divide and conquer
; from de = end1 (d = x-axis, e = y-axis)
; to   hl = end2 (h = x-axis, l = y-axis)

DRAW:
call PLOT

push hl

; calculate hl = centre pixel

ld a,l
add a,e
rra
ld l,a
ld a,h
add a,d
rra
ld h,a

; if de (end1) = hl (centre) then we're done

or a
sbc hl,de
jr z,EXIT
add hl,de

ex de,hl
call DRAW    ; de = centre, hl = end1
ex (sp),hl
ex de,hl
call DRAW    ; de = end2, hl = centre

ex de,hl
pop de
ret

EXIT:
pop hl
ret

; ---------------------------

; plot d = x-axis, e = y-axis

PLOT:
push hl
ld a,d
and 7
ld b,a
inc b
ld a,e
rra
scf
rra
or a
rra
ld l,a
xor e
and 248
xor e
ld h,a
ld a,l
xor d
and 7
xor d
rrca
rrca
rrca
ld l,a
ld a,1
PLOTBIT:
rrca
djnz PLOTBIT
or (hl)
ld (hl),a
pop hl
ret
``````

Alternatively the `de(end1) = hl(centre)` test can be replaced with a recursion depth count to create an even slower 28 byte routine:

``````; draw lines using recursive divide and conquer
; from de = end1 (d = x-axis, e = y-axis)
; to   hl = end2 (h = x-axis, l = y-axis)

DRAW:
ld c,8

DRAW2:
dec c
jr z,EXIT

push de

; calculate de = centre pixel

ld a,l
add a,e
rra
ld e,a
ld a,h
add a,d
rra
ld d,a

call DRAW2   ; de = centre, hl = end1
ex (sp),hl
call DRAW2   ; de = centre, hl = end2

call PLOT
ex de,hl
pop hl
EXIT:
inc c
ret
`````` ## Friday, 27 May 2016

### Langton's Ant for the ZX Spectrum

Langton's Ant is an automata which creates a complex pattern by following a couple of simple rules:

• If the ant is on an empty pixel, turn 90° right, set the pixel then move forward
• If the ant is on a set pixel, turn 90° left, reset the pixel then move forward

The ant's path appears chaotic at first before falling into a repetitive “highway” pattern, moving 2 pixels diagonally every 104 cycles.

Here's the code to display Langton's Ant on the ZX Spectrum in 61 bytes. It runs in just over a second so you might want to add a `halt` to slow things down:

``````  org 65472

ld de,128*256+96

ANT:
; halt
ld a,c      ; check direction
and 3
rrca
add a,a
dec a
jr nc,XMOVE

add a,e     ; adjust y position +/-1
ld e,a
cp 192
ret nc
xor a

XMOVE:
add a,d     ; adjust x position +/-1
ld d,a

; ----------
and 7       ; calculate screen address
ld b,a
inc b
ld a,e
rra
scf
rra
or a
rra
ld l,a
xor e
and 248
xor e
ld h,a
ld a,d
xor l
and 7
xor d
rrca
rrca
rrca
ld l,a
ld a,1
PLOTBIT:
rrca
djnz PLOTBIT
; ----------

ld b,a      ; test pixel
and (hl)

jr nz,LEFT  ; turn left/right
inc c
inc c
LEFT:
dec c

ld a,b      ; flip pixel
xor (hl)
ld (hl),a
jr ANT
`````` 