# Implmenting RLE into a tilemap or how to create a large 3D array?

Currently I've been using a 3D array for my tiles in a 2D world but the 3D side comes in when moving down into caves and whatnot. Now this is not memory efficient and I switched over to a 2D array and can now have much larger maps. The only issue I'm having now is that it seems that my tiles cannot occupy the same space as a tile on the same z level. My current structure means that each block has its own z variable. This is what it used to look like:

map.blockData[x][y][z] = new Block();

however now it works like this

map.blockData[x][y] = new Block(z);

I'm not sure why but if I decide to use the same space on say the floor below it wont allow me to.

Does anyone have any ideas on how I can add a z-axis to my 2D array?

I'm using java but I reckon the concept carries across different languages.

Edit: As Will posted, RLE sounds like the best method for achieving a fast 3D array. However I'm struggling to understand how I would even start to implement it? Would I create a 4D array the 4th being something which controls how many to skip? Or would the x-axis simply change altogether and have large gaps in between - for example [5][y][z] would skip 5 tiles? Is there something really obvious here which I am missing?

The number of z levels I'm trying to have is around 66, it would be preferable that I can have up to or more than 1000 in x and y.

-
As the x and y dimensions seems quite full and the z relatively sparse, shouldn't you use arrays for the x and y and an object for z ? ie. map[][]{}; and then use like this: map[x][y][z]=new Block(); ... ... – Valmond Jul 3 '12 at 15:15
@Valmond Sorry I don't understand, are you suggesting I use a 3D array, because thats what it looks like. Could you elaborate a bit more on what you mean by an object for z? – Smallbro Jul 3 '12 at 15:55
an array (var a[]) is sized (usually) from zero to the highest number-1 (ie. a[0]=10; a[1024]=10; -> your array has 1025 elements!). an Object (ie. var a{};) uses a hash technique and has one entry per 'entry' so if you have few "z" values that might be big or small, that is the way to go. Maybe... Try it out and check the memory consumption! – Valmond Jul 3 '12 at 16:28

## 4 Answers

It sounds like most of your cells are unoccupied.

You can dramatically reduce memory if you store only occupied cells; this is termed "sparse" and is straightforward using a simple run-length-encoding (RLE) scheme (the runs of occupied and unoccupied cells are length-encoded).

For example, you could have an array of block instances:

``````Block[] blocks; // block[0] might be Grass, block[4] might be Water etc
``````

Imagine that each X row on the 3D map is an integer array:

``````int[][][] data = new int[MAX_Z][MAX_Y][];
data[4][4] = new int[]{ 3, 2, 1, 1, 2, 1, 2, 3, 2, 2, 1 }; // some test row
``````

The first integer says how many cells to skip, then how many cells are occupied, then the integer indices of the blocks in them, and so on. So that test row is:

``````  | (x=0)
3 | skip 3 (x=3)
2 | occupied 2
1 | block[1]
| (x=4)
1 | block[1]
| (x=5)
2 | skip 2 (x=7)
1 | occupied 1
2 | block[2]
| (x=8)
3 | skip 3 (x=11)
2 | occupied 2
2 | block[2]
| (x=12)
1 | block[1]
``````

Its straightforward to iterate over, and not too complicated to insert into:

``````void debug_line(int z,int y) {
int[] row = data[z][y];
if(row == null) return; // nothing on that line
int x = 0;
for(int i=0; i<row.length; ) {
int skip = row[i++], occupied = row[i++];
for(int j=0; j<skip; x++, j++) System.out.print("-");
for(int j=0; j<occupied; x++, j++) System.out.print(row[i++]);
}
}
``````

This debug function iterates over all `x` in that row and emits this:

``````---11--2---21
``````

You can likely use shorts or pack into bytes to dramatically reduce RAM further. And completely empty rows, rather than having an empty array (allocated and taking up space), can simply be `NULL`.

(I picked X rows rather than Z because its likely that you are drawing on the XY plane; you always want to be skipping along on the ground plane)

You can also likely share actual block instances; you don't need 100 instances of the 'grass' block if the properties are the same.

This will allow you to use 3D again.

More complicated structures like sparse octrees can reduce memory requirements much further. I'd recommend simple RLE first and then something 'better' if you hit performance or memory problems.

-
+1 I really like your RLE and sparse octree suggestions. It's more work to get your head around but it could be the best solution for Smallbro. Also good tip to use instancing, hadn't thought of that in my answer. – Roy T. Jul 1 '12 at 20:04
Will, I'm not sure how I would achieve what you have suggested. Is it possible that you could show me how to put RLE into an array? Do you have any resources which might help me understand how to implement it? – Smallbro Jul 3 '12 at 15:56

Ok first things first. map.blockData[x][y] points to a place in memory so when you assign a new object reference to map.blockData[x][y] the old one is overwritten so you can't use it multiple times.

Now I'm not sure why you can use larger levels when using a 2D array instead of 3D array, are you having memory problems? This seems unlikely because it looks like Block is a class so the 3D-Array only stores pointers. However if most of the times there is only one block at (x,y) you can save space the following way.

Store the Z component in the block. Then create a new array like this:

``````Block[][][] map = new Block[Width][Height][];
``````

Then populate the array like this:

``````map[x][y] = new Block[]{block1, block2};
map[x+1][y] = new Block[]{block3};
``````

This is called a jagged array, and it uses less memory because we can vary the size of the array for the 3rd component. You can get the size by using map[x][y].length.

Now when rendering you get the block(s) for (x,y) as usual and you check map[x][y].Length to see how much blocks are stacked on each other. Finally you can check with map[x][y][z].Z how high that particular block should be placed.

-

You don't give enough detail for me to conclude if this is a viable method but I'll throw it in there anyway as a possible solution. Someone else may find it useful if you don't.

You don't say how many zlayers there are and if there are only very few layers then this may be an option.

What you can do is store more one tile data in a long variable by using bits.

Let say you have 4 layers and 255 tiles per layer to keep my explanation simple.

You can do that in a single long by using bitwise AND and rotation.

first 8 bits could be layer 1, second 8 bits could be layer 2, and so on.

in order to get the right tile in this particular data format for the layers you would do something like

``````tile1 = (map.blockData[x][y] & 0x000000FF);
tile2 = (map.blockData[x][y] & 0x0000FF00) >> 8;
tile3 = (map.blockData[x][y] & 0x00FF0000) >> 16;
tile4 = (map.blockData[x][y] & 0xFF000000) >> 24;
``````

Of course this all depends on how many layers and tiles you have for this method to work.

-

From what I understood you're now storing the `Z` value as part of the `Block`, but you need the ability to store more than one `Block` in each array position.

``````class Block
{
int z;
}
``````

Option 1

One possibility is to create a 2D array of `ArrayList<Block>` instead of `Block`. This way each position in the array can store more than one `Block` if needed. So you would create the data structure like this (I think, it's been many years since I've used Java):

``````ArrayList<Block>[][] data = new ArrayList<Block>[width][height];
for(int x=0; x!=width; ++x)
for(int y=0; y!=height; ++y)
data[x][y] = new ArrayList<Block>();
``````

And add a new block with the `add` method of the `ArrayList` such as:

``````data[x][y].add(new Block(z));
``````

This way you can have as many `Block` as you need in a single position. You could also use a jagged array instead of an `ArrayList` if you already from the start how many elements will be in that position, and it will probably have less overhead than the `ArrayList`.

Option 2

Another possibility is instead of using the `ArrayList`class, to make the list of blocks implicit to the `Block` class. You could do this by adding a `Next` property to the class that points to the next `Block` that is shared by the same position. I also added an helper method that recursively adds a new `Block` to this implicit list:

``````class Block
{
int z;
Block next;

void Add(Block block)
{
if(next== null)
next= block;
else
next.Add(block);
}
}
``````

With this you can keep using the same structure as before:

``````Block[][] data = new Block[width][height];
``````

But when adding a new `Block` you'd do this instead:

``````Block block = new Block(z);
if(data[x][y] == null)
data[x][y] = block;
else
data[x][y].Add(block);
``````
-