Pixel-perfect collision and doubles

Question

I am working with tiles and entities; they are both rectangles, and I can adjust the speed of the entities, such as setting the speed as 2.3. The problem that complicates is when it comes to collision between the tiles and the entities.

My method for collision actually adds on to check the next tile from its current speed, so if the speed is 2.3, but the distance between the tile and entity is 1.4, it won't let it move that tiny difference, and it will leave the tiniest pixel between the two. This isn't a very good thing to have. I have been trying to work ways around this to add on that tiny difference, but I just cannot figure it out..

Here is my collision method (in Java):

public boolean collision(double xa, double ya) {
    for (int c = 0; c < 4; c++) {

        int xt = (int) ((this.x + xa) + c % 2 * 15 - 7) >> 4; // (n >> 4) is the same as (n / 16), but faster, if you didn't know.
        int yt = (int) ((this.y + ya) + c / 2 * 15 - 8) >> 4;
        if (level.getTile(xt, yt).isSolid()) return true;
    }
    return false;
}

And here is my current method that I am using to handle all of the movement of the entity, where the collision is checked:

public void move(double xa, double ya) {
    if (xa != 0 && ya != 0) {
        move(xa, 0);
        move(0, ya);
        return;
    }

    if (collision(xa, ya)) { //---
        return;          // CONFIGURE DIFFERENCE HERE
    }                        //---

    while (xa != 0) {
        if (Math.abs(xa) > 1) {
            this.x += intValue(xa);
            xa -= intValue(xa);
        } else {
            this.x += xa;
            xa = 0;
        }
    }

    while (ya != 0) {
        if (Math.abs(ya) > 1) {
            this.y += intValue(ya);
            ya -= intValue(ya);
        } else {
            this.y += ya;
            ya = 0;
        }
    }
}

What I want to incorporate is to find the difference between the 2.3 and 1.4 within that comment block where I put the message CONFIGURE DIFFERENCE HERE in the move method. I am probably failing pretty badly, considering this is probably an easy algorithm, but I just cannot think of the right way to find the difference. Every once and a while, I will find myself one pixel off from the wall. Here is a method that I have been trying to get to work in some way.

if (collision(xa, ya)) {
    while (Math.abs(xa) > 1) {
        xa -= intValue(xa); //intValue(int v) returns 1 if v > 0
                                        // returns -1 if v < 0
    }

    while (Math.abs(ya) > 1) {
        ya -= intValue(ya);
    }

    if (collision(xa, ya)) return;
}

Summary & Question

I have a problem where if the speed of an entity isgreater thanthe distance from the tile it is going into, it will leave at least a pixel in between itself and the tile, and I really don't like this. What kind of algorithm could I use that will find the tiniest difference between the entity and the tile?

If you need any additional information, I will be glad to add it.

possible duplicate of [Basic 2d collision detection](http://stackoverflow.com/questions/3851520/basic-2d-collision-detection) — , Jan 14 '14 at 03:49
Could it be that this line: `while (Math.abs(xa) > 1)` should use `>=`? — maackle, Jan 14 '14 at 03:54

score 0 · Answer 1 · answered Jan 14 '14 at 03:48

The way you do the collision is let it run until it overlaps, detect the overlap and then move it back to the actual touch point when you detect that it has overlapped.

This is a well documented technique on all the "how to" sites about writing games.

Here is a good example.

score 0 · Answer 2 · answered Jan 14 '14 at 04:22

Although not exactly the question I asked on GameDev, the answer that I received could be used here: Give your tiles movement correction vectors.

When a player moves onto a tile add the normalized player vector to the normalized tile vector and the resulting (re-normalized) vector is the direction the player should actually move. This helped me budge characters around corners but will help you allow a character to actually touch the wall.

If all else fails, if the speed is bigger than the gap then only move the the player the amount of the gap. In your example, don't move the player 2.3, move them 1.4.

Pixel-perfect collision and doubles

2 Answers2

Linked