Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
Do you mean Minecraft-like? That is, voxel? –  The Communist Duck May 24 '11 at 11:57
4  
Have you looked into octrees? en.wikipedia.org/wiki/Octree –  bummzack May 24 '11 at 12:42
1  
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. –  Daniel May 24 '11 at 13:37
2  
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
1  
@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
show 2 more comments

5 Answers

up vote 18 down vote accepted

Sounds like your looking to learn about Trees!

And I'm being serious, if your 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 players 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 into the multi-dimensional array of cubes (example notation might be world[31][31][31], ie 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 (ie 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.

But, how to 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 you world currently contains 512 (8*8*8) zones, dividing that 8 by 2 gives you a total of 64 (4*4*4) total super-zones. 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).

Therefore, that is why you need to learn about trees. 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; and using smaller sets of data, to minimize overall cost.

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

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.

share|improve this answer
    
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? –  Randomman159 May 24 '11 at 13:02
    
And i am still getting around 5fps :( –  Randomman159 May 24 '11 at 13:03
    
I re-worded my answer, let me know if it helped. –  Daniel 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? –  Randomman159 May 24 '11 at 13:32
2  
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
show 1 more comment

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.

share|improve this answer
2  
+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
4  
@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) –  Randomman159 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
add comment

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.

share|improve this answer
    
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. –  Daniel 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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.