Minecraft-style player-gound collision detection

Question

The title pretty much says it all... (Minecraft is a game consisting of evenly-spaced cubes for terrain, like voxels)
Note: I am using C# XNA.

I am pretty sure AABB is the way to go, yet I don't know how to implement it. I admit, I'm almost looking for code, but theories/ideas are very welcome.

Important capabilities of my code: I have a function that can get a block anywhere in the world, and get a BoundingBox for that cube. Hence, I have created a BoundingBox for the player to collide with those cubes. My idea was to get the blocks around the player (maybe 4x6x4) and test against those.

The problems I have been having: Say the world is a flat plane. If I use the method of go the shortest distance out, then if the player is slightly clipped into the ground (from gravity), but even slighter into the next block over, then the player will be pushed sideways (and so cannot walk along ground). Of course, this is assuming I react to every block intersected. Another problem is knowing which direction to go (aka negative x or positive). That takes me to my final problem- Getting the amount of intersection, in the correct direction (+ or -) has been tough for me.

I hope I haven't been too hard to understand, I'm not too good at explaining things... And if this question has already been asked, I'm sorry, I looked for it... for 3 days straight.
One last thing, if someone knows exactly how minecraft does it, or has source (I know MC modders have the source, how else would they mod), please point me to it.

Answer 1

This is my 2D AABB approach to the solution. It should translate easily into 3D, simply by adding the Z axis. Replace "Left" and "Right" with "West" and "East", add "North" and "South", and keep "Up" and "Down". "West" and "East" would be X, "North" and "South" would be Y, and "Up" and "Down" should then be Z.

What I do is pick all the tiles that intersect with the entity based on size, and then keep it as tile start and end positions. After that, I construct two lists of tiles based on direction, holding only solid tiles. The corner is kept separate, to avoid the list having the same point twice which would be the corner.

I then iterate the list of solid tiles, and then fix velocity according if we intersect with the tile in the next position.

The corner is a special case in my engine, rather than increase the steps, I just rule you always land on top.

Feel free to ask questions, though I'd encourage you to try and rewrite it for your own engine, to get a better grasp on what the function is doing.

...
    private Vector2 ApplyTileCollision(Vector2 velocity)
    {
        Vector2 nextPosition = this.position + velocity;

        Int32 startx = (Int32)(((Single)position.X) / Tile.SIZE) - 1;
        Int32 endx = (Int32)(((Single)position.X + this.Width - 0.0001f) / Tile.SIZE) + 1; // because of float imprecision, we subtract 0.0001f.
        Int32 starty = (Int32)(((Single)position.Y) / Tile.SIZE) - 1;
        Int32 endy = (Int32)(((Single)position.Y + this.Height - 0.0001f) / Tile.SIZE) + 1; // because of float imprecision, we subtract 0.0001f.

        // these variables are filled with only solid tiles
        List<Point> horizontalWall = new List<Point>();
        List<Point> verticalWall = new List<Point>();
        Point ?corner = null;

        if (this.IsMovingRight)
        {
            // we use starty + 1 to remove the corner
            for (Int32 y = starty + 1; y < endy; y += 1)
                if (realm.GetTile(endx, y).IsSolid)
                    verticalWall.Add(new Point(endx, y));
        }
        else if (this.IsMovingLeft)
        {
            // we use starty + 1 to remove the corner
            for (Int32 y = starty + 1; y < endy; y += 1)
                if (realm.GetTile(startx, y).IsSolid)
                    verticalWall.Add(new Point(startx, y));
        }

        if (this.IsMovingDown)
        {
            // we use startx + 1 to remove the corner
            for (Int32 x = startx + 1; x < endx; x += 1)
                if (realm.GetTile(x, endy).IsSolid)
                    horizontalWall.Add(new Point(x, endy));
        }
        else if (this.IsMovingUp)
        {
            // we use startx + 1 to remove the corner
            for (Int32 x = startx + 1; x < endx; x += 1)
                if (realm.GetTile(x, starty).IsSolid)
                    horizontalWall.Add(new Point(x, starty));
        }

        if (this.IsMovingLeft && this.IsMovingUp)
        {
            if (realm.GetTile(startx, starty).IsSolid)
                corner = new Point(startx, starty);
        }
        else if (this.IsMovingRight && this.IsMovingUp)
        {
            if (realm.GetTile(endx, starty).IsSolid)
                corner = new Point(endx, starty);
        }
        else if (this.IsMovingLeft && this.IsMovingDown)
        {
            if (realm.GetTile(startx, endy).IsSolid)
                corner = new Point(startx, endy);
        }
        else if (this.IsMovingRight && this.IsMovingDown)
        {
            if (realm.GetTile(endx, endy).IsSolid)
                corner = new Point(endx, endy);
        }

        foreach (Point point in verticalWall)
        {
            // if our next position would collide with the tile, we fix velocity.
            if (nextPosition.X + this.Width > point.X * Tile.SIZE &&
                nextPosition.X < point.X * Tile.SIZE + Tile.SIZE)
            {
                if (this.IsMovingRight)
                {
                    velocity.X = point.X * Tile.SIZE - (position.X + this.Width);
                }
                else if (this.IsMovingLeft)
                {
                    velocity.X = (point.X * Tile.SIZE + Tile.SIZE) - position.X;
                }
            }
        }

        foreach (Point point in horizontalWall)
        {
            // if our next position would collide with the tile, we fix velocity.
            if (nextPosition.Y + this.Height > point.Y * Tile.SIZE &&
                nextPosition.Y < point.Y * Tile.SIZE + Tile.SIZE)
            {
                if (this.IsMovingDown)
                {
                    velocity.Y = point.Y * Tile.SIZE - (position.Y + this.Height);
                }
                else if (this.IsMovingUp)
                {
                    velocity.Y = (point.Y * Tile.SIZE + Tile.SIZE) - position.Y;
                }
            }
        }

        // in case we only have a corner to consider, we rule that we land on top of it, or hit the bottom of it.
        if (corner.HasValue && verticalWall.Count == 0 && horizontalWall.Count == 0)
        {
            // if our next position would collide with the tile, we fix velocity.
            if (nextPosition.Y + this.Height > corner.Value.Y * Tile.SIZE &&
                nextPosition.Y < corner.Value.Y * Tile.SIZE + Tile.SIZE &&
                nextPosition.X + this.Width > corner.Value.X * Tile.SIZE &&
                nextPosition.X < corner.Value.X * Tile.SIZE + Tile.SIZE)
            {
                if (this.IsMovingDown)
                {
                    velocity.Y = corner.Value.Y * Tile.SIZE - (position.Y + this.Height);
                }
                else if (this.IsMovingUp)
                {
                    velocity.Y = (corner.Value.Y * Tile.SIZE + Tile.SIZE) - position.Y;
                }
            }
        }

        return velocity;
    }
...