TheBackShed.com

Forum Index : Microcontroller and PC projects : Programming Challenge - Compressing a Masterpiece

Author

Message

vegipete

Guru

Joined: 29/01/2013
Location: Canada
Posts: 1132

Posted: 04:49am 16 Jun 2022

Copy link to clipboard

Print this post

I pondered earlier if I should offer some hints and techniques I've used for compressing a program. I've decided to do just that here. Perhaps it will be of interest to some.

As an aside, I will point out that, in my opinion, contests like this do NOT encourage good program style. A heavily compressed program becomes a largely incomprehensible blob of characters. Yes, the MMBasic challenge rewards points for legibility, but my personal goal is to get as close to zero in that category as possible. Instead, I want to jam as much in there as possible for maximum wow factor.

(Also, my preference is to write code using a text editor on a windoze box. Notepad++ works well for me, and includes extra features such as character and word counting, advanced search and replace and other useful tools. Another useful setting is terminating lines with a single [CR] character instead of the common [CR][LF]. This saves as many characters as there are lines in your program.)
=============
I see a few avenues for code compaction:
1) Remove unnecessary characters - this has a few stages.
A: all unnecessary white space gone
B: all names squashed to 1 character, 2 if alphabet gets fully used.
C: combine repeated statements and initialize when defined.
D: change longer identifiers to something shorter ie, use 800 instead MM.HRES if useful, and
if 800 appears many times, assign it to a variable, say, e=800. This turns MM.HRES into a
single character. Program maintenance goes out the window, but that's the price you pay.
E: comments gone - yikes!
2) Remove duplicated code
Turn repeated code into subroutines so it only appears once. If code sections are almost
the same, use double subroutines. Also, move single use subroutines in line.
3) Improve data storage with algorithm changes.
Although not applied to the above bouncing ball program, a good possibility involves
the drawing of the steps. The data statements for each step appear in lines 25 to 80
(859 characters worth,) giving the 4 corners of each step. However, each step is exactly
the same size. So instead, the step location data, lines 187 to 200, could be used to draw
a step at each required location.
4) Use subtle MMBasic quirks to trim a few more characters.
This one requires experimentation. For example, changing FUNCTIONs to SUBroutines can save
a bunch of space. Variables can be returned by reference if used carefully, with 9 characters
saved between FUNCTION D(x,y):D=x+y:END FUNCTION compared to SUB D r,x,y:r=x+y:END SUB
(Watch out for variable type, though.)

So, consider the program that appears at the bottom, written for the CMM2. It's some 4722
characters long over 242 lines.

It shrinks as follows after the first few steps above:
1A) - 4336 characters, 216 lines
1B) - 4065 characters, 216 lines
1C) - 3347 characters, 113 lines - combining DATA statements
1D) - not done, however example use g=rgb(lightgrey)
1E) - 2301 characters, 91 lines
2) - 1904 characters, 70 lines - change read data loops to subroutine

The resulting programs at these stages is contained in this zip file.
As you can see, the program shortens dramatically, but legibility and maintainability
pretty much vanish out the window.

I can't say for sure as I didn't finish the program before compression started, but my "Stellar Battle in the 7 Green Hills Zone" entry could have been approaching the 20,000 character size. Some serious squashing was called for and there has since been even more so that an onscreen title might yet be possible.

'autosave "test01.bas"
' Follow the Bouncing Ball
' It's a long way to the bottom. Will the ball every get there?
'
' by Vegipete, June 2022

option default integer
dim xp(20),yp(20)

xoffset = 100 ' shift the image towards center - bottom of screen
yoffset = 200

' Create the ball on page 2
page write 2 : cls
for i = 0 to 5
circle 100-1.5*i,100-2*i,34-3*i,1,1,rgb(0,32*(i+2),0),rgb(0,32*(i+2),0)
next i

' Put ball image into a BLIT slot
blit read 1,65,65,70,70

' Draw the staircase on page 2
cls
' steps, counterclockwise starting a farthest (highest on screen)
data 391, 68 ' 1
data 454, 37
data 391, 6
data 328, 37
data 328, 86 ' 2
data 391, 55
data 328, 24
data 265, 55
data 265,104 ' 3
data 328, 73
data 265, 42
data 202, 73
data 202,122 ' 4
data 265, 91
data 202, 60
data 139, 91
data 139,140 ' 5
data 202,109
data 139, 78
data 76,109
data 76,158 ' 6
data 139,127
data 76, 96
data 13,127
data 139,176 ' 7
data 202,145
data 139,114
data 76,145
data 202,194 ' 8
data 265,163
data 202,132
data 139,163
data 265,212 ' 9
data 328,181
data 265,150
data 202,181
data 328,230 ' 10
data 391,199
data 328,168
data 265,199
data 391,248 ' 11
data 454,217
data 391,186
data 328,217
data 454,203 ' 12
data 517,172
data 454,141
data 391,172
data 517,158 ' 13
data 580,127
data 517, 96
data 454,127
data 454,113 ' 14
data 517, 82
data 454, 51
data 391, 82

' read each step and draw it in visibility order
for j = 1 to 14
for i = 0 to 3
read xp(i),yp(i)
next i
math add xp(),xoffset,xp()
math add yp(),yoffset,yp()
polygon 4,xp(),yp(),,0
next j

' Draw the walls under the steps
' outer left face
data 13,176
data 13,127 ' +31
data 76,158 ' -13
data 76,145 ' +31
data 139,176 ' -13
data 139,163 ' +31
data 202,194 ' -13
data 202,181 ' +31
data 265,212 ' -13
data 265,199 ' +31
data 328,230 ' -13
data 328,217 ' +31
data 391,248 ' -13
data 391,365

for i = 0 to 13
read xp(i),yp(i)
next i

math add xp(),xoffset,xp()
math add yp(),yoffset,yp()
polygon 14,xp(),yp(),,rgb(lightgrey)

' outer right face
data 391,365
data 391,248
data 454,217
data 454,203
data 517,172
data 517,158
data 580,127
data 580,271

for i = 0 to 7
read xp(i),yp(i)
next i

math add xp(),xoffset,xp()
math add yp(),yoffset,yp()
polygon 8,xp(),yp(),,rgb(grey)

' inner left face
data 454, 37
data 391, 68
data 391, 55
data 328, 86
data 328, 73
data 265,104
data 265, 91
data 202,122
data 202,109
data 165,127
data 188,138
data 202,132
data 251,156
data 265,150
data 314,174
data 328,168
data 377,192
data 391,186
data 391, 82
data 454, 51

for i = 0 to 19
read xp(i),yp(i)
next i

math add xp(),xoffset,xp()
math add yp(),yoffset,yp()
polygon 20,xp(),yp(),,rgb(grey)

' face of last step
data 454,113
data 517, 82
data 517, 96
data 454,127

for i = 0 to 3
read xp(i),yp(i)
next i

math add xp(),xoffset,xp()
math add yp(),yoffset,yp()
polygon 4,xp(),yp(),,rgb(grey)

' inner right wall
pixel fill 444+xoffset,113+yoffset,rgb(lightgrey)

' face of 12th step
pixel fill 444+xoffset,203+yoffset,rgb(lightgrey)

' step location - where the ball will bonce
' bottom center corner on screen
data 391, 68 ' 1
data 328, 86 ' 2
data 265,104 ' 3
data 202,122 ' 4
data 139,140 ' 5
data 76,158 ' 6
data 139,176 ' 7
data 202,194 ' 8
data 265,212 ' 9
data 328,230 ' 10
data 391,248 ' 11
data 454,203 ' 12
data 517,158 ' 13
data 454,113 ' 14

for i = 0 to 13
read xp(i),yp(i) ' read the location of each step
next i

math add xp(),xoffset-40,xp()
math add yp(),yoffset-96,yp()

thisstep = 13 ' start the ball on 'last' step
xstart = xp(thisstep)
ystart = yp(thisstep)
thisstep = thisstep - 1
xend = xp(thisstep)
yend = yp(thisstep)

page write 1

' animate the ball
do ' loop from step to step
xrange = xend - xstart ' calculate ball base position from this step to the next
yrange = yend - ystart
xmid = (xend + xstart) / 2 ' find middle
for i = xstart to xend step sgn(xrange) ' move x postion from start to end
' y position is somewhere along path, elevated with a parabolic arc
DrawBall i,ystart + yrange * (i - xstart) / xrange - 171 + (i - xmid) ^ 2 / 6
next i
' finished this hop so figure out end points of next hop
xstart = xend
ystart = yend
thisstep = thisstep - 1 ' advance to next step, wrap if required
if thisstep < 0 then thisstep = 13
xend = xp(thisstep)
yend = yp(thisstep)
loop

' Redraw entire image with ball at requested location
sub DrawBall x,y
cls
page copy 2,1
blit write 1,x,y,4
page copy 1,0,B
end sub

Visit Vegipete's *Mite Library for cool programs.

Volhout
Guru

Joined: 05/03/2018
Location: Netherlands
Posts: 5089

Posted: 07:41pm 17 Jun 2022

Copy link to clipboard

Print this post

Hi Vegipete,

Thanks for sharing. This will be of interest to people that are still crunching their contribution for the programming challenge....
And I learned some things also...

Volhout

PicomiteVGA PETSCII ROBOTS

Mindwarp

Newbie

Joined: 13/02/2021
Location: Canada
Posts: 29

Posted: 11:38pm 17 Jun 2022

Copy link to clipboard

Print this post

That's a great guide, thanks!

Print this page

To reply to this topic, you need to log in.