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.

Going from a grayscale image to an image with transparency in GIMP 2.10.8 on Linux

I've searched for this in a bunch of places, and I've found a technique that works for me - I think my requirements are a little different from maybe what other people are looking for, so I'm writing this up for my own notes, and maybe somebody else can benefit.

Problem Statement:

I've got some black-on-white grayscale art (possibly pen-and-ink line art) that I'd like to turn into a layer of a single color, but with the grayscale value in the alpha channel.

If I was writing a Python script using PIL, I'd expect the incoming image to be a grayscale format, with 8 bits of lightness information (0 = black, 255 = white), no alpha channel, and the output image is RGBA, where every pixel is (0, 0, 0, A) where A is 255-L, L being the lightness value of the input image.

Why not make a Python script to do this? It sounds like 5 lines of Python or less, right?

Yeah, maybe.

Still, this is how I do it in GIMP. Maybe I want to do additional processing in GIMP, and having it already open might be handy. Or something.

Step 1

Ok, I'm starting with my image loaded in GIMP. I'm not going to help you get to this point.

Optionally, crop the image - for this image, I tried "Image > Crop To Content", which didn't get as tight on the left hand side as I expected, so I followed up by using the rectangular selection box from the toolbar, selected a generous box, and manually pulled in the left side to where I wanted it. And then "Image > Crop To Selection".

I suppose you could do a bunch of other stuff here, too, like resizing the image. Live your best life.

Step 2

Duplicate the layer

This can be done by right clicking on the layer in the Layers panel.

Step 3

Invert the layer. I had best results with "Colors > Linear Invert". You could try the normal invert, I suppose.

Step 4

Right click on the new layer, select "Add Layer Mask"

Select the Grayscale copy of layer. (Why is it grayed out AND selected?)

Step 5

With the paint bucket tool, fill the layer (not the mask) with black, using "Fill whole selection", making sure your selection is all or none of the image.

Step 6

No, there's no step 6. You're done. Make a sweatshirt or whatever it is that you were going to do with your grayscale Half-Elk Fighter-Master. Or whatever.

Making a G+ Sendoff

I'm in the last few hours, as I write this, of Google+, the community-oriented social media site. Google will be (will have, by the time you probably read this) closing it down. The site never got a huge following, though there were people who really enjoyed using it.

I wanted to make a send-off in one way or another. I was thinking about using my AxiDraw pen plotter machine to draw a picture to G+, but that didn't click for me. And then I thought that it'd be fun to have an Apple ][ welcome G+ into the afterlife, a place where systems go after they're shut down for good.

First, I started up LinApple, an emulator of an Apple //e, and wrote a test program into it that would print some text to the screen, one character at a time, reminiscent of reading chat on an old BBS system at maybe 1200 baud.

Aside: years ago, I bought a 1200 baud modem for my family's Apple IIgs, and Dad was suspicious of what purpose I'd put it to. I pointed out that I could dial in to the county library and reserve books. Also, there were BBS systems where I could send messages and play games, but I knew that those purposes would be less compelling to Dad. So, Dad, I bought that modem so that I could remember using it and remember using Google+ and see the similarities. Probably still not compelling.

Listing 1

As you can see here, I first clear the screen and set the cursor to the upper left corner of the screen (Line 10), then I take two lines of text, assign them to the string variable A$ and call out to a subroutine. (Lines 20-50). That subroutine iterates through the line, printing one character at a time, then calling an additional subroutine (Lines 1000-1020), which simply spins, slowing down the program, making the text scroll onto the screen at a readable rate. (Slowdown from lines 2000 to 2020).

Interestingly, there's a bug in this code - the subroutine at 2000 doesn't return explicitly. I guess that it reaches the end of memory, knows that it needs to return, and goes back to line 1030.

At 1030, we continue on to the next character in the string, then at 1040, we print nothing other than a newline, terminating our printing to that row of the screen, automagically moving to the left and down one row. Later, we'll see scrolling, as well. All handled by the system. BASIC had a lot going on that I took for granted as a kid.

So, that structure seemed to work. I set out to write a blort of text that would be long enough to be fitting, short enough to be readable. I knew I didn't want to do text editing in my emulated Apple, so I copied this code out of the emulator and onto my Linux machine. Well, it was already ON my Linux machine, just in a disk image that the Apple emulator could read, but my Linux machine couldn't usefully edit.

So, I used AppleCommander to "export" the BASIC program to a text file, which I saved as reference.

The text file I wrote in emacs, because a) of course I did, and b) emacs is pretty good for editing fixed-width text files, which is the sort of thing that I wanted. It's got word wrapping, which made my life easier, too.

So, I wrote a page and a half or so of text, saved that out as a text file.

This next bit is perhaps unnecessary, but I wrote a Python script (again, because of course I did) that read the lines of my text file and wrote out a BASIC program that would print those lines to the screen. Sort of a compiler of sorts, that compiled a text file to BASIC.

The structure of the output file was the same as my test BASIC file (Listing 1), I just had a lot more calls to the line printing subroutine; one each for each line in the text file.

Listing 2

With this, you can see a few things. For one, you can see that emacs is happier providing syntax highlighting for Python than it was for BASIC. Maybe I don't have the Applesoft BASIC major mode installed. The structure is pretty simple - read all the source text file into memory, write a preamble, write out instructions to handle each line, and then write the closing matter, particularly the subroutines.

The header is super straightforward:

Listing 3

All it does is use the HOME command to move to the top left of the screen and clear it. You'll see that I also increment the line number by a healthy 10 numbers and return that.

Kids these days with their IDEs and their structured programming languages, they don't appreciate the value of leaving a healthy amount of space between line numbers, so that you could go back and add in extra commands if you needed to later.

Listing 4

This simply takes a provided string of text (which I had read from my text file) and generate a line of BASIC that assigns that string into the A$ string variable, then on the same line (something done more in BASIC than any other language I've ever seen) invoked the print subroutine. Again, I increment the line number and return.

Listing 5

And that wraps up the BASIC output, and also the Python script. I just write out the code to print one character at a time, placing that subroutine at line 5000, because that seemed like a safe space. Just to be sure, though, I assert that my text printing body of the code hasn't pushed us past 5000 before we got here. Similarly, I have the delay subroutine at 6000.

So, I ran the program, and ran into a few bugs - I had forgotten the semicolon on "PRINT MID$(A$,I,1);" - the semicolon means "print this string, but do not move the cursor afterwards", which achieves the teletype incremental progress. I had also forgotten the carriage-return (again, the kids don't remember typing on a typewriter where there was a physical lever that would RETURN the physical cylinder (the CARRIAGE) such that the typewriter would go on from the left margin.

I fixed those things up, tweaked the text, and output my WELCOME.BAS output file.

I struggled a bit with AppleCommander, trying to get the BASIC code back onto the disk image that the emulator would use. The tricky bit was that Applesoft BASIC is stored on floppies in a "tokenized" format, not in plain text. This takes one step off the job of the interpreter at runtime, and it makes it more efficient to save BASIC programs to a 140k floppy.

So, I needed to figure out a way to take my plain-text WELCOME.BAS file and tokenize it, and store the tokenized output onto the disk image.

Turns out, AppleCommander has a command-line version with a -bas option that does exactly this. Almost exactly this. It isn't perfect about carriage return / line feed combos, so I tinkered with that, and eventually got my WELCOME.BAS onto a disk image.

I actually had some shenanigans with getting it onto the disk image that I wanted to use, which took some rebooting of my emulator, but in the end, I got the program running as expected.

I fiddled with the display options to get the green monochrome monitor effect, and set out to record the results. The first recording I did was using byzanz, a recorder that outputs an animated GIF. This has been effective enough for many of my previous projects, so I fired it up, and got pretty good results. I loaded the output into GIMP, and cropped the image to the size I wanted, and this was the outcome:

Figure 1 - Animated GIF

Good enough for a post to Google+. But I'm never sure if an animated GIF is really going to make it all the way to the viewer without being resampled, reprocessed, and ultimately de-animated. So, maybe that's not good enough. Also, somehow, there was a glitch of random white rectangles. I don't know what that was.

So, I used SimpleScreenRecorder to capture a movie (MPEG?), suitable for upload to YouTube, in case a GIF (appropriately enough, super old technology) doesn't work into the future. SimpleScreenRecorder has a lot of good options, including allowing me to tweak my recording window, turn off recording the mouse, turn off sound, all good things for this project. And, boom, I uploaded it to YouTube, and by the time that I had filled in the metadata, the upload and processing were complete, and my little bit of remembrance was ready to go live.

Figure 2 - Video on YouTube

At this point, I used the following technologies in this project:

• LinApple
• Ubuntu Linux
• emacs
• Python 2.7
• Applesoft BASIC
• AppleCommander 1.5.0 (GUI and command-line)
• GIMP
• byzanz
• simple screen recorder
• Google+
• YouTube
• Blogger

Seems like a lot, and a big part of writing this blog post was to capture the workflow in case anybody (mostly, my later self) could re-use a part of that flow for later projects.

Because I am putting myself to the fullest possible use, which is all I think that any conscious entity can ever hope to do.

Farewell, G+, we will miss you.

Run/Walk: Kirkland Shamrock 5k

The weather forecast was highs in the 60s, but that doesn't equate to temperatures during the event.

Finish photo

Another year, another St. Patrick's Day themed run. This one took us from the marina park, up the hill to the cross-Kirkland connector trail, and then down through residential roads. The hills were hilly, the temperatures were comfortable, and the roads were dry.

If you can make out a time on the clock on the finish photo, it would say something over an hour, which I want to disclaim, as we were in the second half of the third wave, so there was well over 10 minutes on the clock before we got started. 50 minutes is still not a lightning-fast time, but for a casual jog/stroll, it's fine. I'm content, if not proud.

Numberphile's "Epic Circles" easy bit

So, I was watching a little bit of Numberphile on YouTube, like you do before you get up on a lazy Sunday.

I was watching the "Epic Circles" video which talks about finding the diameter (or radius) of successive circles in a "Pappus Chain". I've played around in this space, playing with circle inversions, flashing back to a particularly bad math professor for my complex analysis class, but it's all still pretty cool stuff.

22 minutes and 20 seconds into the video, Simon Pampena has something like this that he's working with:

And he makes the claim that the smaller circle has a quarter the radius of the larger circle, so R/4 = n in my diagram. I've clearly redrawn the diagram, and am using R to mean something different than he is, and I've introduced n, which shouldn't be too scary. In any case, what we've got is a square of side R, with a quarter circle of radius R with its center at one corner, and a half circle of radius n tangent to the quarter circle, such that the center of the half circle is on the square and the top of the half circle hits that upper right hand corner. The diagram isn't perfect, but it's close.

In the video, Simon just zips past the claim that R/4 = n and it threw me for a bit - where did that come from? So, I took out some graph paper and doodled a bit. Let's first rename things again, making this into a unit square:

In this picture, I've drawn a line connecting the centers of the two circles. You'll see it goes through the point of tangency. (That's obvious, right?)

So, the radius of the large circle is now 1, and I've renamed the radius of the small circle x, just to make things prettier later on.

One thing I thought about halfway through working it out as I describe below is that maybe there was some well-known relationship going on here, and I did notice this:

That is, if we scale up the square to side length 4, we're asserting that the little circle is now a unit circle, and that makes the red diagonal the hypotenuse of a 3:4:5 right triangle. Ok, that's verifying the claim, but that's not really what I wanted - I wanted to derive x from the previous diagram. And now it occrus to me that x in this diagram is scaled up from x in the previous diagram. Don't get confused, this was a tangent. Sigh, math pun.

Ok, so going back to the second diagram, we have that same right triangle which has the red line as a hypotenuse. The length of the hypotenuse is:

hypotenuse = 1 + x

because it's the sum of the two radii of the circles, 1 and x. The height of the triangle is

height = x - 1

because the height of the square is the radius of the big circle, 1, less the radius of the small circle, x. And the width of the triangle, let's not always see the same hands, is

width = 1

because we said so.

And here's yet another picture of that:

We're nearly done now. All we have to do is hit that triangle with our Pythagoras hammer and we get:

hypotenuse ^ 2 = width ^ 2 + height ^ 2

(1+x) ^ 2 = 1 ^ 2 + (1 - x) ^ 2

1 + 2x + x^2 = 1 + 1 - 2x + x^2

And then we cancel and rearrange. I have to admit that it took me a few tries (I claim it's because I still had that lazy Sunday morning brain on), but if you're careful, you cancel out the x^2 terms, pull the -2x over to the left, pull a one from left to right, and get:

4x = 1

and so

x = 1/4

Which is what we believed all along; the small circle is 1/4 the radius of the big circle, and math works, and I can go back to bed.

GDC 2017 Part II : Main Conference Notes

Eesh, I've found this half-written post languishing for practically 2 years now. I could go through my notes and try to finish the post, but that's not going to happen. And maybe the notes are of some use in the state they're in.

Posting This for a Friend

S. John Ross is conducting an experiment of sorts, hosting a document in the cloud, but not in the way that I do when I upload a thing to Amazon. Instead, he sent out copies to folks to host on their own personal website, with the hope that other people would host it, and so on and so on. (And they tell two friends....)

So, if you want to read about Medieval Demographics Made Easy, you've come to (one of many of) the right place(s).

It's late Medieval, it's European, so it hits at what a lot of straight-from-the-box fantasy is going for, but you can adjust if your needs are different.


Share and Enjoy.