Saturday, 20 May 2017

ZX Spectrum BASIC Challenges

Recently I've entered a few of the programming challenges in the BASIC on the ZX Spectrum group on Facebook. They vary in difficultly but it's possible to write a program for most in under 30 minutes. If you're looking for a quick challenge or the opportunity to improve you BASIC, why not take a look.

Here are some examples of the challenges:

Earth/Venus Orbits

David Saphier challenged us to write the fastest code to display the Earth and Venus orbit pattern in BASIC. Being a bit of a rebel I aimed to write the shortest code and managed to completely botch it before coming up with this working version:



Grid

Matthew Logue asked us recreate a grid-like pattern with the shortest code. Surprisingly I actually managed to discover the smallest program:



Weaving

‎Uwe Geiken challenged us to recreate a pattern of weaving attributes. I found this one pretty tricky to reduce in size, but finally got it down to 109 bytes:



Flag

Matthew Logue asked for the shortest code to recreate a 31×21 attribute flag-like pattern. Uwe Geiken solved this is 67 bytes, easily beating my 74:



Rudimentary Gear

Matthew Logue challenged us again, this time to draw a rudimentary gear with 10 teeth and a circular radius. Here's what I came up with:



Saturday, 29 April 2017

ZX Spectrum Scanline Flood Fill

A flood fill is a graphical algorithm to colour an area of screen bounded by pixels of another colour. The scanline technique is a fast, stack-efficient flood fill which can be implemented in 99 bytes of Z80, as demonstrated below:
; scanline fill by John Metcalf
; call with d=x-coord, e=y-coord

; set end marker

fill:
  ld l,255
  push hl

; calculate bit position of pixel

nextrun:
  ld a,d
  and 7
  inc a
  ld b,a
  ld a,1
bitpos:
  rrca
  djnz bitpos
  ld c,b
  ld b,a

; move left until hitting a set pixel or the screen edge

seekleft:
  ld a,d
  or a
  jr z,goright
  dec d
  rlc b
  call scrpos
  jr nz,seekleft

; move right until hitting a set pixel or the screen edge,
; setting pixels as we go. Check rows above and below and
; save their coordinates to fill later if necessary

seekright:  
  rrc b
  inc d
  jr z,rightedge
goright:
  call scrpos
  jr z,rightedge
  ld (hl),a
  inc e
  call checkadj
  dec e
  dec e
  call checkadj
  inc e
  jr seekright

; check to see if there's another row waiting to be filled

rightedge:
  pop de
  ld a,e
  inc a
  jr nz,nextrun
  ret  

; calculate the pixel address and whether or not it's set

scrpos:
  ld a,e
  and 248
  rra
  scf
  rra
  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,b
  or (hl)
  cp (hl)
  ret

; check and save the coordinates of an adjacent row

checkadj:
  sla c
  ld a,e
  cp 192
  ret nc
  call scrpos+1
  ret z
  inc c
  bit 2,c
  ret nz
  pop hl
  push de
  jp (hl)

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

Saturday, 3 October 2015

The Matrix Digital Rain for the ZX Spectrum

A few days ago I coded The Matrix digital rain effect, a fictional representation of the code for the virtual reality of The Matrix. The technique is simple: fill the screen with random characters and scroll down columns of attributes, occasionally switching between black and green.

Here's the final code - 147 bytes of Z80 using the default Sinclair font:

        org 08000h

; black border / black attributes

        xor a
        out (0FEh),a
        ld hl,05AFFh
attr:   ld (hl),a
        dec hl
        bit 2,h
        jr z,attr

; fill screen with random characters

        ld e,a
fillscr:ld d,040h
fill:   call rndchar
        ld a,d
        cp 058h
        jr nz,fill
        inc e
        jr nz,fillscr

; digital rain loop

frame:  ld b,06h
        halt
column: push bc

; randomize one character

        call random
        and 018h
        jr z,docol
        add a,038h
        ld d,a
        call random
        ld e,a
        call rndchar

; select a random column

docol:  call random
        and 01Fh
        ld l,a
        ld h,058h

; ~1% chance black -> white

        ld a,(hl)
        or a
        ld bc,0247h
        jr z,check

; white -> bright green

white:  cp c
        ld c,044h
        jr z,movecol

; bright green -> green

        cp c
        ld c,04h
        jr z,movecol

; ~6% chance green -> black

        ld bc,0F00h
check:  call random
        cp b
        jr c,movecol
        ld c,(hl)

; move column down

movecol:ld de,020h
        ld b,018h
down:   ld a,(hl)
        ld (hl),c
        ld c,a
        add hl,de
        djnz down
        pop bc
        djnz column

; test for keypress

        ld bc,07FFEh
        in a,(c)
        rrca
        jr c,frame
        ret

; display a random glyph

rndchar:call random
crange: sub 05Fh
        jr nc,crange
        add a,a
        ld l,a
        ld h,0
        add hl,hl
        add hl,hl
        ld bc,(05C36h)
        add hl,bc
        ld b,8
char:   ld a,(hl)
        ld (de),a
        inc d
        inc hl
        djnz char
        ret

; get a byte from the ROM

random: push hl
        ld hl,(seed)
        inc hl
        ld a,h
        and 01Fh
        ld h,a
        ld (seed),hl
        ld a,(hl)
        pop hl
        ret

seed:

Sunday, 26 July 2015

Z80 Size Programming Challenge #5

Recently I issued the fifth Z80 challenge for the Sinclair Spectrum:

This time the challenge is to write a solid flood fill routine to fill a region of unset pixels, bounded in 4 directions (up, down, left, right) by set pixels or the screen edge. The routine should be called with the X and Y coordinates in a register. There's no need to set the screen attributes.

Scoring is multi-objective: a routine will be judged by the code size and stack space required to fill a test image. Your routine will be awarded one point for each competing routine it is smaller *and* uses less stack space than. The routine(s) with the most points will be declared winner(s).

The deadline is Wednesday 22nd July, midday (GMT).

  1. The X and Y coordinates are in pixels with 0,0 at the top left.
  2. No memory other than the screen, stack and your routine can be written.
  3. If you call a ROM routine it's size will be added to your code size.
  4. Programs must return. The RET instruction is included in the size.
  5. So everyone has a fair chance comment with the code size not code.
  6. There are no prizes, just the chance to show off your coding skills.

The test image is designed to check correct behaviour at the screen boundary and to be pathological — triggering suboptimal behaviour in some common flood fill algorithms:

Final Results

Congratulations to everyone who coded a working flood fill and to Dworkin Z Amberu who claimed first place by being shorter and using less memory than competing entries.

Entries have been plotted on this genuine fake Spectrum screenshot. If the graph is empty below and to the left of an entry, that entry is in first place:


ColourCoderCodeMemoryTime
RedJohn Metcalf98~2K2.1 seconds
OrangePaul Rhodes102~1.8K3.2 seconds
YellowRalph Becket109~2K8.8 seconds
GreenMiguel Jódar166~800 bytes4.8 seconds
WhiteDworkin Z Amberu58~9.8K28.6 seconds
CyanJohn Metcalf54~6.1K28.6 seconds
BlackDworkin Z Amberu84~270 bytes40 seconds
BlueDworkin Z Amberu1928 bytes~40 minutes
PurpleAdrian Brown19912 bytes~3 hours?

Shortest Entry

The simplest entry is a recursive routine weighing in at 54 bytes. Despite being too heavy on the stack to score well it's one of the easiest to understand. Each time the routine is called it checks whether or not the pixel at X,Y is set. If not the pixel will be set then the fill routine is called recursively with the pixels up, down, left and right of the current pixel:

; called with e = X horizontal, d = Y vertical
FILL:
  ld b,e
  ld a,d
  and 248
  rra
  cp 96
  ret nc
  rra
  rra
  ld l,a
  xor d
  and 248
  xor d
  ld h,a
  ld a,e
  xor l
  and 7
  xor e
  rrca
  rrca
  rrca
  ld l,a
  ld a,128
PLOTBIT:
  rrca
  djnz PLOTBIT
  or (hl)
  cp (hl)
  ret z
  ld (hl),a
  inc e
  call nz,FILL
  dec e
  dec de
  call ZFILL
  inc de
  call FILL
  inc d
  inc d
ZFILL:
  call nz,FILL
  dec d
  ret

The winning entries will be available shortly.

Monday, 6 April 2015

Z80 Size Programming Challenge #4

The fourth Z80 challenge for the ZX Spectrum was issued last week:

Back to something simple for the next challenge, a diagonal fade-to-white CLS. Write the shortest code to wipe the screen by increasing the ink colour of each character until it reaches white.

The clear should start at the top left and move one character across the screen per frame. The initial screen can be assumed to be monochrome — black text, white background, flash off, bright off. There's no need to clear the screen bitmap. Here's a demonstration of the clear in slow motion:

Target: under 50 bytes.

The deadline is Monday 6th April, midday (GMT).

  1. Your program shouldn't rely on the initial contents of registers.
  2. Programs must halt between frames. The HALT is included in the size.
  3. No RAM/ROM other than the attribute memory should be written to.
  4. Programs must return. The RET instruction is included in the size.
  5. So everyone has a fair chance comment with the code size not code.
  6. There are no prizes, just the chance to show off your coding skills.

Final Results

Congratulations to everyone who entered and Arcadiy Gobuzov who claimed first place with a solution in 26 bytes. Most of the solutions use LDDR to move the attribute data with anonymous and Ralph Becket being the two exceptions. Here are the final results:

CoderSize
Arcadiy Gobuzov26
ub880d27
Bohumil Novacek27
anonymous27
Adrian Brown27
John Metcalf27
Ralph Becket30
Jim Bagley31
Paul Rhodes31

Winning Entry

Here's Arcadiy's winning entry in 26 bytes:

        xor a ; if comment then 25, but exit if a==56 on start
loop:        
        ld hl,#5ADF   ;
        cp (hl)       ;
        ld bc,#02E0   ; 23 lines of attributes
        ld de,#5AFF   ; 
        lddr          ; move down attributes
        ld c,e        ; e = #1F
        add hl,bc     ;
        lddr          ; roll upper line of attributes to right
        halt
        ret z
        ld a,(de)     ; de = first address of attibutes
        cp #3F        ;
        adc a,c       ; add 0 or 1 (carry)
        ld (de),a     ; now a in range [38..3f]
        jr loop

Here's my own solution in 27 bytes. Unfortunately I missed the final CP (HL) to squeeze out the last byte:

fadetowhite:
        ld de,23295 ; 90 255
        ld a,(de)
        cp 63
        ret z
        ld hl,23263 ; 90 223
        ld bc,736   ;  2 224
        halt
        lddr
        ld c,e
        add hl,bc
        lddr
        ld a,(de)
        cp 63
        adc a,c
        ld (de),a
        jr fadetowhite

Here's an alternative — a fade-to-black wipe (from white ink, black paper, no bright, no flash) in 25 bytes:

fadetoblack:
        ld de,23295 ; 90 255
        ld a,(de)
        or a
        ret z
        ld hl,23263 ; 90 223
        ld bc,736   ;  2 224
        halt
        lddr
        ld c,e
        add hl,bc
        lddr
        ld a,(de)
        add a,l
        sbc a,l
        ld (de),a
        jr fadetoblack