| | WVL
Registered: Mar 2002
Posts: 902 |
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 ;-) |
|
| | Cruzer
Registered: Dec 2001
Posts: 1048 |
How about something like this...
for each char (x)
....for each char (y)
........for each char (z)
............if (the gfx of x is within the gfx of the (y,z) or (z,y) combination)
............then store the z/y data, and the pointers to x/y/z
........if (there were no hits)
............check if x's gfx is within the allready stored char gfx
................if yes, store the pointer to it
................else store x's gfx and the pointer to it
|
| | Cruzer
Registered: Dec 2001
Posts: 1048 |
It would be nice if the <code> or <pre> tag was enabled btw. |
| | WVL
Registered: Mar 2002
Posts: 902 |
I'm already doing something like that, but more random. The thing is that the search space is just overwhelmingly large, imo about 16^640.
So far i managed to remove 630 bytes from the bin, not counting the pointertables.
I really wonder if other ppl will be able to do it better :) (btw, searching for 630 cost me about 3 hours on a athlon 2800+) |
| | Cruzer
Registered: Dec 2001
Posts: 1048 |
where do you get that 16^640 from? Guess you must do something completely different than my pseudo-code, since as far as I can see, it only runs through the inner loop $a1^3 times. |
| | WVL
Registered: Mar 2002
Posts: 902 |
I'm just estimating the smallest bin is around 640 bytes long. Now i don't use every byte, but i only turn bit-pairs on/off. -> 16 possibilities for each byte. giving a total of 16^640.
ofcourse i don't hunt through it like this, instead i try to put the chars in different order, so i try $a1! permutations. The chars are chosen randomly, but weighted towards more overlapping bytes (the code generates a 2d table with the # of overlapping bytes for each char-pair). During generation of a permutation, it is constantly being checked if any of the other left chars have a match in the final bin.
So _my_ search space is $a1!, but i guess to find the optimal solution, one would have to search through 16^640. |
| | Graham
Account closed
Registered: Dec 2002
Posts: 990 |
cruzer: theoretically you have to check all permutations of the order of those 161 chars. that gives you a search space of 161! = 7.6*10^286 permutations. your routine has a much better big-O performance because it does only search a small fraction of the permutations and will most likely give worse results. |
| | Cruzer
Registered: Dec 2001
Posts: 1048 |
I can't really see why you need to check all permutations of size $a1. Shouldn't it be enuff with size 2, since the 8 bytes of a char can only span across 2 other chars? |
| | Graham
Account closed
Registered: Dec 2002
Posts: 990 |
what you do is local optimization. however, a local optimum often causes other local optima being undiscovered which makes global optimisation impossible. to really find the best solution, you would have to scan all 161! possibilities. ofcourse this is an impossible task... but you still might find better solutions than the ones you find through strict local optimization. |
| | JackAsser
Registered: Jun 2002
Posts: 2014 |
This problem is indeed NP-complete.
Imaging constructing a graph with N*M nodes, all connected with each other. (N,M=$A1)
D[N,M] = 7 - The number of saved bytes by letting N overlap M. (7 is the maximum number of bytes to be saved on a pair considering WVL already have removed duplicate chars)
So, we have N*M nodes, all connected with each other. The lenght of each edge i denoted by the D[N,M] matrix. And if we choose one particular pair to be next to each other, let's call them X and Y, then all other X,? and ?,Y becomes useless (other chars can be next to them at the same time). So, we want to choose N-1 pairs and at the same time minimising the sum of all D[N,M]. This is effectivly the TSP-problem but without having to reach the beginning again, which still is NP-complete to my knowledge.
So find a fast good approximative solution to TSP and you have a good approximate to your problem aswell.
One way is to create a minimum spanning tree, then take the hamiltonian tour of the MST which gives you a correct solution. Then apply local optimisations. This algorithm is O(n^2) and is fairly good. Dunno if it gets below your saving you already have, but it's certainly hellish much faster.
And most probably there are already some academic out there with a very long beard who has implemented a near optimal solution which is lightning fast in C, ready for you to download. :D
/JackAsser
|
| | Cruzer
Registered: Dec 2001
Posts: 1048 |
Btw, since the charset is in double-pixel resolution with only 2 colors you could save half the gfx-data by packing 2 bytes in 1. This will ofcourse make the fetching a bit slower, so it requires that you're not running short on cycles too. |
| | WVL
Registered: Mar 2002
Posts: 902 |
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: 902 |
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: 902 |
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: 902 |
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: 105 |
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: 902 |
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: 105 |
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: 902 |
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: 105 |
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: 902 |
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: 105 |
Is that gif somewhere to download? And what about the other maps?
Its really interesting :-) |
| | WVL
Registered: Mar 2002
Posts: 902 |
http://www.interstyles.nl/CLIP.gif
it looks a bit insane bcoz of all the RLE optimizations. |
| | Hoogo
Registered: Jun 2002
Posts: 105 |
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: 902 |
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: 902 |
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... |
| | Hoogo
Registered: Jun 2002
Posts: 105 |
How Do you manage the fine X/Y-movement? Usually one would place the sprite at the needed pixel-position, but the routine looks as if the block is aligned to a char and the sprite-data is hard-scrolled within the spriteblock to do the fine positioning. What a clever trick :-))) I was wondering how much shifting and buffering was needed to move the clipmap to the correct pixel-position...
I would not call the line-data RLE-encoded. The data contains nothing but a number of equal bits. Using it would have needed an outer loop for each pixel-row and in the inner a loop with adc and some logic to delete from pixel x1 to pixel x2.
|
| | WVL
Registered: Mar 2002
Posts: 902 |
easy.
i have 8 sprite images for each color, shifted 0-7 pixels (luckily, the ball is only 15 pixels wide, so i CAN fit all the shifted images into a sprite :D)
also check how i only need a clipmap-byte once to apply it to all 3 ball-sprites (3 hires sprites, darkgrey,grey,lightgrey), saved a lot of lda's ;)
The trick is that i first apply the ANDing with the clipmap to the dark-grey sprite, which is dgrey+mgrey+lgrey colors, then i and with the mgrey+lgrey colors to get the mgrey sprites, and i and again with the lgrey colors to get the lgrey sprite...
|
| | Hoogo
Registered: Jun 2002
Posts: 105 |
You spend $600 for one small ball and then you start this topic to win maybe $10 by better packing the charset?? Its sick, but I think i like this :-)
|
| | WVL
Registered: Mar 2002
Posts: 902 |
I don't spend $600 for one small ball :-)
the sprite-images are mixed inside the bitmap-gfx! |
| | Hoogo
Registered: Jun 2002
Posts: 105 |
You could ask a musician to perform a remix of your patterns ;-) |
| | Optimus
Registered: Jan 2002
Posts: 122 |
>$600
For a little moment, I thought you were talking about prize money ;) |
| | WVL
Registered: Mar 2002
Posts: 902 |
you can buy my ball for $600 ;) w8! special price for you!! only $599!! |
| | Hoogo
Registered: Jun 2002
Posts: 105 |
...$18 Bytes still unused :-) |
| | tfisher98
Account closed
Registered: Jan 2005
Posts: 3 |
Quote: easy.
i have 8 sprite images for each color, shifted 0-7 pixels (luckily, the ball is only 15 pixels wide, so i CAN fit all the shifted images into a sprite :D)
also check how i only need a clipmap-byte once to apply it to all 3 ball-sprites (3 hires sprites, darkgrey,grey,lightgrey), saved a lot of lda's ;)
The trick is that i first apply the ANDing with the clipmap to the dark-grey sprite, which is dgrey+mgrey+lgrey colors, then i and with the mgrey+lgrey colors to get the mgrey sprites, and i and again with the lgrey colors to get the lgrey sprite...
Dumb question: do you have any free sprites, or are all 8 used in the rasters that contain the ball?
If you have a free sprite, you might be able to make your code faster and less memory hungary by using the free sprite as a mask. Use a higher priority sprite than the ball sprites, and set this mask sprite to have lower priority than the screen data and the same color as the screen background (lets assume black). The way priority works, first the sprites are checked against each other, so wherever the mask sprite contains a 1 it will win, and wherever it contains a 0 the ball sprites will win. Then this combined sprite pixel is compared to the screen; since the mask sprite is lower priority the screen data wins if there is a foreground color. Where there is a background color, the sprite pixel is displayed (either black if the pixel is masked or a ball-sprite pixel if the pixel is unmasked). The only problem with this is only 2 of 4 screen colors count as foreground priority...
But its an idea that might be worth keeping in mind. It would save you having to store shifted sprite images (so save you 7*3*64 = 1344 bytes = 5.25 pages) as well as save you having to do any AND's whatsoever. Just copy the mask byte data for the corresponding bytes to the mask sprite imagedata, with the mask sprite position restricted to be a multiple of 8... |
| | WVL
Registered: Mar 2002
Posts: 902 |
working with priority does NOT work.
the problem is how priority between the multicolor bitmap and sprites is being handled :
%00 color of bitmap (background) -> always behind sprite
%01 color of bitmap -> always behind sprite!!!! <-- problem!
%1x color -> behind or in front of sprite, depending on priority register.
as you see, there's no way to 'hide' the ball beneath all 3 colors.
ofcourse it would work if %01 color is always the same as %00 color.
(you see, i thought about this beforehand, but it's just a no-go :), also check 2nd side of my demo Arcanum (the part with the 5 logos) for some nice priority mayhem ;), also in my demo 'World Demise' is an earlier version of that routine, using priority to fake blending of colors) |
| | Monte Carlos
Registered: Jun 2004
Posts: 359 |
Whats about packing the clipmap into 8x7 pixel wide chars?
The Sprites are 24x21, so they would be exactly 3x3 chars wide. Would be perhaps much easier, than dealing with 3x(2x5/8) wide chars. ;)
The bitmap could be 406 pixel high, instead of 400, do it would fit exactly, too(40x58 chars).
Montecarlos
|
| | WVL
Registered: Mar 2002
Posts: 902 |
I dont see how that would make things much easier? it wouldnt save any memory, but would become a bit harder to determine in what charline you are (dividing by 7 is a lot harder than dividing by 8) |
| | doynax
Account closed
Registered: Oct 2004
Posts: 212 |
Any chance you could search the ROM charset for matching strings too? Shouldn't be much of a problem since you're already storing raw pointers anyway.
It's any ugly hack and probably won't save more than a few chars but I guess it's worth a try. |
| | Monte Carlos
Registered: Jun 2004
Posts: 359 |
It was just a thought, which
i meant was worth to consider. ;)
And perhaps it is not too hard to calculate
the current charline, because if the ball movement
is max. about 16 lines per frame(which is quite fast), then
there are only 4 (2 back and 2 forward) charlines possible for the new ball position.
Monte
|
| | tfisher98
Account closed
Registered: Jan 2005
Posts: 3 |
WVL wrote:
-------------------------
%00 color of bitmap (background) -> always behind sprite
%01 color of bitmap -> always behind sprite!!!! <-- problem!
%1x color -> behind or in front of sprite, depending on priority register.
--------------------------
Yes there is a problem, but not quite exactly the way you wrote. The method I suggested, with an extra mask sprite, has
%00 color -> appears to be behind or in front of sprite, depending on priority register
%01 color -> can't be brought in front of sprite; if you set priority here you get %00 color <-- problem!!!!
%1x color -> behind or in front of sprite, depending on
priority register.
So three colors can be brought in front of the sprite; the fourth (%01) color cannot.
Anyway, it was just an idea. It's cool to see a new game under development, and I'm glad you're sharing the process with us.
Best of luck...
--T |
| | tfisher98
Account closed
Registered: Jan 2005
Posts: 3 |
With a couple more minutes of thought, it seems maybe I wasn't clear in my original suggestion. The ball sprites would ALWAYS have their priority bit in $d01b clear so they have priority over the bitmap. The mask sprite will be used to pull certain pixels of the ball sprites underneath the foreground %1x color pixels, and to hide others by mask (= background) color pixels.
Anyway, still probably not what you want.
--T |
| | WVL
Registered: Mar 2002
Posts: 902 |
it doesnt work, you cannot 'pull' the mask behind the %01 pixels and the %00 pixels. Ofcourse you can make it invisible, by letting the mask sprite take on the %00 color, but then there's always the %01 color the mask does not go behind...
-> wherever the mask sprite has bit 1, you will see color %00 (really the color of the sprite) where the %01 color should be seen. |
| | Hoogo
Registered: Jun 2002
Posts: 105 |
What about packing char-columns instead of char-rows? |
| | WVL
Registered: Mar 2002
Posts: 902 |
i think packing columns instead of rows would :
-reduce bytes needed for pointers
but
-make RLE compression of charscreen worse
you see, since the pinball table is made up from mostly vertical lines, there are a lot of equal horizontal rows. But i'm guessing there would hardly be any equal vertical columns -> compression goes down a lot...
also reading the last byte from columns (64 chars) would take longer than reading from rows (40 chars), since you have to RLE decompress on the fly...
-> i'm not sure it's worth trying.. (or rather, i'm 99% sure things would be a bit worse) |
| | Hoogo
Registered: Jun 2002
Posts: 105 |
It might take more time to decode till Char64, but when looking at the gif I find that the bottom of the picture would compress best in rows, but the upper part would compress better in columns. I'd say its worth a try. Maybe it's also possible to split and do both (increases the code..) ? |
|
