Retro Data Structures

One of the more fun things I do with my spare time is to play around with old computers. Specifically, I enjoy my Atari 800. I recently started thinking about a small game to write on the machine, something with a small map, which you can explore. Think Zork, on a very, very limited scale. This is mostly an exercise for me to see if I could pull this off in Atari BASIC.

If you were to make, say a 3×3 grid with a bunch of data attached to it, without getting all Object Oriented, you might choose simple data structure such as a 2-dimensional array, to retrieve data associated with your particular x,y coordinates on the map. A graphical representation of this data might look like this:

       1                2              3
 1 The start       A treasure!     A river.
 2 A monster!      Inscribed Rock  The wizard.
 3 A forest.       A bird.         Home

Atari BASIC, has three basic data types, number, character, and boolean. It also has arrays, you can make an array of numbers which is a standard thing, even today, or an array of letters. You may be tempted to call this a string, and it is referred to as such, but if you think of strings in Atari BASIC as character arrays, you’re life starts getting easier. You can also make a mufti-dimensional array of numbers. A think that you absolutely cannot do, however, is make a mufti-dimensional character array, a matrix of strings if you will, at least not in a basic straight forward way. This limitation hit me pretty hard. Living in the modern age, I’m used to slamming together data-types in a multitude of different structures, without worrying too much about it.

So, given this limitation, how do you get all that string data into a data structure that you can reference by some sort of position? One place where Atari BASIC helps us out is that I can reference positions in strings and substrings quite easily, which turns out to be the ugly key we need.

Say, I want an array to hold 3 things. myarray$=”Mary Bob I really like dogs, they are my favorite.” If I wanted to get the word “Bob” out of this, I’d call for myarray$(6,9). Mary would be myarray$(1,4), the sentence would be myarray$(9,51). The issue of course is that all the lengths are irregular. I can’t simply retrieve the nth element without knowing it’s position in the larger string. But, what if we make the string lengths regular? First determine what the longest string you’re going to allow is. In this case the sentence about dogs is 42 characters. Then, multiple, by the number of elements you’ll be holding. 3*42=126, so declare a string 126 characters long. Something like the following BASIC code:

10 ELEM=3
20 MAXLEN=42
30 DIM MYARRAY$(ELEM*MAXLEN)

Now, you can reference the different elements by using MAXLEN as a multiplier to get the proper positions. Bob would be MYARRAY$(43,84), or MYARRAY$(MAXLEN,MAXLEN*2-1)
Mary, would be (1,MAXLEN-1). We can wrap the whole idea in a subroutine (No functions here kids!) make the positional calculations:

40 REM GET THE 2nd ELEMENT
50 GET=2
60 GOSUB 100
100 REM ELEMENT RETRIEVAL SUBROUTINE
110 START=GET*MAXLEN-MAXLEN+1
120 END=START+MAXLEN-1
130 PRINT MYARRAY$(START,END)
140 RETURN

The interesting thing to me about this approach is how incredibly space inefficient it is, especially noticeable when you’re working on a machine with 48K of memory. It’s also an good reminder about the kind of stuff that has to go on under the covers in our nice modern languages to make them so comfortable to work with.

Remember though, I’m interested in a matrix of strings! It turns out that with a little math you can extend this scheme to make a 2 dimensional array of strings as well. All it takes is another multiplier in there, which incidentally makes this an order of magnitude less efficient.

10 ROW=3
20 COL=3
30 MAXLEN=50
40 DIM MYMATRIX$(ROW*COL*MAXLEN)
50 REM POSITION
60 X=2,Y=1
70 GOSUB 100
100 REM MATRIX RETRIEVAL SUBROUTINE
110 START=X*MAXLEN-MAXLEN+Y*MAXLEN-MAXLEN-1
120 END=START+MAXLEN-1
130 PRINT ARRAY(START,END)
140 RETURN

In this way by manipulating the X and Y variables, and calling the subroutine we can retrieve different “cells” of data in our matrix.

Go ahead and stare at that second basic program for a few minutes until the math sinks in. The start position is calculated just like in the 1 dimensional example, with an additional Y position offset.

This approach will work decently well, for smaller grids with not too much data. Say a 3×3 grid, with each “cell” containing 255 characters or so, results in a use of just under 2.5K. What if you wanted a larger map though, say a 9×9, well that’s 20K, almost 1/2 your memory.

The strategy for dealing with this, is to break your 9×9 down into 9 different 3×3 grids. Since this, in theory a map that we are traversing, imagine another variable to hold your current “grid” number, and subroutine to calculate what grid you’ll be in when you move. If it’s different, load the new grid grid information from disk. In this way, you can keep the memory foot print pretty small, and 2.5K loads pretty quick from a floppy drive.

When I finish up this exercise I will post the code so you can bask in its glory.