pygame中的线碰撞

Question

我目前正在开发一款 2D 平台游戏，我意识到我的碰撞编程存在一个大问题。你看，为了找出与玩家的碰撞，我只是将玩家矩形移动，然后在碰撞时，我通过查看玩家的 x 和 y 加速度将玩家推开。

问题是，当使用这种方法时，玩家的速度可能会使玩家跳过他应该碰撞的目标，因为他应该碰撞的矩形太小。例如，如果平台大小为 9 像素，而玩家的移动速度为 11 像素，则他有可能会跳过目标。这种情况通常发生在玩家发射的子弹很小且速度很快的情况下（而且由于游戏的性质，我不希望它们是瞬时的）。

所以我想了想，想出了一个解决方案，从子弹之前所在的位置到他现在所在的位置画一条线，然后检查目标矩形是否与其碰撞。我搜索了执行此类操作的方法，但没有找到任何关于如何将其实现到 Pygame 中的好的解释。

我是否使用像素遮罩？如果是，怎么做？Pygame 中是否已有某些函数可以使用此方法？我真的需要一些帮助。

Answer 1

简单的线性AABB碰撞检测

下面是拦截带有许多静止盒子的移动盒子的解决方案。盒子的边必须平行于 x 轴和 y 轴。

它通过寻找两帧之间的第一个截距来解决高速运动的问题，无论障碍物有多薄或物体移动的速度有多快，都能找到正确的截距。（注意盒子必须有正的宽度和高度）

线盒截距

它的工作原理是将移动框的路径表示为一条线。不是将移动框的宽度和高度添加到线条中，而是将移动框的宽度和高度添加到障碍框中，这大大减少了解决问题所需的工作量。（该演示以图形方式展示了一些中间抽象，包括障碍箱的扩展）

要在游戏中使用，演示中的线只是游戏当前对象位置到下一帧中沿增量 x 和 y 的位置。

截距设置从当前位置到截距（如果有）的 x,y 距离。还提供法线（指向远离侧面撞击的矢量）以帮助碰撞响应。您还可以得到到截距点的距离的平方。您可以将该距离除以线长度的平方，得到拦截发生的单位时间。即值 0.5 表示它发生在两帧之间。0 发生在开始处，1 发生在结束处。如果没有截距，则法线长度将为零。

演示

该演示是 javascript，但数学和逻辑才是重要的。感兴趣的功能位于代码片段的顶部并得到了很好的评论（我希望）。下面只是样板和支持。

要使用演示，请左键单击拖动以创建一个框。然后左键单击并拖动以标记出一条线。起始位置是浅绿色框，另一个绿色框是截距（如果有）。还有一些黄色标记表示计算出的截距距离太远。整页可查看更多框。

限制和调整

您可能会注意到，如果开始位置接触一个框，则截取点位于开始位置之前（时间上向后）这是正确的行为，您不应在开始时与框（墙内）重叠

如果您有移动障碍物并且它们沿 x 或 y 轴移动，您可以通过简单地沿移动方向扩展框来调整解决方案（并不完美，但适用于缓慢移动的障碍物（注意下一帧中的重叠）。

您还可以测试移动圆圈。这可以通过检查截取点是否在角的圆半径距离内来完成。如果是这样，则以框真实角处的圆心和与移动圆相同的半径进行线圆截距。

我知道就像泥土一样清晰，所以如果您有任何问题，请询问。

// 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);