4

I will have to implement an endless 3D raster map in program memory. The map may or may NOT start at [0;0;0]. The map has Y coordinate limited by 255, others may be infinite. (yes, now, you may have guessed it is a Minecraft map)
I need to create some class which will have simple McMap::getBlock(int x, short y, int z) and McMap::setBlock(int x, short y, int z) method. Means I need to be able to both read and write the data. I also want to be able to delete blocks and so free the memory.
What should user for this purpose? I think the best solution would be some table with such structure:

int x|short y|int z|int block id|other values...
-----+-------+-----+------------+---------------
   55|     21|  666|           1|

But how do I implement this with C++, without using real MySql (that would be real overkill)? Also, I don't want to keep the map when the program exits, so I want the data to be inside the programs memory.
Once more, consider that the map is infinite and so the coordinates may be whatever. Also do not forget that a very distant points may be mapped.
Also, a very important thing to note: I need to have an effective way to get block by X, Y and Z coordinates - I don't want to walk through all block to find one of them.
I have already included library.

4

2 回答 2

3

You can decompose your map in chunks, like in minecraft. Each chunk is W * H * L (x y z) blocks. So, a chunk is just a 3d array. The best to do is to wrap it into a 1d array:

BlockType* chunk = new BlockType[W * H * L];
BlockType block = chunk[x + z * W + y * W * H];

This is to have a good memory management (and is a lot better than storing the whole possible map in an array). Note than accessing a block in a chunk is O(1) and here should be very fast.

Then, you can store your chunks. Each chunk is given 2d coordinates that are its id. The fastest (for access) should be a std::map:

std::map<ChunkCoord, ChunkType*> map;

Access to block is fast. You need to get the chunk (a division should give you the chunk coords from point coords), then you get the block. Accessing a chunk is in O(log(numChunks)).

Creating a chunk is allocating memory and creating a new item in the map. You will still be limited by the amount of memory in the computer (infinity is not part of this world...), that's why minecraft-like games often save unused chunks to disk. Saving to disk is the only way to have a near-endless map.

The tricky point is to find good values for W, H, and L. For this, I'm afraid you will have to test and measure a lot...

Note: extending this idea leads to quadtrees. You can use them, but they may have too much memory overhead.

于 2013-03-30T16:27:17.260 回答
3

I assume you probably wouldn't need to the have entire possible area of a Minecraft world in memory time because that would be incredibly huge (1024000000 KM^2). If you are just trying to keep the area that anyone would usually end up visiting during a game in memory I think it would be completely feasible to access it using STL (Standard template library).

Minecraft worlds are always loaded in game in chunks which are 16X16X255 blocks. You could store chunks in your program in a std::map. There are a few advantages to this method. The first is it allows representation of locations well beyond the playable area of the map based on the wiki entry for the Far Lands. It also allows for a sparse representation of the minecraft map that will very closely resemble how actual Minecraft maps are rendered. Only the chunks that you are using for your program are loaded in the std::map and hopefully keep memory usage reasonable. You would be able to represent any area no matter its location in the playable area of the total possible Minecraft map area.

To implement this you will just have to first create the world datatype:

using namespace std;
struct Block
{
     // Whatever information you care to store here...
};
typedef vector<block> Chunk;
typedef map<int, map<int, Chunk> > World;

Then to access a single block:

Block McMap::getBlock(int x, short y, int z)
{
    const int WIDTH = 16; // You might want to store these constants elsewhere
    const int HEIGHT = 255;
    int chunkx = x / WIDTH;
    int chunkz = z / WIDTH;
    return yourWorld[chunkx][chunkz][x + z * WIDTH + y * HEIGHT * WIDTH];
}

To erase a chunk:

void McMap::eraseChunk(int x, int z)
{
    if (yourWorld.find(x)) // Tests to make sure that row exists in the map.
        yourWorld[x].erase(z);
}

Another benefit to using this method is that by creating a clever constructor for a chunk rather than just using a typdedef like I did you could automatically generate a chunk when you need to access a new chunk in the world std::map similar to how chunks are generated in Minecraft only when you visit them. Whenever you access an object that does not exist yet in a map it will call the default constructor for that object.

于 2013-03-30T16:42:25.710 回答