Voxel collision without physics

What is the best way of detecting collisions without physics in a voxel game?

I removed physics for performance reasons since I have infinite terrain. Adding the physics controls was causing lots of performance issues and from what I have read the usual approach in a voxel game is to just write the collision detection yourself.

I’m currently casting a Ray downward to detect the collision with the ground. That’s working ok but it seems like I would need to cast 4 Rays down for each block vertex of my character to get it right. Then I have to do the same 4 rays for the front, back and top of the character. This seems expensive and difficult to implement.

It seems maybe I could draw a box around my character and walk one box outward and see if a block is there and do that for all 6 sides without Ray casting.

Can anyone provide some pointers or suggestions on how to implement this?

Thank you!

It kind of depends on what you want to get out of the collisions.

A player bounding box collision with a grid is really simple. Just clip the points to the grid. You’ll end up with up to 8 cell locations and can iterate over the world values to see if you are in solid block or air.

If I recall correctly looking through the source code at:

Each visible chunk’s generated mesh was added to the bullet physics PhysicsSpace, and when a chunk needed to be redrawn you would remove it from PhysicsSpace and add the chunk’s mesh again to the PhysicsSpace.

1 Like

@themiddleman I’m not using physics so that’s a no go for me. Thanks for the comment though.

@pspeed is it as simple as me instantiating a BoundingBox for the player and then calling terrainGeometry.collideWith(playerBox)?

Or am I going to have to create an AABB class and configure it for the player, then instantiate one for each block I am examining and call it’s collideWith method?

Nevermine @pspeed I got it working. It might be kind of what you were suggesting but I’m not sure.

I find the block under the player and create an AABB and collide it with the player AABB. Now I just need to do that all around the player and implement a collision response.

You will have to manage ceillings too. And remember you character is a cylinder (not a cuboid).

I would suggest to

  • first, find potential collisions with 2D test, between you bounding circle and the grid. You will get up to 4 2d tiles
  • then, test each potential collisions : on each involved tile, voxels must be above your head or below your feet.

No ray casting

I would definitly do that as a first implementation. And because you will certainly want to add more physics, like firing arrows or throwing objects, falling with acceleration, explode things, etc. jBullet will certainly help you a lot in the next steps and it may be worthy to learn how to use it now.

@methusalah I was using jbullet and it was working fine but after adding infinite terrain and using the java mission control to create flight recordings I found that physics was causing a lot of noticeable performance issues. Granted multithreading would help with a lot of the perceived performance issues, I have read and kind of understand that a full blown physics engine that handles complex collisions may be overkill in a block world. Granted I will have some issues with implementing arrows without jbullet.

That said, I am still having difficulties with collision. I have implemented an AABB class and even have unit tests to make sure it works correctly. I’m making my player be 2 blocks tall in size. So the player’s AABB center is the local translation of the player. I have to translate those coordinates to coordinates in the block world in order to get the blocks all around the player and create AABB’s for all the blocks. However, I’m still getting confused in how to implement such a solution. It makes sense conceptually, but being a novice at this is causing me all kinds of issues. Like for instance, a player could be standing in between two blocks. My block locations are integer values not floats, however my player’s local translation is a float Vector3f.

If you or anyone else can provide any pointers in this it would be much appreciated. I’m sure I’m making it more complicated than it needs to be but I’m becoming a bit discouraged with it.

Please forgive the novice level of the request. I have never solved this type of problem so my brain is just not thinking about it correctly.

Just to give an idea of what I’m doing, here’s my current collision code. It’s currently working for ground collisions, but seems brittle and difficult to expand to other collisions.

In my PlayerControl.controlUpdate method I call the following detectCollisions method at the end of the controlUpdate method.

    private void detectCollisions()
{
	float cubeSize = GameProperties.CUBE_SIZE;
	float halfCubeSize = GameProperties.CUBE_SIZE/2;
	Vector3f blockWorldLocation = characterNode.getLocalTranslation().divide(cubeSize);
	BlockTerrainControl terrain = terrainManager.getTerrain();
	Vector3Int playerLocation = Vector3Int.fromVector3f(blockWorldLocation);
	Vector3Int blockLocation = playerLocation.clone();
	JBlock block = null;
	for(; blockLocation.y >= 0; blockLocation.y--)
	{
		block = (JBlock)terrain.getBlock(blockLocation);
		if(block != null)
		{
			break;
		}
	}
	
	AABB playerBox = new AABB(new Vector3f(), new Vector3f(halfCubeSize, cubeSize, halfCubeSize));
	playerBox.setCenter(blockWorldLocation);
	Vector3f blockCenter = new Vector3f(blockLocation.x + halfCubeSize, blockLocation.y - halfCubeSize, blockLocation.z + halfCubeSize);
	AABB blockBox = new AABB(blockCenter, new Vector3f(halfCubeSize, halfCubeSize, halfCubeSize));
	if(playerBox.collidesWith(blockBox))
	{
		Vector3f currentLocation = characterNode.getLocalTranslation();
		Vector3f newLocation = new Vector3f(currentLocation.x, blockLocation.y + cubeSize*3, currentLocation.z);
		setLocalTranslation(newLocation);
	}
}

Here’s my PlayerControl.controlUpdate method. I know the gravity and jumping implementation is screwy. I plan to revisit it. I just want to get the collision detection working first and I needed it to make the player fall.

    @Override
protected void controlUpdate(float tpf)
{
    if (isEnabled())
    {
    	setLocalTranslation(characterNode.getLocalTranslation().subtract(0, tpf*15f, 0));
    	
    	
        forwardDir.set(cam.getDirection()).multLocal(currentSpeed, 0.0f, currentSpeed);
        leftDir.set(cam.getLeft()).multLocal(currentSpeed);
        walkDirection.set(0, 0, 0);
        if (left)
        {
            walkDirection.addLocal(leftDir);
        }
        if (right)
        {
            walkDirection.addLocal(leftDir.negate());
        }
        if (forward)
        {
            walkDirection.addLocal(forwardDir);
        }
        if (backward)
        {
            walkDirection.addLocal(forwardDir.negate());
        }
        if (ascend)
        {
            walkDirection.addLocal(ascendDir);
        }
        if (descend)
        {
            walkDirection.addLocal(ascendDir.negate());
        }
        
        Vector3f newPosition = characterNode.getLocalTranslation().add(walkDirection);
        if(jumping)
        {
        	newPosition.addLocal(upVelocity.divide(20));
        	if(upVelocity.y > 0)
        	{
        		upVelocity.y--;
        	}
        	else
        	{
        		jumping = false;
        	}
        }
        setLocalTranslation(newPosition);

        detectCollisions();
        playerLocationSanityCheck();
    }
}

Creating a bunch of AABB classes might be overkill. The player can pretty easily be clipped into the world with math… presuming you have no partial blocks, round blocks, etc. (Mythruna is much more complicated.)

Think of the player as a set of corners. For a second, let’s just deal with the feet.

Imagine an axis square around the player’s feet. Four corners. This square never rotates so these corners are always playerLoc + cornerOffset.

Some pseudo code:

float xPen = 1, yPen = 1, zPen = 1; // penetration vector
corner = playerLoc + cornerOffset;
cell = Math.floor(corner)
boolean penetrating = false;
if( cell is solid ) {
    // calculate penetration
    float x = cornreOffset.x < 0 ? cell.x + 1 - corner.x ? corner.x - cell.x;
    float y = cornreOffset.y < 0 ? cell.y + 1 - corner.y ? corner.y - cell.y;
    float z = cornreOffset.z < 0 ? cell.z + 1 - corner.z ? corner.z - cell.z;
    
    // Update xPen, yPen, and zPen only if abs(n) < abs(nPen)
    if( abs(x) < abs(xPen) ) xPen = x;
    ...etc...

    penetrating = true;
}

Do that for each corner and take the smallest (in absolute values) penetration of each axis and use that to move the player back into clear space.

The idea is to move the player as little as possible so you want to use the smallest adjustment… and in a pure block world, you can just pick the best axis. No diagonals needed.

Something like that got me by on Mythruna for quite a while.

P.S.: Not sure why arrows would be hard(er).

Well I have torches and doors so far that are not regular blocks. Torches are no problem because I don’t want collisions with them so i can ignore them but doors are a different animal. They are different based on the open/closed state and the orientation of the door(which block face is their home).

Starting to wonder If I’m going to be able to do this without Physics being enabled.

Presumably doors are a flat plane. I’d just collide with them separately, personally. You will already have to do separate collisions for other objects and stuff anyway.

@pspeed I almost have it working thanks to your pseudo code. The y axis collision is working fine and I’m trying to get the x and z axis working correctly.

The way I did it is I created a CollisionPoints class with the code you gave me. Then I created 4 instances for front, back, top and bottom. I did this because I need to know which axis to affect. Maybe I’m making it harder than it needs to be.

Is that what you were thinking with the code above or should I only have only 8 points total? The problem I was having with the 8 points is that the feet always collide with x and z with the blocks the player is standing on. So I couldn’t really move on a flat surface.

Just curious if my approach is what you had in mind.

Thanks!

Nevermind. After talking(typing) through it I think I know what I’m doing wrong. I’m only going to have 8 points but I need to feed the correct cell to my CollisionPoints class. Currently I’m only handing it the coordinates of the block I’m standing on, that’s why I’m having problems with x and z.