Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
If you have mc, get mcp and see for yourself. :) –  Aidan Mueller Mar 24 '12 at 16:33

1 Answer 1

up vote 3 down vote accepted

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;
    }
...
share|improve this answer
    
Wow. Ill have to study this a bit. So you split up horizontal and vertical detection into two parts... And you use velocity to determine which direction to react to... interesting... Thanks, though. Ill leave it unaccepted for a bit to see if anyone else has suggestions. –  khyperia Oct 29 '11 at 17:04
    
@khyperia, Yeah, that's the idea, also, if I'm not moving in a direction, there are no checks performed in that direction. A key element to this detection, is I check both directions before actually moving the entity, which is a common issue people run into. I also fix the velocity rather than the position, making sure the entity never enters the space of the tile. –  William 'MindWorX' Mariager Oct 29 '11 at 17:13
    
Good idea! Thanks a lot! –  khyperia Oct 29 '11 at 17:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.