xna - Working with lots of cubes. Improving performance?

Edit: To sum the question up, I have a voxel based world (Minecraft style (Thanks Communist Duck)) which is suffering from poor performance. I am not positive on the source but would like any possible advice on how to get rid of it.

I am working on a project where a world consists of a large quantity of cubes (I would give you a number, but it is user defined worlds). My test one is around (48 x 32 x 48) blocks.

Basically these blocks don't do anything in themselves. They just sit there.

They start being used when it comes to player interaction.

I need to check what cubes the users mouse interacts with (mouse over, clicking, etc.), and for collision detecting as the player moves.

Now I had a massive amount of lag at first, looping through every block.

I have managed to decrease that lag, by looping through all the blocks, and finding which blocks are within a particular range of the character, and then only looping through those blocks for the collision detection, etc.

However, I am still going at a depressing 2fps.

Does anyone have any other ideas on how I could decrease this lag?

Btw, I am using XNA (C#) and yes, it is 3d.

Answer

Sounds like you're looking to learn about Trees!

And I'm being serious, if you're currently looping over an array of all your cubes, then you really should look into various spatial data structures. For this case, the best way to re-imagine your cube world is as a tree.

Before we go into the reasons as to why, lets think about our problem. We're looking for a solution where, for as little cost as possible, we can retrieve a list of nearby cubes that the player may be colliding with. This list should be as small, yet precise as possible.

Now to determine this zone, we need to map our player's coordinate space to the coordinate space of the cube map; that is, we need to map the floating point position of the player to a discrete index of the multi-dimensional array of cubes (example notation might be world[31][31][31], i.e. exact middle for a 64*64*64 multidimensional array).

We could simply calculate the surrounding blocks using this same discrete indexing, perhaps sampling only the nearby cubes, but this still requires constant recalculation, and doesn't allow for any objects that aren't discrete in placement (i.e. may not map to the cube map).

The ideal situation is a set of buckets which contain our sets of cubes for particular sections of our cube map, divided equally so instead of recalculating the surrounding area, we simply move in and out of these zones. For any non-trivial calculation, holding our data like this could eliminate iterating all the cubes, and only these individual sets that are nearby.

The question is: How do we implement this?

For the 64*64*64 world, imagine it broken down to 8*8*8 zones. This means that in your world, you will have 8 zones per axis (X, Y, Z). Each of these zones will contain 8 cubes, easily retrievable by this new simplified index.

If you needed to perform an operation on a set of nearby cubes, instead of iterating every cube in your world, you could simply iterate over these zones, breaking down the maximum number of iterations from the original 64*64*64 (262144) to just 520 (8*8*8 + 8).

Now zoom out from this world of zones, and place the zones into larger super-zones; wherein each super-zone contains 2*2*2 regular zones. As your world currently contains 512 (8*8*8) zones, we can break the 8*8*8 zones into 64 (4*4*4) super-zones by dividing 8 zones by 2 zones per super-zone. Applying the same logic from above, this would break the maximum iterations from 512 to 8 to find the super-zone; and then a maximum of 64 to find the proceeding zone (total max 72)! You can see how this is saving you a lot of iterations already (262144 : 72).

I'm sure you can see now how useful trees are. Each zone is a branch on the tree, with each super-zone as a preceding branch. You are simply traversing the tree to find what you need; using smaller sets of data to minimize overall cost.

The diagram below should help you visualize the concept. (image from Wikipedia:Octrees):

Disclaimer:

In an ideal set up as above, where your voxel-world is already laid out in a fixed size multi-dimensional array, you could simply query the player position, then index surrounding blocks with an O(1) cost! (See Olhovskys explanation) But this becomes more difficult when you start considering that your world is rarely fixed size in a voxel game; and you may need your data-structure to be capable of loading entire super-zones from HDD to memory. Unlike a fixed size multi-dimensional array, trees readily allow this without too much time spent on combinatory algorithms.