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.
Answer
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.
No comments:
Post a Comment