Robotron and OOP
Many years back, joe holt and I pulled the ROMs from a
Robotron machine that I bought. Joe write a disassembler for 6809 and we started poring over the assembly language to try to make head or tail of its operation using the schematics as a guide for hardware. At one point, I even called Eugene Jarvis, the author, to get a couple hints.
From this, we figured out the operational model. I don't have the specific details in my head, but I recall enough to present it. The interesting thing about Robotron is that the underlying game engine is object-oriented, but because it was written in straight assembly language, they could do some pretty fabulous things to make it work.
Robotron had a linked list of processes (Jarvis' term). Each process was used to perform a simple task in the game. In addition, there was a display list of objects that were to be drawn. I'm a little hazy in my memory as to whether or not the display list was the same as the process list - it could be without any loss of generality.
The hardware generated a clock tick and when that hit, each process was checked for whether or not it needed to be run, and if so, it was run. If this was written in C#, it would look something like this:
public class ListItem {
private object _next = null;
public object Next {
get { return _next; }
set { _next = value; }
}
}
public abstract class Process : ListItem {
private int _nextTime;
public Process() { Reset(); }
public int NextTime {
get { return _nextTime; }
set { _nextTime = value; }
}
public bool Tick() { return --_nextTime <= 0; }
public abstract bool Run();
public abstract void Reset();
}Now this is not precisely ideal OO design since the is-a and has-a relationships aren't right. A list should have list items that have processes. A process should not be a list item, but that's what the design was. You'll see why in a bit.
public void OnTick() {
object prev = null;
object curr = ProcessList; // some property
while (curr != null) {
Process p = (Process)curr;
// if the process is ready to run, run it
if (p.Tick()) {
// if run returns true, reset and move on
if (p.Run()) {
p.Reset();
prev = curr;
curr = p.Next;
}
else {
// remove it from the process list
object next = p.Next;
RemoveFromList(ProcessList, prev, curr);
curr = next;
}
}
else { // just move on
prev = curr;
curr = p.Next;
}
}
}As I said, this is not ideal oop design, but bear with me. At this point, to make things that operate in the game on a regular basis, just subclass from Process and insert instances into the process list.
The main game loop will be something like:
public void MainLoop()
{
WaitForTimerInterrupt();
OnTick();
}This design is nice in a few respects. When you are starting a new level, you populate the process list with level processes and off you go. When a level is complete, clear the process list. When it's time to do a cut scene, populate the list with a cut scene process, etc. One process that existed in the Williams games was a process to rotate colors in the hardware colormap to give the slick, flashy look to their games.
Obviously, they didn't have C#. In fact, I doubt there was even a C compiler for the 6809 when the game was written.
So how do you get this nice functionality without the syntactic sugar? Like this:
typedef struct t_ListItem {
struct t_listItem *Next;
unsigned char Size, ID;
} t_ListItem;This is a C struct that represents a linked list item. Now, if I want to make any other struct into a list item, all I need to do is put that struct as the first element in my struct:
typedef struct t_Process {
t_ListItem ListItem; /* must be first */
short NextTime;
f_RunProcPtr RunProc;
f_ResetProcPtr ResetProc;
} t_Process;a t_Process contains a t_ListItem, which means that if I cast a pointer to a t_Process as a t_ListItem, then I can treat it just like a t_ListItem and do it safely.
f_Run and f_Reset are defined like this:
typedef bool (*f_RunProcPtr)();
typedef void (*f_ResetProcPtr)();
So the C implementation of Tick() will look like this:
bool Tick(t_Process *p)
{
return --(p->NextTime) <= 0;
}
And to run a process:
bool RunProcess(t_Process *p)
{
return *(p->RunProc)();
}The beauty of doing the code this way (with the t_ListItem), is that there will only ever be one instance of list manipulation code and it will run properly on anything that has a t_ListItem as its first element. This means that your executable will be a whole lot smaller.
If you noticed, I snuck in a few extra things in the list item - a byte for a size and a byte for an ID. This lets me look at any item and find out how many bytes it is (up to 255) and attach an ID to it. In a low-level debugger, I can look at those two bytes and pretty much know what kind of item I'm looking at right away. As defined, this is really bad for C since you can always have structs that are way bigger than 255 bytes and you may have more than 255 object types, but remember, we're talking about a video game with a tiny amount of RAM.
Robotron didn't have a version of malloc(), but it did do dynamic allocation. At boot time, sections of memory were partitioned into "8 byte structs", "12 byte structs" etc. Then since each struct effectively contained an t_listItem, each newly partitioned block was linked to the next. This means that if you wanted to allocate a new 8-byte block, you'd pull the first item off the 8 byte block list. To free a 16 byte block, you stick it back on the 16 byte block list, and because the size is in the struct, you can tell where it needs to go. This means that allocation and deallocation are wicked fast.
Assembly doesn't really have the notion of structs, just byte offsets. A t_ListItem was really this:
ListNext EQU 0 ; the symbol 'Next' equates to 0 (offset 0)
ItemSize EQU 2 ; ListNext is 2 bytes (points are 16 bit on 6809)
ItemID EQU 3 ;
So a ListItem is 4 bytes.
The bad news is that I lied about the definitions of Run and Reset. Run actually looks like this in a C definition:
typedef bool (*f_RunProcPtr)(t_Process p);
and there is no Reset() - that gets done in Run().
So the offset of the next run time would look like this:
NextTime EQU 4 ; the next time to run
RunProc EQU 6 ;
Tick would look like this in assembly:
Tick PULS Y ; get return address in Y
PULS X ; get process pointer in X
DEC NextTime,X ; decrement the next time, sets condition codes
JMP [Y] ; return
OnTick
... ; set up code omitted - Y points to process
LDY CurrProc
PSHS Y
JSR Tick
BCC .1 ; carry clear - no execution
LDY CurrProc ; refetch current process
JSR [RunProc,Y] ; call its execute
BEQ RemoveCurrProc ; remove the process on false
.1 LDY CurrProc ; refetch currproc
LDY ListNext,Y ; get next
STY CurrProc ; store it om current process
... ; etc
Note that unlike typical C implementations, this code consumes its own arguments.
Now, I can tell you right now that this isn't really what it does - Tick is implemented inline in the code that runs the process list (this is not actual Robotron code - I'm reimplementing it from memory). In this code, Y is the curr pointer and X is the previous. The RunProc not only manages the reset, it manages removing the item from the process list as well. All routines follow a strict do-no-evil policy - that is all routines enter and leave with the registers intact, except for the condition codes.
RunProcesses
PSHS X,Y ; save x and Y
LDY ProcessList ; get the list head in y
BEQ .4 ; exit on null
LDX #0 ; clear x (prev)
.1 DEC NextTime,Y ; drop the tick count
BCC .2 ; still > 0? continue
JSR [RunProc,Y] ; run the process
BNE .3 ; on non-zero, the proc was removed
.2 TFR Y,X ; move curr to prev
.3 LDY ListNext,Y ; get the next
BNE .1 ; on non-null, go back
.4 PULS X,Y ; restore X and Y
RTS
So why is this all notable? In 13 instructions or roughly 23 bytes, we have the core of a non-preemptive multitasking operating system. That's the same amount of memory to hold the phrase, "Eugene P. Jarvis rocks!" in ASCII.
Now, nobody codes like this for any kind of significant applications. It takes just too dang long. And then you have to deal with maintenance and so on. Robotron is a different playing field, though. The machine had a 64K address space, of which a precious 24K was RAM and 32K was ROM (I know, 24K + 32K > 64K - they used some clever tricks to make video RAM write-only and layered ROM over the top of that). In that environment, you can afford to code like you own every single byte in the machine because you know what it does.
Nonetheless, I still think it's important to keep an eye on the past as we move into the future. After all, many embedded systems (for mice, keyboards, disk/flash drives and so on use processors that are on par with the one in Robotron. Some day you might be coding for one of those.