Line collision in pygame

Question

So I am currently working on a 2D platformer game and I have realized a big issue with my collision programming. You see, to find out collisions with the player I just moved the player rect around, then when colliding I pushed the player away by looking at the x and y acceleration on him.

The problem is though when using this method, the player's speed can make the player skip over targets he is supposed to collide with because the rect he is supposed to collide with is too small. For example, if the platform is 9px in size and the speed the player is going at is 11px, there is a chance he will skip the target. This usually happens with bullets the player is shooting which is small and goes quickly (And I don't want them to be instantaneous because of the nature of the game).

So I thought about it and came up with a solution of drawing a line from the position of the bullet was previously at to the one he it is in right now, then checking if the target rect collides with it. I searched for methods to do something like this, but I haven't found any good explanation of how to implement this into Pygame.

Do I use pixel masking? If yes, how to? Is there some function already in Pygame to use this method with? I could really use some help.

Allege

@Jean-FrançoisFabre Hmm, didn't think about that... So you are basically telling me to make a few loops of updates and only then update the screen? This will make things overly complicated for me i think... Or are you telling me to higher frame rate? But that would mess things up... For now though i will wait for someone for help on my method, as it sounds the simplest and cleanest, but thanks anyway! – Allege

@Jean-FrançoisFabre well, what exactly do you mean by "compute more than you update"? I am confused about the matter, can you explain a little more specifically? – Allege

@Jean-FrançoisFabre oh i think i get what you are getting at... So basically do more collision computation and only render at appropriate times, that's the concept correct? I will have to tinker with that to figure it out completely. Didn't quite catch the C code too... i learned a teeny bit of #C but I'm not really there at the moment. Anyways, thanks for the help, really appreciate it. – Allege

Answer 1

Simple linear AABB collision detection

Below is a solution for intercepting a moving box with many stationary boxes. The boxes must have sides parallel to the x and y axis.

It solves the problem of high speed movement by finding the first intercept between two frame, no matter how thin the obstacle is or how fast the object is moving the correct intercept is found. (Note the boxes must have a positive width and height)

Line box intercept

It works by representing the moving box's path as a single line. Rather than adding the width and height to the line the width and height of the moving box is added to the obstacle boxes, this greatly reduces the amount of work needed to solve the problem. (the demo graphically shows some of the intermediate abstraction including the expansion of obstacle boxes)

To use in game the line in the demo is just the game's current object position to the position in the next frame along delta x and y.

The intercept sets the x,y distance from the current position to the intercept (if any). The normal (a vector pointing away from the side hit) is provided as well to aid collision response. You also have the distance squared to the intercept point. You can divide that distance with the line length squared to give you a unit time of when the intercept occurred. ie a value of 0.5 means that it happened mid way between two frames. 0 it happened at the start and 1 it happened at the end. If there is no intercept then the normal will be zero length.

The demo

The demo is javascript, but the math and logic is what is important. The functions of interest are at the top of the snippet and well commented (I hope). Below that is just boilerplate and support.

To use the demo, left click drag to create a box. Then left click and drag to mark out a line. The start position is the light green box, the other green box is the intercept, if there is one. There are also some yellow marks indicating calculated intercepts that were too far away. Full page to see more boxes.

Limits and adaptations

You may notice that if the start position is touching a box that the intercept point is before the start position (backward in time) This is the correct behavior, you should not be overlapping a box (inside a wall) at the start

If you have moving obstacles and they move along the x or y axis you can adapt the solution by simply expanding the boxes in the direction of movement (not perfect but works for slow moving obstacles (watch out for overlapping in the next frame).

You can also test a moving circle. this can be done by checking if the intercept point is within the circle radius distance of a corner. If so then do a line circle intercept with the circle center at the box real corner and radius same as the moving circle.

Clear as mud I know so do ask if you have any questions.

// Moving box 2 box intercepts

var objBox = createBox(0, 0, 0, 0);   // the moving box
var objLine = createLine(0, 0, 0, 0); // the line representing the box movement
var boxes = [];                       // array of boxes to check against


//Find closest intercept to start of line
function findIntercepts(B, L) {
    lineAddSlopes(L);   // get slopes and extras for line (one off calculation)
                        // for each obstacles check for intercept;
    for (var i = 0; i < boxes.length; i++) {
        intercept(B, L, boxes[i]);
    }
    // Line will hold the intercept pos as minX, minY, the normals of the side hit in nx,ny
    // and the dist from the line start squared
}


function lineAddSlopes(l) {           // adds the slopes of the lie for x,y and length as dist
    var dx = l.x2 - l.x1;             // vector from start to end of line
    var dy = l.y2 - l.y1;
    var dist = dx * dx + dy * dy;
    l.dx = dx / dy;                   // slope of line in terms of y to find x
    l.dy = dy / dx;                   // slope of line in terms of x to find y
    l.dist = dist;
    l.minX = dx;                      // the 2D intercept point.
    l.minY = dy;
    l.nx = 0;                         // the face normal of the intercept point
    l.ny = 0;
}


function intercept(moveBox, moveLine, obstructionBox) { // find the closest intercept, if any
    var check, iPosX, iPosY, distSqrX, distSqrY;
    const b1 = moveBox, b2 = obstructionBox, l = moveLine;

    distSqrX = distSqrY = l.dist;
    const lr = l.x1 < l.x2; // lr for (l)eft to (r)ight is true is line moves from left to right.
    const tb = l.y1 < l.y2; // tb for (t)op to (b)ottom is true is line moves from top to bottom

    const w2 = b1.w / 2, h2 = b1.h / 2;
    const right  = b2.x + b2.w + w2;
    const left   = b2.x - w2;
    const top    = b2.y - h2;
    const bottom = b2.y + b2.h + h2;

    check = lr ?                      // quick check if collision is possible
        l.x1 < right && l.x2 > left:
        l.x2 < right && l.x1 > left;     
    check && (check = tb ?
            l.y1 < bottom && l.y2 > top:
            l.y2 < bottom && l.y1 > top);

    if (check) {      
        const lrSide = lr ? left : right;   // get closest left or right side
        const tbSide = tb ? top : bottom;   // get closest top or bottom side

        const distX = lrSide - l.x1;        // x Axis distance to closest side
        const distY = tbSide - l.y1;        // y Axis distance to closest side

        iPosX = l.x1 + distY * l.dx;        // X intercept of top or bottom
        iPosY = l.y1 + distX * l.dy;        // Y intercept of left or right

        if (iPosX >= left && iPosX <= right) { // is there a x Axis intercept?
            iPosX -= l.x1;
            distSqrX = Math.min(distSqrX, distY * distY + iPosX * iPosX); // distance squared   
        }
        if (iPosY >= top && iPosY <= bottom) { // is there a y Axis intercept?       
            iPosY -= l.y1;    
            distSqrY = Math.min(distSqrY, distX * distX + iPosY * iPosY);    
        }         
        
        if (distSqrX < l.dist || distSqrY < l.dist) {
            if (distSqrX < distSqrY) {
                l.dist = distSqrX;
                l.minX = iPosX;      
                l.minY = distY;
                l.nx = 0;                                                
                l.ny = tb ? -1 : 1;                
            } else {
                l.dist = distSqrY;
                l.minX = distX;                               
                l.minY = iPosY;
                l.nx = lr ? -1 : 1;                                   
                l.ny = 0;                
            }
            l.x2 = l.x1 + l.minX;  // Set new line end. This keeps the line
            l.y2 = l.y1 + l.minY;  // length as short as possible and avoid
                                   // unnneeded intercept tests
        }   
    }
}



//======================================================================================================================
// SUPPORT CODE FROM HERE DOWN
//======================================================================================================================
// The following code is support code that provides me with a standard interface to various forums.
// It provides a mouse interface, a full screen canvas, and some global often used variable
// like canvas, ctx, mouse, w, h (width and height), globalTime
// This code is not intended to be part of the answer unless specified and has been formated to reduce
// display size. It should not be used as an example of how to write a canvas interface.
// By Blindman67
const RESIZE_DEBOUNCE_TIME = 100;
var w, h, cw, ch, canvas, ctx, onResize, mouse, createCanvas, resizeCanvas, setGlobals, globalTime = 0, resizeCount = 0;
createCanvas = function () {
    var c,
    cs;
    cs = (c = document.createElement("canvas")).style;
    cs.position = "absolute";
    cs.top = cs.left = "0px";
    cs.zIndex = 1000;
    document.body.appendChild(c);
    return c;
}
resizeCanvas = function () {
    if (canvas === undefined) {
        canvas = createCanvas();
    }
    canvas.width = window.innerWidth;
    canvas.height = window.innerHeight;
    ctx = canvas.getContext("2d");
    if (typeof setGlobals === "function") {
        setGlobals();
    }
    if (typeof onResize === "function") {
        resizeCount += 1;
        setTimeout(debounceResize, RESIZE_DEBOUNCE_TIME);
    }
}
function debounceResize() {
    resizeCount -= 1;
    if (resizeCount <= 0) {
        onResize();
    }
}
setGlobals = function () {
    cw = (w = canvas.width) / 2;
    ch = (h = canvas.height) / 2;
    mouse.updateBounds();
}
mouse = (function () {
    function preventDefault(e) {
        e.preventDefault();
    }
    var mouse = {
        x : 0,
        y : 0,
        w : 0,
        alt : false,
        shift : false,
        ctrl : false,
        buttonRaw : 0,
        over : false,
        bm : [1, 2, 4, 6, 5, 3],
        active : false,
        bounds : null,
        crashRecover : null,
        mouseEvents : "mousemove,mousedown,mouseup,mouseout,mouseover,mousewheel,DOMMouseScroll".split(",")
    };
    var m = mouse;
    function mouseMove(e) {
        var t = e.type;
        m.x = e.clientX - m.bounds.left;
        m.y = e.clientY - m.bounds.top;
        m.alt = e.altKey;
        m.shift = e.shiftKey;
        m.ctrl = e.ctrlKey;
        if (t === "mousedown") {
            m.buttonRaw |= m.bm[e.which - 1];
        } else if (t === "mouseup") {
            m.buttonRaw &= m.bm[e.which + 2];
        } else if (t === "mouseout") {
            !m.buttonRaw  && (m.over = false);
        } else if (t === "mouseover") {
            m.over = true;
        } else if (t === "mousewheel") {
            m.w = e.wheelDelta;
        } else if (t === "DOMMouseScroll") {
            m.w = -e.detail;
        }
        e.preventDefault();
    }
    m.updateBounds = function () {
        if (m.active) {
            m.bounds = m.element.getBoundingClientRect();
        }
    }
    m.addCallback = function (callback) {
        if (typeof callback === "function") {
            if (m.callbacks === undefined) {
                m.callbacks = [callback];
            } else {
                m.callbacks.push(callback);
            }
        } else {
            throw new TypeError("mouse.addCallback argument must be a function");
        }
    }
    m.start = function (element, blockContextMenu) {
        if (m.element !== undefined) {
            m.removeMouse();
        }
        m.element = element === undefined ? document : element;
        m.blockContextMenu = blockContextMenu === undefined ? false : blockContextMenu;
        m.mouseEvents.forEach(n => {
            document.addEventListener(n, mouseMove);
        });
        if (m.blockContextMenu === true) {
            m.element.addEventListener("contextmenu", preventDefault, false);
        }
        m.active = true;
        m.updateBounds();
    }
    m.remove = function () {
        if (m.element !== undefined) {
            m.mouseEvents.forEach(n => {
                m.element.removeEventListener(n, mouseMove);
            });
            if (m.contextMenuBlocked === true) {
                m.element.removeEventListener("contextmenu", preventDefault);
            }
            m.element = m.callbacks = m.contextMenuBlocked = undefined;
            m.active = false;
        }
    }
    return mouse;
})();


resizeCanvas();
mouse.start(canvas, true);
window.addEventListener("resize", resizeCanvas);

w = canvas.width;
h = canvas.height;
cw = w / 2;  // center 
ch = h / 2;
globalTime = new Date().valueOf();  // global to this 


var numRandomBoxes = 10; // number of obstacles
var movePoint = 0;         // which end of the line to move
var boxes = [];            // array of boxes.
onresize = function(){
    boxes = [];
    numRandomBoxes = Math.floor(((w * h) / (30*130)) * 0.25);   // approx box density of 1/8th canvas pixels
    boxes.push(createBox(0,h-100,w,10));  // create a ground box
    var i = 0;   // create some random boxes
    while(i++ < numRandomBoxes){
        boxes.push(createBox(rand(-10,w + 10),rand(-10,h + 10),rand(10,30),rand(10,130)));
    }
}
onresize(); // set up 

var objBoxE = createBox(0,0,0,0);  // a mirror of moving used for display
var boxSizing = false;


function createBox(x, y, w, h) {
    return { x : x, y : y, w : w, h : h};
}
function createLine(x1, y1, x2, y2) {
    return { x1 : x1, y1 : y1, x2 : x2, y2 : y2};
}
function copyBox(b1, b2) { // copy coords from b1 to b2
    b2.x = b1.x;
    b2.y = b1.y;
    b2.w = b1.w;
    b2.h = b1.h;
}
function rand(min, max) { // returns a random int between min and max inclusive 
    return Math.floor(Math.random() * (max - min) + min);
}
// draw a box
function drawBox(b, ox = 0, oy = 0, xx = 0, yy = 0, fill) { // ox,oy optional expand box.
    if (!fill) {
        ctx.strokeRect(b.x - ox + xx, b.y - oy + yy, b.w + ox * 2, b.h + oy * 2);
    } else {
        ctx.fillRect(b.x - ox + xx, b.y - oy + yy, b.w + ox * 2, b.h + oy * 2);
    }
}
// draw a line
function drawLine(l, ox, oy) { // ox and oy optional offsets
    ox = ox ? ox : 0;
    oy = oy ? oy : 0;
    ctx.moveTo(l.x1 + ox, l.y1 + oy)
    ctx.lineTo(l.x2 + ox, l.y2 + oy);
}
// draw a a cross (mark)
function drawMark(x, y, size) {
    ctx.fillRect(x - size / 2, y - 0.5, size, 1);
    ctx.fillRect(x - 0.5, y - size / 2, 1, size);
}




// main update function
function update(timer){
    requestAnimationFrame(update);

    var L,B;  // short cuts to line and box to make code readable
    L = objLine;
    B = objBox;
    globalTime = timer;
    ctx.setTransform(1,0,0,1,0,0); // reset transform
    ctx.globalAlpha = 1;           // reset alpha
    ctx.clearRect(0,0,w,h);
    if(mouse.buttonRaw & 4){  // right button to clear the box and line
        B.x = B.y = 0;
        B.w = B.h = 0;
        L.x1 = L.x2 = 0; 
        L.y1 = L.y2 = 0; 
        copyBox(B,objBoxE);
    }
    if(mouse.buttonRaw & 1){ // if left button drag new box or move line ends
        if(B.w === 0){  // if the box has no size 
            boxSizing = true;  // create a box and flag that we are sizing the box
            B.x = mouse.x;
            B.y = mouse.y;
            B.w = 1;
            B.h = 1;
        }else{
            if(boxSizing){   // drag out the box size
                B.x = Math.min(mouse.x,B.x);
                B.y = Math.min(mouse.y,B.y);
                B.w = Math.max(1,mouse.x-B.x);
                B.h = Math.max(1,mouse.y-B.y);
            }else{
                if(L.x1 === L.x2 && L.y1 === L.y2 ){  // else if line does not exist start a new one
                    movePoint = 1;
                    L.x1 = B.x + B.w / 2;
                    L.y1 = B.y + B.h / 2;
                    L.x2 = mouse.x + 1;
                    L.y2 = mouse.y + 1;
                }else{
                    // if line does exist find closest end
                    if(mouse.oldBRaw !== mouse.buttonRaw){  // mouse button just down
                        movePoint = 1;
                    }

                    L.x2 = mouse.x;
                    L.y2 = mouse.y;
                }
                B.x = L.x1 - B.w / 2;
                B.y = L.y1 - B.h / 2;
                objBoxE.x = L.x2 - B.w / 2;
                objBoxE.y = L.y2 - B.h / 2;
                objBoxE.w = B.w;
                objBoxE.h = B.h;
            }
        }
    }else{
        boxSizing = false;
    }
    // draw obstical boxes
    ctx.strokeStyle = "black";
    for(var i = 0; i < boxes.length; i ++){
        drawBox(boxes[i]);
    }
    // draw start and end boxes
    ctx.strokeStyle = "red"
    drawBox(B);
    drawBox(objBoxE);
    // draw the line
    ctx.beginPath();
    drawLine(L);
    ctx.stroke();
    // draw the box outer edges
    ctx.globalAlpha = 0.25;
    ctx.beginPath();
    drawLine(L,-B.w/2,-B.h/2);
    drawLine(L,B.w/2,-B.h/2);
    drawLine(L,B.w/2,B.h/2);
    drawLine(L,-B.w/2,B.h/2);
    ctx.stroke();

    // if the line has length then check for intercepts
    if(!(L.x1 === L.x2 && L.y1 === L.y2 )){
        ctx.strokeStyle = "Blue"
        findIntercepts(B,L);
        ctx.fillStyle = "#0F0";
        ctx.strokeStyle = "black"
        ctx.globalAlpha = 0.2;
        drawBox(B,0,0,0,0,true);
        drawBox(B);
        ctx.globalAlpha = 1;
        drawBox(B,0,0,L.minX,L.minY,true);
        drawBox(B,0,0,L.minX,L.minY);
        ctx.beginPath();
        ctx.moveTo(L.x1 + L.minX, L.y1 + L.minY);
        ctx.lineTo(L.x1 + L.minX+ L.nx * 30, L.y1 + L.minY+ L.ny * 30);
        ctx.stroke();
    }

    if(mouse.buttonRaw === 0){
        ctx.globalAlpha = 1;
        ctx.font = "16px arial";
        ctx.textAlign = "center";
        ctx.fillStyle = "rgba(240,230,220,0.8)";
        ctx.strokeStyle = "black"
        ctx.fillRect(20,h - 42, w- 40,40);
        ctx.strokeRect(20,h - 42, w- 40,40);
        ctx.fillStyle = "black"    
        if(B.w === 0){ 
             ctx.fillText("Left click drag to size a box",w / 2, h - 20);
             ctx.canvas.style.cursor = "crosshair";
        }else if(!(L.x1 === L.x2 && L.y1 === L.y2 )){
             ctx.fillText("Left click drag to move box destination",w / 2, h - 26);
             ctx.fillText("Right click to clear.",w / 2, h - 6);
              ctx.canvas.style.cursor = "move";
        }else{
             ctx.fillText("Left click drag to move box destination",w / 2, h - 26);
             ctx.fillText("Right click to clear.",w / 2, h - 6);
             ctx.canvas.style.cursor = "move";

       }
    } else {  ctx.canvas.style.cursor = "none"; }





    mouse.oldBRaw = mouse.buttonRaw;
}
requestAnimationFrame(update);

Sera

Jeez... I am... Very confused to say the least. I think you really over-complicated the answer for me. I really appreciate your answer along with the one @Jean-François Fabre made, but i searched for a solution more deeply myself and i found this link which is basically exactly what i needed. I don't know how exactly i haven't thought about it myself to be honest. I'm going to say that you did answer my question though and you even gave me a test code (even though i don't understand javascript), so I will accept it. – Allege

@NeriNigberg Sorry, sometimes what is simple in the head is not so on paper. This solution needs a few diagrams (which I was hoping the demo would help with) to explain the core concept. I will put a little more work into it to clear it up. – Sera

Answer 2

many gaming systems have 2 "callback" methods:

update(int elapsed_time)

used to update game data, and

render(int elapsed_time)

used to render data on screen

The infamous "tunnel" effect happens when the speed of an object is too big so distance being computed like

delta_x = x_speed * elapsed_time;
delta_y = y_speed * elapsed_time;

So the x & y variations may be too high and artificially "cross" thin obstacles/targets.

You can deduce experimentally a threshold elapsed time value beyond which this effect will happen (it happens in "Pac-Man" in the later stages, so happens even to the best coders :)

Example of an update wrapper in C which guarantees that update is not called with a too big elapsed time:

void update_wrapper(int elapsed_time)
{
   int i;
   while(elapsed_time>0)
   {
       int current_elapsed = elapsed_time<max_elapsed_time_without_tunnel_effect ? elapsed_time : max_elapsed_time_without_tunnel_effect;
       update(current_elapsed);
       elapsed_time -= max_elapsed_time_without_tunnel_effect;
   }
}

Solicitous