Block world collision detection

Question

I'm currently working on a block world engine in XNA and can't get the collision detection and handling to work properly. The world is in an array indexed with ( z * width * width + y * width + x ) and containing different blocks represented by bytes. All fine and dandy. Or so I thought.

I've tried different techniques for collision handling and I'm currently using a version where I calculate the players/cameras direction and before adding it to the position I check each individual vector (x, y and z) with half a units offset (to compensate for the block size of 1.0) against the world and only apply it when the result is zero. So far so good. Now the problem arise when I walk straight into a corner because the x- and z-axis does not intersect/collide until after I've come a bit into the cube.

So how am I to properly calculate collision detection and handling in a block world?

I would really like some input on this matter, and preferably on a higher/conceptual level, but code examples are of course welcome aswell.

To further explain my situation, based upon @A-Type's response:

So, let's be more precise here to help me understand you. My character is only one unit big in every direction, which should make things easier.

First of all, do you reccon I should update my characters position first and check for collissions after? This would be my prefered way of doing collision detection but if it's any easier I'll check first and move later if possible.

Well, I understand that the player can only be intersecting 8 cubes (in your example 12) and the rounding seems to be a very good idea too, but I don't quite see the transition from the 12 cubes (again in your example, mine would be 8) to only 3. Wont this cause the same problem where the corners of the character-cube wont be taken into consideration?

I have tried to implement this but failed, so I thought more theory might do it. (I've actually gotten the collision detection to work but in those cases I lost my speed completely, not just in the colliding direction.)

Thanks for your time! Karl

Answer 1

Take advantage of the format of your world to create a more efficient collision algorithm than checking each block.

Assuming you've got a 3D array of bytes for your blocks, with 0 being an empty space, I would highly recommend rounding your player's position to a set of grid spaces in your world and check to see if any of those spaces are not 0. Then do your collision handling code against the non-empty blocks.

For instance, if your character is height 2 and width/depth 1 (like Steve from Minecraft), he can at most be intersecting 12 grid spaces at once (4 above his head, 4 around his waist, and 4 below his feet), and at least 2 (if he is perfectly aligned with the grid).

Translate the body of your character into grid-terms. Round the position of the character to a grid cell, then check the 12 spaces around it (if he is 2x1). If any are not empty, perform collision resolution between those blocks and your character. Which adjacent blocks you check depend on which direction your rounded in. For instance, if your character's position was (3.4, 2.7, 1.1), you might round that to (3, 3, 1), then check blocks which are 1 GREATER in the X direction, 1 LESS in the Y direction, and 1 GREATER in the Z direction, because you rounded DOWN, UP, and DOWN respectively.

I hope maybe this is understandable. If not, just comment. I don't know why in particular, but I can't seem to explain this concept as well as I should, especially since I've been doing stuff like this for almost a year now.

Answer 2

Alright, let's give this another shot then. There are two basic phases to collision detection in any efficient system. There's wide-phase and narrow-phase, if you will. Wide-phase uses inaccurate but cheap methods to determine if two objects could intersect, and passes those on to narrow-phase. Narrow-phase takes our two candidate objects and applies more complex physics to mediate the collision.

With grid-based worlds, we have a very simple and advantageous method for broad-phase collision. That's the grid itself. We can use the player's position and size to determine the 8 blocks he could possibly be intersecting (we'll use your case from now on). Note, in my original answer it did seem like I was talking about narrowing it down to 3 blocks-- I was making it more complicated than it needed to be, especially for a 1-block character. The simplest method is this: round the center of your character to a corner of the grid, i.e. where the corners of 8 blocks intersect. Then select those 8 blocks for narrow-phase testing. Be sure to use midpoint rounding, not floor rounding as is default in working with integers. I.e., if a value is 1.53, it should round to 2, and 1.49999 rounds to 1.

Now, narrow phase I didn't really cover much. You asked whether to move first or after, I think you kind of need to do it first. I'm no master of physics simulation, but I know you first want to calculate the direction of collision (center of character minus center of block). The depth is the length of this vector. If your blocks are 1 wide, then you don't want that length to be less than 1; that shows they are intersecting (somewhat basically).

Now, there are many ways to 'restore' objects from a collision. I would suggest determining which axis the objects collide least on. That is, if the X component of your collision direction vector is the least, that means your player is closest to being out of the collision in the X direction. Apply an opposing force in that direction proportional to the depth of the collision in the X direction. Or, if you choose, simply set the position of your character to be the distance you want away and don't bother with forces. But you'll only want to move the character in one cardinal direction. This makes things simpler and doesn't impede movement along the ground or along walls.

Think of it this way: let's say every frame your character falls .3 into the ground due to gravity. Now, let's say that he's in the center the block when he falls in this frame. That mean's his collision depth with the block below him is (0.5, 0.3, 0.5) (where X is sideways, Y is up, and Z is forward). If you apply a restoring force in all of those directions, you're going to be moving the player to the left, backwards, and back up over the ground. That last bit is the only part you wanted to do. So, ignore the larger axes of collision and only restore on the smaller (Y) one. Now your character's horizontal movement is unimpeded and he stays above the ground.