Working with lots of cubes. Improving performance?

Question

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 1

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.

Answer 2

I agree with Daniels answer, in that iterating through large amounts of boxes is the most likely cause, and that by using spacial partitioning you could speed the game up a lot - but the problem could also be elsewhere, and you could be wasting your time.

In order to increase the speed of your game significantly you need to profile your code. Identify where the bottleneck is, this will allow you to make the biggest improvements.

There are lots of ways to profile your code, you could roll your own performance analysis class (which could make use of the Stopwatch class (MSDN)), or you could use PIX to get a general idea of how busy the CPU/GPU is.

You can also put PIX event markers in your code, which will show up as colored regions in PIX's readouts. There isn't an official C# interface to these functions, but this thread shows how you can make a C# interface yourself.

Answer 3

If your player is large relative to the size of the cubes, then you probably want an octree or other spatial partitioning structure, as other's have suggested.

However, if your player is small relative to the size of the cubes, then probably the fastest way to detect collision with the cubes is to do a simple linear search of the area around the player.

Since your player is smaller than 1 cube, then you only need to test for collision against the neighboring 27 cubes, at most.

This assumes that you store the cubes in an array that you can index into, with one slot in the array for every cube.

As other's have pointed out, you need to profile your code to see what is actually slowing you down.

If I had to guess though, I'd say that you are probably doing a draw call for every cube, which would be your bottleneck by far. To fix that, you should look into geometry instancing.

Answer 4

One more suggestion to speed things up: Your blocks are approximately fixed--that means that there's no way a player can collide with most of them. Add a boolean to blocks indicating whether they are exposed or not. (This can be recalculated by looking at their neighbors.) A block which isn't exposed need not be checked for collisions.

It's obvious Minecraft does something akin to this--I hit a non-loaded chunk once that gave me a view into the world--I could see right through the solid ground, all that showed up was the open spaces (the far side of them was an exposed surface and therefore rendered.)

Answer 5

I had that issue with my voxel engine.

Solution: (Much simpler than octrees) Instead of looping through all the blocks, just use an equation to determine the position of the block in the blocks array.

BlockIndex = (x * WorldWidth * WorldHeight) + (z * WorldHeight) + y;

Then if you want to see if a block exists:

Blocks[BlockIndex].Type > -1;

Or however you determine if the block exists.