Tackling the Logiker 2022 Vintage Computing Christmas Challenge – part 3

See also: part 1, part 2, part 3, part 4, part 5, part 6 and part 7.

So far, we’ve taken a brute force PRINT program and turned it in to a less-brute force program that did the same thing using DATA statements:

0 ' LOGIKER8.BAS
10 CLS
15 CH=32:PRINTTAB(6);
20 READ A:IF A=-1 THEN 220
25 IF A=0 THEN PRINT:GOTO 15
30 PRINT STRING$(A,CH);
35 IF CH=32 THEN CH=42 ELSE CH=32
40 GOTO 20
50 DATA 5,1,7,1,0
60 DATA 5,2,5,2,0
70 DATA 5,3,3,3,0
80 DATA 5,4,1,4,0
90 DATA 1,17,0
100 DATA 2,15,0
110 DATA 3,13,0
120 DATA 4,11,0
130 DATA 5,9,0
140 DATA 4,11,0
150 DATA 3,13,0
160 DATA 2,15,0
170 DATA 1,17,0
180 DATA 5,4,1,4,0
190 DATA 5,3,3,3,0
200 DATA 5,2,5,2,0
210 DATA 5,1,7,1,0
215 DATA -1
220 GOTO 220

All of this in an effort to try to print out this image:

While there are still many BASIC optimizations we could do (removing spaces, combining lines even further, renumbering by 1, etc.), those would apply to any version of the code we create. Instead of doing that, let’s look at some other ways we can represent this data.

Simpsons Atari 2600 did it first.

Let no meme go to waste, I always say.

When the Atari VCS came out in 1977 (you younguns may only know it as the 2600, but it didn’t get that name until 1982 — five years after its release later), it required clever tricks to make games run in only 1K or 2K of ROM and with just 128 bytes of RAM.

The game Adventure was quite the challenge, since it had multiple screens representing different mazes, castles and areas.

Atari’s Greatest Hits on an old iPad

Each screen was represented by only 21 bytes of ROM! If you follow that link, you can read more about my efforts to understand how this worked. Here is an example of how the castle room was represented:

;Castle Definition                                                                                                 
CastleDef:
  .byte $F0,$FE,$15 ;XXXXXXXXXXX X X X      R R R RRRRRRRRRRR                                      
  .byte $30,$03,$1F ;XX        XXXXXXX      RRRRRRR        RR                                      
  .byte $30,$03,$FF ;XX        XXXXXXXXXXRRRRRRRRRR        RR                                      
  .byte $30,$00,$FF ;XX          XXXXXXXXRRRRRRRR          RR                                      
  .byte $30,$00,$3F ;XX          XXXXXX    RRRRRR          RR                                      
  .byte $30,$00,$00 ;XX                                    RR                                      
  .byte $F0,$FF,$0F ;XXXXXXXXXXXXXX            RRRRRRRRRRRRRR   

There are three bytes to represent each line. Three bytes would only be able to represent 24 pixels (8 bits per byte), and the ASCII art shows the screen width is actually 40. Those three bytes cannot represent the entire row of pixels.

In fact, 4-bits of that isn’t used. Each set of three bytes represents halfa row (20 bits out of the 24 the three bytes represent). Look at the first entry:

  .byte $F0,$FE,$15 ;XXXXXXXXXXX X X X      R R R RRRRRRRRRRR   

If you turn those bytes into binary, you get this pattern:

 byte 1  byte 2  byte 3|
--------========--------
111100001111111000010101

The Atari drew the first 8-bits from least significant bit to most. the second 8-bits from most significant to least, then the third from least significant to most. That makes it look like this, matching the ASCII art (skipping the unused 4-bits):

000011111111111010101000
    XXXXXXXXXXX X X X   

To represent a full screen, the Atari had a trick that would mirror or duplicate the other half of the screen. In the case of the castle, the right side was a mirror image. In the case of certain mazes, the data was duplicated.

Looking at our image here, since it is symmetrical, we could certainly use the same trick and only store half of the image.

+----------------+
|           *    |
|           **   |
|           ***  |
|           **** |
|       *********|
|        ********|
|         *******|
|          ******|
|           *****|
|          ******|
|         *******|
|        ********|
|       *********|
|           **** |
|           ***  |
|           **   |
|           *    |
+----------------+

Also, since the top and bottom are also mirror images, we could mirror those, too, and get away with only storing 1/4 of the image:

+----------------+
|           *    |
|           **   |
|           ***  |
|           **** |
|       *********|
|        ********|
|         *******|
|          ******|
|           *****|
+----------------+

Since the image is 17×17 (an odd number, so there is a halfway row and column), we’d actually need to just draw to that halfway row/column, then reverse back through the data.

We should be able to take our existing data and crop it down from this, which represents the full image:

50 DATA 5,1,7,1,0
60 DATA 5,2,5,2,0
70 DATA 5,3,3,3,0
80 DATA 5,4,1,4,0
90 DATA 1,17,0
100 DATA 2,15,0
110 DATA 3,13,0
120 DATA 4,11,0
130 DATA 5,9,0
140 DATA 4,11,0
150 DATA 3,13,0
160 DATA 2,15,0
170 DATA 1,17,0
180 DATA 5,4,1,4,0
190 DATA 5,3,3,3,0
200 DATA 5,2,5,2,0
210 DATA 5,1,7,1,0

…to this, which represents the top left quarter-ish of the image:

50 DATA 5,1,4,0   '     X    '
60 DATA 5,2,3,0   '     XX   '
70 DATA 5,3,2,0   '     XXX  '
80 DATA 5,4,1,0   '     XXXX '
90 DATA 1,9,0     ' XXXXXXXXX'
100 DATA 2,8,0    '  XXXXXXXX'
110 DATA 3,7,0    '   XXXXXXX'
120 DATA 4,6,0    '    XXXXXX'
130 DATA 5,5,0    '     XXXXX'

That represents all the data up to the center row/column, and that seems to be a considerable savings in code space (removing eight lines).

But how do we draw that forward, then in reverse? There is no way to back up when using the READ command, so we’d have to remember what we just did. For a general purpose “compress 1-bit image” routine it would be more complex, but since we know the image we are going to produce, we can make an assumption:

  1. The image never has more than three transitions (space, asterisk, space) in a line.
  2. No line entry has more than 4 numbers total.

Knowing that, we could simply save up to three numbers in variables, so we would print them out A B C and then C B A. We won’t even need the zeros now, since we can read A,B,C and act on them (stopping if C is 0).

Neat!

A quick bit of trial and error gave me this code that will print the top half of the image:

0 ' LOGIKER10.BAS
10 CLS
15 CH=32:PRINTTAB(6);
20 READ A:IF A=-1 THEN 220
21 PRINT STRING$(A,32);
22 READ B,C
25 IF C=0 THEN PRINT STRING$(B*2-1,42);STRING$(A,32):GOTO 15
30 PRINT STRING$(B,42);STRING$(C*2-1,32);STRING$(B,42)
40 GOTO 15
50 DATA 5,1,4
60 DATA 5,2,3
70 DATA 5,3,2
80 DATA 5,4,1
90 DATA 1,9,0
100 DATA 2,8,0
110 DATA 3,7,0
120 DATA 4,6,0
130 DATA 5,5,0
215 DATA -1
220 GOTO 220

It creates this:

I can now say “we are halfway there!”

But now I have another issue to solve. How do I back up? There is no way to READ data in reverse. It looks like I’m going to need to load all those numbers in to memory so I can reverse back through them.

To be continued…

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.