Asked  6 Months ago    Answers:  5   Viewed   63 times

With the help of the Stack Overflow community I've written a pretty basic-but fun physics simulator.

alt text

You click and drag the mouse to launch a ball. It will bounce around and eventually stop on the "floor".

My next big feature I want to add in is ball to ball collision. The ball's movement is broken up into a x and y speed vector. I have gravity (small reduction of the y vector each step), I have friction (small reduction of both vectors each collision with a wall). The balls honestly move around in a surprisingly realistic way.

I guess my question has two parts:

  1. What is the best method to detect ball to ball collision?
    Do I just have an O(n^2) loop that iterates over each ball and checks every other ball to see if it's radius overlaps?
  2. What equations do I use to handle the ball to ball collisions? Physics 101
    How does it effect the two balls speed x/y vectors? What is the resulting direction the two balls head off in? How do I apply this to each ball?

alt text

Handling the collision detection of the "walls" and the resulting vector changes were easy but I see more complications with ball-ball collisions. With walls I simply had to take the negative of the appropriate x or y vector and off it would go in the correct direction. With balls I don't think it is that way.

Some quick clarifications: for simplicity I'm ok with a perfectly elastic collision for now, also all my balls have the same mass right now, but I might change that in the future.


Edit: Resources I have found useful

2d Ball physics with vectors: 2-Dimensional Collisions Without Trigonometry.pdf
2d Ball collision detection example: Adding Collision Detection


Success!

I have the ball collision detection and response working great!

Relevant code:

Collision Detection:

for (int i = 0; i < ballCount; i++)  
{  
    for (int j = i + 1; j < ballCount; j++)  
    {  
        if (balls[i].colliding(balls[j]))  
        {
            balls[i].resolveCollision(balls[j]);
        }
    }
}

This will check for collisions between every ball but skip redundant checks (if you have to check if ball 1 collides with ball 2 then you don't need to check if ball 2 collides with ball 1. Also, it skips checking for collisions with itself).

Then, in my ball class I have my colliding() and resolveCollision() methods:

public boolean colliding(Ball ball)
{
    float xd = position.getX() - ball.position.getX();
    float yd = position.getY() - ball.position.getY();

    float sumRadius = getRadius() + ball.getRadius();
    float sqrRadius = sumRadius * sumRadius;

    float distSqr = (xd * xd) + (yd * yd);

    if (distSqr <= sqrRadius)
    {
        return true;
    }

    return false;
}

public void resolveCollision(Ball ball)
{
    // get the mtd
    Vector2d delta = (position.subtract(ball.position));
    float d = delta.getLength();
    // minimum translation distance to push balls apart after intersecting
    Vector2d mtd = delta.multiply(((getRadius() + ball.getRadius())-d)/d); 


    // resolve intersection --
    // inverse mass quantities
    float im1 = 1 / getMass(); 
    float im2 = 1 / ball.getMass();

    // push-pull them apart based off their mass
    position = position.add(mtd.multiply(im1 / (im1 + im2)));
    ball.position = ball.position.subtract(mtd.multiply(im2 / (im1 + im2)));

    // impact speed
    Vector2d v = (this.velocity.subtract(ball.velocity));
    float vn = v.dot(mtd.normalize());

    // sphere intersecting but moving away from each other already
    if (vn > 0.0f) return;

    // collision impulse
    float i = (-(1.0f + Constants.restitution) * vn) / (im1 + im2);
    Vector2d impulse = mtd.normalize().multiply(i);

    // change in momentum
    this.velocity = this.velocity.add(impulse.multiply(im1));
    ball.velocity = ball.velocity.subtract(impulse.multiply(im2));

}

Source Code: Complete source for ball to ball collider.

If anyone has some suggestions for how to improve this basic physics simulator let me know! One thing I have yet to add is angular momentum so the balls will roll more realistically. Any other suggestions? Leave a comment!

 Answers

95

To detect whether two balls collide, just check whether the distance between their centers is less than two times the radius. To do a perfectly elastic collision between the balls, you only need to worry about the component of the velocity that is in the direction of the collision. The other component (tangent to the collision) will stay the same for both balls. You can get the collision components by creating a unit vector pointing in the direction from one ball to the other, then taking the dot product with the velocity vectors of the balls. You can then plug these components into a 1D perfectly elastic collision equation.

Wikipedia has a pretty good summary of the whole process. For balls of any mass, the new velocities can be calculated using the equations (where v1 and v2 are the velocities after the collision, and u1, u2 are from before):

v_{1} = frac{u_{1}(m_{1}-m_{2})+2m_{2}u_{2}}{m_{1}+m_{2}}

v_{2} = frac{u_{2}(m_{2}-m_{1})+2m_{1}u_{1}}{m_{1}+m_{2}}

If the balls have the same mass then the velocities are simply switched. Here's some code I wrote which does something similar:

void Simulation::collide(Storage::Iterator a, Storage::Iterator b)
{
    // Check whether there actually was a collision
    if (a == b)
        return;

    Vector collision = a.position() - b.position();
    double distance = collision.length();
    if (distance == 0.0) {              // hack to avoid div by zero
        collision = Vector(1.0, 0.0);
        distance = 1.0;
    }
    if (distance > 1.0)
        return;

    // Get the components of the velocity vectors which are parallel to the collision.
    // The perpendicular component remains the same for both fish
    collision = collision / distance;
    double aci = a.velocity().dot(collision);
    double bci = b.velocity().dot(collision);

    // Solve for the new velocities using the 1-dimensional elastic collision equations.
    // Turns out it's really simple when the masses are the same.
    double acf = bci;
    double bcf = aci;

    // Replace the collision velocity components with the new ones
    a.velocity() += (acf - aci) * collision;
    b.velocity() += (bcf - bci) * collision;
}

As for efficiency, Ryan Fox is right, you should consider dividing up the region into sections, then doing collision detection within each section. Keep in mind that balls can collide with other balls on the boundaries of a section, so this may make your code much more complicated. Efficiency probably won't matter until you have several hundred balls though. For bonus points, you can run each section on a different core, or split up the processing of collisions within each section.

Tuesday, June 1, 2021
 
VostanAzatyan
answered 6 Months ago
68

Some things to take note of:

  • When two balls, each of radius r collide their centers are 2r apart.
  • Your first ball can be assumed to travel in a straight line (well, first approximation, but start with this), and you can find the angle, alpha between this path and the direction from the first ball to the second.
  • You know the center of the stationary ball, no?

Now you have some geometry to do.

Do this construction:

  1. Mark the current center of the first (moving) ball as point A.
  2. Mark the center of the stationary ball as point B.
  3. Construct line segment AB.
  4. Construct the ray, R, from A in the direction of movement.
  5. Construct a circle of radius 2r around B.
  6. Drop a segment from B perpendicular to R call the point of intersection C.
  7. You know the distance AB and you can find the angle alpha between AB and R, with the Law of Sines find the length of BC.
  8. From that length determine if there are 0, 1 or 2 solutions. If there are 0 or 1 you are done.
  9. Construct point D where the circle meets R closer to A, and use the Law of Sines again to find the distance AD.
  10. The point of collision is the midpoint of BD

and now you know everything.

Constructing efficient code from this is left as an exercise.


BTW-- This construction won't work if both balls are moving, but you can transform into a frame where one is stationary, solve it that way, then transform back. Just be sure to check that the solution is in the allowed area after the reverse transformation...

/ Physicists can't not make comments like this. I tried to resist. I really did.

Tuesday, August 10, 2021
 
phuongzzz
answered 4 Months ago
20

Try these:

  • http://code.google.com/p/language-detection/ (Java)
  • http://code.google.com/p/chromium-compact-language-detector/ (C++/Python)

This blog post shares some tests to compare the 2 libraries (along with a 3rd - the Language Identification module of Apache Tika, which really is a complete toolkit for Text Analysis).

Wednesday, August 11, 2021
 
PLPeeters
answered 4 Months ago
100

Here's how to test for circle (ball) collisions) versus any line in your polygon.

First, calculate the closes point on a line relative to your ball:

function calcClosestPtOnSegment(x0,y0,x1,y1,cx,cy){

    // calc delta distance: source point to line start
    var dx=cx-x0;
    var dy=cy-y0;

    // calc delta distance: line start to end
    var dxx=x1-x0;
    var dyy=y1-y0;

    // Calc position on line normalized between 0.00 & 1.00
    // == dot product divided by delta line distances squared
    var t=(dx*dxx+dy*dyy)/(dxx*dxx+dyy*dyy);

    // calc nearest pt on line
    var x=x0+dxx*t;
    var y=y0+dyy*t;

    // clamp results to being on the segment
    if(t<0){x=x0;y=y0;}
    if(t>1){x=x1;y=y1;}

    return({ x:x, y:y, isOnSegment:(t>=0 && t<=1) });
}

Second, test if the ball is close enough to collide with that line like this:

var dx=ballX-nearestX;
var dy=ballY-nearestY
var isColliding=(dx*dx+dy*dy<ballRadius*ballRadius);

Finally, if the ball collided with that side, calculate the ball's reflection angle (== its outgoing angle):

Here's an illustration of the angles involved in the calculation:

  • The red line indicates the ball's incoming angle.
  • The gold line indicates the ball's outgoing angle.
  • The outgoing angle equals the incoming angle plus twice the diff-angle.

enter image description here

And here's some pseudo-code showing how to do the calculation:

var wallNormalAngle = wallAngle-PI/2; // assuming clockwise angle calculations
var differenceAngle = incidenceAngle - wallNormalAngle;
var reflectionAngle = incidenceAngle + 2 * differenceAngle
Friday, August 27, 2021
 
Ram kiran
answered 3 Months ago
63

@MPdoor2 "I made...". Anywho, when I gave you that code I did specifically say I had hacked it from a method I created to be used on tilemaps. The method works flawless for that purpose although there is more to the code and yes it is built for squares since that's what tiles map mainly are.

I have been playing with alternate methods of doing CD. Here's a shorter method that (so far) seems to be working well. This method still determines the distance between each side but in a different way. Once the broadphase determines a collision has occurred it calls the narrow phase and whichever side has the shortest distance is the side being penetrated. i.e. when you collide with another block from the player right to the object left we know that even the Y axis penetrates (top and bottom corners of player). This calculates the distance between all three and since the distance between X would be 0 it is the shortest and the CD for moving the player in the Y direction does not get called.

Try the snippet below and see if this works for you.

const canvas = document.getElementById('canvas');
const context = canvas.getContext('2d');

canvas.width = 700;
canvas.height = 500;

let gravity = 1.5;
let friction = 0.9;

//CHARACTER:
class Player {
    constructor(x, y, vx, vy, c, j) {
        //each player must have separate values for control purposes i.e. velocity/jump/attack etc.
        this.x = x;
        this.y = y;
        this.w = 50;
        this.h = 50;
        this.vx = vx;
        this.vy = vy;
        this.color = c;
        this.jumping = j;
        this.center = {x: this.x + this.w/2,  y: this.y + this.h/2};
        this.topLeft = {x: this.x, y: this.y};
        this.topRight = {x: this.x + this.w, y: this.y};
        this.bottomRight = {x: this.x + this.w, y: this.y + this.h};
        this.bottomLeft = {x: this.x, y: this.y + this.h};
    }
    draw() {
       context.fillStyle = this.color;
       context.fillRect(this.x, this.y, this.w, this.h);
    }
    canvasCollision() {
        if (this.x <= 0) this.x = 0;
        if (this.y <= 0) this.y = 0;
        if (this.x + this.w >= canvas.width) this.x = canvas.width - this.w;
        if (this.y + this.h >= canvas.height) {this.y = canvas.height - this.h; this.vy = 0; this.jumping = false};
    }
    update() {
        this.draw(); 
        this.vy += gravity;
        this.x += this.vx;
        this.y += this.vy;
        this.vx *= friction;
        this.vy *= friction;
        this.center = {x: this.x + this.w/2,  y: this.y + this.h/2};
        this.topLeft = {x: this.x, y: this.y};
        this.topRight = {x: this.x + this.w, y: this.y};
        this.bottomRight = {x: this.x + this.w, y: this.y + this.h};
        this.bottomLeft = {x: this.x, y: this.y + this.h};
        this.canvasCollision() //must be after other updates
    }
}
let player = new Player(0, 0, 0, 0, 'red', false); 

function controlPlayer1(obj) {
    if (controller1.up1 && !obj.jumping) { obj.vy -= 25; obj.jumping = true };
    if (controller1.left1) { obj.vx -= 0.5 };
    if (controller1.right1) { obj.vx += 0.5 };
    obj.update();
}

class Platform {
    constructor(x,y,w,h) {
        this.x = x;
        this.y = y;
        this.w = w;
        this.h = h;
        this.center = {x: this.x + this.w/2,  y: this.y + this.h/2};
        this.topLeft = {x: this.x, y: this.y};
        this.topRight = {x: this.x + this.w, y: this.y};
        this.bottomRight = {x: this.x + this.w, y: this.y + this.h};
        this.bottomLeft = {x: this.x, y: this.y + this.h};
    }
    draw() {
        context.fillStyle = 'blue';
        context.fillRect(this.x, this.y, this.w, this.h);
    }
}

let platforms = [];
function createPlatforms() {
    for (let i=0; i<4; i++) {
       platforms.push(new Platform(200 * i, 450 - (i * 75), 100, 25));
    }
}
createPlatforms();

let platform1 = platforms.push(new Platform(300, 400, 50, 100));
let platform2 = platforms.push(new Platform(400, 400, 50, 50));

//MOVEMENT:
class Controller {
    constructor() {
        this.left1  = false;
        this.up1    = false;
        this.right1 = false;
        this.left2  = false;
        this.up2    = false;
        this.right2 = false;

        let controller1 = (e) => {
            if (e.code === 'ArrowRight') { this.right1 = e.type === 'keydown' }
            if (e.code === 'ArrowLeft')  { this.left1 = e.type === 'keydown' }
            if (e.code === 'ArrowUp')    { this.up1 = e.type === 'keydown' }           
        }
    
    window.addEventListener('keydown', controller1);
    window.addEventListener('keyup', controller1);
    }
}
let controller1 = new Controller();

function collisionDetection(obj) {
    if (player.x + player.w < obj.x ||
        player.x > obj.x + obj.w ||
        player.y + player.h < obj.y ||
        player.y > obj.y + obj.h) {
            return
        }
        narrowPhase(obj);
}

function narrowPhase(obj) {
    let playerTop_ObjBottom = Math.abs(player.y - (obj.y + obj.h));
    let playerRight_ObjLeft = Math.abs((player.x + player.w) - obj.x);
    let playerLeft_ObjRight = Math.abs(player.x - (obj.x + obj.w));
    let playerBottom_ObjTop = Math.abs((player.y + player.h) - obj.y);

    if ((player.y <= obj.y + obj.h && player.y + player.h > obj.y + obj.h) && (playerTop_ObjBottom < playerRight_ObjLeft && playerTop_ObjBottom < playerLeft_ObjRight)) {
        player.y = obj.y + obj.h;
        player.vy = 0;
    }
    if ((player.y + player.h >= obj.y && player.y < obj.y) && (playerBottom_ObjTop < playerRight_ObjLeft && playerBottom_ObjTop < playerLeft_ObjRight)) {
        player.y = obj.y - player.h; 
        player.jumping = false;
        player.vy = 0;
    }
    if ((player.x + player.w >= obj.x && player.x < obj.x) && (playerRight_ObjLeft < playerTop_ObjBottom && playerRight_ObjLeft < playerBottom_ObjTop)) {
        player.x = obj.x - player.w;
        player.vx = 0; 
    }
    if ((player.x <= obj.x + obj.w && player.x + player.w > obj.x + obj.w) && (playerLeft_ObjRight < playerTop_ObjBottom && playerLeft_ObjRight < playerBottom_ObjTop)) {
        player.x = obj.x + obj.w;
        player.vx = 0; 
    }
}

function animate() {
    context.clearRect(0, 0, canvas.width, canvas.height); 
    context.fillStyle = 'grey';
    context.fillRect(0, 0, canvas.width, canvas.height);
    controlPlayer1(player); 
    for (let i=0;i<platforms.length;i++) {
        platforms[i].draw();
        collisionDetection(platforms[i])
    };
    requestAnimationFrame(animate)
}
animate();
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="user-scalable=no, initial-scale=1, maximum-scale=1, minimum-scale=1, width=device-width, height=device-height">
    <title>CD</title>
</head>
<body>
<canvas id="canvas"></canvas>
<script src="squareRectCollision2.js"></script>
</body>
</html>
Friday, November 5, 2021
 
Shepmaster
answered 4 Weeks ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :  
Share