python 3.x - 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.

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;
        }