Minecraft Style Collision

10/30/24

DISCLAIMER: This is based on reading the source code of Beta 1.7.3, so I can't speak on what the modern versions use.

Minecraft Coordinate System:

    Y
    |
    |
    |_ _ _ _ _ X
    /
   /
  /
 Z

Entity vs. World:

Entities have bounding boxes described by a width and a height. That is, they have the same width along X and Z. The position of an entity is the center of its bounding box.

During the tick, entities attempt to move along their velocity vector. Since Minecraft uses a fixed timestep (as any self-respecting PC game should), there is no delta-time factor in our physics calculations. The velocity is the vector the entity will attempt to move by during the next tick.

Processing a single entity tick:

We make a copy of the velocity vector and call it the "displacement" vector. The displacement will be consumed during the tick. The velocity will be optionally modified, depending on if we hit something.

Each entity maintains its min-max bounding box, found by subtracting and adding the half extents vector (width/2, height/2, width/2) from/to the center of the entity. Crucially, this bounding box is used as the ground truth of where the entity is in the world, not the entity's center. Reason being that if the bounding box is reconstructed each tick from the center, floating point error is introduced on the min and max values which will cause tunneling.

A copy of this box is made each tick and then expanded by the displacement vector to cover all the blocks that could possibly be collided with. This means element-wise adding positive values of the displacement vector to the max, and negative values of the displacement vector to the min.

We take the floor of the min and max of the expanded box to get integer world block coordinates that we can iterate through. We then iterate through all the blocks in this bounding box and add their bounding boxes to a list. This is to handle special blocks like stairs and slabs that have non-cubic shapes.

The key insight used by Notch is to process the displacement one axis at a time. This is technically innacurate to real-world motion, but in practice produces so little error that I've never seen anyone mention it. Probably because the horizontal speed of Minecraft entities is capped at so much less than the maximum vertical speed. This changed with the introduction of Elytra, which makes me think they probably now use the Minkowski sum method I will describe in my next post.

First we handle the vertical axis (Y). We move the entity along the Y component of the displacement, and stop if we hit something. That means finding the nearest block bounding box from our list in the direction of the vertical displacement that overlaps with the entity bounding box along X and Z. The overlap test is:

        box.min.x < entity.max.x && box.max.x > entity.min.x &&
        box.min.z < entity.max.z && box.max.z > entity.min.z
    

If we're moving up, we only consider boxes that are above the entity or touching it. Likewise, if we are moving down, we only consider boxes that are below the entity or touching it. That gives the added conditions:

        displacement.y > 0: box.min.y >= entity.max.y
        displacement.y < 0: box.max.y <= entity.min.y
    

If we hit something, we set the entity's velocity Y component to zero.

We then repeat this process for X and Z. Just adjust everything. For X, find boxes overlapping on Y and Z. Etc.

Handling jumping:

We need to only be able to jump when we are on the ground. So we add a boolean to our entity class called "onGround" that defaults to false. During the tick, if we hit something while moving down, we set onGround to true. Otherwise, we set it to false. Then whenever the player presses jump, we check if onGround is true. If true, we set the Y component of the velocity to some positive value (whatever you want for a jump height).

Handling stepping up short things:

DISCLAIMER: I haven't implemented this part and am just going based off the code I'm reading. I might miss something.

After handling X, Y, Z, if the entity was onGround and hit a box while moving horizontally such that the distance between the top of the box and the bottom of the entity was less than or equal to some threshold (0.5 in Steve's case), we make a copy of our final bounding box location (in case the step operation fails), and restart with the original position of the entity. We set the vertical component of our displacement to the step threshold, and attempt to move along that displacement like before. We then try to move down by the step threshold, so that we collide with the top of the box. If by the end our total horizontal distance traveled is less than or equal to that of the original motion, we know we hit something that prevented a proper step, and we set our bounding box to the copy we made earlier. Otherwise we just use the stepped bounding box.

I will note that it is a tad bit strange to always move the player up by the step threshold, instead of by just enough to clear whatever we are trying to step up onto. But it makes sense considering in Beta the only steps you would ever encounter were 0.5 units tall. If I were implementing this, I would step up by just enough to clear the step.

Entity vs. Entity:

Notch did NOT use mark and sweep. Instead, each entity's bounding box is just brute force checked against every other entity's bounding box each tick. There are few enough entities at any given time that this is not a problem. For overlapping living entities (like player and mobs), Notch used this code (maybe it's small enough to not be considered theft):

    collide_with(entity){
        double d = entity.posX - posX;
        double d1 = entity.posZ - posZ;
        double d2 = abs_max(d, d1);
        if(d2 >= 0.01)
        {
            d2 = sqrt(d2);
            d /= d2;
            d1 /= d2;
            double d3 = 1.0 / d2;
            if(d3 > 1.0)
            {
                d3 = 1.0;
            }
            d *= d3;
            d1 *= d3;
            d *= 0.05;
            d1 *= 0.05;
            addVelocity(-d, 0.0, -d1);
            entity.addVelocity(d, 0.0, d1);
        }
    }
    

This is a bit of a curveball. Clearly entities are only collided with each other along X and Z, and only if at least one component of the separation vector between them has an absolute value greater than or equal to 0.01. I think by taking the component with the greatest absolute value, we treat this more like a box vs box collision than a circle vs circle collision. It seems every living entity is treated this way, so they all effectively have the same horizontal size.

Maybe I'll cover boats and minecarts some other time.