Embedding an infinite card in memory

Question

I will need to implement an infinite three-dimensional raster map in the program memory. A card may or may not begin with [0; 0; 0]. The map has a Y coordinate limited to 255, others can be infinite. (yes, now, perhaps you guessed it was a Minecraft map)
I need to create a class that will have a simple method McMap::getBlock(int x, short y, int z) and McMap::setBlock(int x, short y, int z) . So I need to be able to read and write data. I also want to be able to delete blocks , so frees up memory .
What should the user be used for? I believe that a table with such a structure would be the best solution:

 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 (this would be a real overkill)? In addition, I do not want the card to be saved when the program terminates, so I want the data to be inside the program memory.
Think again that the map is infinite , so the coordinates can be independent of . Also do not forget that you can display points very distant .
In addition, it is very important to note: I need to have an effective way to get the block by the coordinates X, Y and Z - I do not want to go through the entire block to find one of them.
I already turned on boost .

Answer 1

I assume that you probably won’t need to have all the possible area of ​​the Minecraft world during your memory, because that would be incredibly huge (1024000000 KM ^ 2). If you are just trying to keep an area in which someone would normally visit while playing a game in memory, I think it would be entirely possible to access it using STL (the standard template library).

Minecraft mines are always loaded into the game in pieces that are 16X16X255 blocks. You can store chunks in your program in std::map . There are several advantages to this. Firstly, it allows you to display locations well above the playing area of ​​a map based on a wiki entry for Far Lands . It also allows a rare view of the minecraft map, which is very close to how real Minecraft maps are displayed. Only those pieces that you use for your program are loaded into std::map and, I hope, it is wise to use memory. You could represent any area regardless of its location in the playing area of ​​the total possible area of ​​the Minecraft map.

To implement this, you just need to first create a world data type:

 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 one 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 fragment:

 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 advantage of using this method is that by creating a smart constructor for a piece, and not just using a typdedef like me, you could automatically generate a fragment when you need to access a new fragment in the std::map world, like how pieces are generated in Minecraft only when they are visited. Whenever you access an object that does not yet exist on the map, it will call the default constructor for that object.

Answer 2

You can lay out the card in pieces, for example, in minecraft. Each block is W * H * L (xyz). So a piece is just a 3D array. It is best to wrap it in the 1st array:

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

This should have good memory management (and much better than storing all the possible card in an array). Please note that access to the block in the piece is O (1), and it should be very fast here.

Then you can store your pieces. Each block is assigned 2d coordinates, which are its identifier. The fastest (for access) should be std :: map:

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

Access to the unit is quick. You need to get a piece (the unit should give you pieces from the point coordinates), then you get a block. Access to the fragment is performed in O (log (numChunks)).

Fragment creation - memory allocation and creation of a new element on the map. You will still be limited by the amount of memory on your computer (infinity is not part of this world ...), so games like mini-games often save unused pieces on disk. Saving to disk is the only way to have an almost endless map.

The difficult task 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 quadrants. You can use them, but they may have too much overhead.