Real Life Tron on an Apple IIgs

One of my favorite movies as a kid was Tron, the early 1980's film about a computer programmer who gets “digitized” and sucked into a computer world inhabited by personified computer programs.  In the film, the protagonist joins a group of resistant programs in an effort to take down the oppressive Master Control Program (MCP), a rogue piece of software which had evolved, acquired a thirst for power, and was attempting to take over the Pentagon's computer systems.

In one of the most exciting scenes in the film, the hero programs race in light cycles, which were two-wheeled motorcycle-like vehicles that left walls in their wake.  One of the protagonists forced an enemy cycle to crash into the arena's wall, leaving a gaping hole.  The heroes dispatched their opponents and escaped through the hole to freedom – the first step on their way to take down the MCP.

When I watched that movie, I had no idea that I would unwittingly recreate the Tron world years later, rogue programs and all, with an Apple IIgs computer.

Here's how it happened: When I first learned to program, I decided to create a version of the Tron light cycles game.  My friend Marco Busse and I programmed it on an Apple IIgs using ORCA/Pascal and 65816 assembly language.  During play, the screen background was solid black with a white border, with one color line representing each player.  We displayed the game score in a horizontal strip at the bottom of the screen.  It wasn't the most graphically advanced program, but it was simple and fun.  It looked something like this:

The game supported up to four players – that is, if they scrunched up close together on the same keyboard.  It was clumsy, but it worked.  We rarely had enough people in the same place to play as all four cycles, so Marco eventually added computer-controlled players that could put up a reasonable fight.

The Arms Race

At this point, the game was a lot of fun already, but we wanted to experiment. We added missiles in order to give players a second chance to blow their way out of an impending crash.  As Marco described it years later, “Both the AI and the humans had three missiles they could use during the course of the game. When a missile hit a wall, it would create a mini 'explosion' that would erase the color on the background back to black as it faded out – thereby eliminating sections of the trail left by previous cycles.”

Soon we had players and computers firing missiles to shoot their way out of tight situations. Nonetheless, Tron purists may scoff, since the movie programs didn't have such luxuries as missiles to get them out of a bind.

The Escape

Like all accidents of a bizarre and unusual nature, this one was unexpected.

One day, when Marco and I were playing against two computer opponents, we forced one of the AI cycles to trap itself between its own walls and the bottom game border.  Sensing an impending crash, it fired a missile, just like it always did whenever it was trapped.  But this time was different – instead of firing at another trail, it fired at the game border, which looked like any other light cycle trail as far as the computer was concerned.  The missile impacted with the border, leaving a cycle-sized hole, and the computer promptly took the exit and left the main playing field.  Puzzled, we watched as the cycle drove through the scoring display at the bottom of the screen.  It easily avoided the score digits and then drove off the screen altogether.

Shortly after, the system crashed.

Our minds reeled as we tried to understand what we had just seen.  The computer had found a way to get out of the game.  When a cycle left the game screen, it escaped into computer memory – just like in the movie.

Our jaws dropped when we realized what had happened.  

So what did we do after discovering a defect in our program that could methodically crash the entire system?

We did it again.  First we tried to blow our own way out of the game screen.  Then we forced the computer to escape – repeatedly.  Each time we were rewarded with fantastic crashes. Sometimes the disk drive light would twitch as the drive groaned into unending service. Other times, the screen would change to nonsensical text, or the speaker emitted a shriek or a low drone.  Sometimes all of these things happened at once, leaving the computer in a state of total meltdown.

So why did this happen?  To understand the answer, let's peek into the architecture of the Apple IIgs computer.

(Un)Protected Memory

The Apple IIgs operating system didn't have protected memory, a feature present in most modern operating systems that assigns programs memory space and restricts them from accessing memory outside that space.  The upshot was that an Apple IIgs program could read or write anywhere it wanted (except it couldn't write to ROM – Read-Only Memory).  The IIgs used memory-mapped I/O to access devices like the disk drive, which meant that you could activate the disk drive by reading from a certain memory location.  Graphics programs took advantage of this design by reading and writing directly to the screen memory. 

The game used one of the IIgs's Super Hi-Res modes; it ran at a glorious 320x200 pixels with a palette of 16 colors.  To choose the palette colors, the programmer mapped sixteen entries (numbered 0 – 15 or $0 – F in hexadecimal) to 12-bit color values. You could read and write colors directly to the video RAM to paint the screen, just like you could read and write in program data memory.

Crash-detection algorithm

The game took advantage of this fact and implemented crash detection by reading directly from video RAM.  For each light cycle, the game computed its next position based upon its current heading and read that pixel from video memory.  If the position was empty, represented by a black pixel (palette entry $0), the player was safe and the game continued.   But if the position wasn't empty, then the player had collided with a either a light cycle wall or the white game border (palette entry 15 or $F).  Here's an example:

This example shows the upper-left corner of the screen, with color $F representing the white game border and color entry $1 representing player one's green cycle.  Here the player is moving left as indicated by the arrow, which means the next space is empty, or color $0.  If the player continued in this direction for one more move, they would collide with the wall (color $F) and crash.

Going off the grid

The algorithm to determine which pixel to check next used some fast assembler math to calculate a memory address – either one pixel above, below, to the left, or to the right of the current pixel.  But since any given pixel on the screen was really just a memory address, the algorithm simply calculated a new memory location to read.  So when the light cycle left the screen, the game happily calculated the next location in system memory to check for a wall crash.  This meant that the cycle was now cruising through system RAM, wantonly turning on bits and “crashing” into memory. 

Writing to random locations in system memory isn't generally a wise design practice. Unsurprisingly, the game would generate spectacular crashes as a result.  A human player would be driving blind and usually crash right away, limiting the scope of system casualties.  The AI opponents had no such weakness.  The computer would scan immediately in front, to the left, and to the right of its position to determine if it was about to hit a wall and change directions accordingly.  So as far as the computer was concerned, system memory looked no different than screen memory.  As Marco described it,

We can only speculate what it started doing once it left screen memory, since it obviously would look to find a way to continue going in a direction that was occupied by 0’s. If it became blocked and ran into a “wall” of numbers, it would die. In those spectacular crashes though, it would sometimes be running around very much “alive” until at some point it either overwrote some code being executed with a trail that didn’t make sense, or it would access some memory mapped device that would then cause a crash.  But it wasn’t immediate – the AI ran around for a little while out there before it crashed the system.

In the end, we had not only recreated the light cycle game from the movie, but recreated the escape as well.  And just like in the movie, the escape had great consequences.

Nowadays, with operating systems that have protected memory, this sort of thing wouldn't happen so easily.  Still, it makes me wonder if there are Tron-like programs out there trying to break free from their “protected spaces” — all in an effort to stop rogue AI code from taking over the Pentagon.

I guess we'll have to wait for that digitizer to get invented in order to find out.

--

Thanks to Marco Busse, Jamie Lendino, Jonathan Stark, Joe Leo, and Ariel Valentin for their tech edits and feedback.  Crashed Apple II computer image from Mike's Hobby Home - Apple II Repair Tips.

Updated 10/8/2008 10:29 AM ET - Fixed CPU model typo, thank you Reddit readers!

Comments

[Ariel Valentin]

This was fun! I think I am going to go back now and hack Leisure Suit Larry or Police Quest!

[Jesse Farmer]

Wow, that's awesome. But those poor guys in the light cycles...

[ken]

"The game supported up to four players – that is, if they scrunched up close together on the same keyboard. It was clumsy, but it worked."

You just need another keyboard. One of the nice things about ADB was that you could just chain another keyboard, and it would work -- kind of like a super-simplified USB, but with the same connector on both ends.

I remember borrowing a iigs keyboard to play Dueltris comfortably. iigs keyboards even had stretchy cables, unlike USB keyboards of today, so you could sit just about anywhere. Those were the days.

[Bri]

Hey there. Great story! A very interesting read with an intelligent explanation. I did some BASIC programming on an old IIg myself. I also seem to recall the PEEK and POKE commands for ATARI BASIC, which were pretty permissive.

[Razee Marikar]

He he... So these kinds of movies are not baseless after all!!!

[Avery]

The game supported up to four players – that is, if they scrunched up close together on the same keyboard. It was clumsy, but it worked.

Wow, you gave me flashbacks to when I wrote a Megazeux game specifically for me and my two little brothers. I would add silly things like missiles just as you did. Unfortunately I lost that game in a move...

[Elmer]

Makes me want to be a little boy again, watching Tron and playing 8-bit computer games :) Great story!

[www.codingthewheel.com]

One of the few times I've laughed out loud while reading a development story. Great retro stuff. Too bad we have to deal with those pesky protected-mode operating systems these days, although memory overwrites can still produce strange and wonderful bugs.

[Tom]

That was a great read, I now have this mental image of a tiny light bike cruising through the ram.

[dequeued]

Ah, I used to do something very similar, when I would write games in QuickBASIC.
Of course I didn't use much assembler, but, as a young programmer, I found it much easier to incorporate the framebuffer into the very logic of my program, like what was done here.

Of course, I quickly realized the flaws with that.
Any time I wanted to add a graphical effect I had to completely rewrite my collision detection!

[Khurrum]

This was one of the most entertaining and informative programming related articles that I have ever read.

[Phill]

Sir, I award thee several internets.

[Tim Lesher]

What a great story.

Thanks for bringing back awesome memories, and for helping me remember why I got into this crazy industry in the first place.

[PockyBum522]

Makes me want to write a display for when the AI goes outside of the screen. It would be fun to watch.

[Anson]

A magnificent tale!

[GTAStud.com]

That's amazing! Most likely I would have just blown it off as a bug in the code. But if you change your perspective, well it really a mind bender!!!

That's a great take on such a simple bug. I just wonder how long a bike could last before it imploded or did some real damage to the system...

[Alex]

See, that's what happens when you don't use the MVC paradigm! :p

[Mark Richards]

Ironically, back when I was learning to program, I wrote a version of Tetris with a similar problem. If you turned a piece right before it hit the bottom of the board, the piece would crash through and keep falling- right on down through memory. I use to tell people I had made the pieces too heavy and that's why they were breaking through the floor :)

[Martyn]

Vast buckets of awesomesauce. Cracking tale, well told. I commend thee.

[Jak]

Hey thanks for a great story from the good old days.

I just found this on Reddit, came here to read, and then I see Marco Busse mentioned. I used to work with him at Tiburon. Great guy. Please tell him I said hello next time you talk to him.

[Devin]

HA! Great story! I put it up on CrunchGear.com.

[Dave]

One thing I don't understand is how the missile blasted a hole in the wall, you say:
"When a missile hit a wall, it would create a mini 'explosion' that would erase the color on the background back to black as it faded out – thereby eliminating sections of the trail left by previous cycles.”"

So what caused the AI to be able to make a hole in the wall? Could you recreate it as a human?

[Daniel Wellman]

Thank you all for your kind feedback and distributing this article, it was fun to reminisce.

@ken Yes, absolutely - the ADB was a lifesaver. We did end up plugging two keyboards together which made it more comfortable to have the full four (human) players.

@Jak I'll pass on your hello!

@Dave Both the human and computer player could fire a missile at any time (assuming they had some left). Missiles always created a hole on impact; what was surprising was when the computer decided to fire at the game border. We hadn't even considered this possibility.

[ace]

This reminds me of playing the race car that played on Intellivision. You could drive off-course, between the houses, and as long as you didn't hit a tree you could keep going.

The cartridges were only 4K or so, so there wasn't a million ways to pack in the detail, but you could go exploring and find little mini-racecourses and other hidden details off-road. The world actually 'wrapped', so if you went far enough 'east' you re-entered from the 'west side.

There were even pathways, stitch points where the blocks met, where you could drive unmolested due east or west, but the developers had obviously discovered these, and they added one tree in the stitches that you had to navigate around.

Game hacking - the early days - what a thrill.

Someday, I'll remember some ZX81 magic and write back.

Best,
ACE
Roberts Creek, BC

[Shaun]

I suppose it would be easy to cheat then... just blast a hole through the wall, and circle around the outside.

Of course, the simplest way to stop it from happening would be to make the border invulnerable to missile attacks
(my limited programming skills at work)
if memory(wall) = "f" then missile = 0
But who would want to stop such an awesome little bug =D