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