Advice on storing a 3D map please


(Mike McRoberts) #1

I’m currently working on an isometric view game where the world is made up of 3D Blocks. I want a 128x128 block map with a max height of 8 blocks. Storing each vertical column of blocks as a bit per block would mean 1 byte per vertical column and 16384 bytes in total to store the map.

Clearly, this is way too much. However, the majority of the map is empty space so could be compressed.

I am trying to think up ways of compressing the map. One way would be to simply use RLE on the entire map. The problem with that is trying to draw the small section of the map visible on the screen at any one time (probably approx 10x10x10 or thereabouts) and having to process the entire compressed array just to find out what blocks are within that smaller area.

So, I thought of breaking the map down into smaller areas, say 64x64x8 or and compressing those as separate sections of the map. This would mean processing a visible area would be a lot less processor intensive. The disadvantage is less compression as it also splits areas with zero blocks up.

So, what are your thoughts on this guys? Any suggestions?

Thanks,

Mike


(Holmes) #2

With 1 byte, there are 256 different combinations of blocks in each column. This means that there are 256 different stacks you could see, up to 8 blocks tall. If you needed to not use as many, you could cut the space in half by only making them 4 blocks tall, with 16 different combinations.

If you don’t plan on using 256 different combinations and think 16 is fine, but also need 8 blocks high, what you could do to still save about half the space is to define each of the 16 cases in the half of the byte. This can also allow you to store other kind of columns that can be taller than 8 blocks.


(Mike McRoberts) #3

I would definitely need it to be 8 blocks tall.

However, now you’ve said the above, it has made me realise that not all of those 256 combinations (presumably) are going to be used. I could, therefore, run a Huffman algorithm on the completed map and have a lookup table for the resulting codes produced (presuming this saves memory). I guess I’m not going to know how many block combinations are required until I design the map.

It may be possible to restrict the possible number of block combinations to 16 but it would require a very carefully planned map.


(spinal) #4

I don’t think you would have to plan the map too carefully. Maybe if you come up with the 16 combinations first, then use those building blocks to create your map?


(Mike McRoberts) #5

I could do that but it would restrict the freedom of the map. I’d rather have access to the full 256 combinations (or as many within that set I would need for my map) and find ways of compressing the resultant map size than going down that route.


(Mike) #6

Since the majority of the map is empty space, why not use a data structure appropriate to sparse data? For instance, store each box a pair of points for diagonal corners. Then put a data structure on top of that that allows the operations you need to be to be efficient. Links to the next object in each direction, or a hash table that quickly lets you find the object enclosing a point, etc. There’s been quite a bit of research on immutable data structures if you want to store them in flash.


(Mike McRoberts) #7

Sorry, i’ve read that several times and I still can’t make head nor tail of what you are trying to say.


(Mike) #8

Basically, I’m suggesting that you fundamentally rethink your map storage data structure.

Since it’s a 128x128 array with a max height of 8, you could store a triple for each non-empty spot: x, y, height. That would take 7 + 7 + 3 bits, which is unfortunate. If you only need 4 heights, or can otherwise free up a bit, you could do this with 2 bytes for each non-empty element.

You might want to look at sparse matrix techniques. But there are also techniques for dealing with objects in more complex spaces.

Which encoding - if any - will be fast enough will depend on what operations you want to do.


(Mike McRoberts) #9

The map is going to be made up of blocks as in the picture above. The max height will be 7 or 8 blocks max. As you can see, in-between objects there is plenty of empty space allowing for map compression. Just storing a value for height is no good as there may be several blocks with several gaps inbetween them. So for example a block with nothing on top then a block above the empty space, then nothing then a block above that empty space, etc. Storage for that column would be 10101010 (reading from left to right). But inbetween COLUMNS there may well be lots of empty columns with no blocks in at all (as in the picture).


(Mike) #10

In that case, your storage is three bytes for every map point that’s not empty: x, y, and the 8-bit pattern of blocks.

But that’s just ONE of the many sparse matrix data structures. There are lots of others, plus variants for specific types of matrices, and variants for three dimensions, and various graph structures (for some reason, finger trees come to mind, but I’m not sure why). Figuring out which one is right for you you’ll have to do yourself.


(Mike McRoberts) #11

That’s more than at present. Currently I have one byte per vertical column of 8 blocks with a 1 meaning a block and a 0 meaning an empty space.


(Mike) #12

IIUC, you’re storing every column. My example doesn’t do that - it only stores columns that have something in them. It needs three bytes for each NON-EMPTY column. So a map with nothing on it would use 0 bytes, one with one column somewhere on it but otherwise empty would use 3 bytes (the x and y coordinates plus the value you store now), etc.

The amount of storage varies depending on how empty the map is, which is common for such techniques. This example breaks even at ⅔rds empty, but there are lots of alternatives that take advantage of structure in the data. For instance, you could encode a “wall” with an x, y, a byte indicating length/direction, and then length bytes of column info. So a wall across the middle would be 131 bytes TOTAL storage, not the 384 my first example used. You could use RLE inside of a wall.

I haven’t looked at this stuff in thirtyfive years, so not only have I forgotten a lot, but there’s almost certainly been interesting work in the interim (in particular, the recent rise in popularity of functional languages has led to a a lot of research on immutable structures which would let you store them in flash). So you really need to read up on sparse matrices (say https://en.wikipedia.org/wiki/Sparse_matrix). If you’re still confused about why this might be a win, that wiki page would also help.


(Mike McRoberts) #13

Right I think I get you now. Each point on the map that has a block in it has an x and y co-ordinate plus a byte for the vertical blocks. Yeah that may work. I suppose it could be an array of structs with byte x, byte y, byte blocks as elements.

I guess until I draw out a potential map and then try a few techniques I am not going to know. I should do that next.

Thanks.


(Mike McRoberts) #14

@mwm thanks for your suggestion. I’ve created a 3D Voxel based map that is 88 x 88 x 8 blocks in max size with 3564 cubes in the map area. I’ve then taken an export from my 3D software as a text file and ran it through a parsing script to convert the X,Y, Z co-ordinates into a compressed format.

The raw data at 1 byte per x,y,z co-ordinate comes out at 10,692 bytes.

Running the file through my script and using a compression scheme based on your idea I have reduced this to 1,580 bytes. It means I could effectively make a much larger map if I so wish (depending on how much space the game engine takes up).

Thanks again,

Mike.


#15

That’s a great saving! Just make sure to keep in mind that unlike a PC, you cannot decompress your entire data structure back to raw in memory, as you only have 2.5kb of memory maximum, so you will have to do it in parts.


(Mike McRoberts) #16

Most of the saving is by ignoring map areas with no blocks in them. I’m actually only compressing the vertical columns and storing them as bits in a byte (8 block max height) so although it’s a huge saving it means minimal processing to view the relevant map area.


(Mike) #17

Just to be clear, this wasn’t an original idea. I first ran into it when I was in college 40 years ago, and it was old then. While applying sparse matrix techniques may be my idea, saying “the majority of the map is empty” just says “columns are sparse”, making it an easy suggestion.

It’s not really a compression, so you shouldn’t “decompress” it. It’s a different representation that uses different techniques to process. Instead of looping x & y over the coordinates of the map, you loop an index over an array and pull x & y values from that array. Finding the contents at a given x, y position is expensive.

Did you do the run encoding? That only takes more space for a single-pixel column. If you can get two, then it’s 5 bytes instead of 6.


(Mike McRoberts) #18

No, I didn’t bother with RLE as that means decompressing the entire map just to access the data for the camera FOV. This particular scheme means very fast data access for the camera’s view without having to process large chunks of data. 1.5Kb for a 3D map this large is good enough for me.


(Mike McRoberts) #19

Made a miscalculation. The map size is 4740 Kb but it’s still small enough to leave plenty of room for the game engine.