| | WVL
Registered: Mar 2002
Posts: 888 |
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: 888 |
ofcourse i could put 2 bytes in just one, but that would slow down things a lot.. I have to fetch 45 of these bytes, and the only fast way would be to use tables, which is not really memory efficient ;) |
| | WVL
Registered: Mar 2002
Posts: 888 |
for those who are interested :
my program looks like :
//-------------------------------------------
#include <stdio.h>
#include <fstream.h>
#include <stdlib.h>
#include <math.h>
int main(int argc, char *argv[])
{
int numberofchars;
int sortarray [256][256];
int sortarraycopy [256][256];
int sortarray2 [256][256];
int charset [256*8];
int solution [256];
int bestsolution [256];
int bin [256*8];
int checkeduntil [256];
int pointers [256];
bool present;
FILE *in;
FILE *out;
//input charsetdata
int counter=0;
int inputbyte=0;
in = fopen ("CHARSET.PRG","rb"); // open charset
fgetc(in); // load adress
fgetc(in);
while(feof(in)==0) {
charset[counter]=fgetc(in);
counter++;
}
numberofchars = counter/8;
cout << numberofchars << " chars read." << endl;
fclose(in); // close stream
// calculate overlap for all char-pairs
cout << "calculating overlap matrix";
int char1,char2,overlap,maxoverlap;
bool overlapping;
for (char1=0;char1<numberofchars;char1++){
for (char2=0;char2<numberofchars;char2++){
// calculate overlap for char pair
maxoverlap=0;
for (overlap=7;overlap>0;overlap--){
overlapping=true;
for (counter=0;counter<overlap;counter++){
if (charset[char1*8+(8-overlap+counter)]!=charset[char2*8+counter]) {
overlapping=false;
} // if
} // for
if (overlapping==true && overlap>maxoverlap) {maxoverlap=overlap;}
} // for overlap
sortarray[char1][char2]=maxoverlap;
sortarraycopy[char1][char2]=maxoverlap;
}//for char2
if (char1 % 16==0) {cout << ".";}
}//for char1
cout << endl;
//-----------------
// sort char-pairs-
//-----------------
cout << "Sorting overlap values." << endl;
int occurances [8];
int char3,counter2,counter3;
int random;
for (char1=0;char1<numberofchars;char1++){
//-------------------------------------------------
// count how many times a certain overlap occurs -
//-------------------------------------------------
for (counter=0;counter<8;counter++) {occurances[counter]=0;} // clear overlap occurances table
for (char2=0;char2<numberofchars;char2++){
occurances[sortarray[char1][char2]]++;
} // for char2
// starting with overlap=7, select a random char with that overlap and store it in sortarray2
counter2=0;
for (overlap=7;overlap>-1;overlap--){ // all overlaps from 7 to 0
for (counter=0;occurances[overlap]>0;occurances[overlap]--){ // fetch n chars
// fetch a random char with this occurance
random = (int) ( ( (double)rand() / (double)(RAND_MAX+1) ) * occurances[overlap]);
for (counter3=0;counter3<numberofchars;counter3++){ // get the nth char with correct overlap
if (sortarraycopy[char1][counter3]==overlap) {
if (random==0) {char2=counter3; counter3=numberofchars;}
random--;
} // if
} // for counter3
sortarray2[char1][counter2]=char2; // store fetched char
counter2++;
sortarraycopy[char1][char2]=-1;
} // for counter // fetch another char
} // for overlap // next overlap
} // for char1 // all char-pairs
// go through permutations...
int savedbytes;
int maxsavedbytes = 0;
int usedchars [256];
int usedchars2 [256];
int runs = 0;
int charsleft;
int orderedchars[256];
int solcount=0;
int bytes,minbytes;
cout << "Finding optimum solution..." << endl;
while (1){
for (counter=0;counter<numberofchars;counter++){
//usedchars[counter]=counter;
usedchars2[counter]=0;
checkeduntil[counter]=0;} // clear used chars
runs++;
savedbytes=0;
minbytes=0;
charsleft=numberofchars-1;
// pick a random char to start with
char1= (int) ( (double)rand()/(double)(RAND_MAX+1) * numberofchars);
for (counter=0;counter<8;counter++){bin[bytes+counter]=charset[char1*8+counter];}; // add char to bin
pointers[char1]=0;
bytes=8;
solution[0]=char1;
solcount=1;
// we used that char...
usedchars2[char1]=1;
//for (counter=char1;counter<charsleft;counter++){usedchars[counter]=usedchars[counter +1];} // for
// pick another char, randomly weighted
while (charsleft>0){
// make sorted table of all chars that are left
counter2=0;
for (counter=0;counter<numberofchars;counter++){
if (usedchars2[ (sortarray2[char1][counter]) ]==0){
orderedchars[counter2]=sortarray2[char1][counter];
counter2++;
} // if
} // for
random = (int) ( (pow( ((double)rand()/(double)(RAND_MAX+1) ),100)) * (charsleft/4));
char2 = orderedchars[random];
solution[solcount]=char2;
solcount++;
pointers[char2]=bytes-sortarray[char1][char2];
usedchars2[char2]=1;
charsleft--;
//for (counter=char2;counter<charsleft;counter++){usedchars[counter]=usedchars[counter +1];} // for
for (counter=sortarray[char1][char2];counter<8;counter++){ //store extra bytes in bin
bin[bytes+counter]=charset[char2*8+counter+sortarray[char1][char2]];
} // for
bytes+=(8-sortarray[char1][char2]); //extra bytes - overlapping bytes
savedbytes+=(sortarray[char1][char2]);
char1=char2;
// check if we can fit one of the left chars in the bin
for(counter=0;counter<numberofchars;counter++){ // check all left chars
if (!usedchars2[counter]){
for (counter2=checkeduntil[counter];counter2<bytes-7;counter2++){ // check whole bin
present=true;
for (counter3=0;counter3<8;counter3++){ // check 8 bytes in char
if (bin[counter2+counter3]!=charset[counter*8+counter3]){
present=false;
counter3=8; // stop checking..
} // if
} //for counter3
if (present){
savedbytes+=8; // 8 bytes saved
usedchars2[counter]=1; // mark char as checked
solution[solcount]=-counter; //store in solution
solcount++;
charsleft--; // one char less
counter2=bytes; // stop looking for this char
pointers[counter]=counter2;
//for (counter3=counter;counter3<charsleft;counter3++){usedchars[counter3]=usedchars[c ounter3+1];} // for
} // if present
} // for counter2
checkeduntil[counter]=bytes-8;
} // if
} // for counter
} // while
if (savedbytes>maxsavedbytes) {
maxsavedbytes=savedbytes;
cout << "best solution after " << runs << " permutations, saving " << maxsavedbytes << " bytes" << endl;
for (counter=0;counter<numberofchars;counter++){
bestsolution[counter]=solution[counter];
}
//--------------------------------------------------------------------
// check solution for correctness!
savedbytes=0;
for (counter=0;counter<numberofchars;counter++){usedchars[counter]=0;}
for (counter=0;counter<numberofchars;counter++){
if (usedchars[abs( bestsolution[counter] )]) {cout << "ERROR! CHARS DOUBLE! : " << bestsolution[counter] << endl;}
usedchars[abs(bestsolution[counter])]=1;
if (counter>0) {
if (bestsolution[counter]<0) {savedbytes+=8;}
else {savedbytes+=sortarray[char2][bestsolution[counter]];}
} // if
if (bestsolution[counter]>-1){char2=bestsolution[counter];} // put last attached byte in char2
} // for
if (savedbytes!=maxsavedbytes){cout << "ERROR! #saved bytes not correct! : " << savedbytes << ", " << bytes << endl;}
//---------------------------------------------------------------------
// write solution
out=fopen("solution.txt","w");
fputs(";pointer table for clip chars\n\nclipcharslow\n",out);
//-------------------------
// output pointer table -
//-------------------------
charsleft=numberofchars;
counter=0;
while (charsleft>0){
if(counter%8==0){fputs(" .byte ",out);}
fputs("<(clipcharsdata+",out);
fprintf(out,"%i)",pointers[counter]);
if (pointers[counter]<100){fputs(" ",out);}
if (pointers[counter]<10){fputs(" ",out);}
charsleft--;
counter++;
if(counter%8==0){
fputs("\n",out);
}//if
else{
if(charsleft>0) {fputs(",",out);}
else {fputs("\n",out);}
}// else
} // while charsleft
fputs("\n",out);
//---------------------
// output pointerhigh -
//---------------------
fputs("clipcharshigh\n",out);
charsleft=numberofchars;
counter=0;
while (charsleft>0){
if(counter%8==0){fputs(" .byte ",out);}
fputs(">(clipcharsdata+",out);
fprintf(out,"%i)",pointers[counter]);
if (pointers[counter]<100){fputs(" ",out);}
if (pointers[counter]<10){fputs(" ",out);}
charsleft--;
counter++;
if(counter%8==0){
fputs("\n",out);
}//if
else{
if(charsleft>0) {fputs(",",out);}
else {fputs("\n",out);}
}// else
} // while charsleft
fputs("\nclipcharsdata\n",out);
//----------------------
// output charsetdata -
//----------------------
counter=0;
while(counter<bytes){
if(counter%32==0){fputs(" .byte ",out);}
fprintf(out,"%i",bin[counter]);
if (bin[counter]<100){fputs(" ",out);}
if (bin[counter]<10){fputs(" ",out);}
counter++;
if(counter%32==0){
fputs("\n",out);
}//if
else{
if(counter<bytes) {fputs(",",out);}
else {fputs("\n",out);}
}// else
} // while
fputs("\n",out);
fclose(out);
//---------------------------------------------------------------------
} // if
} // while
// output best solution
cout << "Best solution found :" << endl << bestsolution[0];
for (counter=1;counter<numberofchars;counter++){cout << "," << bestsolution[counter];}
cout << endl;
return 0;
}
//-----------------------------------------------------
giving a solution which looks like
;pointer table for clip chars
clipcharslow
.byte <(clipcharsdata+102),<(clipcharsdata+32) ,<(clipcharsdata+187),<(clipcharsdata+98) ,<(clipcharsdata+274),<(clipcharsdata+54) ,<(clipcharsdata+69) ,<(clipcharsdata+454)
.byte <(clipcharsdata+79) ,<(clipcharsdata+150),<(clipcharsdata+149),<(clipcharsdata+144),<(clipcharsdata+ 5) ,<(clipcharsdata+223),<(clipcharsdata+537),<(clipcharsdata+208)
.byte <(clipcharsdata+108),<(clipcharsdata+64) ,<(clipcharsdata+657),<(clipcharsdata+167),<(clipcharsdata+117),<(clipcharsdata+ 115),<(clipcharsdata+522),<(clipcharsdata+55)
.byte <(clipcharsdata+225),<(clipcharsdata+158),<(clipcharsdata+610),<(clipcharsdata+6 1) ,<(clipcharsdata+233),<(clipcharsdata+6) ,<(clipcharsdata+160),<(clipcharsdata+31)
.byte <(clipcharsdata+410),<(clipcharsdata+334),<(clipcharsdata+467),<(clipcharsdata+2 85),<(clipcharsdata+310),<(clipcharsdata+104),<(clipcharsdata+641),<(clipcharsda ta+65)
.byte <(clipcharsdata+106),<(clipcharsdata+67) ,<(clipcharsdata+113),<(clipcharsdata+70) ,<(clipcharsdata+203),<(clipcharsdata+219),<(clipcharsdata+75) ,<(clipcharsdata+212)
.byte <(clipcharsdata+318),<(clipcharsdata+25) ,<(clipcharsdata+377),<(clipcharsdata+152),<(clipcharsdata+268),<(clipcharsdata+ 123),<(clipcharsdata+180),<(clipcharsdata+420)
.byte <(clipcharsdata+567),<(clipcharsdata+463),<(clipcharsdata+10) ,<(clipcharsdata+374),<(clipcharsdata+262),<(clipcharsdata+573),<(clipcharsdata+ 201),<(clipcharsdata+417)
.byte <(clipcharsdata+62) ,<(clipcharsdata+74) ,<(clipcharsdata+335),<(clipcharsdata+19) ,<(clipcharsdata+28) ,<(clipcharsdata+0) ,<(clipcharsdata+137),<(clipcharsdata+135)
.byte <(clipcharsdata+220),<(clipcharsdata+194),<(clipcharsdata+27) ,<(clipcharsdata+384),<(clipcharsdata+4) ,<(clipcharsdata+41) ,<(clipcharsdata+139),<(clipcharsdata+503)
.byte <(clipcharsdata+35) ,<(clipcharsdata+529),<(clipcharsdata+1) ,<(clipcharsdata+48) ,<(clipcharsdata+46) ,<(clipcharsdata+44) ,<(clipcharsdata+391),<(clipcharsdata+3)
.byte <(clipcharsdata+143),<(clipcharsdata+339),<(clipcharsdata+438),<(clipcharsdata+5 44),<(clipcharsdata+215),<(clipcharsdata+551),<(clipcharsdata+278),<(clipcharsda ta+14)
.byte <(clipcharsdata+406),<(clipcharsdata+633),<(clipcharsdata+665),<(clipcharsdata+2 88),<(clipcharsdata+482),<(clipcharsdata+474),<(clipcharsdata+293),<(clipcharsda ta+224)
.byte <(clipcharsdata+460),<(clipcharsdata+446),<(clipcharsdata+103),<(clipcharsdata+3 14),<(clipcharsdata+349),<(clipcharsdata+90) ,<(clipcharsdata+244),<(clipcharsdata+33)
.byte <(clipcharsdata+321),<(clipcharsdata+625),<(clipcharsdata+353),<(clipcharsdata+2 55),<(clipcharsdata+257),<(clipcharsdata+329),<(clipcharsdata+327),<(clipcharsda ta+238)
.byte <(clipcharsdata+251),<(clipcharsdata+617),<(clipcharsdata+398),<(clipcharsdata+3 23),<(clipcharsdata+356),<(clipcharsdata+246),<(clipcharsdata+361),<(clipcharsda ta+490)
.byte <(clipcharsdata+84) ,<(clipcharsdata+589),<(clipcharsdata+597),<(clipcharsdata+509),<(clipcharsdata+ 305),<(clipcharsdata+559),<(clipcharsdata+344),<(clipcharsdata+428)
.byte <(clipcharsdata+9) ,<(clipcharsdata+496),<(clipcharsdata+433),<(clipcharsdata+175),<(clipcharsdata+ 603),<(clipcharsdata+516),<(clipcharsdata+450),<(clipcharsdata+125)
.byte <(clipcharsdata+235),<(clipcharsdata+649),<(clipcharsdata+151),<(clipcharsdata+2 27),<(clipcharsdata+419),<(clipcharsdata+289),<(clipcharsdata+298),<(clipcharsda ta+209)
.byte <(clipcharsdata+191),<(clipcharsdata+442),<(clipcharsdata+72) ,<(clipcharsdata+193),<(clipcharsdata+93) ,<(clipcharsdata+581),<(clipcharsdata+368),<(clipcharsdata+131)
.byte <(clipcharsdata+30)
clipcharshigh
.byte >(clipcharsdata+102),>(clipcharsdata+32) ,>(clipcharsdata+187),>(clipcharsdata+98) ,>(clipcharsdata+274),>(clipcharsdata+54) ,>(clipcharsdata+69) ,>(clipcharsdata+454)
.byte >(clipcharsdata+79) ,>(clipcharsdata+150),>(clipcharsdata+149),>(clipcharsdata+144),>(clipcharsdata+ 5) ,>(clipcharsdata+223),>(clipcharsdata+537),>(clipcharsdata+208)
.byte >(clipcharsdata+108),>(clipcharsdata+64) ,>(clipcharsdata+657),>(clipcharsdata+167),>(clipcharsdata+117),>(clipcharsdata+ 115),>(clipcharsdata+522),>(clipcharsdata+55)
.byte >(clipcharsdata+225),>(clipcharsdata+158),>(clipcharsdata+610),>(clipcharsdata+6 1) ,>(clipcharsdata+233),>(clipcharsdata+6) ,>(clipcharsdata+160),>(clipcharsdata+31)
.byte >(clipcharsdata+410),>(clipcharsdata+334),>(clipcharsdata+467),>(clipcharsdata+2 85),>(clipcharsdata+310),>(clipcharsdata+104),>(clipcharsdata+641),>(clipcharsda ta+65)
.byte >(clipcharsdata+106),>(clipcharsdata+67) ,>(clipcharsdata+113),>(clipcharsdata+70) ,>(clipcharsdata+203),>(clipcharsdata+219),>(clipcharsdata+75) ,>(clipcharsdata+212)
.byte >(clipcharsdata+318),>(clipcharsdata+25) ,>(clipcharsdata+377),>(clipcharsdata+152),>(clipcharsdata+268),>(clipcharsdata+ 123),>(clipcharsdata+180),>(clipcharsdata+420)
.byte >(clipcharsdata+567),>(clipcharsdata+463),>(clipcharsdata+10) ,>(clipcharsdata+374),>(clipcharsdata+262),>(clipcharsdata+573),>(clipcharsdata+ 201),>(clipcharsdata+417)
.byte >(clipcharsdata+62) ,>(clipcharsdata+74) ,>(clipcharsdata+335),>(clipcharsdata+19) ,>(clipcharsdata+28) ,>(clipcharsdata+0) ,>(clipcharsdata+137),>(clipcharsdata+135)
.byte >(clipcharsdata+220),>(clipcharsdata+194),>(clipcharsdata+27) ,>(clipcharsdata+384),>(clipcharsdata+4) ,>(clipcharsdata+41) ,>(clipcharsdata+139),>(clipcharsdata+503)
.byte >(clipcharsdata+35) ,>(clipcharsdata+529),>(clipcharsdata+1) ,>(clipcharsdata+48) ,>(clipcharsdata+46) ,>(clipcharsdata+44) ,>(clipcharsdata+391),>(clipcharsdata+3)
.byte >(clipcharsdata+143),>(clipcharsdata+339),>(clipcharsdata+438),>(clipcharsdata+5 44),>(clipcharsdata+215),>(clipcharsdata+551),>(clipcharsdata+278),>(clipcharsda ta+14)
.byte >(clipcharsdata+406),>(clipcharsdata+633),>(clipcharsdata+665),>(clipcharsdata+2 88),>(clipcharsdata+482),>(clipcharsdata+474),>(clipcharsdata+293),>(clipcharsda ta+224)
.byte >(clipcharsdata+460),>(clipcharsdata+446),>(clipcharsdata+103),>(clipcharsdata+3 14),>(clipcharsdata+349),>(clipcharsdata+90) ,>(clipcharsdata+244),>(clipcharsdata+33)
.byte >(clipcharsdata+321),>(clipcharsdata+625),>(clipcharsdata+353),>(clipcharsdata+2 55),>(clipcharsdata+257),>(clipcharsdata+329),>(clipcharsdata+327),>(clipcharsda ta+238)
.byte >(clipcharsdata+251),>(clipcharsdata+617),>(clipcharsdata+398),>(clipcharsdata+3 23),>(clipcharsdata+356),>(clipcharsdata+246),>(clipcharsdata+361),>(clipcharsda ta+490)
.byte >(clipcharsdata+84) ,>(clipcharsdata+589),>(clipcharsdata+597),>(clipcharsdata+509),>(clipcharsdata+ 305),>(clipcharsdata+559),>(clipcharsdata+344),>(clipcharsdata+428)
.byte >(clipcharsdata+9) ,>(clipcharsdata+496),>(clipcharsdata+433),>(clipcharsdata+175),>(clipcharsdata+ 603),>(clipcharsdata+516),>(clipcharsdata+450),>(clipcharsdata+125)
.byte >(clipcharsdata+235),>(clipcharsdata+649),>(clipcharsdata+151),>(clipcharsdata+2 27),>(clipcharsdata+419),>(clipcharsdata+289),>(clipcharsdata+298),>(clipcharsda ta+209)
.byte >(clipcharsdata+191),>(clipcharsdata+442),>(clipcharsdata+72) ,>(clipcharsdata+193),>(clipcharsdata+93) ,>(clipcharsdata+581),>(clipcharsdata+368),>(clipcharsdata+131)
.byte >(clipcharsdata+30)
clipcharsdata
.byte 51 ,243,243,48 ,48 ,243,243,51 ,15 ,3 ,3 ,255,255,255,63 ,255,255,255,255,255,15 ,0 ,192,192,192,192,240,252,252,252,255,255
.byte 255,0 ,0 ,255,15 ,0 ,192,192,240,192,0 ,0 ,252,255,255,255,255,255,63 ,255,252,255,255,63 ,15 ,255,255,63 ,255,63 ,15 ,3
.byte 63 ,63 ,63 ,15 ,15 ,0 ,255,255,255,255,255,192,192,192,0 ,0 ,0 ,252,240,15 ,15 ,15 ,63 ,3 ,0 ,0 ,243,243,240,192,240,240
.byte 252,252,195,195,243,243,207,207,252,252,255,255,255,0 ,255,255,255,255,0 ,0 ,3 ,63 ,3 ,0 ,0 ,3 ,3 ,3 ,0 ,252,3 ,255
.byte 255,255,255,0 ,0 ,192,240,255,255,255,255,255,255,15 ,3 ,252,252,252,255,255,255,255,3 ,0 ,255,255,255,0 ,0 ,255,255,255
.byte 15 ,0 ,255,255,255,255,3 ,3 ,15 ,0 ,0 ,0 ,0 ,0 ,15 ,207,207,207,15 ,15 ,0 ,0 ,0 ,0 ,0 ,3 ,60 ,63 ,0 ,15 ,63 ,15
.byte 15 ,15 ,15 ,255,0 ,63 ,255,240,240,240,240,0 ,0 ,0 ,0 ,0 ,0 ,252,252,195,243,0 ,192,192,252,252,240,255,63 ,63 ,63 ,255
.byte 0 ,15 ,15 ,3 ,3 ,3 ,15 ,3 ,252,15 ,15 ,3 ,0 ,255,255,255,255,255,255,255,63 ,255,255,0 ,240,252,252,255,255,255,0 ,0
.byte 0 ,15 ,195,63 ,15 ,15 ,255,15 ,195,195,240,0 ,0 ,0 ,63 ,63 ,15 ,63 ,255,255,63 ,255,0 ,0 ,0 ,0 ,255,255,63 ,255,0 ,3
.byte 0 ,0 ,0 ,0 ,0 ,255,255,252,15 ,15 ,252,252,252,255,255,255,195,195,240,15 ,63 ,63 ,255,255,255,204,240,240,63 ,63 ,252,252
.byte 252,243,207,207,207,207,192,240,240,252,207,195,15 ,15 ,204,255,255,255,243,255,63 ,63 ,255,252,240,0 ,0 ,0 ,0 ,0 ,207,207
.byte 243,243,243,207,207,243,243,243,63 ,63 ,15 ,15 ,195,192,240,12 ,204,192,252,204,252,252,255,255,207,192,0 ,0 ,0 ,0 ,252,252
.byte 255,63 ,15 ,3 ,192,240,252,255,252,255,63 ,15 ,195,240,252,192,240,243,195,195,195,195,192,192,192,192,0 ,0 ,0 ,0 ,0 ,207
.byte 207,243,63 ,0 ,0 ,0 ,0 ,0 ,0 ,63 ,63 ,15 ,243,243,243,0 ,0 ,243,243,243,255,0 ,0 ,0 ,0 ,207,207,207,240,240,0 ,15
.byte 255,0 ,3 ,3 ,3 ,3 ,252,252,252,252,255,255,255,255,15 ,15 ,255,255,255,255,240,240,255,255,252,252,192,15 ,12 ,0 ,0 ,0
.byte 15 ,15 ,60 ,252,252,252,252,252,252,252,192,192,192,15 ,63 ,63 ,207,207,0 ,15 ,15 ,0 ,0 ,192,243,240,252,252,252,255,255,255
.byte 15 ,60 ,48 ,48 ,51 ,195,63 ,51 ,63 ,63 ,255,255,243,63 ,15 ,63 ,255,255,255,15 ,3 ,195,240,252,252,255,63 ,15 ,15 ,3 ,3 ,0
.byte 0 ,15 ,255,255,255,255,255,255,192,15 ,15 ,15 ,15 ,15 ,0 ,204,207,207,12 ,12 ,207,207,204,3 ,15 ,15 ,63 ,63 ,63 ,63 ,63 ,252
.byte 252,0 ,0 ,0 ,0 ,207,207,207,0 ,0 ,207,207,204,240,192,0 ,15 ,63 ,255,207,207,3 ,3 ,3 ,240,252,252,243,243,255,243,240
.byte 0 ,0 ,3 ,51 ,15 ,15 ,15 ,63 ,63 ,63 ,63 ,15 ,15 ,195,195,195,195,240,195,195,15 ,15 ,63 ,63 ,255,60 ,60 ,60 ,252,60 ,60 ,60
.byte 60 ,240,192,0 ,0 ,0 ,0 ,0 ,0 ,243,243,243,0 ,0 ,243,243,51 ,192,192,192,192,192,192,192,192,12 ,12 ,12 ,12 ,0 ,0 ,0
.byte 0
|
| | WVL
Registered: Mar 2002
Posts: 888 |
erh..
taking a closer look the solution doesnt seem to be correct.. well, have to do some bug hunting then :)
bin[bytes+counter-(sortarray[char1][char2])]=charset[char2*8+counter];
this is the correct line, instead of the one in the source above.. |
| | Cruzer
Registered: Dec 2001
Posts: 1048 |
Damn that looks ugly w/o tabs... My eyes hurt! |
| | WVL
Registered: Mar 2002
Posts: 888 |
LOL ;) yeah.. csdb doesn't support extra whitespace :D well.. whatever :) anyway, in the above code there still is one bug, which i'll leave in there right now ;) it has something to do with the addition of the first char to the bin.
also, i just imported one of the solutions into my sourcecode for PD64 and it seems to be working quite nicely :) |
| | Hoogo
Registered: Jun 2002
Posts: 103 |
All in all you cut a bitmap of 160*400 pixels into pieces of 4*8 pixels, puzzle these chunks, create a map and compress that map with RLE.
How about cutting it into lines (160*1), doing the puzzle-thing with that lines, after that cuttingthe lines into independent zero- and 1bits and then try a huffman on that (a bit like Telefax)?
0000001111110000 => 3 demo-lines
0000111111000000
0011111100000000
00.00.0011111100000000 => puzzled, beginnings are marked
3*00 =%0 => Huffmann-Tree
1*111111 =%100
1*00000000 =%101
=%000100101 (+pointers for each of the 400 lines)
AS it is used for a clipmap it might even be handy to adress lines instead of chars, but I find it hard to say if you save memory at the end |
| | WVL
Registered: Mar 2002
Posts: 888 |
bit-operations? YUCK :)) slooooow!
the idea is to have a well-crunched map that can be quickly randomly accessed => no bit operations :) |
| | Hoogo
Registered: Jun 2002
Posts: 103 |
And how about a kind of RLE (counting zero- /bits)? $07 = 7 Bits are zero, $8a = 10 bits are set? How many changes do You have each line?
And wasn't there a gravity-map, too? |
| | WVL
Registered: Mar 2002
Posts: 888 |
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. |
| Previous - 1 | 2 | 3 | 4 | 5 - Next | |
