Recently I issued the fifth Z80 challenge for the Sinclair Spectrum:
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:
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:
|Red||John Metcalf||98||~2K||2.1 seconds|
|Orange||Paul Rhodes||102||~1.8K||3.2 seconds|
|Yellow||Ralph Becket||109||~2K||8.8 seconds|
|Green||Miguel Jódar||166||~800||4.8 seconds|
|White||Dworkin Z Amberu||58||~9.8K||28.6 seconds|
|Cyan||John Metcalf||54||~6.1K||28.6 seconds|
|Black||Dworkin Z Amberu||84||1K||40 seconds|
|Blue||Dworkin Z Amberu||192||8 bytes||~40 minutes|
|Purple||Adrian Brown||199||12 bytes||~3 hours?|
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.