4 ms·

I’m a bit short on time and can’t dig into the code, but maybe somebody can answer this for this or the original version: In what data structure are the blocks

I’m a bit short on time and can’t dig into the code, but maybe somebody can answer this for this or the original version: In what data structure are the blocks in Minecraft actually stored? And by which mechanism are they quickly retrieved to check which block the player was hitting? I would think the model partitions the space with an octree and their position jumps from parent node to parent node. Then at each bit we just have to go through 8 elements to find a block and all the entities for this partition.

garba_dlm 3y ago
this is the kind of question a co-pilot programming assistant AI should be able to answer with direct quotations of the relevant code
lelandbatey 3y ago
A bit of searching implies that they are not stored as Octrees due to "performance reasons": > [...] To understand why octrees are slower for Minecraft games, it isn’t really necessary to invoke such exotic explanations. The underlying reason for the worse performance is purely algorithmic: each time an arbitrary voxel is touched, either when iterating or performing a random access, it is necessary to traverse to the entire height of the octree. Since octrees are not necessarily balanced, this can be as much as log(maximum size of game world)! Assuming the coordinate system is say 32 bit, this brings an added overhead of 32 additional non-coherent memory accesses per each operation that touches the map (as opposed to the flat array, where everything is simply constant time). https://0fps.net/2012/01/14/an-analysis-of-minecraft-like-engines/ https://0fps.net/2012/01/14/an-analysis-of-minecraft-like-en...
- protoman3000 3y ago
  Thanks a lot! Posts like yours are exactly what make this community great.
Tuna-Fish 3y ago
Why would you need a tree? You always know the location of the player in x,y,z. The world is extremely regular, first you figure out the co-ordinates of what you are hitting, then you do a direct lookup of that from the world, with like a single top-level hashtable that links to large fixed-size segments. This will be dramatically faster than any tree.
Macha 3y ago
https://minecraft.fandom.com/wiki/Anvil_file_format https://minecraft.fandom.com/wiki/Anvil_file_format https://minecraft.fandom.com/wiki/Chunk_format https://minecraft.fandom.com/wiki/Chunk_format The main unit of minecraft storage is the chunk, which is a 16x16xWorld height area of the map. Chunks are bundled into groups of 32x32 chunks for storage on disk. Minecraft keeps a map of chunks for an area of (configured render distance + 3) chunks in memory, and pages these in and out as you move around (including generating new chunks if you reach a chunk that's never been generated before). Chunks themselves are subdivided into 16x16x16 sections of blocks by vertical height. So the process is: 1. Find chunk containing co-ordinate (maths + dict lookup) 2. Find array containing data based on y co-ordinate (basically an array lookup) 3. Find block in array (another array lookup) There's also various data of more variable size (e.g. lists of entities, structures, etc.) tacked onto the chunk format. These tend to be much smaller in number for any given chunk, so my understanding is these are basically just linearly searched or iterated on a per chunk basis when required.

garba_dlm 3y ago

this is the kind of question a co-pilot programming assistant AI should be able to answer with direct quotations of the relevant code

lelandbatey 3y ago

A bit of searching implies that they are not stored as Octrees due to "performance reasons": > [...] To understand why octrees are slower for Minecraft games, it isn’t really necessary to invoke such exotic explanations. The underlying reason for the worse performance is purely algorithmic: each time an arbitrary voxel is touched, either when iterating or performing a random access, it is necessary to traverse to the entire height of the octree. Since octrees are not necessarily balanced, this can be as much as log(maximum size of game world)! Assuming the coordinate system is say 32 bit, this brings an added overhead of 32 additional non-coherent memory accesses per each operation that touches the map (as opposed to the flat array, where everything is simply constant time). https://0fps.net/2012/01/14/an-analysis-of-minecraft-like-engines/ https://0fps.net/2012/01/14/an-analysis-of-minecraft-like-en...

protoman3000 3y ago
Thanks a lot! Posts like yours are exactly what make this community great.

Tuna-Fish 3y ago

Why would you need a tree? You always know the location of the player in x,y,z. The world is extremely regular, first you figure out the co-ordinates of what you are hitting, then you do a direct lookup of that from the world, with like a single top-level hashtable that links to large fixed-size segments. This will be dramatically faster than any tree.

Macha 3y ago

https://minecraft.fandom.com/wiki/Anvil_file_format https://minecraft.fandom.com/wiki/Anvil_file_format https://minecraft.fandom.com/wiki/Chunk_format https://minecraft.fandom.com/wiki/Chunk_format The main unit of minecraft storage is the chunk, which is a 16x16xWorld height area of the map. Chunks are bundled into groups of 32x32 chunks for storage on disk. Minecraft keeps a map of chunks for an area of (configured render distance + 3) chunks in memory, and pages these in and out as you move around (including generating new chunks if you reach a chunk that's never been generated before). Chunks themselves are subdivided into 16x16x16 sections of blocks by vertical height. So the process is: 1. Find chunk containing co-ordinate (maths + dict lookup) 2. Find array containing data based on y co-ordinate (basically an array lookup) 3. Find block in array (another array lookup) There's also various data of more variable size (e.g. lists of entities, structures, etc.) tacked onto the chunk format. These tend to be much smaller in number for any given chunk, so my understanding is these are basically just linearly searched or iterated on a per chunk basis when required.