Ram Cram Techniques for Atari
Original Adventure in 32K
Robert A. Howell
A few months ago something new was added to my family. A 10-lb. 16" by 12" by 4" Atari 800 computer. Not only that, this new computer had no disk. That's right, no disk. Only a cassette recorder to save and load programs and 32K (32,768) bytes of RAM. After having spent 17 years of my life talking to big computers with millions of bytes of memory and unlimited disk space (well, almost unlimited). I was understandably a little nervous about the usefulness of such a small computer.
About this same time, I had just finished several weeks of lunch hours (half hours if my boss is reading this) doing some fantastic arm chair spelunking. Yes, I had become hooked on exploring that colossal underground cave where magic is said to work and others had found fortunes in treasure and gold!
My large, friendly computer at work had been my eyes and hands guiding me past a giant snake and dragon through scores of rooms deep underground. I even tricked a troll. I was able to retrieve 15 magnificent treasures bringing them to the surface to be mine forever! Once in that cave it wouldn't let me give up, as I soon discovered, until finally, finally, many lost lunch hours (half hours if my boss is still reading this) later, every corner and dead end had been explored, a map of the cave was in hand and I had solved the original "Adventure."
Then a thought came to mind. I promptly dismissed it as absurd. But the thought kept haunting me until it became a challenge. Could this tiny little 32K computer with no disk which I now owned--could it possibly handle "Adventure"? Would the original Crowther and Woods Adventure program fit into 32,768 bytes of memory? I had seen several versions of this program advertised which required at least one disk drive and 32K or more of memory, but none for my little one. Was my little computer really equal to the task, or was I just fooling myself?
The challenge lay before me: get "Adventure" running in Basic on an Atari 800 computer with no disk and only 32K bytes of memory. Little did I realize what I was getting myself into when I accepted this challenge. A challenge that would certainly tell me if this new little addition to the family was really a giant in disguise!
Have you ever spent your whole summer beside the swimming pool out back, with the tops of your hands, shoulders and knees burning up from the sun, never once getting your swimming suit wet? No? Well then, you have never spent the summer trying to cram "Adventure--messages and all--into 32K of RAM. I did. And to spare you the gruesome details, suffice it to say that I accepted the challenge and won! Just as it was time to close down the pool for the winter, "Adventure" was running on my big computer (never again to be called "little").
The messages and vocabulary were not as extensive as in the original, but they were there, along with the rooms in various colors (except the "all alike" maze where passages and dead ends were all black). Almost everything from the original "Adventure" was included.
Now I know what you just said. You said, "How did he do it?" Well if you didn't say that then you should have, because that's the purpose of this article. As a result of my programming effort, as well as missing out on a whole season of swimming, I learned many techniques for efficient use of memory in Atari Basic. I am going to pass these along so that you will never need to worry about the swimming season passing you by.
Although my examples and techniques refer to Apple Basic and "Adventure" type programs in particular, most of them can be applied to any computer and to programming in general. Why purchase 48K of memory and two disk drives, when in many instances 32K or less of memory is all you really need. Why bemoan the fact that the latest "GLOP" game from the pages of this magazine requires 10K of RAM and your computer only has 8K. Apply a couple of the techniques that I am about to describe and you can probably get the program into 7K or less without losing a single feature!
REMarks
Although I realize that adequate documentation is often lacking in many programs today, when memory is at a premium, REMark statements must be sacrificed. A remark N characters long including imbedded blanks) occupies N+3 bytes if on the same line as another statement and N+6 bytes on a line by itself. Thus, REM's interspersed throughout a large program can waste a significant amount of memory.
An alternative which I use successfully, is to keep the remarks separately on paper, referring to the line numbers in the program. As the program is developed and changed, these remarks are also updated. Then, when the program is finished, a good set of documentation is already available. Also, by maintaining an up-to-date set of remarks, I found I was able to debug the program much more quickly. I estimate I saved about 1000 bytes of memory by eliminating the REMark statements from my "Adventure."
Line Numbers
When a new line (with a new line number) is added to a program, 6 bytes of memory are required by the new line. When that same Basic statement is added to an already existing line, only 3 additional bytes are required. Therefore, 3 bytes of memory are saved each time a new statement is added to a line which already exists, (Multiple statements per line are, of course, separated by colons.) To illustrate the savings that can result, in my version of "Adventure" there are about 720 individual Basic statements (not including DATA statements) but only 325 line numbers. This saves (720-325)*3 or 1185 bytes of memory.
Having written programs for many years using one statement per line, I was a little apprehensive about how difficult multiple statements per line would make program legibility and debugging. However, I found I had no trouble whatsoever reading the program and working with it, even though the Basic statements were packed very tightly.
Putting more than one statement on a line can cause problems if one is not careful, especially in a Basic that contains no ELSE capability. Consider the following example:
100 SUM=0 110 FOR I=1 TO 10 120 IF A(I)>0 THEN SUM=SUM+A(I) 130 NEXT I 140 PRINT SUM
One would be tempted to rewrite this sequence all on one line (with one line number) as follows:
100 SUM=0:FOR I=1 TO 10:IF A(I)>0 THEN SUM=SUM+A(I):NEXT I:PRINT SUM
However, this puts the NEXT and PRINT statements under the control of the IF, causing them to be executed only when the IF is true. This will produce incorrect results. The proper way to consolidate these statements is:
100 SUM=0:FOR I=1 TO 10:IF A(I)>0 THEN SUM=SUM+A(I) 130 NEXT I:PRINT SUM
Statements after an IF should be placed at the front of the following statement, or on a line by themselves if the following statement has a branch to it from elsewhere in the program. Of course if the statements after the IF clause are to be executed only when the IF condition is true, then they must be left on the same line as the IF statement.
Here is another example which sets X to 10 or 20 depending on the value of L:
100 IF L=R THEN 400 200 X=10 300 GOTO 1000 400 X=20 500 GOTO 1000
This section of the program can be neatly condensed into two lines as follows (eliminating one GOTO and saving 27 bytes):
100 X=10:IF L=R THEN X=20 200 GOTO 1000
Again, the GOTO 1000 must be placed on a separate line so it does not fall under the control of the IF statement.
It may not be obvious what will happen when some statements in Atari Basic are imbedded in the middle of a multi-statement line. Figure 1 lists these statements with an explanation of what happens to statements which follow each of them on the same line.
|
||||||
Make a similar table for your Basic by trying out each statement in a small test program. Then keep this table handy for reference when you are optimizing a large program.
Another way to eliminate line numbers is by inserting a NOT in front of an IF condition. For example:
100 IF A=1 AND B>5 THEN 130 110 B=B-1 120 GOTO 1000 130 PRINT
may be rewritten on two lines (saving II bytes) as follows:
100 IF NOT(A=1 AND B>5) THEN B=B-1:GOTO 1000 130 PRINT
Here is a different example that may occur in a program:
90 ON X GOTO 100,200,300,400 100 T=0:GOTO 1000
These two lines may be condensed onto one line:
90 ON X-1 GOTO 200,300,400:T=0:GOTO 1000
eliminating line 100 and saving three bytes.
There are many other ways that multiple statements may be squeezed onto one line in order to save memory. A program that does not already do this can probably be reduced to 75%, or 50% of its original line numbers. Keep in mind however, that a branch to a statement from elsewhere in the program requires that statement to be at the beginning of a line. Also, in Atari Basic this technique is limited by the length of a logical line which is equal to a maximum of three physical lines or 120 characters. Greater savings can be obtained using Basics which allow more characters per logical line.
Don't Use Constants!
One of the biggest memory wasters in Atari Basic is the use of constants. Each occurrence of a numeric constant or a line number in a Basic statement is replaced by one byte pointing to the memory location where the value of that constant is stored. This value in memory is stored in internal binary form and occupies an additional 6 bytes regardless of the size of the constant. Therefore, each use of a numeric constant or line number in a statement requires 7 bytes of memory. This method of storing numeric constants is what would be expected. Now for the bad news. Since Basic is an interpreter (that is, every statement is kept in memory in almost its original form and decoded each time the statement is executed), when it encounters a constant in a new statement being entered in, it has no way of knowing if that constant was used before. Therefore, it just goes ahead and converts into internal binary form and stores it in memory again using another 7 bytes.
Now, suppose a large program uses the constant 0 (zero) 50 times. Then that one constant occupies 7 times 50 or 350 bytes of memory! Likewise, suppose line number 100 is referenced in GOTO and IF...THEN statements 50 times throughout a program. That one line number also occupies 350 bytes of memory. So we have 700 bytes of memory being used to store the two values 0 and 100. Wouldn't it be nice if each new use of the same constant or line number would point to the memory locations where that Value was stored the first time?
Fortunately, there is a way to make that happen: by the use of variables in place of numeric constants and line numbers. The first time a variable is used in a statement four things happen:
1. The variable name is placed in a table in memory called the VNT (Variable Name Table).
2. Six bytes of memory are allocated to store the value of the variable.
3. Two additional bytes are stored in the VNT which point to the value of the variable in memory.
4. One byte is placed in the Basic statement in place of the variable name. This byte points to the VNT.
Thus N+6+2+1 or N+9 bytes of memory are used to store the first occurrence of a variable name (where N is the number of characters in the name of the variable). Now the memory-saving aspect of this method comes into play with the second, third. etc. time the variable name is used. Each subsequent use causes only 1 additional byte of memory to be allocated: the byte in the Basic statement that points to the VNT. Unlike when a constant is used, the 6 bytes of memory to store the value is not allocated over and over again.
To use this method of replacing constants with variables, one other item must be considered. The variable being used must be initialized with the value of the constant it represents. The most efficient way to do this is with READ and DATA statements at the beginning of the program. In an initialization section, values are read in for all the variables which are being used to replace numeric constants and line numbers.
A good rule of thumb to use in deciding whether or not to replace a particular numeric constant or line number with a variable is the following: If the same numeric constant or line number is used four or more times in a program, memory will be saved by converting it to a variable. If used three or fewer times, leave it in its original form.
Of course, the more characters there are in the variable name and in the constant, the more memory will be used in the VNT (to store the variable name) and in the READ/DATA statements. However, the break between three and four occurrences seems to work in most cases.
Now you are probably saying to yourself, "How can I possibly make any sense out of my program if I convert all the constants and line numbers to variable names?" And I agree. If you can't distinguish between the constants and actual variables, then reading the program listing becomes difficult.
|
Therefore, decide on a pattern for variable names which will be used to represent numeric constants and line numbers in the program and stick to this pattern. An example of what I use is found in Figure 2.
Then for real variables which do actually vary, I use the names J through Y and names that contain all letters (such as AA, AB, QX, ZZ, etc.). This way I can always distinguish constants from variables. If the program uses negative and decimal constants, then establish a pattern for them also.
Figure 3 is example of a program segment before and after the constant-to-variable surgery has taken place.
Note, when a statement number on an IF...THEN is changed to a variable, a GOTO must be inserted (see line 60 in Figure 3). Other than this one exception, any place a numeric constant or line number can be used in an Atari Basic statement, a variable can be substituted.
|
Also note line 40; even the dimensions in an array can be made variables, thus saving the memory that would be used to store the constant dimensions.
Is it really worth the trouble to convert most of the constants and line numbers in a program into variables? In my "Adventure" program, I changed 58 constants and line numbers to variables and saved over 3500 bytes! This represents 12% of the free memory on a 32K Atari system, so the effort certainly paid off. The maximum number of variable names allowed in a single program in Atari Basic is 128. This is as big as the VNT can get.
Therefore, start with the numeric constants and line numbers that are used most often since these will result in the greatest savings. Also, instead of converting constants which are not used very often, consider that GOTO 9 can be changed to GOTO D+E. This will save changing the constant 9 into a variable if D and E are already defined to be 4 and 5 respectively. The constant 9 requires 7 bytes whereas D+E requires only 3, a saving of 4 bytes of memory. Use this technique of combining variables to replace constants that occur three or fewer times in a program.
As can be seen, substitution of variables for oft-used numeric constants and line numbers can result in a substantial increase in memory available in a program.
Numeric Arrays
How much memory will the following statement use:
10 DIM A(100),B(100),C(100),D(100),E(100)
If your answer is 500 bytes, you are not even close. The above dimension statement will require over 3000 bytes of memory. Yes. 300! Why? As we discussed earlier, numbers in Atari Basic are kept in memory in internal binary form occupying 6 bytes each. Therefore, each of the above arrays uses 100 times 7 bytes of memory apiece, and 5 of them will take 100 times 6 times 5 or 3000 bytes. When the memory space is tight, there are two rules to observe in using numeric arrays: 1. Keep their dimensions as small as possible. 2. Eliminate them whenever possible.
There are several ways to eliminate numeric arrays. I will mention two of them: Convert them to strings, and store numeric data in DATA statements and access it with READ statements each time the data is required.
In Atari Basic, strings must be dimensioned. In the statement:
10 DIM R$(100),R(100)
R as we now know occupies 600 bytes, but R$ occupies only 100 because it is a string 100 characters long. Now suppose in an "Adventure" program there are 100 rooms and the program keeps track of which rooms have been visited and which have not. Each element of R(100) would represent a room. R would be initialized to all zeros and when a room was entered, the corresponding element of R would be set to 1. Since each element of R holds only a 0 or 1, this same function can be accomplished with string R$(100) using approximately one-sixth the memory. First R would be initialized to all "N" characters (representing "No. the room has not been entered") as follows:
100 FOR I=1 TO 100:R$(I,I)="N":NEXT I
(Note in Atari Basic. R$(i,j) represents the substring from R$ starting with character i and ending with character j. Therefore. R$(i,i) represents the ith character of string R$.) Then when room number I is entered, R$(I,I) would be set to "Y" (indicating "Yes, the room has been entered"). At the end of the game, the number of rooms visited would be counted as follows:
1000 SUM=0:FOR I=1 TO 100:IF R$(I,I)="Y" THEN SUM=SUM+1 1010 NEXT I
Of course, if a numeric array is needed to store many different values, this method will not work. However, for storing just a few different values, try using a string instead of a numeric array and substitute different characters for the various values in order to save on memory.
Now suppose a program uses numeric data that never changes. The room move table in "Adventure" is a good example of this. My "Adventure" has 126 rooms and there are 10 possible directions to take out of each room (N=1. NE=2. E=3...NW=8. UP=9. DOWN=10). If an array were used to hold this data, it would contain 126 times 10 or 1260 elements. At 6 bytes for each element, this table would occupy 7560 bytes or almost one-fourth of my 32K memory. The data in this array would be room numbers to move into from each room. So for example, to move West (direction 7) from room 29, the contents of array element (29.7) would be the room number to move into going in that direction. Zero of course would mean no path that way.
This data never changes. Therefore it can be put into DATA statements, one DATA statement per room. 10 numbers (corresponding to the 10 directions) per DATA statement. Suppose the DATA statement for room number 1 is on line 10001, room 2 on line 10002, etc. Also suppose variable DR contains the direction in which the adventurer wishes to go and RC the number of the room he is currently in. Here is how the program would locate the room number to move into:
100 RESTORE 10000+RC:FOR J=1 TO DR:READ RN:NEXT J
The RESTORE locates the DATA statement for room RC, the FOR loop reads until the room number corresponding to direction DR is read at the end of the loop. RN contains the desired room number. Using this technique, I saved about 3650 bytes of memory on the room move table in my "Adventure" program.
To go even one step further, I put the data for rooms 1, 2 and 3 all on DATA statement 10003: rooms 4, 5 and 6 on DATA statement 10006 and so forth, thus eliminating two thirds of the DATA statements and saving another 600 bytes. The RESTORE statement will still work in Atari Basic because a RESTORE to line 10001 (for room 1) will actually start reading at line 10003 if lines 10001 and 10002 do not exist. Of course, the FOR loop had to be modified to read the correct set of 10 room numbers as now there were 30 room numbers per DATA line. With this modification, the room move table has now been reduced from 7560 to about 3300 bytes for a 56% reduction in memory used.
Furthermore, upon examining the room move table data, I found that it contained many zeros. This occurs because there are exits from most rooms in only a few of the 10 directions. Therefore, I replaced n consecutive zeros in the DATA statements with the number -n. For example, if one of the DATA statements contained 8 zeros in a row, these zeros were eliminated and a single -8 put in their place. This was done in all DATA statements where 2 or more zeros occurred together. The read routine was then modified to expand negative numbers back to the original number of zeros as the data was read. This modification further reduced the room table from 3300 bytes to 2236 bytes now occupying 70% less space than if a 126 by 10 numeric array had been used. Thus, over 5300 bytes of memory were saved with several very simple modifications to the room move table part of the program.
Since numeric data items require 6 bytes each when stored in numeric variables or arrays, if the data does not change during program execution, keep it stored in DATA statements and READ it when it is needed. Pack it on the DATA statements as tight as you can. Otherwise use string arrays if possible. The fewer numeric arrays a program uses, the more memory will be available to it.
Strings
Although strings require less memory than numeric arrays, still try to keep their length to a minimum. Don't set up A$(100) when the maximum length A$ will ever be is 50 characters, Also, eliminate string variables when possible. If three strings are defined in a program and one of the strings could do the functions of all three, eliminate two of them.
"Adventure" type programs always have a vocabulary of words which they recognize (NORTH, TAKE, DRAGON, INVENTORY, DIAMONDS, etc.). Cut these words down to their first five characters (NORTH, TAKE, DRAGO, INVEN, DIAMO, etc.) Although some games use the first four or three characters, five is about the minimum length which can be used and still make the words unique. When the player's input is received, each word of it is truncated to five characters before a search is done against the vocabulary in the program.
As discussed previously with numeric data, place the vocabulary in DATA statements and READ it when it is required. In Atari Basic, strings are placed in DATA statements without quotes and are separated by commas. Since Atari Basic does not have string arrays (e.g. A$(100) does not mean 100 strings, but defines a string to be a maximum of 100 characters long), to store the words otherwise, they would need to be packed into a string. Since the words are variable in length (INVEN is five characters long but TAKE is four, OIL, three, etc.), this would require extra program statements and overhead. With the vocabulary on DATA statements, it may be searched by READing it from beginning to end with a special character )*.$, etc.) marking the end of the table.
This will take a considerable amount of time, especially for words at the end of the table. Therefore, a more efficient way is to place all words beginning with the same letter in a separate DATA statement. Then a RESTORE is used, keyed off the first character of the word being searched for, to locate the DATA statement containing all words starting with this letter.
As can be seen, putting both numeric and string data into DATA statements can be a very effective way to reduce the amount of memory required by a program. Before numeric arrays and strings are set up, consider the use of the READ/DATA statement technique. It may make the difference in being able to get a program into memory.
Eliminate Unneeded Statements
When you need to alternate a program variable between 0 and 1, how do you do it? Before reading on, take a piece of paper and write the Basic statements to set B equal to 0 if its value is 1 and vice versa (keeping in mind that Atari Basic does not have an ELSE capability). Now look at your programming. Is this the way you (lid it?
10 IF B=0 THEN B=1:GOTO 30 20 B=0
Or how about this way?
10 ON B+1 GOTO 20:B=0:GOTO 30 20 B=1
Or better yet?
10 ON B+1 GOTO 2O:B=-1 20 B=B+1
Each of these methods is good and will accomplish the task, but they all use two lines. Is there a way (without using ELSE) to write this code on one line? Yes there is. A little creative programming reveals the following method:
10 B=ABS(B-I)
The first three examples require 52, 60 and 53 bytes respectively: the last example only 20 bytes. The point here is, eliminate unneeded statements wherever possible to save on memory.
I found in my "Adventure" program that the statement:
Z=B:GOTO 90
occurred 16 times. So I did the obvious: kept the first occurrence of this statement and replaced the other 15 with a branch to the first one. Now I know I have just caused a program abort to occur in the mind of every structured programmer in the audience. Please note, I am not against structured programming.
In fact, I encourage it along with good program documentation wherever possible. However, the preceding example saved 90 bytes of memory. By doing this same thing with several other statements that occurred multiple times in the program, I was able to save another several hundred bytes. So use of this technique really paid off.
Untokenize The Program
When Atari Basic places a statement into memory, it uses a 'tokenized' form. That is, each Basic keyword, each arithmetic operator and each relational operator are replaced by a unique 1-byte code called a token. At the same time (as previously discussed), constants are placed in memory in internal form and variable names are placed in the VNT (Variable Name Table). This is the way Basic interpreters work. Thus, they automatically provide some efficiency in their use of memory.
Now, after a new program is entered into memory, typically a debugging phase begins. The program is run and rerun (and rerun and rerun and rerun ....) many times to find and correct as many logic errors as possible. In this phase, statements are added, changed, deleted, rewritten, etc. If the program is large, debugging may take many days or weeks. During this time a number of variable names which were once used in the program will probably be completely eliminated. Or a typing error may have caused the variable TB, for example. to be entered when T was supposed to be used. Later on, this error is discovered and TB is replaced by T in the statement, thus completely eliminating the variable TB from the program.
Sounds logical so far, doesn't it. However, something else occurs that is not immediately obvious. When TB is replaced by T, Basic, being an interpreter, does not know that the variable TB has been completely eliminated from the program. Basic has no way of knowing that TB is now used in any other statement. Therefore, TB still occupies 4 bytes in the VNT and 6 additional bytes of memory are still reserved to hold the value of TB. Ten bytes of memory are being used by TB. Multiply this by another 10 or 15 variables that may have been used in the program but have since been eliminated, and we find hundred or more bytes of memory being wasted.
"Well," you respond, "when I CSAVE the program onto tape and then CLOAD it back into memory, doesn't the VNT and related memory get cleaned up?"
The answer to this question is "No." because a CSAVE causes the tokenized version of the program to be written onto tape and along with the tokenized program, the VNT and associated memory are also written. One of the reasons CSAVE works this way is because the tokenized version takes much less time and tape to write out. Now when a CLOAD is done, the old VNT still containing the unused variable names and their associated memory is read back in unchanged.
How do you eliminate the unused variables from the VNT and free up their memory bytes? Simple. The program must be written out in its untokenized form. This is the form that is seen on the screen when the program is listed with the LIST command. In Atari Basic, this is done exactly like a CSAVE except the command LIST"C" is used. LIST"C" causes the program to be LISTed to cassette tape. The tape will be written with the untokenized version of the program only and not include the VNT nor any other values from memory.
Note, this process will take two to three times as long as CSAVE and require at least twice as much tape. The tape should then be rewound, NEW typed to clear memory (this is important to erase the old program and VNT), and the untokenized version read back in with the command ENTER"C" (which works just like CLOAD). The untokenized statements will be read in one by one, retokenized and a new VNT constructed. Since the old variable names are no longer in this set of Basic statements on tape, they will not be entered into the new VNT.
When I had finished debugging my "Adventure" program, I untokenized and retokenized it and gained 150 bytes of memory. This allowed me to add a few more vocabulary words that I had previously eliminated for lack of space. Note also that a program should be untokenized and retokenized whenever an ERROR 4 occurs. Error number 4 means the VNT is completely full with 128 variable names. Of course, if the program actually has 128 legitimate different variable names, then this method will not work and some of the variable names must be eliminated or combined into an array (which takes up only one slot in the VNT).
Use of POP Statements
When I finally had the "Adventure" program finished, there were 450 bytes of memory available after loading and 50 bytes free after execution began. I felt the program was now bug-free and ready for the final test: my 10-year old son, David. But a strange thing began to happen. After David played for one or two hours. ERROR 2 would occur and the program would abort. Error number 2 means out of memory. This error would occur randomly after about an hour of play without restarting the game, and always at a different spot. How could this be? I had very carefully calculated that there should be at least 50 spare bytes of memory. I was puzzled. It took me a while to figure out what the problem was, but I finally found it.
When a GOSUB is executed, Atari Basic puts the return address into a push-down, pop-up stack in memory. Then when the RETURN statement is executed, the top address is popped off of the stack and the computer returns control to the program at this address. Thus the stack is constantly expanding and contracting in memory as GOSUB's and RETURN's are executed. Now suppose a subroutine branches elsewhere in the program, never executing a RETURN statement. The return address remains on the stack forever. This is exactly what was happening in my program. Every once in a while the program would exit from a subroutine without executing a RETURN. Each time this happened, 4 bytes of memory remained on the stack, never to be released, and the stack gradually expanded until it had eaten up the 50 bytes of available memory.
There are two ways to eliminate this problem. The most obvious is to exit from every subroutine via a RETURN statement. However, it is not always possible nor desirable to do this. Therefore, before branching out of a subroutine where the RETURN will never be executed, a POP statement should be inserted. This causes the stack to be popped up one time, and the return address removed, just as if the RETURN statement had been executed. The format of this statement is:
100 POP
In my program, I put several POP statements just before the INPUT statement. The program continually returns here to get the player's next response. Thus, I made sure at this point that the stack was completely empty. Executing a POP when the stack is empty acts like a do-nothing statement and does not cause an abort. This small modification solved the problem.
One note of caution when using POP statements in Atari Basic: FOR loops are also placed on the stack. Therefore, if a program is in the middle of a FOR loop when a POP is executed, the FOR information may be removed from the stack. This will cause the program to abort with error number 13 (NEXT encountered with no matching FOR) when the corresponding NEXT statement is executed. The way to avoid this is to make sure POP statements are not placed within FOR loops, or to make sure that you know exactly what order FOR and GOSUB information was placed on the stack so it may be correctly popped off. Note also that branching out of a FOR loop without completely finishing the loop does not cause the stack to grow, and waste memory like GOSUB's do, so one only needs to be concerned about this problem when branching out of subroutines without executing a RETURN.
Message Text
Approximately one half of the memory in my "Adventure" program is text consisting of room descriptions and messages. Since the original "Adventure" text is too large to fit, it had to be cut down. There are several way to do this.
One way is to eliminate completely a number of the least used, least important messages. Another way is to delete some of the descriptive adjectives and/or change the wording so that the message is smaller but still retains its original meaning. Abbreviating, using contractions and substituting smaller words all help considerably. Here is an example:
Original message: "You are in a complex junction. A low, hands and knees passage from the north joins a higher crawl from the east to make a walking passage going west. There is also a large room above. The air is damp here."
Abbreviated message: "You're in a complex junction. A low N pass joins a higher crawl from the E making a walking passage W. There's a large room above. The air is damp." Counting spaces, the message has been reduced by 28 from 204 to 147 characters.
Half of the room descriptions (63) begin with the 11 characters 'You are in" (including the space following the word in). I eliminated these words from the front of those 63 messages and modified the print message subroutine to print them if the first character of the message to be printed was not a capital letter. This resulted in another 600-byte savings.
Message text is stored in DATA statements. Message number 1 at line 15010, message 2 at line 15020, etc. The start of a message is located with a RESTORE 15000+N*10 where N is the message number. Many of the messages extend onto multiple DATA statements.
A special character which is not used anywhere else in the message text was placed at the end of every message. This character is detected by the print message subroutine telling it when the end of the message has been reached. Adding this single character per message was the simplest way to allow the program to determine the end of a message when the messages were variable in length. This method also uses the least amount of memory.
With a little creative rewriting, the original "Adventure" message text was cut approximately in half so that it fit into 14K to 15K of memory, but still retained its original meaning. The attractiveness of the game was not lost, and all of the excitement of the original "Adventure" was still there even though the messages were now in an abbreviated form.
Miscellaneous
Here are a few other hints for optimal memory use:
1. Do not use long variable names (Atari Basic allows up to 120 character names, all characters significant). Each character in a variable name occupies 1 byte of memory in the variable name table.
2. Replace IF X<>0 with IF X (which is equivalent and saves 3 to 9 bytes depending on whether the 0 is a constant or a variable).
3. Use GOSUB's to eliminate multiple occurrences of identical program statements.
4. Use as few variable names as possible by making them do double and triple duty. Rather than use I, J, K, L, M and N as FOR loop variables, or Z0 through Z9, see if you can get along with using just I and J or Z1 and Z2. The same applies to scratch variables and other variables in the program.
5. Remove unnecessary parentheses and rely on operator precedence wherever possible (except, due to a known bug in Atari Basic, always enclose NOT and its associated variable in parentheses--(NOT B) instead of NOT B).
6. Spaces may be used anywhere for program readability (except of course in strings). Spaces are not stored in memory when a program statement is tokenized.
7. A new line always requires 6 bytes of overhead regardless of the size of the line number used.
8. Change IF NOT (A=B and C=D and E=F...)
to IF A<>B OR C<>D OR E<>F...
Change IF NOT (A=B or C=D or E=F...)
to IF A<>B AND C<>D AND E<>F...
Memory will be saved in both cases.
9. Use of the LET keyword does not cause extra memory to be allocated. It may be included or omitted as desired.
10. The RUN command clears all simple numeric variables to zero and sets all strings to empty (length zero) so don't waste memory clearing them. However, numeric arrays are not cleared! If they must be initialized to zero, use a FOR loop (all on one line, of course).
11. Many of the Atari Basic keywords can be abbreviated. Abbreviations have no effect on memory utilization.
One last question lingers which must be answered: After optimization for efficient memory use with these methods, how slowly does the program actually run? When I had finished the "Adventure" program. I did find the response to the player's input to be too slow. It was in the five to ten second range. However, upon investigation I discovered that the program was taking five seconds searching the vocabulary list. The further down the list it had to search, the longer it took. Therefore, I did sacrifice some memory by placing words that start with the same letter together on separate DATA statements. Then I changed the search routine to do a RESTORE to the proper DATA statement keying off of the first letter of the word that was being searched for. This reduced the search from a maximum of 150 words to 20 or less. Also, I placed the most often used words at the beginning of each DATA statement. Thus the vocabulary is not packed as tightly onto DATA statements as it could be. However, with this one small change, response time is now in the one to two second range for most responses, with a maximum of five seconds for the GET/TAKE verb which has the largest number of program statements associated with it. It appears that, on the Atari 800, chaining constants to variables, reading from DATA statements, jumping all over the place with GOTO's and GOSUB's etc, doesn't cost the program too much in time. This, of course, may not be the case for a program that uses some of the fancy Atari sound and graphics capabilities. However, for "Adventure" in graphics mode 0 (full screen text), the speed is adequate, even when a Basic program is highly optimized for memory usage.
|
Robert A. Howell, 20 Richman Road, Hudson, NH 03051.
Table of Contents
Previous Section: An Atari Library of Sound
Next Section: From Burn-Out to Born Again
