One problem is that all operations in octree are O(log n). For a world as big as minecraft, each operation takes 26 times longer to complete.
2 Likes
You dont always need to traverse the biggest sectors of the Octree however, you can do shortcuts to decrease “n” significantly, by starting with the innermost possible Octree Segment (which contains everything in view range) instead of the outermost (which contains EVERYTHING).
2 Likes
I would imagine the ‘top’ of the tree would be decently low level, with a ‘page’ being paged in an out en masse.
2 Likes
Maybe I’ve misunderstood your idea. I think you are using octree to generate world dynamically, implementing Microblocks and overview . In other words, use octree as a 3D segment tree. Is that true?
2 Likes
Uh, I am not well versed with professional terms for things so, I dont exactly know what you mean? But it might sound correct? I am not sure.
2 Likes
Ah, then I think you mean that to update lowest common ancestor of every reachable blocks. It might works well in many place, but no effect on special situations: For an example, it will still need to update to root of Octree when you standing at center of the world.
2 Likes
Another problem is how to locate blocks. When using “micro blocks”, you can’t just use a coordinate to find for a block. A probable solution is to use a binary sequence to show the path from root, an u128 can keep about 42 levels.
It might be hard to use for users, but coordinates can be prevented to use. In gregtech, there are only a few usages, and all of this can be replaced by latitude and longitude or so on.
As for this, I haven’t got an idea.
O(log n) isn’t growing slowly when n is small. Even updating a chunk of minecraft (16 blocks) will cost 4 times time.
2 Likes
Isn’t there an easy way to handle that though? If every Node knows about which types of “Blocks” are contained in the Sub-Nodes, it could make it much easier to “find” Blocks without having to iterate over an Area that for example does not contain ANYTHING that you are looking for.
That would make searches insanely performant, since you could scan an entire Planet by just looking at the Sets that the Root Nodes have of the contained Blocks.
Edit:
And Blocks that have specific Boundaries, could easily encode those Boundaries in their non/less-searchable Data. Would only need one Coordinate if the Boundaries are fixed for that type of Block.
Also everything will be “encouraged” to stay in line with the 0.25m Grid. Sure you CAN place things off-grid, but that will involve holding a Key or something… wait I would probably default that to the Caps-Lock or Scroll-Lock indicators, which would make that easy… Well but it will be difficult to place things “perfectly” the way you want, because it always is… unless I make it snap to (potentially off-grid) walls, floors and ceilings if the cursor is close enough… well it will align to the Grid by Default, that is enough encouragement!
2 Likes
Why not? The unit of measure should be 0.25m3 instead of 1m3. The distance between (0x,0y,0z) and (0x,0y,4z) would be 4*0.25m, or 1m. If you want the user to think in terms of meters just do the conversion in the UI code.
The trade off compared to a flat array is the smaller footprint. Any given world will be broken up into regions. That puts an upper limit on the depth of the octree.
Minecraft regions are 512x512x256 m. 2048x2048x2048 0.25m3 will have depth=11.
~Max
3 Likes
Microblocks are Single-Voxel Blocks not 0.25m Blocks. 3.125cm to be precise.
And the breaking into Regions Part is more for making it possible to do Massive-Multiplayer easier, and will have fuzzy borders, and not straight grid aligned lines. I might even scrap that part of the Idea if it turns out too complicated to implement.
2 Likes
Another thing I should maybe mention, it is perfectly feasible to just have Entities cache the 1 to 8 Nodes of the Octree that they are inside of. Especially useful for Collision Checks and such. You dont have to traverse the entire damn Tree just for changing minor things.
I am aware that you will probably have to update the “List of contained Blocks” of all Nodes up to the Root Node, but if you are placing a Wall of Cobblestone Blocks, you wont even need to go all the way up to Root, just up to whatever Node already has Cobble in it.
2 Likes
The trouble is when removing the block, one will have to check all siblings to see if the material was inherited only from the single point that was just removed. Yes, still not up to Root in general, but a much larger computational overhead.
Caching up to the eight corners of AABB for the entity collision, versus caching a single point location, to avoid traversing from Root to find world blocks at the entity’s coordinates makes a lot of sense for large worlds. Bit of memory vs search balance there, and relies on how easily siblings are linked for the search.
2 Likes
The worst case would be if you removed the only piece of Cobblestone that existed on the entire Planet, which considering how I plan on spontaneously generating “Block States”, might be a very common case actually. However I dont think that will matter a lot, because if you have looked at how Minecraft handles the setBlock Function, yeah that one is inefficient as fuck and will likely be much more laggy than my Octree thing.
After thinking about it, it could just be always 8 Nodes too, if that makes iteration for collision and storing the Nodes easier, since even if you happen to be in 1 Node, that Node could still be split in 8. 
2 Likes
Wait, you are going to storage blocks and doing entity collision in single octree? Won’t it make things more complex?
2 Likes
How exactly do you mean that complexity bit? Because each Pixel/Voxel would have a simple boolean for if it is collidable or not, along with a second boolean for if it has a special effect on movement (like Water would have).
2 Likes
I’m not sure about this, but I’v thought processing entity collisions need to insert AABBs into octree, and I think map and collisions should be processed separately.
2 Likes
You know that Gigantic Zombie that Minecraft has hidden in the Code? Imagine it would only collide with full Blocks, that is about what you would need to expect in complexity. No real need for Axis Aligned Bounding Boxes (AABB) inside of each individual Voxel.
And since they are so small, most of the time you wont even have to know if the Voxel is sloped or not.
1 Like
Why would you need to do that?
~Max
2 Likes
To prevent things from checking for “does this Block exist anywhere in this area” and returning true for that check despite there being none of that Block.
1 Like
So far the only state data is color, which I have cached in the octree’s interior nodes. I can add other properties to the BlockState struct, and plan on doing so at a later time, but I don’t know if we should cache anything else in the octree itself. Each property cached adds a considerable memory footprint.
Answering the question “do any leaf nodes in a given area match this color exactly” will not involve the color data cached in the octree’s interior nodes, except maybe a null check to see if the node is completely empty. This is because the interior node’s color, at least as I envision it, is the average color of its child nodes. Looking just at the cached color, you can’t distinguish between a node whose children average out to the color you are searching for, and a node whose children all match the color you are searching for.
When changing the color of a single voxel, if color is cached (which it currently is), all of the nodes up-tree are dirty and must be updated. That does involve querying all eight children to compute a new color; however, I can mark nodes as dirty and batch the update calls, or update lazily, theoretically at a cost of one bit per node.
It may not be necessary or wise to cache even color into the octree. I mentioned this before, but I have no idea how to code for a GPU. Not only do I lack the knowledge, my computer also lacks a dedicated GPU chip… not really sure how that works.
~Max
2 Likes