Calculate x/y point that 2 moving balls will collide

Question

I'm trying to make what is (essentially) a simple pool game, and would like to be able to predict where a shot will go once it hits another ball.

The first part is, I believe, to calculate if the cueball will hit anything, and if it does, where it collides. I can work out collision points for a line and a ball, but not 2 balls.

So given the x/y positions and velocities of 2 balls, how do I calculate the point at which they collide?

(PS: Im aware I can do this by calculating the distance between the two balls every step along the way, but I was hoping for something a little more elegant and optimal.)

Example of setup: trying to calculate the red dot

http://dl.dropbox.com/u/6202117/circle.PNG

Answer 1

Calculating the time of collision

Part of a physic sim is collision resolution. This is most often best done using a time step process. Start with the earliest collision, resolve and repeat for more collisions after this collision.

The time is a unit time. 0 the time of the last frame and 1 the frame we are rendering.

Thus we are really only interested in the time of collisions and can ignore the actual position until when know which two object collide first.

This answer provides a function that will return all possible collisions times (there are up to two) for two moving balls, ideally suited for time based collision resolution.

For TLDR go down to The solution

For the how read on.

Solving for u

First to define the ball (using JS)

const ball = {
     x, y,   // position start of frame
     r,      // radius
     vx, vy, // velocity vector per frame
}
// Two balls A, and B
A = {...ball, r: 20, etc}  
B = {...ball, r: 20, etc}

If we imagine the balls traveling along their vectors as a point. We start by looking at how we solve if only one ball is moving.

Ball A not moving, ball B moving, (to fit line removing dot notation A.x is Ax, B.vx is Bvx Also ** means to the power in JS)

We can find the distance a point is from a line using the following two steps.

First unit distance on line of closest point to A, Then use the unit dist u to get the distance dA from ball A is from the line B moves along

u = (Bvx * (Ax - Bx) + Bvy * (Ay - By)) / ((Ax - Bx) ** 2 + (Ay - By) ** 2);
dA = (((Bx + Bvx * u) - Ax) ** 2 + ((By + Bvy * u) - Ay) ** 2) ** 0.5;

We can do the same if ball 'B' not moving and ball A is

u = (Avx * (Bx - Ax) + Avy * (By - Ay)) / ((Bx - Ax) ** 2 + (By - Ay) ** 2);
dB = (((Ax + Avx * u) - Bx) ** 2 + ((Ay + Avy * u) - By) ** 2) ** 0.5;

If we now consider that if both balls are moving, if there is a collision it has to be at the same time. Thus the value u in both of above function must be the same.

We now have two equations for the same value u, however we need a little more to solve.

We also know that at time u (the time of collision) that the two balls must be the sum of their radius apart. That is dA + dB == Ar + Br. To get rid of the square roots the same holds true for dA * dA + dB * dB == Ar * Ar + Br * Br

Now we have only 1 unknown u and a function...

Ar*Ar+Br*Br = (((Bx+Bvx*u)-Ax)**2+((By+Bvy*u)-Ay)**2)+(((Ax+Avx*u)-Bx)**2+((Ay+Avy*u)-By)**2);

Or

f(u) = Ar*Ar+Br*Br-(((Bx+Bvx*u)-Ax)**2+((By+Bvy*u)-Ay)**2)+(((Ax+Avx*u)-Bx)**2+((Ay+Avy*u)-By)**2)

It may not be obvious but this function is just a quadratic eg f(u) = au^2 + bu + c and if we know the coefficients a, b, c we can find the roots using the quadratic formula (we all learnt in high school)

The solution

To solve we need rearrange the formula so that we can get a, b, c which we can plug into

// return array if 0, 1, or 2 roots
Math.quadRoots = (a, b, c) => {
    if (Math.abs(a) < 1e-6) { return b != 0 ? [-c / b] : []  }
    b /= a;
    var d = b * b - 4 * (c / a);
    if (d > 0) {
        d = d ** 0.5;
        return  [0.5 * (-b + d), 0.5 * (-b - d)]
    }
    return d === 0 ? [0.5 * -b] : [];
}

The rearrange turns into a page full, so to save the pain the following function returns the values u for two moving balls

// For line segements
// args (x1, y1, x2, y2, x3, y3, x4, y4, r1, r2)

Math.interceptTime = (a, e, b, f, c, g, d, h, r1, r2) => { 
    const A = a*a, B = b*b, C = c*c, D = d*d;
    const E = e*e, F = f*f, G = g*g, H = h*h;
    var R = (r1 + r2) ** 2;
    const AA = A + B + C + F + G + H + D + E + b*c + c*b + f*g + g*f + 2*(a*d - a*b - a*c - b*d - c*d - e*f + e*h - e*g - f*h - g*h);
    const BB = 2 * (-A + a*b + 2*a*c - a*d - c*b - C + c*d - E + e*f + 2*e*g - e*h - g*f - G + g*h);
    const CC = A - 2*a*c + C + E - 2*e*g + G - R;
    return Math.quadRoots(AA, BB, CC);
}   

To use

Get the time

const res = Math.interceptTime(A.x, A.y, A.x + A.vx, A.y + A.vy, B.x, B.y, B.x + B.vx, B.y + B.vy, A.r, B.r);
// remove out of range values and use the smallest as time of first contact
const time = Math.min(...res.filter(u => u >= 0 && u < 1));

Use that time to find earliest collision, once found use that time to get the ball positions

// point of contact for balls A and B
ax = A.x + A.vx * time;
ay = A.y + A.vy * time;
bx = B.x + B.vx * time;
by = B.y + B.vy * time;

Usage example

Above used in robust iterative collision resolution. Note small ball can travel at very high speed. Iterations capped at 200 per frame total due to JS being rather slow.

// See answer for details
Math.circlesInterceptUnitTime = (a, e, b, f, c, g, d, h, r1, r2) => { // args (x1, y1, x2, y2, x3, y3, x4, y4, r1, r2)
    const A = a * a, B = b * b, C = c * c, D = d * d;
    const E = e * e, F = f * f, G = g * g, H = h * h;
    var R = (r1 + r2) ** 2;
    const AA = A + B + C + F + G + H + D + E + b * c + c * b + f * g + g * f + 2 * (a * d - a * b - a * c - b * d - c * d - e * f + e * h - e * g - f * h - g * h);
    const BB = 2 * (-A + a * b + 2 * a * c - a * d - c * b - C + c * d - E + e * f + 2 * e * g - e * h - g * f - G + g * h);
    const CC = A - 2 * a * c + C + E - 2 * e * g + G - R;
    return Math.quadRoots(AA, BB, CC);
}   
Math.quadRoots = (a, b, c) => { // find roots for quadratic
    if (Math.abs(a) < 1e-6) { return b != 0 ? [-c / b] : []  }
    b /= a;
    var d = b * b - 4 * (c / a);
    if (d > 0) {
        d = d ** 0.5;
        return  [0.5 * (-b + d), 0.5 * (-b - d)]
    }
    return d === 0 ? [0.5 * -b] : [];
}



canvas.width = innerWidth -20;
canvas.height = innerHeight -20;
mathExt(); // creates some additional math functions
const ctx = canvas.getContext("2d");
const GRAVITY = 0;
const WALL_LOSS = 1;
const BALL_COUNT = 40;  // approx as will not add ball if space can not be found
const MIN_BALL_SIZE = 6;
const MAX_BALL_SIZE = 20;
const VEL_MIN = 1;
const VEL_MAX = 5; 
const MAX_RESOLUTION_CYCLES = 200; // Put too many balls (or too large) in the scene and the 
                                   // number of collisions per frame can grow so large that
                                   // it could block the page.

                                   // If the number of resolution steps is above this value
                                   // simulation will break and balls can pass through lines,
                                   // get trapped, or worse. LOL
const SHOW_COLLISION_TIME = 30;
const balls = [];
const lines = [];
function Line(x1,y1,x2,y2) {
    this.x1 = x1;
    this.y1 = y1;
    this.x2 = x2;
    this.y2 = y2;
}
Line.prototype = {
    draw() {
        ctx.moveTo(this.x1, this.y1);
        ctx.lineTo(this.x2, this.y2);
    },
    reverse() {
        const x = this.x1;
        const y = this.y1;
        this.x1 = this.x2;
        this.y1 = this.y2;
        this.x2 = x;
        this.y2 = y;
        return this;
    }
}
    
function Ball(x, y, vx, vy, r = 45, m = 4 / 3 * Math.PI * (r ** 3)) {
    this.r = r;
    this.m = m
    this.x = x;
    this.y = y;
    this.vx = vx;
    this.vy = vy;
}
Ball.prototype = {
    update() {
        this.x += this.vx;
        this.y += this.vy;
        this.vy += GRAVITY;
    },
    draw() {
        ctx.moveTo(this.x + this.r  - 1.5, this.y);
        ctx.arc(this.x, this.y, this.r - 1.5, 0, Math.PI * 2);
    },
    interceptLineTime(l, time) {
        const u = Math.interceptLineBallTime(this.x, this.y, this.vx, this.vy, l.x1, l.y1, l.x2, l.y2,  this.r);
        if (u >= time && u <= 1) {
            return u;
        }
    },
    checkBallBallTime(t, minTime) {
        return t > minTime && t <= 1;
    },
    interceptBallTime(b, time) {
        const x = this.x - b.x;
        const y = this.y - b.y;
        const d = (x * x + y * y) ** 0.5;
        if (d > this.r + b.r) {
            const times = Math.circlesInterceptUnitTime(
                this.x, this.y, 
                this.x + this.vx, this.y + this.vy, 
                b.x, b.y,
                b.x + b.vx, b.y + b.vy, 
                this.r, b.r
            );
            if (times.length) {
                if (times.length === 1) {
                    if(this.checkBallBallTime(times[0], time)) { return times[0] }
                    return;
                }
                if (times[0] <= times[1]) {
                    if(this.checkBallBallTime(times[0], time)) { return times[0] }
                    if(this.checkBallBallTime(times[1], time)) { return times[1] }
                    return
                }
                if(this.checkBallBallTime(times[1], time)) { return times[1] }                
                if(this.checkBallBallTime(times[0], time)) { return times[0] }
            }
        }
    },
    collideLine(l, time) {
        const x1 = l.x2 - l.x1;
        const y1 = l.y2 - l.y1;
        const d = (x1 * x1 + y1 * y1) ** 0.5;
        const nx = x1 / d;
        const ny = y1 / d;            
        const u = (this.vx  * nx + this.vy  * ny) * 2;
        this.x += this.vx * time;   
        this.y += this.vy * time;   
        this.vx = (nx * u - this.vx) * WALL_LOSS;
        this.vy = (ny * u - this.vy) * WALL_LOSS;
        this.x -= this.vx * time;
        this.y -= this.vy * time;
    },
    collide(b, time) { 
        const a = this;
        const m1 = a.m;
        const m2 = b.m;

        a.x = a.x + a.vx * time;
        a.y = a.y + a.vy * time;
        b.x = b.x + b.vx * time;
        b.y = b.y + b.vy * time;

        const x = a.x - b.x
        const y = a.y - b.y  
        const d = (x * x + y * y);
        const u1 = (a.vx * x + a.vy * y) / d
        const u2 = (x * a.vy - y * a.vx ) / d
        const u3 = (b.vx * x + b.vy * y) / d
        const u4 = (x * b.vy - y * b.vx ) / d
        const mm = m1 + m2;
        const vu3 = (m1 - m2) / mm * u1 + (2 * m2) / mm * u3;
        const vu1 = (m2 - m1) / mm * u3 + (2 * m1) / mm * u1;

        b.vx = x * vu1 - y * u4;
        b.vy = y * vu1 + x * u4;
        a.vx = x * vu3 - y * u2;
        a.vy = y * vu3 + x * u2;
        a.x = a.x - a.vx * time;
        a.y = a.y - a.vy * time;
        b.x = b.x - b.vx * time;
        b.y = b.y - b.vy * time;
    },
    doesOverlap(ball) {
        const x = this.x - ball.x;
        const y = this.y - ball.y;
        return  (this.r + ball.r) > ((x * x + y * y) ** 0.5);  
    }       
}

function canAdd(ball) {
    for(const b of balls) {
        if (ball.doesOverlap(b)) { return false }
    }
    return true;
}
function create(bCount) {
    lines.push(new Line(-10, 20, ctx.canvas.width + 10, 5));
    lines.push((new Line(-10, ctx.canvas.height - 30, ctx.canvas.width + 10, ctx.canvas.height - 3)).reverse());
    lines.push((new Line(30, -10, 4, ctx.canvas.height + 10)).reverse());
    lines.push(new Line(ctx.canvas.width - 3, -10, ctx.canvas.width - 30, ctx.canvas.height + 10)); 
    while (bCount--) {
        let tries = 100;
        while (tries--) {
            const dir = Math.rand(0, Math.TAU);
            const vel = Math.rand(VEL_MIN, VEL_MAX);
            const ball = new Ball(
                Math.rand(MAX_BALL_SIZE + 30, canvas.width - MAX_BALL_SIZE - 30), 
                Math.rand(MAX_BALL_SIZE + 30, canvas.height - MAX_BALL_SIZE - 30),
                Math.cos(dir) * vel,
                Math.sin(dir) * vel,
                Math.randP(MIN_BALL_SIZE, MAX_BALL_SIZE),
            );
            if (canAdd(ball)) {
                balls.push(ball);
                break;
            }
        }
    }
}
function resolveCollisions() {
    var minTime = 0, minObj, minBall, resolving = true, idx = 0, idx1, after = 0, e = 0;
    while (resolving && e++ < MAX_RESOLUTION_CYCLES) { // too main ball may create very lone resolution cycle. e limits this
        resolving = false;
        minObj = undefined;
        minBall = undefined;
        minTime = 1;
        idx = 0;
        for (const b of balls) {
            idx1 = idx + 1;
            while (idx1 < balls.length) {
                const b1 = balls[idx1++];
                const time = b.interceptBallTime(b1, after);
                if (time !== undefined) {
                    if (time <= minTime) {
                        minTime = time;
                        minObj = b1;
                        minBall = b;
                        resolving = true;
                    }
                }
            }
            for (const l of lines) {
                const time = b.interceptLineTime(l, after);
                if (time !== undefined) {
                    if (time <= minTime) {
                        minTime = time;
                        minObj = l;
                        minBall = b;
                        resolving = true;
                    }
                }
            }
            idx ++;
        }
        if (resolving) {
            if (minObj instanceof Ball) {
                minBall.collide(minObj, minTime);
            } else {
                minBall.collideLine(minObj, minTime);
            }
            after = minTime;
        }
    }
}
create(BALL_COUNT);
mainLoop();
function mainLoop() {
    ctx.clearRect(0,0,ctx.canvas.width, ctx.canvas.height);

    resolveCollisions();
    for (const b of balls) { b.update() }
    
    ctx.beginPath();
    ctx.strokeStyle = "#00F";
    ctx.lineWidth = 3;    
    for (const b of balls) { b.draw() }
    ctx.stroke();
     
    ctx.lineWidth = 1;
    ctx.strokeStyle = "#000";
    ctx.beginPath();
    for(const l of lines) { l.draw() }
    ctx.stroke();

    requestAnimationFrame(mainLoop);
}

function mathExt() {
    Math.TAU = Math.PI * 2;
    Math.rand = (min, max) => Math.random() * (max - min) + min;
    Math.randP = (min, max, pow = 2) => Math.random() ** pow * (max - min) + min;
    Math.randI = (min, max) => Math.random() * (max - min) + min | 0; // only for positive numbers 32bit signed int
    Math.randItem = arr => arr[Math.random() * arr.length | 0]; // only for arrays with length < 2 ** 31 - 1

    Math.interceptLineBallTime = (x, y, vx, vy, x1, y1, x2, y2,  r) => {
        const xx = x2 - x1;
        const yy = y2 - y1;
        const d = vx * yy - vy * xx;
        if (d > 0) {  // only if moving towards the line
            const dd = r / (xx * xx + yy * yy) ** 0.5;
            const nx = xx * dd;
            const ny = yy * dd;
            return (xx * (y - (y1 + nx)) - yy * (x -(x1 - ny))) / d;
        }
    }
}

<canvas id="canvas"></canvas>