1
\$\begingroup\$

I'm coding a one-dimentional elastic collision animation (demo) with balls. I've used fixed position values when testing and now I want to use random values.

The problem with random values is that at the beginning (no animation, initial setup), balls might intersect. If this happens between two balls and in the middle of the container, current collision detection handles this kind of intersection. But if the balls are at the ends of the box and one intersects with both the wall and the other, this causes a problem.

For example, examine the below image.

  1. One ball is randomly assigned a position and is in the middle.
  2. Again, one ball is randomly assigned a position and it overflows to the left. It is repositioned to stay in the container.
  3. Two balls are randomly assigned a position (no intersection) and are in the middle.
  4. Two balls are randomly assigned a position (they intersect) and are in the middle. They're repositioned to touch each other.
  5. Two balls are randomly assigned a position (they intersect) and one of them overflows to the left. Both should be repositioned with respect to each other and to the left wall. (demo)

enter image description here

Currently, I don't know how to handle the fifth case. I'll also increase the number of the balls, so the solution should be appliable to multiple balls.

If I can't find an easy solution, I'm gonna try empty space detection and reposition the balls starting from the farthest to the wall.

Most relevant parts:

var balls = [
    new Ball(25, 25, 25, 0, 0),
    new Ball(25, 50, 25, 0, 0, "blue"),
    // new Ball(25, random(0, 400), 25, 0, 0, "purple"),
];

function draw() {
    context.clearRect(0, 0, canvas.width, canvas.height);
    trackCollisions();
    balls.forEach(function(ball) {
        ball.draw();
    });
}
draw();

function trackCollisions() {
    // wall collisions
    balls.forEach(function(ball) {
        if (ball.intersectingWithWall()) {
            ball.snap2wall();
            ball.wrframe();
        }
        else if (ball.collidingWithWall()) {
            ball.flash("red");
        }
    });
    // ball collisions
    for (var i = 0; i < balls.length; i++) {
        for (var j = i + 1; j < balls.length; j++) {
            if (balls[i].intersectingWith(balls[j])) {
                balls[i].snap2ball(balls[j]);
                balls[i].wrframe();
                balls[j].wrframe();
            }
            else if (balls[i].collidingWith(balls[j])) {
                balls[i].resolveCollision(balls[j]);
                balls[i].flash("lime");
                balls[j].flash("lime");
            }
        }
    }
};

I've decided to share this experiment I'm working on here in case people came across similar problems or just want to know more about collisions: https://github.com/akinuri/bouncing-balls

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

DMGregory's answer gave me an idea. Let's say I have 5 balls and I want to place them in 400px wide area randomly. I could divide 400 by 5. Now I have 80px wide cells. Something like

cells = [ [0,80], [80, 160], [160, 240], [240,320], [320, 400] ];

I can generate random positions inside every 80px cells. Of course, I need to consider the edges and overlaping of balls at the edges. But this approach works:

function init() {
    balls = spawnBalls(5, 25);
    balls.forEach(function(ball) {
        ball.draw();
    });
    // draw();
}

function draw() {
    context.clearRect(0, 0, canvas.width, canvas.height);
    balls.forEach(function(ball) {
        ball.move();
    });
    trackCollisions();
    balls.forEach(function(ball) {
        ball.draw();
    });
    requestAnimationFrame(draw);
}

function spawnBalls(count, radius) {
    var balls = [];
    var cellWidth = Math.floor(canvas.width / count);       // 80
    var cellEdgeOffset = 1;                                 // prevent balls from touching walls and each other
    var allowedCellWidth = cellWidth - 2 * cellEdgeOffset;  // 78
    if (allowedCellWidth < 2 * radius) {
        throw new Error("There's not enough room for " + count + " balls.");
    }
    var cells = []; // [ {"x1":26, "x2":54}, {"x1":106, "x2":134}, {"x1":186, "x2":214}, {"x1":266, "x2":294}, {"x1":346, "x2":374} ]
    for (var i = 0; i < count; i++) {
        cells.push({
            x1 : i * cellWidth + (radius + 1),       // left side of the cell
            x2 : (i + 1) * cellWidth - (radius + 1)  // right side of the cell
        });
    }
    for (var i = 0; i < cells.length; i++) {
        balls.push(new Ball(radius, random(cells[i].x1, cells[i].x2), 25, random(0, 4), 0));
    }
    return balls;
}

Five random placement:

enter image description here

\$\endgroup\$
1
  • \$\begingroup\$ Solid solution! Note that a method like this will never give you 3 balls touching in a row, or a group of balls clustered off to one side, but that might not matter for many use cases. \$\endgroup\$
    – DMGregory
    Feb 6, 2017 at 14:37
0
\$\begingroup\$

I'd be tempted to make the placement method avoid collisions by construction.

Here's an example that tries to place a ball inside a given interval. Then, it looks at the remaining room on either side of that interval. If either/both are big enough to fit another ball inside, it keeps them around, then tries to place the remaining balls in the leftover space.

By construction, it won't place two balls so close that they overlap, because it shrinks the intervals to only include valid placements.

function Interval(start, end) {
    this.start = start;
    this.end = end;
    this.length = end - start;
}

function SpawnBallsInRange(start, end, radius, ballCount) {
    var intervals = [new Interval(start + radius, end - radius)];
    var totalLength = intervals[0].length;

    while(ballCount > 0)    {
        var placement = Math.random() * totalLength;
        var intervalID = 0;
        while(intervalID < intervals.length - 1 && intervals[intervalID].length < placement) {
            placement -= intervals[intervalID].length;
            intervalID++;            
        }                   

        var interval = intervals.splice(intervalID, 1)[0];

        totalLength -= interval.length;

        if(placement > 2.0 * radius) {
           var child = new Interval(interval.start, interval.start + placement - 2.0 * radius);
           intervals.push(child);
           totalLength += child.length;
        }

        placement += interval.start;

        SpawnBallAt(placement);

        if(end - placement > 2.0 * radius) {
           var child = new Interval(placement + 2.0 * radius, interval.end);
           intervals.push(child);
           totalLength += child.length;
        }

        ballCount--;

        if(intervals.length == 0 && ballCount > 0) {
            console.log("Ran out of room with " + ballCount + " remaining to place.");
            // Maybe abort and try again?
            break;
        }
    }    
}
\$\endgroup\$
3
  • \$\begingroup\$ I haven't implemented your solution yet, but it gave me an idea and I've got it to work. I'll also try yours soon. \$\endgroup\$
    – akinuri
    Feb 6, 2017 at 14:12
  • \$\begingroup\$ I'm glad it helped you find something useful! I'd suggest posting your solution as an answer too, so folks can see what worked for you. \$\endgroup\$
    – DMGregory
    Feb 6, 2017 at 14:25
  • \$\begingroup\$ Haha. Just saw your reply. Was writing my solution :) \$\endgroup\$
    – akinuri
    Feb 6, 2017 at 14:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .