Johan van Mol .org - Collision detection & bouncing part 3: bouncing balls: demo 3: recursive collision detection

Johan van Mol .org

demo 3: recursive collision detection

Let's find out why the ball flies through the wall near corners.
The collision with the lower wall is detected and as a result of that the ball bounces up and right. But the new position is passed the right wall. In the next step we try to detect a collision with the right wall, but it can't be detected because the ball has already passed the wall. The algorithm we're using only detects collisions before they happen.

This is how to solve this problem:
1. loop through all walls to detect a collision from the current position with the current speed vector
2. if a collision is detected, move the ball to the collision point and change the speed vector
3. loop through all walls again to detect a collision from the new position with the new speed vector
4. if a collision is detected, move the ball to the collision point and change the speed vector
5. loop through all walls again to detect a collision from the new position with the new speed vector
6. etc.

This sounds like a recursive function to me. We'll create a new function move() which will handle all the collision detection and bouncing code. The move() function returns an Object() with the x and y coordinate of the new position e.g {x: 250.4587, y: 315.2545}. The move() function calls itself recursively if necessary. The step() function is trimmed down to this:

public function step() {
    if (this.bPlaying) {
        var o = this.move(this.ball_mc._x, this.ball_mc._y,
                          new Vector(this.v.x, this.v.y));
        this.ball_mc._x = o.x;
        this.ball_mc._y = o.y;
    }
}

The move(x:Number, y:Number, speedVec:Vector) function contains the code of our previous step() function. It takes the arguments x and y are the coordinates of the ball from which to detect collisions and speedVec is the speed vector to use for the detection.

private function move (x:Number, y:Number, speedVec:Vector) {
    // determine the new position by adding the speed vector
    var newX = x + speedVec.x;
    var newY = y + speedVec.y;

    // collision detection
    ...

    if (this.walls[bestResultObj.wallIdx].n.x == 0) {
        this.v.y *= -1;
        speedVec.y *= -1;
    } else {
        this.v.x *= -1;
        speedVec.x *= -1;
    }

After the collision detection we have the collision position and a new speed vector. (Note that this.v is the actual speed vector we're using to move the ball and that speedVec is a temporary speed vector used in the next iteration of the collision detection.) Now we'll call this function recursively, with the position at the collision and the remainder of the speed vector (speedVec), to see if the ball hits another wall by bouncing off of this one.
The speed vector is cloned by the statement new Vector(speedVec.x, speedVec.y) because if you pass speedVec as such, it is passed as a reference to the Vector object and recursive calls of the move() function will all work on the same object. This would mess up the results.

        speedVec = speedVec.cross(1.0 - bestResultObj.isectRatio);
        var o = this.move(isectPos.x, isectPos.y, new Vector(speedVec.x, speedVec.y));
        newX = o.x;
        newY = o.y;
    }

    return {x: newX, y: newY};
}

If you try this demo in Flash, you'll see that it hangs here. The output window will tell you:
256 levels of recursion were exceeded in one action list.
This is probably an infinite loop.
Further execution of actions has been disabled in this movie.

The move() function is called in an endless loop. Since the ball is being put on the collision point, which is against the wall the same collision will be detected over and over again, the speed vector will flip over and over, but the ball won't move.

Download all demos' source code as zip | view this demo's source code in a new window

<< Previous - Next >>

Comments

Its a gr8 tutorial for how can we use vectors instead of trigonometry for motions and collisions
Posted by poonam sheth, Whose homepage is http://smspoonam.blogspot.com on Wednesday, 11 October 2006 at 10:17

There's a typo on step 3bis:
...the Y-component of Y...
instead of
...the Y-component of v...
but great work ;).
Posted by Fugus, on Thursday, 19 October 2006 at 12:47

I fixed the typo. Thanx.
Posted by Johan van Mol, on Thursday, 19 October 2006 at 3:06

Thanks for the great set of tutorials, very helpful!

One issue I've been trying to solve is dealing with walls that the ball can hit from either side. The direction of the normal throws things off. What I did was added an else after the 'if (this.walls[i].n.dot(speedVec) < 0) { ' block in move().

Instead of var vec:Vector = this.walls[i].n.getInverted().cross(this.radius); in the else I have it as var vec:Vector = this.walls[i].n.cross(this.radius);

This seems to work, but I'm worried I've recreated the bugs you addressed in demo4, and I'm guessing there might be a better solution out there.
Posted by peter, Whose homepage is http://www.thup.com/ on Thursday, 07 December 2006 at 11:17

do you got a tool to convert a drawed wallshape to this wall array that needed?
Posted by Peter, Whose homepage is http://index.hu on Wednesday, 30 May 2007 at 4:03

First I draw the shape in Illustrator and save the file in Illustrator 8 format. Open the file in a text editor, scroll to the bottom and you'll find something like
(Layer 1) Ln
... more stuff here ...
24 803 m
69 828 l
108 775 l
31 757 l
24 803 l
The numbers in front are the X and Y coordinates. 'm' means moveTo, 'l' means lineTo. I copy and paste these codes, save them as a string in actionscript and parse the string.
Posted by Johan van Mol, on Wednesday, 30 May 2007 at 5:20

Add your comments to this article Collision detection & bouncing part... ...