Tile based collision detection errors if player is smaller than tiles

Question

I have implemented a tilemap where each tile is at a non-negative x and y position. (So at the moment think like chess)

At the moment a tile is 16, 16 pixels in size

Tile 0,0 is at the left bottom corner

Some tiles should be collidable. I've never implemented something like that and during research stumbled upon: https://jonathanwhiting.com/tutorial/collision/

The general idea + collision response handling:

let mut new_pos = Point2::new(curr_pos.x + x_offset, curr_pos.y);

let collision_on_x = collide_with_world(&new_pos, &world);

if !collision_on_x  {
    transform.translate_x(x_offset);
}

new_pos.y = curr_pos.y + y_offset;

let collision_on_y = collide_with_world(&new_pos, &world);

if !collision_on_y  {
    transform.translate_y(y_offset);
}

The collision detection

fn collide_with_world(new_pos: &Point2<f32>, world: &World) -> bool {
    // TODO make these sizes i16 instead so we can grow in any direction!
    let mut left_tile: u16 = (new_pos.x / TILE_SIZE_IN_PIXELS as f32) as u16;
    // -1 so that we do not collide until we are exactly at the thing
    let mut right_tile: u16 = ((new_pos.x + PLAYER_WIDTH - 1.0) / TILE_SIZE_IN_PIXELS as f32) as u16;
    let mut top_tile: u16 = ((new_pos.y + PLAYER_HEIGHT - 1.0) / TILE_SIZE_IN_PIXELS as f32) as u16;
    let mut bottom_tile: u16 = (new_pos.y / TILE_SIZE_IN_PIXELS as f32) as u16;

    println!("new_pos: {:?}, left {}, right {}, top {}, bottom {}", (new_pos.x, new_pos.y), left_tile, right_tile, top_tile, bottom_tile);

    // Useless as long as we use unsigned coordinates
    //if left_tile < 0 {
    //    left_tile = 0;
    //}

    if right_tile > WORLD_WIDTH_IN_TILES {
        right_tile = WORLD_WIDTH_IN_TILES;
    }

    // Useless as long as we use unsigned coordinates
    //if bottom_tile < 0 {
    //    bottom_tile = 0;
    //}

    if top_tile > WORLD_HEIGHT_IN_TILES {
        top_tile = WORLD_HEIGHT_IN_TILES;
    }

    let mut any_collision = false;

    for i in left_tile..=right_tile {
        for j in bottom_tile..=top_tile {
            let tile = world.get_tile(i, j);
            println!("tile at {:?} is {:?}", (i, j), tile);

            match tile {
                Some(tile) => {
                    if tile == WALL {
                        println!("hit a wall at {:?}!", (i, j));
                        any_collision = true;
                    }
                }
                None => (),
            }
        }
    }

    return any_collision;
}

I basically took (or tried to take) the optimised version of the linked blog-entry.

Now to the problems:

If PLAYER_WIDTH and PLAYER_HEIGHT are both 16.0 - collision works fine

But note that I had to put -1.0 in the calculation of the right_tile and top_tile, else the collision for UP and RIGHT would occur one pixel to early (so the player would never touch walls to their top or right)

This change alone makes me a bit suspicious - looks like I made an error there.

The real problems start if the player is smaller than a tile:

In the following screenshots the following rules apply:

*) the PLAYER_WIDTH and PLAYER_HEIGHT are both 8 *) Greenish tiles are the only walls! *) All the screenshots were taken in ONE run - no parameters were changed during this run!

1) -> Trying to collide with right tile -> overlapping 2) -> Trying to collide with top tile -> cannot go any nearer than 4 pixels (half the height of the player) 3) -> Trying to collide with left tile -> cannot go any nearer than 4 pixels (half the width of the player) 4) -> Trying to collide with top tile -> suddenly overlapping although different tile didn't collide? 5) -> Trying to collide with bottom tile -> cannot go any nearer than 4 pixels

I cannot grasp 2 and 4 at the moment.

Answer 1

Does new_pos define the player's center, or its bottom-left corner? Because your checks make sense if it's the corner, but usually location is defined by centers. Try this -

let width_change = PLAYER_WIDTH /2;  
let height_change = PLAYER_HEIGHT /2; 
let mut left_tile: u16 = ((new_pos.x - width_change) / TILE_SIZE_IN_PIXELS as f32) as u16;
let mut right_tile: u16 = ((new_pos.x + width_change - 1.0) / TILE_SIZE_IN_PIXELS as f32) as u16;
let mut top_tile: u16 = ((new_pos.y + height_change - 1.0) / TILE_SIZE_IN_PIXELS as f32) as u16;
let mut bottom_tile: u16 = ((new_pos.y - height_change) / TILE_SIZE_IN_PIXELS as f32) as u16;

Answer 2

Consider this an answer also. This example isolates the hit detection to movement in the upward direction only, with further isolation from sprite to a single non playable object. It uses rectangular hit detection. I am placing non playable objects on a tiled background also. The sprite and non playable objects are at the same z-order for now.

else if (up) { pGraveyard_Objects->DisplayGraveyardFence();
pGraveyard_Objects->DisplayGraveyardObjects();

    // NonPlayableObject npo_pumpkin
    // PlayableObject po_sprite

    po_sprite.x = buzzR->row;
    po_sprite.y = buzzR->col; 
    
    po_sprite.width = TILE_WIDTH; 
    po_sprite.height = TILE_HEIGHT;

    //NonPlayableObject npo_pumpkin;
    npo_pumpkin.x = FENCE_RIGHT;
    npo_pumpkin.y = FENCE_BOTTOM + (TILE_HEIGHT);
    
    npo_pumpkin.width = TILE_WIDTH;
    npo_pumpkin.height = TILE_HEIGHT; 



    if (rectHit(po_sprite, npo_pumpkin)) 
    {
        wave2->Play();
        buzzR->MoveTo(buzzR->row, buzzR->col -= GRANULARITY_IN_Y); // show      
    }
    else
    {
        buzzR->MoveTo(buzzR->row, buzzR->col -= GRANULARITY_IN_Y); // show      
        
    }

}

// site source of algorithm // take from https://github.com/jeffThompson/CollisionDetection //
BOOL rectHit(SceneObject r1, SceneObject r2) { TRACE("rectHit Invoked\n");

// are the sides of one rectangle touching the other?


if (r1.x + r1.width >= r2.x &&    // r1 right edge past r2 left
    r1.x <= r2.x + r2.width &&    // r1 left edge past r2 right
    r1.y + r1.height >= r2.y &&    // r1 top edge past r2 bottom
    r1.y <= r2.y + r2.height) {    // r1 bottom edge past r2 top
    return TRUE;
}
return FALSE;

}