Tile map collision detection

Question

There are many topics like this, but none with concrete answers. I am drawing a tile-map in the traditional way (two for loops) and keeping my player centered except when the edges of the map is reached. How would I create collision detection? I need to know how to translate tile location in the array to screen coordinates I think.

Answer 1

I will give you the code i wrote for point/tilemap collision detection. The code assumes that you have a point at (xfrom, yfrom) and you want to move it to (xto, yto) and want to see if there is a collision with a block in the tilemap map[Y][X]. I assume a method isSolid(tileId) which will return true if the tile is solid.

 /**
 * This method returns true if there is a collision between a point and a 2D tilemap map[Y][X]. 
 * The isSolid method must be implemented to indicate if a tile is solid or not 
 * Assumes the tilemap starts at (0,0) and TILEWIDTH and TILEHEIGHT hold the size of a tile (in pixels) 
 * @param xfrom the original x-coordinate of the point
 * @param yfrom the original y-coordinate of the point   
 * @param xto the destination x-coordinate of the point 
 * @param yto the destination y-coordinate of the point 
 * @param outCollisionPoint output the location where the collision occurs
 * @return true if a collision is found
 */
public boolean collisionDetection(int xfrom, int yfrom, int xto, int yto, Point outCollisionPoint){
    //Ref: A fast voxel traversal algorithm J.Amanatides, A. Woo
    float tMaxX, tMaxY, tDeltaX, tDeltaY, collisionLength;
    int X, Y, stepX, stepY, endX, endY, blkX, blkY;

    //Calculate direction vector
    float dirX = (xto - xfrom);
    float dirY = (yto - yfrom);

    float length = (float) Math.sqrt(dirX * dirX + dirY * dirY);

    //Normalize direction vector
    dirX /= length;
    dirY /= length;

    //tDeltaX: distance in terms of vector(dirX,dirY) between two consecutive vertical lines
    tDeltaX = TILEWIDTH / Math.abs(dirX);
    tDeltaY = TILEHEIGHT / Math.abs(dirY);

    //Determine cell where we originally are
    X = xfrom / TILEWIDTH;
    Y = yfrom / TILEHEIGHT;

    endX = xto / TILEWIDTH;
    endY = yto / TILEHEIGHT;

    //stepX: Determine in what way do we move between cells
    //tMaxX: the distance in terms of vector(dirX,dirY) to the next vertical line
    if (xto > xfrom){
        blkX = 0;
        stepX = 1;
        tMaxX = ((X+1) * TILEWIDTH - xfrom) / dirX;
    }else{
        blkX = 1;
        stepX = -1;
        tMaxX = (X * TILEWIDTH - xfrom) / dirX;
    }
    if (yto > yfrom){
        blkY = 0;
        stepY = 1;
        tMaxY = ((Y+1) * TILEHEIGHT - yfrom) / dirY;
    }else{
        blkY = 1;
        stepY = -1;
        tMaxY = (Y * TILEHEIGHT - yfrom) / dirY;
    }

    if (isSolid(map[Y][X])) {
        //point already collides
        outCollisionPoint = new Point(xfrom, yfrom);
        return true;
    }
    //Scan the cells along the line between 'from' and 'to'
    while (X != endX || Y !=endY){
        if(tMaxX < tMaxY){
            tMaxX += tDeltaX;
            X += stepX;
            if (isSolid(map[Y][X])) {
                collisionLength = ((X + blkX) * TILEWIDTH - xfrom) / dirX;
                outCollisionPoint = new Point((int)(xfrom + dirX * collisionLength), (int)(yfrom + dirY * collisionLength));
                return true;
            }
        }else{
            tMaxY += tDeltaY;
            Y += stepY; 
            if (isSolid(map[Y][X])) {           
                collisionLength= ((Y  + blkY) * TILEHEIGHT - yfrom) / dirY;
                outCollisionPoint = new Point((int)(xfrom + dirX * collisionLength), (int)(yfrom + dirY * collisionLength));
                return true;
            }                   
        }
    }
    return false;
}

Answer 2

It depends on the model.

If your model (the data) is a grid, then a collision occurs simply when two incompatible objects occupy the same location. The easiest way to handle this type of collision is just to make sure where you are trying to move a game entity to is "available". If it is, no collision, and update the model. If it wasn't free, then there was a collision.

The screen simply renders the model. With the exception of something like of per-pixel collision detection (think the original lemmings or worms), don't use it for collision detection.

The screen/view is just the rendering agent. While you can have the model tied tightly to the screen (e.g. you only need to update parts of the screen in which things have changed such as when a piece is moved), the screen is not, and should not, generally be considered part of the model. However, with modern computing speed, you might as well simple re-render the entire visible model each frame.

(Yes, I know I repeated myself. It was on purpose.)

Now, to answer the secondary question not mentioned in the title:

When you start rendering, simply draw screen_width/cell_width/2 cells to the left and screen_width/cell_width/2 cells to the right of the player (the player is assumed to take 1x1). Do the same for the up-and-down. Make sure to not cause an Index-Out-Of-Bounds exception. You can run the for-loops with out-of-bounds values, as long long as you clamp/filter before using them. If you wish to only make the character "push" the edge when he gets close, keep track of a current model-to-view reference as well.