Mandelbrot set on an emulated Apple ][

I figured I'd start off with a pretty picture, so that maybe you'll let me go on a discursive narrative.

When I was but a wee lad, I learned to program on my family's Apple ][. I started off with the little stuff that you do, like 

10 PRINT "HELLO, WORLD"

20 GOTO 10

and the like. I began drawing pictures on the "High Resolution Graphics" (HGR) screen, with a staggering 280x160 pixels (280x192, if you were fancy and used the second page and gave up the 4 lines of text at the bottom of the screen). But, eesh, I was playing fancy games like Space Invaders, Donkey Kong, and Pac Man in the arcades, and I wasn't getting anywhere near the performance that the professional developers were. And even games written for the Apple were a lot more capable than what I was able to get done in BASIC.

Somehow, somewhere, I learned that the professionals didn't do high-performance graphics in Applesoft BASIC. The big boys used Assembly Language. So, that's where I decided I needed to focus my energy.

As an aside, probably around this time, my dad did have Apple Pascal running on the home machine, but maybe Pascal also was sluggish in its own way. For whatever reason, I never spent much time with Pascal for the Apple ][. A few years later, the Apple IIgs came around, and that's when I learned Pascal, which led directly to C, then C++, which may account for the majority of code that I've written in my life, though there are plenty of others. C and C++ I learned on a 286 IBM PC and a 486 IBM PC Compatible, back when IBM was relevant in the PC space.

There were a few dead ends that I learned on the Apple ][, though, including GraFORTH and Apple Logo - both promising to give good graphics, in their own way. GraForth was a Forth implementation, which introduced me to stacks, which would help me with Postscript and RPN years later. And Logo was LISP without all the parentheses. So, even though the languages themselves didn't help me make cool animations, they planted seeds.

The idea fixed in my mind was to learn Assembly Language one way or another. On a family trip to the Pacific Science Center in Seattle, Washington, we passed through the gift store (back when it occupied the balcony of Building 4), and I found a book for sale titled "Assembly Language for the Applesoft Programmer". Well, that was exactly what I wanted. This was the key to writing computer games, and being successful, and avoiding actually having to "work" at a "job" - I'd write some sort of platformer for the Apple ][, and, I don't know. Profit. I didn't have all the steps worked out, but I knew I needed this book.

I begged and pleaded for Dad to buy the book for me, and he flipped through it, and decided it was a fairly substantial work, but it had a lot of programs to type in (back in the day, we typed in programs, even from magazines). So, Dad made me a deal; he'd buy me the book if I promised that I'd work through all the programming tasks, type in all the code, actually go through the whole thing. Yes, of course. 

I probably read the first chapter in the car ride home, which introduced a number of concepts. So far, so good. But then, chapter 2 instructed the reader to open up any one of a number of commercial assemblers for the Apple ][. My heart sank - I had just used up all my negotiating capital to get a $12 book, there's no way that Dad would go on to drop $200 on a commercial assembler, as well.

So, the book gathered dust on a shelf. Dad did work through a small number of the examples, using the Apple ]['s built-in monitor, the poor man's assembler toolchain.

I felt guilty about the promise I had made, and I kept the book as a reminder. As I mentioned, the Apple IIgs came along, and I learned Pascal, which introduced me to procedural programming, and I went off to college, and learned Scheme and LISP and C and C++ and CLU. Perhaps a few others, besides. 

Years later, like probably around 30 years after making that promise to work through the examples, I had experience with working with LinApple and a variety of other Apple ][ emulators, and I knew that there were disk images of various old pieces of Apple software available on the Internet, including some software that was actually legally available.

I dusted off the book, looked up the suggestions of commercial assemblers mentioned to build the samples, and discovered that Bob Sander-Cedarlof of S-C Software had made his S-C Assembler available for free, and so I was able to begin to make progress on my long-delayed promise.

I learned about the X, Y, and A registers, I learned about the Zero Page, I learned about the various flags that arithmetic operations would set. I learned a little bit of magic locations in memory. I wrote a sort routine that would organize literally dozens of pieces of data.

Yeah, this wasn't going to actually have practical benefits, but a promise is a promise, and I continued to plug through.

The Apple ][ used the Motorola 6502 CPU, which had support for addition, subtraction... branching... using 8-bit integers. As I recall, some of the addressing modes allowed you to use contiguous pairs of bytes to support 16-bit integer math. The hardware did not support multiplication, division, or floating point numbers. So, I wasn't going to have it easy if I wanted to write a 3d flight simulator or first person shooter. Not really what my goals were - I just needed to complete the book.

Well, except that I decided that I should build something of my own, based on what I had learned. And one of the programming go-tos (sigh) that I had gone back to over and over again was to write a Mandelbrot Set fractal renderer. I had done this in Pascal on the IIgs, C on the 286, and over and over again, as my own little proof to myself that I understood how various programming environments worked. In the years since, I've heard this referred to as a "coding kata".

So, pushing the (emulated) Apple ][ to render a Mandelbrot set, which requires complex algebra and looks best with lots of pixels, that was a challenge I felt was worthy of this journey.

I built multiplication of complex numbers, I wrote pixels to the screen, I got stuff sort of looking sort of right, but not quite, and debugging was a huge pain. So, I ported my assembly program back into Applesoft BASIC, and I was happy and sad to see that the BASIC program drew pictures that looked correct to me, while my assembly code was giving me a similar-looking blob on the screen, but not the recognizable bumblebee shape. Eventually, I managed to track down a flag that was being set that I didn't expect to be set, which was causing a conditional branch to happen when I didn't expect it. I rearranged the logic, and I had my assembly program drawing images to the screen, as I had imagined to begin with:

   

What you can see in that image is that I was drawing the image progressively - here, you can see every other row drawn, but initially, I drew widely-spaced pixels:

which is enough to tease the recognizable shape. Once that pass is done, I drew a lot more pixels horizontally:

Those look like solid horizontal lines, but I'll get back to that. Then, I filled in vertically:

And then I had one more pass filling in pixels horizontally:

wait, what? If you're unfamiliar with the Apple ]['s graphic screen, you'll wonder where all that white and orange came from. If you've spent time in the pixel trenches, you probably know that orange is accomplished by lighting up the odd columns of the second palette, blue is even columns of the second palette, green is odd columns of the first palette, and purple the even columns of the first palette. Because my progressive renderer was drawing only even columns for the first several passes, there was a lot of purple and a little bit of blue. No orange, no green, until later. Also, white was a result of lighting adjacent odd and even pixels. It's almost like it wasn't a 280 column display, but more like a 140 column display.

And so, tada:

 

Working to the level that I was shooting for. There's some color fringing, like the blue on the far left, the green on the edge of the orange field. But you know, that's fine. Also, I want to point out that the white circle actually looks like a circle, even though the Apple ][ did not have square pixels. The aspect ratio math wasn't hard. But kids these days, they don't even think about that sort of thing.

Earlier, I mentioned that I had an Applesoft implementation and an Assembly implementation - to my recollection, the Assembly version took me about 10x as long to write, and ran about 3x as fast. That doesn't seem like an especially fair trade. I consider, though, that I was pushing the mathematical capabilities (multiplication of fixed-point numbers on a 6502), which was going to be slow, no matter what. Performance was an important part of what set me on the road to learning Assembly, but by the time I had finished the book, even a fast program on a 64K 1MHz machine wasn't going to impress a lot of people. So, I considered myself done.

Giddy with my accomplishment, I printed out the various screenshots that you've seen up to this point. I took them to show off to Dad the next time I visited. He wasn't super impressed - I don't think he even remembered that day, three decades earlier, when I had committed myself to learning assembly. But he nodded and there was some small level of recognition that I had done something.

A related story, which I won't tell now, has to do with Dad and I collaborating on making a Pac Man clone on the Apple ][. Things went comically badly.