Hello,

I was thinking about structure for storing building block information, and I consider two most common approaches:

1) Array grid (x, y, z) containing block information, pros - very easy and quick access to adjacent blocks, easier to work with, cons - uniform block size, no easy way to store bigger and smaller units, takes large amount of storage even if most of blocks will be empty

2) Octree, pros - smaller space requirement, possibility to have different size of building blocks, cons - hard (?) to acquire adjacency information

I require adjacency information to check whether I can build something - like disallowing putting some block in thin air if there is no support below, so I need to check what is below. With array grid its simple, just query block thats [0, -1, 0] from current block position. With octree it becomes more complicated, not only because I don't have easy access to information at a given location (like whats at x, y, z) but also that blocks are not uniform anymore.

Is there some solution to allow quick access to neighbouring "blocks" when using octree? Lets say I'm interested in blocks of same size (so if it turns out that below block of size 4x4 there are smaller, subdivided blocks, I just consider there is either full block or no block, don't dig deeper into what those blocks are), so I guess this limits the depth I will be searching for, then I need to step up to parent node and check specific nodes around? How do I know if that node contains neighbours of my block?

I hope you get what I'm looking for, if not I will try to provide some diagram later

I made a diagram that shows 3 cases where I need to query elements below block that I will be building. Red border shows block I wanna build, gray blocks mean solid type block. I used quadtree because its easier to represent but consider it as a 2D slice of 3D octree - I marked UP direction with an arrow.

Where are we and when are we and who are we?
How many people in how many places at how many times?

One other advantage of QuadTrees and OctTrees is that the search time is logarithmic rather than exponential.

Here are some ideas you could try:
-Array grid could contain the smallest allowable blocks, and larger irregular blocks are composed of lots of smallest blocks.
ie, smallest block would be 1x1. A 1x2 block would be two 1x1 blocks linked together. You'll have to create four "connectors" for each block object (left, right, top, bottom) which point to attached neighbors.

-OctTree Method: Find the adjacent blocks when you're construction the octtree and put that data into the node. Figure it out conceptually before writing the code.

You can think of octrees as mipmapped 3d grids with some space saving hax.

So you can index them just like images, using a position and the level/depth.

If you keep octree nodes in an array, it's possible to work out the nodes adjacent to any particular node without too much hassle, provided you have the index and depth of the node.

Let's consider a quadtree for simplicitly, but the idea extends to an octree naturally.

Start with a division of the entire space, giving us 4 initial nodes. Walking clockwise, put the top-left at index 0, top-right at index 1, bottom-right at 2 and bottom-left at 3.

Now sub-divide the top left into four nodes. In the same clockwise ordering, these will be placed at indices 4, 5, 6, 7. The subdivisions of the top-right will 8, 9, 10, 11. After those go the subdivisions for the bottom-right and finally for the bottom-left. Keep doing this as far as is required.

[s]Now, given a node at depth K, where K = 0 means the initial four nodes, take a look at bits 2K and 2K+1. These bits tell you the position of the node within it's parent. Go 2 bits lower and those tell you the position of your parent node within its parent, and so on. [/s] Now given a node's index, the lower two bits tell you its position within its parent (0 => top left, 1 => top-right, ...). Also, dividing its index by 4 with integer truncation and subtracting 1 gives you the index of the parent. So you have enough here to derive adjacency information without actually storing, say, pointers in your nodes. For an octree, you'd look at the lower 3 bits and do divisions by 8, I think.

If you aren't uniformly dividing everything, you could perhaps use a hash-table to represent a sparse array, or if your tree is shallow, perhaps having an 'unused' flag in the array elements would suffice.

You can also use a x,y,z position.

so to know which child node to go to, you take (x[curDepth],y[curDepth],z[curDepth]) (component[depth] takes the depth:th pixel of the component) which gives you a bool,bool,bool which corresponds to 1 of the child nodes.

Though edd's way of having all of it in a single integer would probably be more space efficient if that matters.