1

**Other Calc-Related Projects and Ideas / Re: Compressing maps**

« **on:**May 11, 2016, 01:11:48 pm »

Holy necropost batman!

Yeah yeah, I'm resurrecting this from its grave, but since the last time I visited here I've studied Computer Science at a university for a couple of years so I wanted to make an addendum to this technique in case anybody is still interested. Note that this is still interesting no matter what kind of calculator you are using, even if you don't use matrices.

So, the entire point of this compression in the first place was to reduce the wasted space from numbers having a much larger range than what you are actually making use of. My initial idea was to use prime numbers, but even that's wasteful is what I've found now that I have more experience with this sort of stuff. I won't touch on other compression techniques that rely on encoding here as a quick search on the site for "compression" already reveals plenty of topics about that.

So, the best way to actually do this is to use binary numbers instead. Take the number of tiles you have as N

The trick kicks in when you want to store additional maps. Calculate the same B-value for your second map, so B

The way this works is by relying on binary numbers. If you don't know what these are I'm sure there are good primers on them somewhere on the internet so I'm not gonna bother explaining them right here. Basically what this math does is calculate what the least amount of bits is that can store all your tile ID's (B) and shift every consecutive map over by the sum of all B-values for the previous maps.

So let's take N

This is much more efficient than the prime number conversion, and simpler to boot since you don't have to make a prime number calculator and can simply use built-in logarithms for the math instead. As a comparison, the prime-number method could only store 10 maps with 2 features this way, while this method can store 46 bits in total with 14 decimals of precision in the floating point numbers, which means a whopping 23 maps with 2 features as opposed to the 10 from the old method (Or 46 if you use 0 as traversible space instead of a special 'this is outside of the map' value)

This method of compression can be used for other purposes as well - you could even use it on the table of N-values for each map to combine all of those! Simply treat each N-value as a map with only 1 tile ID and use the value itself for the N-value of this imaginary map and you're set! You could store all N-values for all maps that fit in one matrix/other data structure in a single number this way if you wanted to. And for the true geeks who want to compress even further you could even use other compression techniques on this already compressed map to compress it even further, though the gains will be lessened as is usually the case when you're stacking compression methods.

Well, there's my first post to omnimaga in I think over three years. If this is too necro-y feel free to just move this to another thread altogether, but I felt that it was appropriate to post this improved version of a trick I came up with three years ago (but which has been widely known in the much improved version in this post to most computer scientists for decades) in the same thread I originally posted it. Hope this helped someone!

Yeah yeah, I'm resurrecting this from its grave, but since the last time I visited here I've studied Computer Science at a university for a couple of years so I wanted to make an addendum to this technique in case anybody is still interested. Note that this is still interesting no matter what kind of calculator you are using, even if you don't use matrices.

So, the entire point of this compression in the first place was to reduce the wasted space from numbers having a much larger range than what you are actually making use of. My initial idea was to use prime numbers, but even that's wasteful is what I've found now that I have more experience with this sort of stuff. I won't touch on other compression techniques that rely on encoding here as a quick search on the site for "compression" already reveals plenty of topics about that.

So, the best way to actually do this is to use binary numbers instead. Take the number of tiles you have as N

_{1}and calculate B_{1}= Floor(log_{2}(N_{1})) as the number of bits you need to store your tiles. There's no need to use this number just yet, just store your tiles as the regular numbers in a data structure of your choice, like matrices. Be warned though that this only works if your tile id's start at 1 and increment by 1 - so for example if you have N=6 then the ID's for the tiles would be in the inclusive [1...6] range, leaving the 0 spot as a special 'this is not a tile' case that'll allow you to stack maps of different sizes using this method.The trick kicks in when you want to store additional maps. Calculate the same B-value for your second map, so B

_{2}= Floor(log_{2}(N_{2})). Now calculate the sum of all previous B-values, B_{sum,1}= B_{1}in this case since there is only one previous B-value. Make sure not to count the B-value of the current map! Now, multiply all of your tile ID's (again, the same range should be used) by 2^{Bsum,1}and add each of these adjusted tile ID's to the ones of the first map. Of course, you can keep repeating this for more maps, for example with B_{sum,2}= B_{1}+ B_{2}for the large map. Now you can retrieve any map from this compound map by dividing by 2^{Bsum,[map number - 1]}(the same number the original ID's were multiplied by) and taking the Floor() of the result. So for the second map this would be Floor(ID / 2^{Bsum,1})The way this works is by relying on binary numbers. If you don't know what these are I'm sure there are good primers on them somewhere on the internet so I'm not gonna bother explaining them right here. Basically what this math does is calculate what the least amount of bits is that can store all your tile ID's (B) and shift every consecutive map over by the sum of all B-values for the previous maps.

So let's take N

_{1}= 6 and N_{2}= 21 as an example. B_{1}= 3 which is correct since the highest ID would be 6 which is 110 in binary, taking up the predicted 3 bits. B_{2}= 5, also correct since 21 is 10101 in binary. Now multiplying by 2 in binary has the interesting property of shifting all the bits one space to the left - 6*2=12 and indeed 12 in binary becomes 1100. So when multiplying the tile ID's for the second map by 2^{Bsum,1}= 2^{B1}= 2^{3}all the bits will shift three spaces to the left, ensuring that there are always three unused bits all the way on the right - which are precisely filled by the bits that form the tile ID's of the first map! No matter which tile ID's are transformed this way those bits will never be overwritten, thus preserving both maps. That this works for multiple maps is easy to see, as the next map will have its ID's shifted B_{sum,2}= B_{1}+ B_{2}= 3 + 5 = 8 places to the left, leaving room for both previous maps.This is much more efficient than the prime number conversion, and simpler to boot since you don't have to make a prime number calculator and can simply use built-in logarithms for the math instead. As a comparison, the prime-number method could only store 10 maps with 2 features this way, while this method can store 46 bits in total with 14 decimals of precision in the floating point numbers, which means a whopping 23 maps with 2 features as opposed to the 10 from the old method (Or 46 if you use 0 as traversible space instead of a special 'this is outside of the map' value)

This method of compression can be used for other purposes as well - you could even use it on the table of N-values for each map to combine all of those! Simply treat each N-value as a map with only 1 tile ID and use the value itself for the N-value of this imaginary map and you're set! You could store all N-values for all maps that fit in one matrix/other data structure in a single number this way if you wanted to. And for the true geeks who want to compress even further you could even use other compression techniques on this already compressed map to compress it even further, though the gains will be lessened as is usually the case when you're stacking compression methods.

Well, there's my first post to omnimaga in I think over three years. If this is too necro-y feel free to just move this to another thread altogether, but I felt that it was appropriate to post this improved version of a trick I came up with three years ago (but which has been widely known in the much improved version in this post to most computer scientists for decades) in the same thread I originally posted it. Hope this helped someone!