Storing tile data

Newbie & Debugging Questions
#1

Hi,

As my game progresses, I’m now looking at reducing my 2d array size, it current is 3000x2000:


TileEntity[][] worldMap = new TileEntity[3000][2000];

TileEntity is defined as:


abstract class TileEntity
{
    protected int xPos,yPos;
    protected int txPos,tYPos;
    protected int lightValue;
    protected int hits;
    
    protected void draw(SpriteBatch s) { ... }

}

Then other tile entities derive from this one. Now, looking at the class the int’s could be changed to a short for the xPos,yPos, the txPos,tYPos could be changed to byte and same for lightValue and hits thus saving up some memory.

Is there another way - maybe make array smaller and read from file storage?

Any advice is appreciated.

Thanks

#2

Do you have performance issues or you want just to optimize it?

How big is each tile? Is it just a texture?

#3

You may need to explain what the fields are supposed to store, plus their numerical range.

I suppose (xPos, yPos) is the tile X/Y position in worldMap. For a start you should ask yourself if a tile really needs to know its own position. Usually you look it up in worldMap, which means you already know X/Y, so this information is redundant.

(txPos, tyPos) supposably describe the tile texture coordinates. Dependent on the size of your tile set this can probably be stored in a single short value, and (txPos, tyPos) calculated for rendering as needed.

It isn’t easy to recommend more improvements without knowing your requirements. E.g. “lightValue” and “hits” may only be required in a rather small area around the player, for example when damage done to tiles is allowed to “heal” if the player moves away. In this case that data can be stored in a separate, smaller structure, which is copied or wrapped around as the player moves.

Also, using “abstract” indicates that you want to store different subclasses of TileEntity. This approach usually leads to very unpredictable storage requirements. I’d advise you to start with a data-driven approach where worldMap only stores data, and contains no logic. Functions can be done by “worker” classes which iterate over the visible part of worldMap and pull the data they need.

#4

Hi,

Running 60fps, but of course the memory req’s of the array can be reduced and some of the things mentioned here will help a great deal.

I will look at removing the int xPos, yPos and possibly the draw method and the texture positions. Using bytes where possible so TileEntity consist just of hits and lightlevel - two bytes but guess can store both this information in the one byte?

Many thanks

#5

You just need to contain the ID of the tile. All the information you have given are already known. You aren’t going to refer to the tile without knowing what the tiles x and y are. So a simple int table would do.

int[][] table = new int[2000][3000];

Depending on the amount of tiles, you can use shorts or bytes.

short[][] table = new short[2000][3000];
byte[][] table = new byte[2000][3000];

#6

Hi,

My tiles though do have props such as light value of each one, how many hits it takes to destroy and I decrement this hit count in the tile object, when zero, break the tile and then reset it.

Agree about the x,y position, this isn’t needed. I also have a batch.draw method in the tile object, guess this can be removed also.

Thanks

#7

I’ve got 8000x2000 tiles @60fps, each tile taking up 3 bytes of memory (byte visited, byte lightvalue, byte hits).

Other ideas to shorten size of 2d array would be to load game in from disk, is this a good idea as it would also need saving as well as the world can be altered?

8000x2000 with tile size of 16x16 and screen width 1024 is around 125 screens wide and 42 screens deep.

#8

Premature optimization is the root of all evil! Unless this is ridiculously memory heavy and you know it’s definitely the world map, consider loading in chunks of the work from disk only when you’re nearby.

First, split your world into chunks. Minecraft uses 16x16 (cubes but obviously yours isn’t 3D). Try a number and see what works best for you.

Since your world isn’t infinite, you won’t have to worry about generating new chunks on the fly since you’ll do that at the very beginning and whatnot. You have your array of chunks, but they’re all currently null. What you’ll have to do is have some sort of getChunk method so that in case the chunk you want is not there yet, you can load it in from disk. That I’ll leave up to you.

Chunks can have a non-saved timer that ticks down how long they should exist for before unloading themselves to save memory. The things that can reset the timer include the player being nearby, or you just loaded the chunk and you should keep it in memory for a minute or less to avoid rapid IO operations if you’re accessing a chunk frequently.

#9

Hi,

Some good ideas there Chrislo27. I guess I could get away with not having to do file i/o as to me, 8000x2000 is big enough and I believe it will do more, think to my calculations unless I’m wrong this about 48mb (8000x2000x3/1024)?

If doing infinite terrain I would go with the file i/o and use chunks, I did this in a minecraft style clone I did a while back.

Thanks

#10

Properly designing data structures is essential for software development and has nothing to to with the infamous premature optimization.

#11

Creating an object for each tile also produces some overhead - cpu-wise, garbage-wise and memory-allocation-wise. An Array is also an object, so nesting arrays produce more overhead.

However, while this is all very bearable, you could go more oldschool: treating your whole tileset as block of data would reduce all these overhead:


    class TileManager {
        static final int GRID_WIDTH=8000;
        static final int GRID_HEIGHT=2000;
        static final int TILE_WIDTH=32;
        static final int TILE_HEIGHT=32;

        static final int TILE_TYPE_GAP=0;
        static final int TILE_TYPE_GRASS=1;
        static final int TILE_TYPE_ROCK=2;
        static final int TILE_TYPE_WHATEVER=3;

        static final int TILE_TYPE=0;
        static final int TILE_VISITED=1;
        static final int TILE_LIGHT_VAL=2;
        static final int TILE_HITS=3;

        // you might want to reserve some space for future extensions...
        static final int TILE_SIZE=8;

        byte[] tiles=new byte[GRID_WIDTH*GRID_HEIGHT*TILE_SIZE];

        draw(SpriteBatch s) {
            s.begin();
            for(int gy=0; gy < GRID_HEIGHT; gy++){
                for(int gx=0; gx < GRID_WIDTH; gx++){

                    int tileStart = (gy*GRID_WIDTH + gx) *TILE_SIZE;
                    byte tileType = tiles[tileStart+TILE_TYPE];

                    if( tileType != TILE_TYPE_GAP )
                    {
                        // calculate position
                        int x = gx * TILE_WIDTH;
                        int y = gy * TILE_HEIGHT;

                        // get tex coords for this type
                        int tx = getTXbyType(tileType);
                        int ty = getTYbyType(tileType);

                        // get what else you need
                        byte visited = tiles[tileStart+TILE_VISITED];
                        byte lightVal = tiles[tileStart+TILE_LIGHT_VAL];
                        byte hits = tiles[tileStart+TILE_HITS];

                        // now draw it...
                    }
                }
            }
            s.end();
        }
    }

Isn’t as pretty though and more the way you would do in C.

This way you would exactly use the amount of memory declared by the byte array, without any hidden overhead. Saving and loading this is obviously also straight forward…

#12

Thanks for that, yeah looks good, although would mean quite a few code changes to my game!

#13

Using a single index array has in the past saved me a lot of memory and if you manage your access pattern, can be quite a bit faster as well. However I wouldn’t normally bother until memory or performance has become an issue and you know it is the cause. It is easy to get hard to find bugs in such code because you don’t throw index out of bounds, you simply keep scanning across.

In may case i was using over 20G on our cluster nodes. The fix reduced that down to 12G or so, this is not far off the raw numbers of doubles i needed to store anyways.

#14

Make a list which holds all the information such as light value and hit breaks to everything that isnt default.

I.E all the tiles are brightness of 1 unless otherwise specified.
I.E all the tiles take 6 hits to break (or so set dynamically) so all can stay default or be added into the list when needbe.

#15

Oh whoops, I thought I mentioned that the amount of data he’s storing isn’t all that much (I did the math myself to estimate how much memory that would use and thought that wasn’t all that much) but I guess I didn’t include it. Thanks for the correction.