# 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.

• Do you mean Minecraft-like? That is, voxel? – The Communist Duck May 24 '11 at 11:57
• Have you looked into octrees? en.wikipedia.org/wiki/Octree – bummzack May 24 '11 at 12:42
• Have you tried profiling your game? It may show some key areas where the most time is being spent. It may not be what you think it is. – deceleratedcaviar May 24 '11 at 13:37
• Rather than drawing all 6 faces of each cube, you could only draw the faces that aren't in contact with anything – David Ashmore May 24 '11 at 14:47
• @David: Yeah, or he could stop doing a single draw call per cube first, and then worry about individual polygons later. – Olhovsky May 24 '11 at 17:49

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.

• I would say i get it, but unfortunately i don't. The collision boxes of the blocks aren't moving, only the collision box of the player. And i have a method now which (without looping through all the blocks) returns all the blocks that are within a 5 block radius of the player. Sorry for the hassle, but any clarification? By the way, to make it simpler could you assume the world is 64 x 64 x 64? – Joel May 24 '11 at 13:02
• And i am still getting around 5fps :( – Joel May 24 '11 at 13:03
• I re-worded my answer, let me know if it helped. – deceleratedcaviar May 24 '11 at 13:24
• So i narrow down the blocks in which the player could be, using this octree technique. I'm pretty sure i get that. But are you suggesting i use my collision detection once i have narrowed it down to just a small selection of blocks, or do you have some other method? – Joel May 24 '11 at 13:32
• Unless the player is very large relative to the size of the cubes, then checking collision around the player is probably the fastest way. If the player occupies no more space than one cube for example, then he only needs to check 27 surrounding cubes at most, to find a collision. This does not require a tree as you can index directly into those cube locations, assuming he stores the cubes in an array that he can index into, with one slot allocated for every possible cube location. – Olhovsky May 24 '11 at 17:38

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.

• +1, totally agree. You shouldn't be looking into algorithms, you should be looking at profiling your code. My guess is it's nothing to do with the fact that you're iterating through the blocks (it's not that many), it's what you are doing with each block. Ultimately yes you need to have a better method than brute force, but if you can't handle a simple iteration on 48x32x48 cubes, you need to rethink what you are doing with each cube, not how you are looping. – Tim Holt May 24 '11 at 15:33
• @Tim: Unless his player is large enough to occupy a space of 48x32x48, then he should not be iterating through anywhere near that many cubes. If he is iterating through 73000 cubes per frame, then I can tell you without doing any profiling, that it's worth it for him to fix that, if for no other reason than to learn how to avoid doing tens of thousands of times more iterations than are necessary. This is not what I would call micro or premature optimization. – Olhovsky May 24 '11 at 17:45
• My player is less than the size of 1 cube, though may be larger at some stage (but not much) – Joel May 25 '11 at 5:10
• Randomman159: Then you only need to test against his surrounding 27 cubes to find collision. See my answer. – Olhovsky May 25 '11 at 9:45

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.

• Or you could have a 'bounding box' that surrounds the player, and then you simply check what objects it is colliding with to determine what objects the player should collide with. A good physics engine will be able to do all the optimizations for you; it will also allow for more than just 'blocks' to collide with. – deceleratedcaviar May 25 '11 at 0:08
• Personally, I would not want to rely on a physics engine's broadphase to test against 73000 cubes for me, when I could just write two dozen or so lines of code to efficiently test for collision for me. Also, he probably doesn't have a physics engine to tap into at this time. – Olhovsky May 25 '11 at 9:48

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.)

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.

• Problem here is more complicated, because you have only 2 coordinates for your mouse, to test with 3D world. If the view was top-down, you could find 2 out of 3 right indexes for a mouse position, and then loop for height, starting from top - closer to camera, and find first occurence of a block. – Markus von Broady Oct 11 '12 at 8:24