| |
WVL
Registered: Mar 2002
Posts: 889 |
WVL/Xenon's challenge!
A small challenge for all coders out there.
first let me explain how i got here. As most of you will know i'm working on a c64 conversion of Pinball Dreams. And as some will know, i'm rather stumbling on the 64K memory limit. So I'm always puzzling and optimizing to free up some more memory.
This morning i got an idea to optimize the way the clipmap data is stored. (what is the clipmap, you might ask? it's a black/white map that describes where the ball goes behind objects on the table).
Now this clipmap is stored as a 40*64 charscreen (RLE-ed) and a charset (lucky for me, it fitted in $a1 chars).
The idea comes to letting go of putting the chars at n*8 memory position with n integer and using pointers to point to where the data is to be fetched. The pointers will not costs any memory themselves, as for speed i'm already using a 512 table (lo/hi) with numbers times 8.
;---------------------------------------
so here's my challenge to you all!
;---------------------------------------
try to fit all $a1 chars of this charset : http://www.interstyles.nl/Charset.prg into the minimum amount of bytes you possibly can!
the answer has to be in the following form :
-a pointer table, with $a1 pointers to the positions in the chardata
-a chardata bin, as small as possible.
ofcourse all the chars still have to be made from the pointer table and the bin. All the chars have to lie COMPLETELY inside the bin, don't assume the bytes before or after the bin take on certain values.
Winner gets a beer + a hug if winner is a girl ;-)
regards,
WVL/XENON, who's anxious to win the competition himself ;-) |
|
... 38 posts hidden. Click here to view all posts....
|
| |
WVL
Registered: Mar 2002
Posts: 889 |
there are all kind of maps :) but the gravity-map is mostly unrelated to the clipmap.
RLE-ing a bitmap directly would not work. f.e. i would need at least 512(pixels high) pointers to all the RLE lines, which eats up 1024 bytes already. And i don't have any data yet in that case..
some more explanation about this :
the way i see it the best thing you can do is try to divide the screen up in blocks, so you have as close to 256 different blocks as possible. It turns out that chosing 8x8 blocks gives you $a1 different 'blocks', so imo dividing the bitmap into a charscreen is the most logical solution.
ofcourse the clipmap is completely optimized to take as best advantage as possible from this representation! |
| |
Hoogo
Registered: Jun 2002
Posts: 103 |
If I count it correctly you currently have packed the chars into ~650 Bytes, 2560 Bytes for the charmap (but RLE'd, how much ist it exactly?) + 128 for pointers. Don't know the results for line-wise. 1024 for pointers + x.
Now it depends on how many different lines you have, how good lines can be puzzled, and how good each line can be compressed (how many changes between 0 and 1 there are each line).
And you can maybe use the same system not only for this clipmap, but can add some more bitplanes before compressing it. Depends on your other maps. |
| |
WVL
Registered: Mar 2002
Posts: 889 |
some quick numbers..
compressed charset : 678 bytes
pointers to chars : 322 bytes
RLE-ed screendata+pointers : 1115 bytes
makes 2115 bytes total = $843
not bad for describing a 160*512 b/w bitmap (raw data = 10240 bytes). f.e. the same file as .gif is 4867 bytes. |
| |
Hoogo
Registered: Jun 2002
Posts: 103 |
Is that gif somewhere to download? And what about the other maps?
Its really interesting :-) |
| |
WVL
Registered: Mar 2002
Posts: 889 |
http://www.interstyles.nl/CLIP.gif
it looks a bit insane bcoz of all the RLE optimizations. |
| |
Hoogo
Registered: Jun 2002
Posts: 103 |
Hm, a fast hack (I only removed duplicate lines) without puzzling and the simple counting of 0/1 gives 2.450 Bytes. I doubt that optimizations in the graphic, the puzzling and a fast dictionary compression could press that to less than 1.100 bytes... So this might only be of use if it is used for more than one map (2 maps will turn that from 0/1 to 0..3. That compresses poorer, but the 1024 Bytes pointer are only needed once). |
| |
WVL
Registered: Mar 2002
Posts: 889 |
erh.. but then you have to do RLE decoding for every byte..
I only have to do RLE-decoding for every char (saves a lot of cycles) and then i can fetch data by a simple loop. Also my data is smaller ;) |
| |
TDJ
Registered: Dec 2001
Posts: 1879 |
Quote: erh.. but then you have to do RLE decoding for every byte..
I only have to do RLE-decoding for every char (saves a lot of cycles) and then i can fetch data by a simple loop. Also my data is smaller ;)
Hmm .. normally people just brag about their 'data' being bigger ;) |
| |
Cruzer
Registered: Dec 2001
Posts: 1048 |
Btw, how about enabling backwards fetching of char-gfx from the bin? This shouldn't take many more cycles if you make a dedicated routine for it. The highest bit of the address could indicate if it should be fetched backwards, so it wouldn't mean more lut-data. |
| |
WVL
Registered: Mar 2002
Posts: 889 |
cruzer : that probably wont work very well in my code, that reads from 3 chars at the same time. It's a good idea, but unfortunately a no-no :)
the loop that uses the clipdata looks like :
clipoffset
ldy #0
cliploop
spritea1 lda $1000,x
char1 and $1000,y
point1a sta spriteimage,x
spriteb1 and $1000,x
point2a sta spriteimage2,x
spritec1 and $1000,x
point3a sta spriteimage3,x
dex
spritea2 lda $1000,x
char2 and $1000,y
point1b sta spriteimage,x
spriteb2 and $1000,x
point2b sta spriteimage2,x
spritec2 and $1000,x
point3b sta spriteimage3,x
dex
spritea3 lda $1000,x
char3 and $1000,y
point1c sta spriteimage,x
spriteb3 and $1000,x
point2c sta spriteimage2,x
beq point3c
spritec3 and $1000,x
point3c sta spriteimage3,x
dex
bmi endclip
dey
bpl cliploop
lda #7
sta clipoffset+1
bne bigcliploop
endclip
char1/char2/char3 pointing to 3 different chars in the clipmap.
I was thinking of improving the search routine a bit, so it would also search in the bitmap-gfx for finding certain patterns... |
| Previous - 1 | 2 | 3 | 4 | 5 - Next |
