Quick Links: Download Gideros Studio | Gideros Documentation | Gideros Development Center | Gideros community chat | DONATE
Compressing locally stored data of a customised grid — Gideros Forum

Compressing locally stored data of a customised grid

totebototebo Member
edited March 2015 in Game & application design
Hi,

A quick thought experiment. Imagine a 1000x1000 tile grid where the player can select an arbitrary amount of tiles. When they come back to the game the tiles they have already selected in a previous session are still selected; the data is stored locally on the device.

What is the best way of optimising the storing of these coordinates, and possibly other parameters, without running into megabytes? My thinking is going with JSON so I can quickly encode and decode the data. Then maybe compress the JSON in turn with a non-destructive format. Zip? Gif?!

Any ideas or suggestion or philosophical arguments welcome.

Cheers,

Niclas
My Gideros games: www.totebo.com

Comments

  • talistalis Guru
    edited March 2015
    Text files are always great in compression. But in my opinion rather than thinking how to store and to compress, need to find a good data format (protocol, algorithm ) to represent data.
    Then it will be much more easy to decrease the data size.

    Ok just a quick idea maybe useless but brain storming here :

    Supposing 100x100 grid.

    I will divide the grid into sectors of 10 . so i will have 100 sectors of 10x10. So a sector consists of 100 tiles.

    In each sector before saving i will count the selected tiles if it is less then 50, suppose 25, then i will put a flag in my json file like i am saving the selected ones only.
    If the user somehow selected more than 50 tiles lets suppose 89, then i will just save the not selected tiles and put my flag as saving not selected tiles mode.

    In this case i will decrease the data saved in a json file.
    Scenario 1: selected tiles in the sector is 25, and saved just 25 coordinates with a flag of selected mode.
    Scenario 2: selected tiles in the sector is 89, and saved only 11 coordinates with a flag of not selected mode on.


    And when i divide into sectors i will increase the optimization of counting i guess.
  • Thanks @Talis, some really good ideas!

    If it was straight up raw data, I wonder if there is a good way of compressing this? If there are patterns and big areas of the same value, there might be a compression that takes this into account. That's why I thought of GIF, it seems pretty good at compressing large areas of the same colour.

    Niclas
    My Gideros games: www.totebo.com
  • hgy29hgy29 Maintainer
    @talis is right in is way of thinking, however in this particular case, I would have used a bitmap representation (total binary size=1000x1000/8, 125k). Generally speaking, most of compression algorithm are good at finding redundancies, a standard gzip would do a great job on this kind of data.

    BTW, an API for accessing zlib functions of gideros may be useful...
  • HolonistHolonist Member
    edited April 2015
    Hi, let's say you have 1000x1000 tiles, and they are either "green" or "grey". That's how i understand your problem.

    Instead of saving an array that contains the color-state of each and every single tile, you can save an additional array like this:

    tileColors = {1027,"grey",1,"green",500,"grey",3,"green",...}

    in short, you simply summarize all adjacent tiles with similar color.
    In the best case, your extra array looks like this:

    {1000000, "grey"}.

    in the worst case, where all tiles go in the order "grey", "green", "grey", "green", etc, your array will become twice as big as your number of tiles.

    About the coordinates... I would give every newly created tile an id by simply iterating a value. And then display the tiles with a for-loop that calculates the position by the tile id

    I don't want to go too much into specific code before ensuring this method makes sense for you.

    Greetings

    edit: this is so called run-length encoding http://en.wikipedia.org/wiki/Run-length_encoding, i think it is used in minecraft to store the world.
  • Guys, this is gold dust. The ID idea is great. Will be back when I've run some tests. :)
    My Gideros games: www.totebo.com
  • totebototebo Member
    edited April 2015
    Actually, extending the ID idea. Instead of numbers, is there a standard (or otherwise good) way of using alphanumeric numbering instead of integers? If a player wanted to manually reference a specific tile it would be great if it was represented by a short string. So instead of "1000000" for the millionth tile it would be a shorter string.
    My Gideros games: www.totebo.com
  • HolonistHolonist Member
    edited April 2015
    i think for internal saving there is no reason not to use integers or double. But you can always transform your numbers into anything you like for display.

    here is a number to hex-function
    function num2hex(num)
        local hexstr = '0123456789abcdef'
        local s = ''
        while num > 0 do
            local mod = math.fmod(num, 16)
            s = string.sub(hexstr, mod+1, mod+1) .. s
            num = math.floor(num / 16)
        end
        if s == '' then s = '0' end
        return s
    end
    edit: but keep in mind in this particular function, a string will be returned. so you can't do any math with the number anymore.

    edit2: actually you can convert hex back into a number by the lua inbuilt function tonumber.

    tonumber(hexString, 16)
  • This is great, thanks @holonist!
    My Gideros games: www.totebo.com
  • Found this base 36 encoder/decoder which makes very large numbers even smaller: https://github.com/phyber/Snippets/blob/master/Lua/base36.lua
    My Gideros games: www.totebo.com
Sign In or Register to comment.