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!
I'm wondering if Some of the crashes were from the AI getting stuck somewhere in a RAM alley and blowing away some vital code in a memory address. They might have still had a missile or two after escaping from the game . . .
Posted by: Justin | October 10, 2008 at 06:44 AM
One of the funniest things on South Park was how they used the MCP from Tron as Moses.
I also wrote a Tron light cycle game, but mine was on the Commodore 64... I had way more colors to chose from (at the same time)
Posted by: ElevatedSteve | October 11, 2008 at 04:39 PM
could this glitch work with a Macintosh IIsi. I know the video shared the main system memory but I don't know the permissions it gives applications.
Posted by: Seth | October 11, 2008 at 10:48 PM
That takes me back a ways. Thanks for the story!
Posted by: Perri Nelson | October 24, 2008 at 05:20 PM
You could've certainly "watched" the AI driver by listing the memory addresses visited on the screen or providing a copy of the bike's movements on screen (use mod arithmetic to bound the copy to the visible screen), etc.
Posted by: Steve Clay | January 04, 2009 at 04:32 PM
Do you have the code lying around? It would be a lot of fun to run it in
emulation. Also, as PockyBum suggests, it would be fun to make a hack
so that when a player, human or AI, blasts through a border, the
framebuffer "tracks" them (see below).
Getting a bit more technical, it should only produce really surprising
results when the player goes through the top or bottom of the field, as
I imagine video RAM was successive scanlines concatenated together, so
going off the edge, say, on the right-hand side on line y would simply
wrap the player around to the left-hand side of the field on line y+1.
If the Apple was anything like the Atari, you could actually POKE to
shift the start of video RAM (change the mapping for the display in
memory-mapped RAM), and "follow" the player in his path of destruction,
above or below the playing field, by tracking his Y position and
adjusting the start of the framebuffer accordingly. (I believe games
like Goldrunner and Goldrunner II used a similar trick to provide
extremely fast scrolling over a playing field, sort of a smooth
page-flipping, but I could be talking out my arse)
Posted by: Kim | January 10, 2009 at 09:24 AM
Ah it's so awesome to hear such funny and amazing tales from the world of programming. And if one lives through them, they are every bit as memorable for one's whole life like the other great moments they have had.
Posted by: Abeer V. Dey | January 27, 2009 at 07:52 AM
shaun the pixel check program uses assembler code so it is likely the missiles run the same way and I'm sure they run open loop; it's just not that easy.
I love just thinking about how this would fail. AI blows hole in wall and runs out instantly its path finding reads the addresses accessible to it. this causes memory mapped IO to go crazy because not only is it reading the cell in front of it but likely 2 cells in front of that as well as the sides. then you have the path its leaving behind it, a constant stream of ones which a running program may interpret as an on state or part of a larger system causing more programs to go haywire. it would be like John Conway's Game of Life; programs madly expanding then fading out causing more reactions all the while. You have created the mother of all memory leaks.
Posted by: Quadrapod | August 20, 2009 at 02:33 AM
I'm surprised nobody mentioned the pushwall bug from Rise Of The Triad yet. "I'm FREEE!!"
Posted by: Kawa | September 23, 2009 at 09:21 AM
That's funny.. though instead of imagining what the AI players are doing, you could 'peek' at what it is they're looking at and draw that on a 'reserved' part of the screen.. like a top-down-radar view of each player that's offscreen. I'd love to see a video of that.
Posted by: Chris | October 27, 2009 at 11:57 AM
I love it! Even now i can see one of your bots firing missiles at key system data! Eat that kernel bit!
Posted by: daemon | October 27, 2009 at 01:29 PM
The LoseThos operating system, http://www.losethos.com , is a modern 64-bit PC operating system without protected memory, for just such purposes. It's for having fun programming and screwing around is fun and educational. It's 64-bit and supports multicores and is simple.
Posted by: Terrence Davis | January 09, 2011 at 11:31 PM
posts like this make me wish i could program
Posted by: jamie | January 10, 2011 at 08:22 AM
I wrote a Star Trek game back in Ye Daye on the TRS-80 and - due to a not dissimilar bug - accidentally fired a phaser shot straight down out of video RAM and into my source code. If you reacted before it got too much further and crashed, you could could LIST the source and see the phaser shot character recurring every 64 bytes down in the lines of BASIC. XD
Posted by: Solarbird | January 11, 2011 at 12:42 AM
Heh, nice article, reminds me of good old times :)
Prince of Persia for the PC had a similar 'bug', in some places you could fall through the wall to the sides. You'd end up in a weird, random place and basically fall forever until you crashed against a randomly laid trap, piece of wall or floor.
But the idea of an AI player crawling around memory is even more intruiging. In contrast to the player, they would probably survive there.
Posted by: Wladimir | January 11, 2011 at 07:53 AM
I bet the most spectacular crashes happened when the bot fired a missile at what it thought was an obstacle.
Posted by: qole | July 02, 2013 at 11:45 PM
We played the hell out of this game, when we were kids. And when wee saw the Tron movie (with a bit of a delay), we tought that it was inspired by the game.
It's nice to see it again, thanks for making it, thanks for posting!
Posted by: Zed | July 07, 2013 at 04:59 PM
Please put the source for this game on github! :)
Posted by: Bryan | July 15, 2013 at 05:10 PM
@Bryan - I wish I had an image of my IIgs hard drive to do that!
Posted by: Daniel Wellman | July 22, 2013 at 10:49 AM
I loved Tron and very much loved the Apple IIGS. It actually took 6 years for the Mac (black & white in 1984) to catch up to the color Apple IIGS, and that "catch up" didn't include a MIDI synthesizer. :)
Posted by: Roger Wagner | March 12, 2015 at 10:49 AM
@Roger Wagner - Thank you for visiting and commenting! Reading "Apple IIGS Assembly Language for Beginners" helped me learn to write in assembly language - which helped me write this program! Thank you for writing it and all your contributions to the Apple II line!
Posted by: Daniel Wellman | March 17, 2015 at 07:37 PM