You can help CodeWalrus stay online by donating here. | New CodeWalrus | Old (dark mode) | Old (light) | Discord server

## Fairly easy map compression

0 Members and 1 Guest are viewing this topic.

b/Calculator Development publicado por u/E37 October 10, 2016, 09:13:40 PM

## Fairly easy map compression

So... I was discussing map compression with p2, and figured it was worthy of a topic to explain it.
Let's pretend you are making a game. Most games have multiple maps, it takes up a lot of space to have multiple arrays to hold all your maps.
Here is how to make all your maps (with in reason) take up the space of one!
First you need to know the number of tile types. If your game just has air, grass, and stone, then there is 2 (assuming that the first tile type is 0)
You need 2 maps. They must be the same size!
I want to edit the slot. I will set the slot on the compressed matrix equal to: (valueOfFirstMap) + (valueOfSecondMap*Prime)
What? Where did that prime come from? That is what lets me compress the map. The prime must be bigger that the amount of types.
In my example, I had 3 different types. I will pick 5 since it is the first prime greater than 3.
If you do mod (prime), then the remainder will have to be the first map's entry because the second entry will be some multiple of the prime and come out evenly. Divided by the prime will ignore the remainder (the first layer) and only give the second map.

Want more maps?
lets pretend that you have a total of 3 types of tiles for each layer
How to add / get from any of the layers (Let's pretend there are 3):
The first prime will be 5. that is the smallest prime that is greater than 3 (the supposed total number of tiles for the first layer)
If there are 3 types on the next, here is how to get the next prime. 3*5 +3 is 18. That is the highest number that the the first 2 layers combined can be right?
Well, for the third layer, we need a prime bigger than 18. let's use 19. You add the third layer to the total of the previous two.
To get layer 1 and 2 it is the same as above. To get the third, just divide by the second prime (19 in the example)

You can continue this pattern until it overflows. (if the max you can hold in one entry is 2^16, then the highest possible entry must be less than that)

It works well for multilayer maps, but it will work for any sets of data that are the same size.
Last Edit: October 10, 2016, 09:19:47 PM by E37
Inicia sesión o crea una cuenta para dejar un comentario
u/kotu October 10, 2016, 09:24:36 PM
Nice  never come across this before

Worth mentioning though that although you get better compression than using bit shifts, this method is more cpu-intensive
u/E37 October 10, 2016, 09:28:00 PM
Quote from: kotu on October 10, 2016, 09:24:36 PM
Nice  never come across this before

Worth mentioning though that although you get better compression than using bit shifts, this method is more cpu-intensive
True, but it is also easier to use assuming that your language doesn't have a direct way of bit shifting. (and you instead have to multiply or divide by a multiple of 2)
Also, not all languages take advantage of the multiply/divide by a multiple of 2 shortcut.
u/kotu October 11, 2016, 12:16:53 AM
Thinking about it, why do you have to use primes? Perhaps i'm missing something obvious

The mod and div will work regardless.
u/c4ooo October 11, 2016, 12:32:00 AM
Sure, but as runer112 had pointed out when I used a similar method in Laser II, this is more like phsudo-compression, since your simply putting data into unused space, and not contracting two used spaces. In your example you used 3 tiles, but it is very likely a game will have upwards to hundreds of different tiles  ;)
u/kotu October 11, 2016, 01:11:57 AM
@p2 - i think it's like a magic spell.
u/E37 October 11, 2016, 04:14:05 PM
Quote from: kotu on October 11, 2016, 12:16:53 AM
Thinking about it, why do you have to use primes? Perhaps i'm missing something obvious

The mod and div will work regardless.
The mod would work fine. If the first layer is a multiple of the number you pick (why I am using primes) then the second layer would read to be one more that it actually is.
u/TheMachine02 October 11, 2016, 05:13:04 PM
Actually I think it is better to not actually combine map : when you do, you will fetch unecessary data and maintains such data in a usable workspace - like RAM.

If you have less title, you can simply set a number of bits used by title (usually power of two, cause faster bit shift) and that way have multiple title index in one octet. This is quite interesting, cause you can simply fetch only one byte for rendering multiple title  Futhermore, you can get rid of thing like division and mod by prime - which are usually quite bad on any old processor.

However, it is still quite an interesting method, which could be used for even more application like, multilayer rendering, one octet packing multiple layer of one title.
u/rwill October 11, 2016, 05:26:08 PM
u/p2 October 11, 2016, 08:28:18 PM
it's a perfect way to create multiple layered maps or even combining many maps in a single matrix even if they had different sizes as the result is such a case yould just be 0 without ever causing an error ^^Definitely gonna use it for my walrus game ^^ (actually working on that part right now)
Thx @E37 for sharing this with us ^^
u/E37 October 11, 2016, 08:58:32 PM
Quote from: p2 on October 11, 2016, 08:28:18 PM
it's a perfect way to create multiple layered maps or even combining many maps in a single matrix even if they had different sizes as the result is such a case yould just be 0 without ever causing an error ^^Definitely gonna use it for my walrus game ^^ (actually working on that part right now)
Thx @E37 for sharing this with us ^^

Note what TheMachine02 said also. While this form is nice for COMPRESSION, it is rather CPU intensive to use.  While the player is using the map(s) it is best to copy them to separate locations. (Unless you can afford the slowdown)
u/c4ooo October 11, 2016, 09:14:44 PM
Quote from: p2 on October 11, 2016, 08:28:18 PM
it's a perfect way to create multiple layered maps or even combining many maps in a single matrix even if they had different sizes as the result is such a case yould just be 0 without ever causing an error ^^Definitely gonna use it for my walrus game ^^ (actually working on that part right now)
Thx @E37 for sharing this with us ^^
You shouldn't use this for PC. First of, memory isn't going to be an issue, and you just going to complicate things It would just be much better to create a Matrix for each map level. (If you don't know how many levels you will have then you could always create an array of Matrices) Not trying to say that E37's method is bad though It's fine for storing data but its bad when using it.

Also @p2 you could also look into VBO's; where you send all the data to the GPU and render it at once.

Also (x2) i think ime going to write a tutorial for how to make a good tile mapper in java.
u/p2 October 11, 2016, 09:25:53 PM
A tutorial would be really helpful

I'll for now I think I'll stick to this method as I write all the map data by hand and it's much easier for me to simply think of "2320" as a tree tile instead of having to create 3 different matrixes with 12, 5 and 41 in them xD
u/c4ooo October 11, 2016, 09:33:30 PM
Well ok, your choice
Also you should make use a tile editor. You could either use an existing one like Tiled, but your going to have to write a converter. Alternatively you could write one yourself
u/p2 October 11, 2016, 11:09:03 PM
do you mean a map editor? ^^
Yess this time I'm definitely creating one xD
And I prefer writing my own since I hate using code I dont fully understand ^^
But sadly the first test maps (only very little regions of cause) will still have to be made by hand >.<

My java code (working)
`double _data = 901*901*5 + 901*6 + 7; // 5, 6, 7int _mod1 = (int) _data%901;int _mod2 = (int) ((_data-_mod1)/901)%(901);int _mod3 = (int) (_data-_mod1-901*_mod2)/(901*901);System.out.println(_mod1);System.out.println(_mod2);System.out.println(_mod3);`
Last Edit: October 12, 2016, 11:14:59 AM by p2

## b/Calculator Development

Showcase your newest TI, Casio, HP, Numworks or Sharp calculator projects here, discuss programming and share or browse user tutorials!

320
Topics
Website statistics

MyCalcs | Ticalc.org | Cemetech | Omnimaga | TI-Basic Developer | MaxCoderz | TI-Story | Casiocalc.org | Casiopeia | The Museum of HP Calculators | HPCalc.org | CnCalc.org | Music 2000 Community | TI Education | Casio Education | HP Calcs | NumWorks | SwissMicros | Sharp Calculators