Worth the trouble?

Member
Posts: 194
Joined: 2009.02
Post: #1
I'm working on a game in which I use a giant 3-dimensional array to represent the world, it ends up being about 800mb or so. Over 75-85% of the array is empty and much that isn't is redundant. Using standard compression the file gets down to about 5mb now( and I cant see it getting above 40 in the future). So the download size of my game should be quite small when compressed.

Since I stream this file continuously, I've been planning on writing some kind of rle compression algorithm to read and write from this file to keep the size small, but I'm kind of wondering if it's even worth the effort considering how cheap storage has become. Any advice?
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #2
I advise you not to take up 1.6GB on my disk! (800MB for the uncompressed copy you ship, 800MB for the copy you stick in ~/Library somewhere so you can write to it).

10MB is much more reasonable.
Quote this message in a reply
⌘-R in Chief
Posts: 1,254
Joined: 2002.05
Post: #3
It's not worth the trouble trying to compress the file, but it's certainly worth the trouble not using an 800 MB array to represent the world.
Quote this message in a reply
Moderator
Posts: 3,572
Joined: 2003.06
Post: #4
OneSadCookie Wrote:10MB is much more reasonable.

Even 15 or 20MB would be fine by me.

Seriously though, NelsonMandella, if you can compress it to 5MB for shipping, there *must* be a way you can come up with to keep it within reason. I don't recommend drugs, but this sounds like a good situation to explore your creative side. Wink 800 MB is definitely out of control.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #5
What are you putting in this giant 3D array? Voxels?

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 194
Joined: 2009.02
Post: #6
AnotherJake Wrote:Seriously though, NelsonMandella, if you can compress it to 5MB for shipping, there *must* be a way you can come up with to keep it within reason. I don't recommend drugs, but this sounds like a good situation to explore your creative side. Wink 800 MB is definitely out of control.

Yeah I realize that 800 is totally out of control and that what I'm doing is terribly inelegant and inefficient, but I just can't seem to wrap my head around a possible solution. For one thing the map needs to be 1 giant file, and I need to be able to arbitrarily jump to any location within the map, in an instant. When doing something like rle, this is tough because jumping arbitrarily would mean starting at the beginning of the file and reading all the way up until the origin of where i would need to load new tiles.

Skorche Wrote:What are you putting in this giant 3D array? Voxels?

Map data for a large scale rpg I'm working on.
The 7 layers represent height in the world for multiple building levels.
0 = floor, 1 = walls, 2 = cieling/second level floor, etc...

tile_type map[10000][10000][7];

Code:
typedef struct
{    
    unsigned short palette_index : 13;
    unsigned short room_flag : 3;
    unsigned char location_flag : 2;
    unsigned char active : 1;
    unsigned char level_flag : 3;
    unsigned char building_flag : 2;

}tile_type;
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #7
As cool as gigantic arrays like that are as a data structure, they tend to be equally as difficult to use efficiently. Now, presumably, you never see more than a tiny fraction of that world at once. It also sounds like there are significant sized empty spaces.

One good place to start if you want to keep the giant voxel map idea is to split it up into chunks. Example, instead of a 300x300x300 array, make a 30x30x30 (chunks) array of pointers to 10x10x10 arrays of tiles. When looking up a particular tile, use the chunk array to find the chunk you want and then grab the tile you need. The chunk array can even start out will all null pointers, and you just load in the chunks as needed. This saves on loading times and memory. If your world is destructable, you can write individual chunks back to disk without having to rewrite the entire map.

Additionally, if a chunk is completely empty, you can just use some small placeholder value when storing it on disk. If you make the chunks a few kilobytes in size, you could use zlib to compress individual chunks fairly efficiently.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 144
Joined: 2009.11
Post: #8
As most of the array is empty space (probably the different levels for the second-story and what not) I'd suggest that you use another data structure.

You describe having an array dimension for each level, but some levels are only going to be sparsely populated. Such as the level reserved for the second story of buildings. Obviously buildings are going to take up a minority of area in the overall map, and so that level is going to be very sparse.

I'd suggest dumping that level entirely, and simply keeping a linked list or hash map of chunks describing those second story areas. If you imagined taking all the little areas where that level isn't blank, then extracting it to its own little array, that's what I'm talking about. Just a simple listing of relevant areas.

Everyone's favourite forum lurker!
https://github.com/NSError
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Worth going through the effort with Xcode 2.5? monteboyd 34 12,573 Sep 30, 2008 03:30 AM
Last Post: monteboyd