I have a somewhat unconventional (I think) desire for a C++ container. Right now, I am storing a bunch of chunks of a tiled level map (2D game) in a 2D vector. I am currently changing it, so that it only keeps the chunks that are near the player in memory. The rest are saved to disk, and as the player moves between chunks, it saves the old ones and loads the ones the player enters. At all times, the player (and other game objects) keep track of their current location in the world, in terms of "chunk coordinates."

What I want to be able to do is keep the whole "only a few chunks are in memory" thing transparent for the objects in the game. If a Player object wants to look at tiles around itself for collision detection or what have you, it can look in the current chunk. It would access this by something like "world[chunk_location_x][chunk_location_y].tilesblahblah."

The problem with this, of course, is that if only a few chunks are in memory, the coordinates won't match up with the location in the vector where the chunks are stored. What I would love to be able to do is keep the vector at the size of the whole world, but only have it actually hold data for chunks in memory. So, for instance, the whole 'world' 2D vector would be WORLD_SIZE_X by WORLD_SIZE_Y all the time. Most elements at any given time would be NULL, instead of the usual Chunk data they hold. As far as I know, there is no way to do this. Is there a way that I am unaware of? Or another container that can be used in this way?

I can think of a solution to this, but it wouldn't be as pretty as I'd like. I could use a 3D vector instead, and for each of the usual 2 dimensions, have either 0 or 1 elements in the third dimension. 0 elements would mean that chunk was not loaded, 1 would mean it was. The only reason I don't like this idea is that I would have to access the world vector all over my code with something like "world[chunk_location_x][chunk_location_y][0]," and that would not look as nice.

you could expand upon this idea by using a bitfield that is maxElements/sizeof(int64) in size (aligned propperly of course) and just bit twiddle because then with a single compare you can check 64 elements for being in use and unload if they are not in use.

something like this

for(int i=0;i<chunks.length;i++)
{
if(chunks.bitfield != INT64MAXVAL)
{
// check this chunk
}
}


[quote name='Dark_Oppressor' timestamp='1304669882' post='4807279']
I can think of a solution to this, but it wouldn't be as pretty as I'd like. I could use a 3D vector instead, and for each of the usual 2 dimensions, have either 0 or 1 elements in the third dimension. 0 elements would mean that chunk was not loaded, 1 would mean it was. The only reason I don't like this idea is that I would have to access the world vector all over my code with something like "world[chunk_location_x][chunk_location_y][0]," and that would not look as nice.

Well, then write a wrapper around that "not as nice" looking construct. I guess If i were in your place I'd either use a Hash Map with some sort of unloading strategy (mark every element with the time it was last used and when there are too many chunks loaded at the same time unload the "oldest" ones) or have a "local" 2d array and a offset and have everything outside the local array unloaded.
[/quote]

This is not that hard to do. You definitely want to write a class that provides a neat interface that makes the details of swapping to and from disk invisible.

I would implement the class using two containers:
* An unordered_map from ChunkCoordinates to Chunks
* An list of ChunkCoordinates with age, to keep track of when was the last time each chunk was accessed, making sure that obtaining the least recently used one is a fast operation.

In the map you can also keep an iterator to the location of the chunk in the list. This way, when a chunk is accessed you can update the list to move it to the front.

Alternatively, you could use something like the transposition tables used in computer chess. You basically have a fixed-size table of things you remember. Whenever you need to add something to the table, you compute a hash key for your object and try to store it in the location indexed by the lower bits of the hash key. If the location is already taken, you can get rid of whatever was there before. Then you can improve the system by using "buckets", so an object will be placed in one of, say, 8 possible consecutive places in the table, and you'll kick out the least important of the things sitting in that bucket (in your case, the least recently used). This will probably work very well in practice.

I take it that you're talking about the usual way that is nothing but a "window" sliding across your world.

Mapping world coordinates to array coordinates is a simple matter of modulo array size (don't be sloppy with negative numbers). Check your world index against the offset and offset + array size and that's all the extra work it takes (preferably inside some getChunk function that either returns 0 or a pointer to the chunk).

Of course you can overcomplicate things with maps that pretend that the loaded chunks are randomly selected from the world and do weird "is this one loaded" checks.

This. Keep it simple!!!

"A 2d vector", by which I assume you mean [font="Courier New"]std::vector<std::vector<Chunk> >[/font], is rarely what you actually want. If you need to resize it at runtime, use [font="Courier New"]boost::multi_array<Chunk, 2>[/font]. If you don't, then use [font="Courier New"]boost::array<boost::array<Chunk, size_1>, size_2>[/font].

You know which chunks you want at any given time and they have a very particular relationship to each other (adjacency). So you don't need any weird mapping solutions. The idea is simply to treat your buffer as a circular one. We do this with judicious application of the '%' operator and by implementing a strategy for replacing rows and columns at an appropriate time. A given portion of the world will always load into the same location in the grid.