Line collision in pygame

2019-07-16 13:26发布

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 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 are small and go 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 on 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.

2条回答
forever°为你锁心
2楼-- · 2019-07-16 13:40

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;
   }
}
查看更多
该账号已被封号
3楼-- · 2019-07-16 13:44

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 behaviour, 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(b1, l, b2) { // find the closest intercept, if any, of b1 (box1) moving along l (line1)
                                // with b2. l.minX,l.minY will hold the position of the intercept point
                                // l.dist will hold the distance squared of the point from the line start
    var check = false;
    var lr = l.x1 < l.x2; // lf for (l)eft to (r)ight is true is line moves from left to right.
    var tb = l.y1 < l.y2; // tb for (t)op to (b)ottom is true is line moves from top to bottom
    var w2 = b1.w / 2;    // half width and height of box 1
    var h2 = b1.h / 2;

    // get extended sides of  box2. They are extended by half box1 width, height on all sides
    var right = b2.x + b2.w + w2;
    var left = b2.x - w2;
    var top = b2.y - h2;
    var bottom = b2.y + b2.h + h2;

    // check if box2 is inside the bounding box of the line
    if (lr) {                                      // if line from left to right
        check = (l.x1 < right && l.x2 > left);     // right hand side expression evaluates to boolean
    } else {
        check = (l.x2 < right && l.x1 > left);     // right hand side expression evaluates to boolean
    }
    if (check) {
        if (tb) {                                  // if line from top to bottom
            check = (l.y1 < bottom && l.y2 > top); // right hand side expression evaluates to boolean
        } else {
            check = (l.y2 < bottom && l.y1 > top); // right hand side expression evaluates to boolean
        }
    }
    if (check) {                                   // check is true if box2 needs to be checked
        ctx.strokeStyle = "blue";                  // draw box2's extened outline
        ctx.globalAlpha = 0.4;
        drawBox(b2, w2, h2);
        ctx.globalAlpha = 1;                       // set up for marking the intercept points if any
        ctx.fillStyle = "yellow";

        // Next check the horizontal and vertical lines around box2 that are closest to the line start
        // Use the slopes to calculate the x and y intercept points

        var lrSide = lr ? left : right;                               // get the closest top bottom side
        var tbSide = tb ? top : bottom;                               // get the closest top bottom side


        var distX = lrSide - l.x1;                                    // find x distance to closest side of box
        var distY = tbSide - l.y1;                                    // find y distance to closest side of box

        var posX = l.x1 + distY * l.dx;                               // use x slope to find X intercept of top or bottom
        var posY = l.y1 + distX * l.dy;                               // use y slope to find Y intercept of left or right
        if (posX >= left && posX <= right) {                          // is posX on the box perimeter?
            drawMark(posX, tbSide, 8);                                // mark the point
            var dist = distY * distY + (posX - l.x1) * (posX - l.x1); // get the distance to the intercept squared
            if (dist < l.dist) {                                      // is this intercept closer than any previous found intercepts?
                l.dist = dist;                                        // save the distance
                l.minX = posX - l.x1;                                 // and the x,y coordinate of intercept
                l.minY = tbSide - l.y1;
                l.nx = 0;                                             // get the normal of the line hit
                l.ny = tb ? -1 : 1;
            }
        }
        if (posY >= top && posY <= bottom) {                          // is posY on the box perimeter
            drawMark(lrSide, posY, 8);                                // mark the point
            var dist = distX * distX + (posY - l.y1) * (posY - l.y1); // get the distance to the intercept squared
            if (dist < l.dist) {                                      // is this intercept closer than any previous found intercepts?
                l.dist = dist;                                        // save the distance
                l.minX = lrSide - l.x1;                               // and the x,y coordinate of intercept
                l.minY = posY - l.y1;
                l.nx = lr ? -1 : 1;                                   // get the normal of the line hit
                l.ny = 0;
            }
        }
    }
}





//======================================================================================================================
// 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 = 0;
            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 => {
            m.element.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, oy, xx, yy, fill) { // ox,oy optional expand box.
    // xx,yy optional offset of box
    // fill options if true then fill
    ox = ox ? ox : 0;
    oy = oy ? oy : 0;
    xx = xx ? xx : 0;
    yy = yy ? yy : 0;
    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 = mouse.x;
                    L.y1 = mouse.y;
                    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
                        var d1 = (L.x1 - mouse.x) * (L.x1 - mouse.x) + (L.y1 - mouse.y) * (L.y1 - mouse.y);
                        var d2 = (L.x2 - mouse.x) * (L.x2 - mouse.x) + (L.y2 - mouse.y) * (L.y2 - mouse.y);
                        if(d1 < d2){
                            movePoint = 0;
                        }else{
                            movePoint = 1;
                        }
                    }
                    // drag the closest line end
                    if(movePoint === 0){
                        L.x1 = mouse.x;
                        L.y1 = mouse.y;
                    }else{
                        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();
    }
    ctx.globalAlpha = 1;
    ctx.font = "16px arial";
    ctx.textAlign = "center";
    ctx.fillStyle = "rgba(220,220,220,0.5)";
    ctx.strokeStyle = "black"
    ctx.fillRect(20,h - 40, w- 40,36);
    ctx.strokeRect(20,h - 40, w- 40,36);
    ctx.fillStyle = "black"
    if(mouse.buttonRaw === 0){
    if(B.w === 0){ 
         ctx.fillText("Left click drag to size a box",w / 2, h - 20);
    }else
    if(!(L.x1 === L.x2 && L.y1 === L.y2 )){
         ctx.fillText("Left click drag near a line end to move the line",w / 2, h - 26);
         ctx.fillText("Right click to clear.",w / 2, h - 6);
    }else{
         ctx.fillText("Left click drag to create a linear path for box",w / 2, h - 26);
         ctx.fillText("Right click to clear.",w / 2, h - 6);

    }
    }






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

查看更多
登录 后发表回答