# Collision Detection problems in Voxel Engine (XNA)

I am creating a minecraft like terrain engine in XNA and have had some collision problems for quite some time. I have checked and changed my code based on other peoples collision code and I still have the same problem. It always seems to be off by about a block. for instance, if I walk across a bridge which is one block high I fall through it. Also, if you walk towards a "row" of blocks like this:

You are able to stand "inside" the left most one, and you collide with nothing in the right most side (where there is no block and is not visible on this image).

Here is all my collision code:

    private void Move(GameTime gameTime, Vector3 direction)
{
float speed = playermovespeed * (float)gameTime.ElapsedGameTime.TotalSeconds;

Matrix rotationMatrix = Matrix.CreateRotationY(player.Camera.LeftRightRotation);
Vector3 rotatedVector = Vector3.Transform(direction, rotationMatrix);

rotatedVector.Normalize();

Vector3 testVector = rotatedVector;
testVector.Normalize();

Vector3 movePosition = player.position + testVector * speed;
Vector3 midBodyPoint = movePosition + new Vector3(0, -0.7f, 0);
Vector3 headPosition = movePosition + new Vector3(0, 0.1f, 0);

if (!world.GetBlock(movePosition).IsSolid &&
!world.GetBlock(midBodyPoint).IsSolid &&
{
player.position += rotatedVector * speed;
}

//player.position += rotatedVector * speed;
}


...

    public void UpdatePosition(GameTime gameTime)
{
player.velocity.Y += playergravity * (float)gameTime.ElapsedGameTime.TotalSeconds;

Vector3 footPosition = player.Position + new Vector3(0f, -1.5f, 0f);
Vector3 headPosition = player.Position + new Vector3(0f, 0.1f, 0f);

// If the block below the player is solid the Y velocity should be zero
if (world.GetBlock(footPosition).IsSolid ||
{
player.velocity.Y = 0;
}

UpdateJump(gameTime);
UpdateCounter(gameTime);
ProcessInput(gameTime);

player.Position = player.Position + player.velocity * (float)gameTime.ElapsedGameTime.TotalSeconds;
velocity = Vector3.Zero;
}


and the one and only function in the camera class:

    protected void CalculateView()
{
Matrix rotationMatrix = Matrix.CreateRotationX(upDownRotation) * Matrix.CreateRotationY(leftRightRotation);
lookVector = Vector3.Transform(Vector3.Forward, rotationMatrix);

cameraFinalTarget = Position + lookVector;

Vector3 cameraRotatedUpVector = Vector3.Transform(Vector3.Up, rotationMatrix);
viewMatrix = Matrix.CreateLookAt(Position, cameraFinalTarget, cameraRotatedUpVector);
}


which is called when the rotation variables are changed:

    public float LeftRightRotation
{
get { return leftRightRotation; }
set
{
leftRightRotation = value;
CalculateView();
}
}

public float UpDownRotation
{
get { return upDownRotation; }
set
{
upDownRotation = value;
CalculateView();
}
}


World class:

    public Block GetBlock(int x, int y, int z)
{
if (InBounds(x, y, z))
{
Vector3i regionalPosition = GetRegionalPosition(x, y, z);
Vector3i region = GetRegionPosition(x, y, z);

return regions[region.X, region.Y, region.Z].Blocks[regionalPosition.X, regionalPosition.Y, regionalPosition.Z];
}

return new Block(BlockType.none);
}

public Vector3i GetRegionPosition(int x, int y, int z)
{
int regionx = x == 0 ? 0 : x / Variables.REGION_SIZE_X;
int regiony = y == 0 ? 0 : y / Variables.REGION_SIZE_Y;
int regionz = z == 0 ? 0 : z / Variables.REGION_SIZE_Z;

return new Vector3i(regionx, regiony, regionz);
}

public Vector3i GetRegionalPosition(int x, int y, int z)
{
int regionx = x == 0 ? 0 : x / Variables.REGION_SIZE_X;
int X = x % Variables.REGION_SIZE_X;

int regiony = y == 0 ? 0 : y / Variables.REGION_SIZE_Y;
int Y = y % Variables.REGION_SIZE_Y;

int regionz = z == 0 ? 0 : z / Variables.REGION_SIZE_Z;
int Z = z % Variables.REGION_SIZE_Z;

return new Vector3i(X, Y, Z);
}


Any ideas how to fix this problem?

EDIT 1:

Graphic of the problem:

EDIT 2

GetBlock, Vector3 version:

    public Block GetBlock(Vector3 position)
{
int x = (int)Math.Floor(position.X);
int y = (int)Math.Floor(position.Y);
int z = (int)Math.Ceiling(position.Z);

Block block = GetBlock(x, y, z);

return block;
}


Now, the thing is I tested the theroy that the Z is always "off by one" and by ceiling the value it actually works as intended. Altough it still could be greatly more accurate (when you go down holes you can see through the sides, and I doubt it will work with negitive positions). I also does not feel clean Flooring the X and Y values and just Ceiling the Z. I am surely not doing something correctly still.

• Looks similar to your problem with cube selection. Perhaps they're connected? Jan 18, 2012 at 4:27
• Perhaps :), I still haven't figured out how to fix that either :D Jan 18, 2012 at 5:07
• So what does your get getblock function look like? Is the collision always off by one? Jan 18, 2012 at 19:26
• Yes, the collision is always off by one in the Z direction. (Always shifts one block back in the -z) Jan 19, 2012 at 3:05
• Make sure you use Math.Floor, and don't count on (int) casting to floor your results, I know I made that mistake before. This will cause everything to be weird when moving around in any negative dimensions. Here's why: (int)(-0.5) = 0 but (int)Math.Floor(-0.5) = -1 Jan 20, 2012 at 6:49

A few things I noticed you can check:

• In Move() you subtract 1.4 to get the head position while in UpdatePosition() you add 0.1. Double-check that this calculation is correct as I would have assumed you should be adding the same value in the same direction.
• Is the collision issue the same in each direction (+/-, X/Y/Z) or does it matter which direction you're going? For example, if the collision issue was different while travelling in +X vs -X I would guess there's a mismatch between where the collision detection thinks a voxel is and where the game actually displays it. In other words, does you voxel at (0,0) occupy (0,0)-(1,1) or (-0.5, -0.5)-(0.5, 0.5) or (-1,-1)-(0,0). If you make a mistake here you will be off by as much as one block which sounds close to the issue you describe.
• Drawing your collision box may be helpful in debugging as can be stepping through and observing what the variables are and what you think they should be.
• I assume player.position vs player.Position is just a typo (though I've been bitten by dynamic case-sensitive languages before).

Edit: The way you describe it sounds exactly like an "off-by-one" type error. You also use GetBlock(Vector3) but posted code for GetBlock(int, int, int). If you are relying on automatic conversion from float to int it may round/truncate in ways you aren't expecting.

Edit 2: I would follow MindWorX's comment about specifically using floor()/ceil() when you convert from float to int. This may or may not be the issue you are having. You really need to add some diagnostic output to the display (player position, camera position, collision boxes, selected block info, etc...) and trace through everything to make sure it does what it should. At this stage it is dangerous to think "it can't be X". Don't assume anything and make sure you actually read what the code does and not what you think it does.

• Nice answer. Those would be great things to checkout. @darestium Define globals for all those constants! And just use one position for your character, managing two is kind of silly. Jan 18, 2012 at 19:29
• Well, with the player.position vs player.Position... I'll fix that ;) Position is a get/set acsessor of the position variable which I should keep private. Regarding the collision issue, I have posted a graphic decpicting the problem, also the first block starts at 0,0,0 and the block size is 1,1,1. And the first dot point - I see what you mean and just fixed it, i'll also post the updated code. Jan 19, 2012 at 2:57
• I will also post the Vector3 version. Jan 20, 2012 at 5:19

Casting to int round positive numbers down, and negative numbers up.

So, do a check:  if(x < 0) x -= 1; 

I had exactly the same problem with my voxel engine.