Join us on Discord!
You can help CodeWalrus stay online by donating here.

Fairly easy map compression

Started by E37, October 10, 2016, 09:13:40 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

E37

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.
  • Consoles, mobile devices and vintage computers owned: Ti83,Ti84!
I've never finished a project, there is always a way to improve!
What's my calc's name? Convert $37 to decimal. Look up that element in the periodic table. Then take the abbreviation of that element and you have it!
Look! A slime!    <(^.^)>

kotu

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
  • Calculators owned: TI 84+CE-T
  • Consoles, mobile devices and vintage computers owned: Sega Master System, Sony PlayStation 3
SUBSCRIBE TO THE FUTURERAVE.UK MAILING LIST
http://futurerave.uk

E37

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.
  • Consoles, mobile devices and vintage computers owned: Ti83,Ti84!
I've never finished a project, there is always a way to improve!
What's my calc's name? Convert $37 to decimal. Look up that element in the periodic table. Then take the abbreviation of that element and you have it!
Look! A slime!    <(^.^)>

kotu

Thinking about it, why do you have to use primes? Perhaps i'm missing something obvious

The mod and div will work regardless.
  • Calculators owned: TI 84+CE-T
  • Consoles, mobile devices and vintage computers owned: Sega Master System, Sony PlayStation 3
SUBSCRIBE TO THE FUTURERAVE.UK MAILING LIST
http://futurerave.uk

c4ooo

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  ;)

kotu

@p2 - i think it's like a magic spell.
  • Calculators owned: TI 84+CE-T
  • Consoles, mobile devices and vintage computers owned: Sega Master System, Sony PlayStation 3
SUBSCRIBE TO THE FUTURERAVE.UK MAILING LIST
http://futurerave.uk

E37

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.
  • Consoles, mobile devices and vintage computers owned: Ti83,Ti84!
I've never finished a project, there is always a way to improve!
What's my calc's name? Convert $37 to decimal. Look up that element in the periodic table. Then take the abbreviation of that element and you have it!
Look! A slime!    <(^.^)>

TheMachine02

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  :P 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.


p2

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 ^^ :)
  • Calculators owned: ti-83+, ti-84+, ti-84+, ti-84+se, ti-84+se(te), ti-nsphire, ti-nsphire CAS, ti-nsphire CX-CAS, ti-voyage, ti-voyage, Who reads this list anyways...?
Anyway war sucks. Just bring us your food instead of missiles  :P ~ DJ Omnimaga (11.10.2016 20:21:48)
if you cant get a jframe set up, draw stuff to it, and receive input, i can only imagine how horrible your game code is _._   ~ c4ooo (14.11.2016 22:44:07)
If they pull a Harambe on me tell my family I love them ~ u/Pwntear37d (AssangeWatch /r/)
make Walrii great again ~ DJ Omnimaga (28.11.2016 23:01:31)
God invented the pc, satan the smartphone I guess ~ p4nix (16.02.2017 22:51:49)

E37

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)
  • Consoles, mobile devices and vintage computers owned: Ti83,Ti84!
I've never finished a project, there is always a way to improve!
What's my calc's name? Convert $37 to decimal. Look up that element in the periodic table. Then take the abbreviation of that element and you have it!
Look! A slime!    <(^.^)>

c4ooo

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.

p2

A tutorial would be really helpful :D

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
  • Calculators owned: ti-83+, ti-84+, ti-84+, ti-84+se, ti-84+se(te), ti-nsphire, ti-nsphire CAS, ti-nsphire CX-CAS, ti-voyage, ti-voyage, Who reads this list anyways...?
Anyway war sucks. Just bring us your food instead of missiles  :P ~ DJ Omnimaga (11.10.2016 20:21:48)
if you cant get a jframe set up, draw stuff to it, and receive input, i can only imagine how horrible your game code is _._   ~ c4ooo (14.11.2016 22:44:07)
If they pull a Harambe on me tell my family I love them ~ u/Pwntear37d (AssangeWatch /r/)
make Walrii great again ~ DJ Omnimaga (28.11.2016 23:01:31)
God invented the pc, satan the smartphone I guess ~ p4nix (16.02.2017 22:51:49)

c4ooo

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 ;)

p2

#14
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, 7
int _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);
  • Calculators owned: ti-83+, ti-84+, ti-84+, ti-84+se, ti-84+se(te), ti-nsphire, ti-nsphire CAS, ti-nsphire CX-CAS, ti-voyage, ti-voyage, Who reads this list anyways...?
Anyway war sucks. Just bring us your food instead of missiles  :P ~ DJ Omnimaga (11.10.2016 20:21:48)
if you cant get a jframe set up, draw stuff to it, and receive input, i can only imagine how horrible your game code is _._   ~ c4ooo (14.11.2016 22:44:07)
If they pull a Harambe on me tell my family I love them ~ u/Pwntear37d (AssangeWatch /r/)
make Walrii great again ~ DJ Omnimaga (28.11.2016 23:01:31)
God invented the pc, satan the smartphone I guess ~ p4nix (16.02.2017 22:51:49)

Powered by EzPortal