C64 Praise Be The Spiral!!

Just a few weeks ago, Shallan50k on twitch was running a friendly challenge to his followers and interested folks. The winners were to receive some sort of FPGA board that can run the Mega65 core.

The challenge was to reproduce the following screen on the Commodore 64 using just about any technique you can think of, IE using Basic or Basic kernel routines or assembly language. The use of compression was forbidden since it went against the general spirit of the competition. The user who generated the smallest compiled PRG file would be declared the winner.

This challenge intrigued me. As you can see from the image, it is a fairly basic spiral, nothing too tricky. My first thought was there is probably some easy math formula that could quickly generate this thing, but I had no idea what it could be.

Anyhow the competition is now closed, the winners declared. In this video I am going to cover some of the solutions that I came up with, both in basic and at least one solution in Assembly language, and at the end I will share ALL the top winning solutions the PROs came up with over on the Twitch and Discord channels. I will post all of the source code mentioned in the video on my Github account. I will tell you now there were a couple of tricks I never knew about and a few ideas that never even dawned on me. Stay tuned for that.

If you would like to try your hand at cranking out a succinct elegant solution to this challenge, please feel free to pause this video and give it a go, since the rest of the video is essentially spoilers.

I thought I might be able to come up with a solution, I just wasn’t sure if it would be very elegant, and in the end, my solutions were mostly far from it. As I first started trying to code a solution in Assembly, people started chiming in on Discord with their final product byte counts, mostly coming in at under 100 bytes. This was discouraging at first since I was somewhere above 200 bytes, but it did set the bar.

At any rate, I welcomed the idea of the challenge and no matter what. I thought this could be a great learning experience.

I decided to start out by writing a basic program to try to come up with an algorithm that might work and came up with this first BASIC program:

Test.bas
As it turns out, this particular solution is not that far off from some of the best ones out there. This was the first one I decided to try converting to assembly language, but was quickly discouraged as I realized there are four loops and each loop in my example had to do some simple calculations, which can balloon in ASM. My initial code was more than 200 bytes and the leading solutions online were coming in at under 100 bytes, so I abandoned my first attempt and went on to try other algorithms. I didn’t even realize until I started making this video, I was so focused on the algorithm that I didn’t notice the character I draw on the screen was not the correct one for the challenge.

100 x=27
110 y=12
115 xw=16
118 yh=1
200 gosub 1000
210 gosub 1000
215 gosub 1000
218 gosub 1000
219 gosub 1000
222 gosub 1000
224 gosub 1005
230 end
1000 gosub 1005:gosub 1025:return
1005 for x=x to x-xw step -1
1010 poke 1024+y*40+x,0
1020 next
1022 return
1025 xw=xw+2
2000 for y=y to y+yh
2010 poke 1024+y*40+x,1
2020 next
2030 yh=yh+2
3000 for x=x to x+xw
3010 poke 1024+y*40+x,0
3020 next
3030 xw=xw+2
4000 for y=y to y-yh step -1
4010 poke 1024+y*40+x,0
4020 next
4030 yh=yh+2
4040 return

Test1.bas

My second attempt was not much different from the first. The program was shorter but still not quite what I was looking for.

505 sys 58692
508 gosub 2000
1000 for y=0 to 12 step 2
1010 for x=xw to 40-xw
1020 poke 1024+y*40+x-1,1
1030 if x>xw then poke 1024+(24-y)*40+x-1,2
1035 rem if x<>(39-xw) then
1040 next x
1050 xw=xw+2
1060 next y
1070 goto 1070
2000 xw=0: yw=0
2005 rem for x=0+xw to 39-xw step 2
2008 for x=0 to 10 step 2
2010 for y=yw+1 to 23-yw
2020 poke 1024+(y+1)*40+x,3
2022 poke 1024+(y)*40+(39-x),4
2040 next y
2050 yw=yw+2
2060 next x
2070 return

Test2.bas

Next I thought, what if I could do the same as the previous attempt only this time, do it using ONE “for loop”, would that even be possible? I think this might be the most enjoyable one to watch being drawn.

10 sys 58692
20 for y=0 to 12 step 2
30 x=xw-1
40 poke 1024+(y)*40+x,1
50 if x>21-xw then goto 90
60 poke 1024+(x+3)*40+y,3
80 poke 1024+(x+2)*40+(39-y),4
90 x=x+1: if x<40-xw then poke 1024+(24-y)*40+x,2:goto 40
110 xw=xw+2
120 next y

Test6.bas

On test6.bas I decided to try a different tact and use the basic kernel to move the cursor around for some reason. This was the one I decided to try to implement in Assembly. As it turns out, I was only able to crunch it down to 130 bytes. From this I knew it was not the proper algorithm.

40 dim cnt(26)
100 print “{clear}{home}”;
110 cd$=“rdilurdlurdlurdlurdlurdlur”
130 for i=1 to 26
135 read cnt(i)
140 gosub 170
150 next i
165 goto 165:end
170 for x=1 to cnt(i)
180 if mid$(cd$,i,1)=“r” then print “@”;
190 if mid$(cd$,i,1)=“d” then print “{down}@{left}”;
195 if mid$(cd$,i,1)=“i” then print “{left}{down}@{left}{148} “;
210 if mid$(cd$,i,1)=“l” then print “{left}@{left}”;
220 if mid$(cd$,i,1)=“u” then print “{up}@{left}”;
230 next x
235 if mid$(cd$,i,1)=“r” then print “{left}”;
240 return
250 data 40,23,1,39,22,38,20,35,18,34,16,31,14,30,12,27,10,26,8
260 data 23,6,22,4,19,2,18

Test8.bas

Finally I came up with another solution taking yet another tact. I think it could be made into a smaller routine in ASM, not small enough to compete with the PROs, but I never got around to implementing it.

100 sys 58692
110 a$=“{A*40}”
120 b$=“@ @ @ @ @ @ @ @”
130 lf=1:off=1:rr=38:cc=0
140 for y=0 to 24 step 1
150 if (y and 1)=0 then print left$(b$,lf);mid$(a$,lf,rr);right$(b$,lf-cc);
160 if (y and 1)=1 then print left$(b$,lf);spc(rr);right$(b$,lf-cc);
170 if y=12 then off=-1:cc=3:rr=rr-1:lf=lf+2
180 lf=lf+off
190 rr=rr-(2*off)
200 next
210 goto 210

SP175

Next, I want to show you a BASIC solution submitted by user SP175 on Discord. It thought it was clever, and elegant. It seems like it would easily translate as well.

10 PRINT “{clear}”
20 L=.:S=1024
50 gosub150:IFS<(1024+(40*L)+39-L)THENS=S+1:GOTO50
60 IF S=1531THEN20
80 gosub150:IFS<1024+(40*(24-L))THENS=S+40:GOTO80
110 gosub150:IFS>1024+(40*(24-L)+L)THENS=S-1:GOTO110
120 L=L+2
140 gosub150:IFS>1024+((40*L)+L)THENS=S-40:GOTO140
145 GOTO 50
150 pokes,128:return

AKMAFIN

The final BASIC solution I came across submitted by user AKMAFIN on Discord. I was blown away by how short and succinct the solution is, only three short lines. The ASM conversion translated to 70 bytes.

0 print“{clear}”:s=1024:c=2:fori=0to7:reada(i):next:data40,25,40,23,1,40,-1,-40
1 pokes,128:o=o+1:ifo<a(q)thens=s+a(q+4):goto1
2 a(q)=a(q)-c:c=4:o=0:q=(q+1)and3:goto1

Now I want to show you the TOP 5 top solutions out there, leading up to the winning solution and cover some of the tricks that were used to squeeze out a few additional bytes. You may notice as I bring up the various solutions, the code looks pretty similar, in that most of them are using the same general algorithm, that is, to start drawing the spiral starting from the top left.

Solution 1:

User “GEE_HAF” . 62 bytes. Right off the bat this one uses a Stack trick to save a byte telling the C64 where to start the program. However it was pointed out by Shallan on stream, that the next instruction to clear the screen, could have been added to the stack, saving one additional byte. The next couple of entries made the same “mistake”.

Solutions 2 & 3, both came in at 61 bytes and were submitted James and Endurion. In James’ example we first see yet another trick that had never crossed my mind, and that was the use of illegal Opcodes. These are instructions that can still be utilized, but are considered unstable. They can save a byte here and there by combining multiple operations into one command. James used one called “ANC” which sets the carry bit without affecting the accumulator. For this challenge, as long as the program functions properly there was no harm in using these illegal op-codes.

Opcode – C64-Wiki (c64-wiki.com)

Solution 4 by Andy the Magic Knight, was 53 bytes, and took second place!

Andy also used an illegal OP code, “XAA”, which “ands” together the A, X and immediate register.

“XAA transfers the contents of the X register to the A register and then
ANDs the A register with an immediate value.”

www.ffd2.com/fridge/docs/6502-NMOS.extra.opcodes

Andy as well as the next two entries also employed yet another really clever idea, that I hadn’t thought of, and that was to start their programs at address space in zero page, specifically $42, loading the entire program into zero page, saving many bytes.

Anyhow his entry was really smart & elegant, again using only 53 bytes.

I asked him about how he chose to start his program at that address. He gave a detailed explanation on his blog which I appreciated.

MagiC64Knight

Shallan’s solution was only 52 bytes, but he was running the challenge and had access to everybody’s, entries and ideas, so it doesn’t really count but it is included in the download file. He employed the “BIT” command to save a few bytes.

And Finally, the WINNING solution clocking in at only 51 bytes, was submitted by Carl Henrik. His solution, really clever, in that the algorithm, is not directional, instead it scans each row and column of the screen from left to right, making the determination on what character to draw. Clever indeed. Carl gives a more in-depth explanation of his solution over on his github page:

https://gist.github.com/Sakrac/448e136531e8731da80350a565a17846

My translation of one of his early pseudo-code examples:

5 s=1024
10 for y=0 to 24
20 for x=0 to 39
25 x2=39-x
30 if x<20 then x2=x
50 if y<=12 then y2=y
60 if y>12 then y2=24-y
70 if x280 if x2>=y2 then v=y2
85 if x2>20 and y>=12 then x2=x2+2:end
90 if (v and 1)=1 then c$=“2”
100 if (v and 1)=0 then c$=” “
110 poke s,asc(c$)
115 s=s+1
120 next
130 next

Anyhow, I had fun racking my brains and following this challenge. I learned a few new techniques along the way. One of the things I realized after seeing everyone’s solutions was the way I was approaching the drawing the characters on the screen was a bit bloated in comparison to the PRO solutions… lesson learned.

Tangentially, I learned a few more things as a result of this challenge:

Even though these techniques were not used on any of the final solutions I did learn a few tips:

New ways to position the cursor to print things on the screen.

From Arthur Jordison:

print at x,y equivalent – Commodore 64 (C64) forums (melon64.com)

Tricks in basic to move cursor around

This one is old but you can use commands on a print statement with curly brackets

0 x$=“{home}{right*39}”:y$=“{down*24}”
10 x=12:y=10
20 print left$(x$,x);right$(y$,y)“{@*13}”;

Hi, Low table in ASM already in ROM

I used to use a short table in most of my programs containing the high and low bytes of each row of the screen. Well, I just learned these values are stored in memory at the following locations:

.const scr_off_l = $ecf0
.const scr_off_h = $d9

This could save your code around 50 bytes if needed.

Oh and last but not least the command “jsr $e544” or “sys 58692” in BASIC will clear the screen.

Anyhow that’s all for this video. I hoped you learned something as well, and thanks for watching!

Shallan mentioned perhaps selling Spiral T-shirts on his Patreon channel. I think it would be cool.

Youtube Description:

Shallan50K on Twitch recently concluded the create a Commodore 64 Spiral challenge. The idea was to write as small a program as you can to create the image displayed. Many people, myself included, spent many hours trying to conquer the problem. Join me to see my solutions as well as the top 5 winning solutions on our corner of the internet.

Sp175 Basic Solution:
6:22

AKMAFIN Basic Solution:
6:54

C64 Praise Be The Spiral!!

Related

Leave a Reply Cancel reply