Calculator Community > Other Calc-Related Projects and Ideas

Compressing maps

(1/2) > >>

sjasogun1:
Most people who program games on their calculator have encountered them: maps. They can take many shapes, sizes and forms, but they always have one thing in common. They occupy a lot of memory. Now, I think I have found a solution to this problem or at least an improvement from the current situation. It mainly revolves around using Matrices to store variables for 2D maps in.

Normally a matrix is very handy for storing numbers in that represent something on the map without having to worry about storing the coordinates for you since matrices have the coordinates built into them. The problem is that matrices tend to take up a lot of memory as they get bigger. For example, on my calculator, an fx-9860GII, a small 10x10 matrix takes 1236 bytes, and a 7x21 matrix that has the dimensions of the screen as far as ASCII goes takes 1800 bytes. And that is just a single matrix. A game will need many more to be of any use as a single screen-sized level won’t allow you to make much of a game that actually needs maps. Storing it in an array doesn’t make any difference either: it still takes 1800 bytes on my device (though it may save you a little bit on another device).

The solution I propose is as follows. You start by generating a list of prime numbers. You probably won’t need much more than 10 for simple maps that only include walls and have the exit hard-coded into them (meaning it is represented as an ‘empty’ square in the matrix but the code has something happen when the player stands on the spot where the exit is), but for maps that have more features on them you’ll need to generate more prime numbers as well (how many exactly will be detailed further in the explaination.)

Now, start by making yourself a map, probably something simple like a maze because you only have walls to work with for now. Put 1 in the matrix for any empty square and the first prime number on your list, which should be 2 if you did it correctly, for any wall. The reason for not using 0 as the 'empty' squares will become obvious in a minute. Now we have our first map. Nothing much, right? A player should be able to solve this maze in well under a minute. So, we’ll need more mazes. But instead of making another matrix to store the next maze in we’ll store it in this one, without changing it dimensions.

To do this you take your list of prime numbers. The first prime number is 2, but we already have 2 in our maze. So we’ll start with the second prime number: 3. Now, to make the process of making the new maze easier make yourself a new matrix. Make another maze of the same size as the previous one here, but this time use 3 for the walls instead of 2. Empty squares are still 1. Now, when you’ve finished, you multiply each square in the matrix with the matching square in the other one. So, you multiply A[1,2] with B[1,2] and A[5,12] with B[5,12]. This multiplication is why empty squares shouldn't be 0; multiplying with them would always give you zero. Before you start the multiplication, there is one important precaution to take: multiplying each square in a matrix with its corresponding square in another matrix is not the same as multiplying the two matrices. You’ll have to write a double loop in order to get the multiplication right.

Now, you end up with a matrix that looks like garbage. It has 1,2,3 and 6 scrambled all over it. The trick is that this matrix contains both of the original maps. Extracting them goes as follows: If you want the first map you take the first prime number (2) and go over each square of the combination matrix to see if the number in that square is divisible by 2. If so, count that square as a wall. If not, count that square as an empty square. If you draw the result on the screen you’ll see that it has produced your original maze again. You can extract the second maze in the same way, with the difference that you’ll take the second prime number (3) as your divisor. You can make many more mazes and multiply the squares in them with those in the combination matrix to store them all in the same one, going over the rest of the prime numbers. So 5 will be the wall in the third maze. 7 the wall in the fourth maze, 11 the wall in the fifth maze and so on.

This neat little trick makes use of one of the useful properties of prime numbers: every number has a unique set of prime factors. This means that if you take a random number like 59175839719 and figure out how to divide it into prime numbers there will be no other product of prime numbers that will produce the same number. In the compressed matrix this is easy to see. No prime number is divisible by 2 except 2 itself since the basic definition of prime numbers is that they can only be divided by themselves and 1. So, only the squares that were labeled with 2 in the first maze will ever be divisible by 2 since we only multiply by prime numbers. The same goes for all of the other prime numbers we used.

The only downside of this technique is that, in its current form, it only works for maps that have only two different kinds of squares: empty ones and walls in this case. There is an easy way to add more types of squares to the map though: simply skipping prime numbers. For example, in the first maze you’d use 1 for empty squares, 2 for walls, 3 for pitfalls that put you back a level and 5 for invisible walls. In the second maze you’d then use 1 for empty squares, 7 for walls, 11 for pitfalls and 13 for invisible walls. The only downside of this is that you need more prime numbers for more different features in your maps, scaling linearly for the amount of features. 1*10 prime numbers will allow you to make 10 maps with 1 feature (walls), 2*10=20 prime numbers will allow you to make 10 maps with 2 features (walls and pitfalls) and 3*10=30 prime numbers will allow you to make 10 maps with 3 features (walls, pitfalls and invisible walls). Luckily this only scales linearly so adding a feature will only add as many prime numbers as you want maps. Another advantage is that arrays (called Lists on my fx-9860GII) and matrices will usually reserve the same amount of memory for every element: enough to hold a number up to 9.99*10^99. This means that having a value like 6469693230 in your matrix (the product of the first 10 prime numbers) in your list won’t take any extra memory, effectively making the limit 53 prime numbers (after which the combined product of them, which is the worst case scenario, exceeds 10^99). Of course, this limit only applies to maps that only use walls: in maps with two features 2 and 3 can’t be multiplied, nor can 5 and 7 or 11 and 13, thereby raising your limit to 91 primes (took me a while to calculate that :P). The limit to the amount of maps you can make does shrink as you add more features (from 53 to 45 in this case) but it won’t shrink too fast, especially not when you consider that adding more features gives maps potential to be harder thus requiring less to make an interesting game.
Also, if you need to store more maps you can simply make a second matrix in which you can re-use your prime numbers to store even more maps, thus reducing your memory load by a factor of 30~50, depending on the amount of features you add (not 30~53 as the code for generating primes, the storage for the primes and the code for extracting a map all take extra space as well, but not much and the 'memory reduction factor' only increases as you add more maps).

I hope you all like my idea and can put it to some use!

Builderboy:
This sounds like a very intriguing new way to save memory!  You better watch out though, since even though the maximum value for a number in a matrix is 10^99, the numbers are stored in floating point format.  What this means is that even though you can store very large numbers, the precision of them will only be about the last 14 digits or so (depending on your calculator model).  This will result in extremely large numbers being seemingly divisible by numbers they cannot be divisible by.  For example, a large enough power of 2 will return 0 when you ask for remainder 3.

Xeda112358:
Another method that you might be interested in works like this:
Say you have 10 different tiles and numbers are stored with 14 digits of precision. You can then store each map layer with the nth digit in the number. To access the map in TI-BASIC code:

--- Code: ---10fPart(10^-N[A]

--- End code ---
If you aren't familiar with TI-BASIC, fPart( simply grabs the decimal part of a number (leaving off the integer part). If the language you are using doesn't have that, there is probably some equivalent to a floor() function (round down to the nearest integer) and you would essentially do #-floor(#).

If you have M different tiles, you can theoretically store up to floor(14/log(M)) different maps in a single matrix element, this way. However, I would go with 1 less than that to avoid precision problems. Your code for extracting a given matrix would be to replace the 10 in the above code with M.

I hope to see more ideas :D Encoding data with primes and properties of numbers can have some pretty interesting effects.

Streetwalrus:

--- Quote from: Xeda112358 on March 27, 2013, 01:35:50 pm ---Encoding data with primes and properties of numbers can have some pretty interesting effects.

--- End quote ---
Yeah true, that's how compression works : complex math algorithms to gain a lot of space. ;)

zeldaking:
I have a question about this for Ti-basic. Matrices do take longer to display because you have to change each number back into a corresponding character correct? So to speed things up we could use strings, but similarly string take up memory especially when having many strings. Is there anyway to "compress" a string similarly to this matrices way, while still retaining speed?
----
Oohh I just came up with a good idea while thinking of some stuff.
Strings do take less memory than matrices, so say take a string: "123456789" comparable to the matrix of: [[1,2,3][4,5,6][7.8.9]]. So we take our string and use that prime factor "compression" talked about above. We take the matrix and put them instead into a string, "12121212" and whatever prime we are using and do the same way as the matrix. But instead using Substr( and converting to the correct character. I am not sure if that is faster, probably more confusing for map collision testing but oh well. Just a thought.

Navigation

[0] Message Index

[#] Next page