Turtle Graphics on the Fignition
The Fignition board is a fun little piece of 8-bit fun I tell ya! I’ve been having a blast with it. It’s an ATmega168 with 8Kb SRAM and 4Mbits of flash with video out (there’s also a sound mod for it). In this post I want to show off an implementation of Turtle Graphics I’ve made for it.
Forth as an “OS”
Most interestingly the Fignition is a completely standalone FIG-Forth system. It has an 8-button input system and, as is common for old Forths, there is an editor and screen-sized block “file system” of sorts. Compilation happens as blocks are loaded. This is all the “operating system” you need. For the first few days I programmed it entirely this way.
This is what is meant when people say that Forth is a language and an operation system. Normally it doesn’t mean giving up a normal keyboard, but still this idea of a complete system entirely in Forth is where it’s at. I’ll probably fall to temptation when the Raspberry Pi comes out but, com’on Linux is overkill (WinCE single board computers are too).
Development Host Machine
The above being said, it is quite tedious to program with the 8-button keyboard. Yesterday I got bulk loading of data over USB working; still a process but easier. There are instructions here (I initially had driver issues on Win8 – be sure to get the latest USBasp from here). The AVRDude tool allows you to transfer source one 500-byte block at a time from a PC/Mac to EPROM. Then you can edit on the device itself and write to flash, from where it can then be loaded/compiled to the dictionary and executed.
There was a 160x160 graphics mode added in firmware 0.9.6. This gave me the idea of making a rudimentary Logo-like system (I love it as a teaching language). I had a silly goal of getting it working snugly within a single block of code and managed to pull that off. It adds the following words for controlling the “turtle”:
c – clear screen (cls doesn’t work in 160x160 graphics mode)
g – Go to an x y coordinate (0,0 is the center of the screen)
h – Set heading (0-60 - 0 is North, 15 East, 30 South, 45 West)
b – Begin (enters 160x160 graphics mode, clears, resets turtle)
e – End (waits for key, exits graphics mode)
t – Turn the turtle (see h above – negative values for counter-clockwise)
n – Sine function (used internally – see h above – returns scaled by 255)
m – Move turtle number of pixels along current heading (no drawing)
p – Plot pixel currently under turtle
f – Forward number of pixels while plotting
Yes, this all fits in a single block and compiles to just 307 bytes!
Fixed-point Trig Functions
It uses a table-based cosine function with 6 degree (pi/30 radian) increments – think minute marks on a clock. This is still divisible by many things (2, 3, 4, 5, 6, 10, 12, 15, 20, 30), so it works out well enough for Logo and makes the lookup table small.
Resorting to 8.8 fixed-point numbers, I started with a quarter-cosine table with values scaled by 256. This leaves plenty of room for the turtle coordinates with a desired 160*256 range easily with the 16-bit integers supported. Some F# to generate it:
let table = let pi = System.Math.PI let
fix x = round (cos x * 256.) |> int
Array.map fix [|0. .. (pi / 30.) .. (pi / 2.)|]
Array.iter (printf "%x "
> 100 ff fa f3 ea de cf be ab 96 80 68 4f 35 1b 0
Just these values can be reflected and/or shifted to generate sine/cosine results for all sixty angles; something like the following (but in Forth):
let cosine x = let a = abs x % 60 let i = if a > 29 then 60 - a else a let s, i' = if i > 14 then -1, 30 - i else 1, i table.[i'] * slet sine x = x - 15 |> cosine
The Forth is intentionally compacted into obfuscation:
-2 var n F9F2 , E9DD , CEBD , AA95 , 7F67 , 4E34 , 1A c,
: s abs 3C mod dup 1D > if 3C swap - then dup E > if
-1 1E rot - else 1 swap then n + c@ 1+ * ;
The rest of the implementation is relatively straight forward (but not so readable because of poor factoring and naming due to wanting to squeeze down the character count):
0 var x 0 var y 0 var a
0 var q 0 var w
: c 9380 C80 0 fill ;
: k >r 50 + 8 << r> ! ;
: m dup q @ * x +! w @ * y +! ;
: g y k x k ;
: h dup a ! dup s w ! 2D + s q ! ;
: f >r q @ x @ y @ w @ r 0 do >r r + >r over +
dup 8 >> r 8 >> plot r> r> loop o y ! x ! o r> o ;
: e key 0 vmode cls ;
: b 1 vmode 1 pen c 0 0 g 0 h ;
: t a @ + h ;
Demo, demo, demo!
In a second block are some demos putting it to use.
[UPDATE: Now 4x faster!] I was stupidly calculating sine/cosine for every single-pixel of motion. Of course this only needs to be done when the heading changes - just keep the multipliers around for future use. Also, I made a small optimization to avoid multiplication for single-pixel movement. This sped things up by a factor of four or five.
[UPDATE: Now 15x faster!] Julian Skidmore, the designer of the Fignition, was nice enough to look at the code and came up with some brilliant performance optimizations - mostly around using 8.8 fixed point so that bit shifts could be used rather than multiplication/division and a slick simplification to the trig function.
The sine (s) function can be seen to work with:
: sin 160 0 do i i s 4 / 80 + plot loop ;
And we can see that using it to plot lines in each of the 60 available angles works:
: burst 60 0 do 0 0 g i h 110 f loop ;
Other demos show off some of the creative Logo patterns you may have played with as a kid:
: squiral -50 50 g 20 0 do 100 f 21 t loop ;
: circle 60 0 do 4 f 1 t loop ;
: spiral 15 0 do circle 4 t loop ;
: star 5 0 do 80 f 24 t loop ;
: stars 3 0 do star 20 t loop ;
: rose 0 50 0 do 2 + dup f 14 t loop ;
One of my favorites is this flower:
: hp 15 0 do 5 f 1 t loop 15 0 do 2 f -1 t loop ;
: petal hp 30 t hp 30 t ;
: flower 15 0 do petal 4 t loop ;
Here’s the source and generates hex files.