Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

My game is having a map like that of Minecraft, in the way it's pseudoinfinite and randomly generated. And big. Say the user has explored a 1000x1000 zone (2D here), so that's 1,000,000 tiles.

Obviously I'm not going to be able to store it all in memory. Nor do I just want to ignore everything out of a 10 tile or whatever radius - both will nothing update (all the NPCs, perhaps reactive tiles) and I would have to work with awkward positions like 1382,12918.

So if I was to split it down into chunks or zones or whatever of say 64x64 tiles, I would have to store each tile and object's position like:

Chunk a,b. Position x, y.

But what if I wanted dungeons and the like in my map? So a single tile that leads to maybe a 40 floor dungeon, each with an area of 40x40. I can't exactly store those in the same map.

And there's the memory side; how much could I potentially store in memory at the same time reasonably? I could do tiles by ID quite easily, and have the normal 2D array there. Or again, is there a more effective solution than having a data file of tile types? So for a 64x64..that's only going to be 20K or whatever. I'd like as much as possible surrounding to be loaded for the most realistic update. But I don't know what sort of limits I can hit without becoming memory hogging.

share|improve this question
add comment

2 Answers 2

up vote 9 down vote accepted

While I agree with the sentiment: "don't worry about it unless it's a proven issue", I do think it's worth thinking about early on: retro-fitting a solution is much more painful. And yes, only updating 'nearby' tiles is they way to go. But storage and addressability of items in your game world efficiently is very important for performance reasons.

What you're really thinking about here is a sparse data-set: something where the potential indexes are large (or unlimited), but only a small proportion are actually used. The key point is that you do not know exactly which proportion will be used.

The standard solution to a sparse data-set problem is to separate the index/addressability from the actual data storage. So if the tile object is expensive, then store it in a compact form (e.g. a flat array). But allow it to be indexed through a cheaper object. In its simplest form, this can be a 2D (or 3D) matrix which you can easily index by coordinate, but each item in the matrix is simply an index. You then use that index to look up the actual tile contents in a separate, compact array. If the tile contents do not yet exist, then add them to the end of the array, and store the index in the 3D matrix.

The solution gets more complex if you wish to support deletion of contents (as it leads to fragmentation of the contents array), and if your tile contents are cheap, then the extra weight of the index (32-bit or 64-bit indices) will probably overwhelm the savings from not storing every single potential tile. It's also an extra lookup, which will hurt your cache performance.

You can get even more storage efficiency by introducing extra layers of indirection. Let's say you organise your tiles into chunks, and chunks have a granularity of 64x64x64. Given a tile at 125, 1, 132, you know it belongs in chunk (1,0,2). So you have a world, which consists of a compact chunk array, and a matrix of chunk indices (-1 if the chunk doesn't exist). The contents of each chunk (if present) are a 64x64x64 matrix of tile indices (-1 if the tile doesn't exist yet), and a compact array of used tiles. This way, you don't burn a massive amount of tile indices for chunks which are never used. By following this sort of approach, and picking sensible numbers for the chunk granularity, you can scale up your universe massively, and keep your memory usage under control. Actually, if you make your chunks 32x32x32, you can even make your tile indices 16-bit.

You can also do sneaky tricks as well, like using the high order bit of your chunk or tile indices to mean something special. So if an entry in the tile matrix has the top bit set, then the lower 31 bits don't mean a tile index, instead they mean a 'warp index' or something similar, and you can look that up in a separately maintained list to find out the coordinates it leads to.

share|improve this answer
    
I'd caution anyone coming across this question in the future: While nothing in this post is incorrect, it's honestly horrible for a game like Minecraft, which has a non-sparse world. (And MrCranky says as much.) Your world only benefits from this if it has a few somethings and lots of nothings, not a few somethings and lots of empties. –  user744 Dec 6 '10 at 22:11
1  
I heartily agree that the overhead involved in maintaining a sparse data set storage solution is pretty high, so you'd only go for it if the balance was clearly skewed towards sparseness. The key factors here are: cost-of-data-item and probability-that-data-item-is-unused. Minecraft has a massive, massive potential data set (some large number of tiles in each direction). The actual proportion of the potential game world used is tiny. Even though you claim large swathes of it as you move around the world, it's still a tiny fraction of the potential data items. –  MrCranky Dec 8 '10 at 15:18
1  
What makes Minecraft different is that the per-unit cost is tiny - it's a single byte of storage maybe? One value indicates 'nothing there', the rest are block types, and you could easily fit that in a byte. So you wouldn't have an index to a single block, that's just mad, the index is much larger than just storing the actual block value. But the sparse data set rules still work at the higher levels. Each chunk (e.g. 64x64x64) is expensive to store (256K blocks), so if you can use a single small value to indicate it's absence, or its address if it does exist, then you've saved massive storage. –  MrCranky Dec 8 '10 at 15:21
add comment

Why can't you store one million tiles in memory? Even my phone has 256MB RAM; a million empty tiles is going to be what, 4-32MB?

share|improve this answer
    
It just seemed such a huge number to be storing. As well as that, it's also going to take a long time to update them. –  The Communist Duck Nov 29 '10 at 21:18
2  
It's a lot easier to just ignore a set of tiles for updates than it is to deal with some kind of disk-paging solutions. Just.. ignore them. Don't update tiles more than X distance from a known actor. –  user744 Nov 29 '10 at 21:45
2  
@TheCommunistDuck The only thing that matters is the total amount of memory used to store the tiles, not the number of tiles. –  Justin Nov 29 '10 at 22:35
1  
Agreed with Kragen and Joe. Don't worry about what sounds like a lot - do the mathematics and work it out. It's unlikely to be an issue. –  Kylotan Nov 30 '10 at 0:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.