Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
 Welcome to our latest new user eightbitswide ! (Registered 2024-12-24) You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > WVL/Xenon's challenge!
2005-01-15 20:12
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 ;-)
 
... 38 posts hidden. Click here to view all posts....
 
2005-01-17 01:30
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
2005-01-17 08:07
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.
2005-01-17 08:53
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 ;)
2005-01-17 10:29
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  


2005-01-17 10:36
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..
2005-01-17 11:39
Cruzer

Registered: Dec 2001
Posts: 1048
Damn that looks ugly w/o tabs... My eyes hurt!
2005-01-17 11:53
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 :)
2005-01-18 06:40
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
2005-01-18 10:11
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 :)
2005-01-18 10:19
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?
Previous - 1 | 2 | 3 | 4 | 5 - Next
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
Jammer
SLC
Guests online: 84
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 The Demo Coder  (9.6)
6 Edge of Disgrace  (9.6)
7 What Is The Matrix 2  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)
Top onefile Demos
1 Layers  (9.6)
2 Cubic Dream  (9.6)
3 Party Elk 2  (9.6)
4 Copper Booze  (9.6)
5 X-Mas Demo 2024  (9.5)
6 Dawnfall V1.1  (9.5)
7 Rainbow Connection  (9.5)
8 Onscreen 5k  (9.5)
9 Morph  (9.5)
10 Libertongo  (9.5)
Top Groups
1 Performers  (9.3)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Censor Design  (9.3)
5 Triad  (9.3)
Top Coders
1 Axis  (9.8)
2 Graham  (9.8)
3 Lft  (9.8)
4 Crossbow  (9.8)
5 HCL  (9.8)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.125 sec.