I want to write a simple game with a block world like in Minecraft. My theoretical question is what is the best way to handle this block informations during playing. My first Idea was a huge array but this will cause running out of memory I think. Maybe I have to only load the blocks near the player.
How can I handle the loading of needed block informations from a file and the holding only of needed ones in memory?
Answer
There are a couple different ways to store the data for a game with blocks like Minecraft.
The way I believe Minecraft does it is breaks the world up in the 16x16x256 Chunks. The chunks around the player are loaded into memory when the player starts the game, then a background thread loads more as you walk around. Here is a video that shows it: http://www.youtube.com/watch?v=oR_ZdJH9eho.
Another way to do it is to break the world up into an Octree. Michael Goodfellow wrote a blog about implementing a cube world with this data structure: http://www.sea-of-memes.com/LetsCode1/LetsCode1.html. The Octree is nice because it gives you some built in compression, but it will probably be a little harder to work with then an Array.
About keeping the "only needed ones in memory?" This is a little harder since you have to ask what is "needed". If you have NPCs that live in another part of the world with AI that interacts with the environment then you "need" a lot more of the world to be in memory. Voxel world data can get very large very fast, so it is best to try to keep the least possible amount in memory. (IE, only have NPCs near the player).
The graphics engine will "need" every block not completely surrounded by other non-transparent blocks. The usual way to render the world is to build a single mesh that contains the vertices for every visible block. This is much faster to draw since you are only making 1 call to the draw methods for 65,536 blocks (in Minecraft size chunks). Since the graphics engine will need to build this mesh, it generally needs to know all the cubes in a chunk. Note that this is why when you see through the floor in Minecraft, a lot of the world is invisible. This is because every block that is surrounded on all six sides is skipped. I believe Minecraft also reduces the number of vertices by combining horizontal sides of the same kind of texture into one box with the texture repeating.
My advice would be to go with the 16x16x256 chunks. Store them in an Array since you will need fast iteration and editing due to building the mesh and game logic (collision detection, adding/removing blocks, ect). Then load as many chunks in a circle around the player as you can. Scale the number of chunks up or down for better or worse computers.
The loading of Chunks will be a huge hit on performance, so put it in a thread that runs it over time. Make it so you can completely load 3 new Chunks during the time it takes a player to walk from one end of a chunk to the other.
No comments:
Post a Comment