Sometimes collisions work, sometimes they don't.

Post: #1
I'm building a maze game controlled via motion sensors. Think that old tabletop Labyrinth game.

When the ball strikes a wall at a low speed, it stops, but if it's at a high speed, it passes right through. This also means that if the ball has stopped, I can tip the laptop farther, and it will eventually go through the wall.

The collision detection is in a controller class that has a reference out to the CustomView used for rendering. The collision detection is called after the new dot position has been figured and the screen has been refreshed. There also seems to be a problem when two walls intersect- I can sometimes sneak the ball through the corner, although this could be related to the current problem. I've been banging my head against the wall for weeks on this, so I'm throwing it up here to see if anyone has any thoughts.

I'm obviously missing something really butt simple. But I've spent years avoiding game programming for just this very reason.

- (void) collideDot:(Dot*) d withWall:(Wall*) w
    NSRect wBounds = [myView scaleWall:[w getBounds]];
    NSRect dBounds = [d dotRect];
    NSPoint center = [d getCenter];
    NSPoint lastLoc = [d getLastLoc];
    float radius = [d getRadius];
    [d setColor:[NSColor redColor]];
    if ([self collidePossibleWithOtherRect:wBounds ThisRect:dBounds]) {
                //the  pastLeft, beforeRight, aboveBottom, and belowTop variables should be renamed.
                //but I'm testing if at least the dot started or ended with an intersection in that range.
        Boolean startToTheLeft, startToTheRight, endToTheLeft, endToTheRight, startBelow, startAbove, endBelow, endAbove, pastLeft, beforeRight, aboveBottom, belowTop;
        //all of the tests for horizontal intersection    
        startToTheLeft = lastLoc.x < wBounds.origin.x;
        startToTheRight = lastLoc.x > wBounds.origin.x + wBounds.size.width ;
        endToTheLeft = center.x + radius > wBounds.origin.x;
        endToTheRight = center.x - radius < wBounds.origin.x + wBounds.size.width;
        aboveBottom = [self Value:lastLoc.y isBetweenA:wBounds.origin.y andB:wBounds.origin.y + wBounds.size.height];
        belowTop = [self Value:center.y isBetweenA:wBounds.origin.y andB:wBounds.origin.y + wBounds.size.height + radius];
        //all of the tests for vertical intersection
        startBelow = lastLoc.y < wBounds.origin.y;
        startAbove = lastLoc.y > wBounds.origin.y + wBounds.size.height;
        endAbove = center.y + radius > wBounds.origin.y;
        endBelow = center.y - radius < wBounds.origin.y + wBounds.size.height;
        pastLeft = [self Value:lastLoc.x isBetweenA:wBounds.origin.x andB:wBounds.origin.x + wBounds.size.width];
        beforeRight = [self Value:center.x isBetweenA:wBounds.origin.x -radius andB:wBounds.origin.x + wBounds.size.width];
        //left edge test
        //lastX is to the left of the left side, and the curX is to the right of the left edge, and we're in line between the top and bottom
        if (startToTheLeft && endToTheRight && (aboveBottom || belowTop)) {
            center.x = wBounds.origin.x - radius; //move the center back to the left
        } else //if our lastX is to the right of the left edge + width, and the curX is to the left of the left edge + width, and we're in line between top and bottom
        if (startToTheRight && endToTheLeft && aboveBottom && belowTop) {
            center.x = wBounds.origin.x + wBounds.size.width +  radius; //move the dot to the right        
        } else //bottom edge
        if (startBelow && endAbove && (pastLeft || beforeRight)) {
            center.y = wBounds.origin.y - radius;
        } else
        if (startAbove && endBelow && (pastLeft || beforeRight)) {
            center.y = wBounds.origin.y + wBounds.size.height +  radius;
        } else {
            //we're on a corner- figure out how to fix that, will ya?
            //test each corner, and move the ball to one of the edges?
            //yeah, i like that. TL=top, TR=right, BL=left, BR=bottom
            NSPoint bl = wBounds.origin;
            NSPoint tl = bl; tl.y += wBounds.size.height;
            NSPoint br = bl; br.x += wBounds.size.width;
            NSPoint tr = br; tr.y = tl.y;
            [d setColor:[NSColor purpleColor]];
            if ([self collidePossibleForDot:d withPoint:bl havingRadius:0]) center.x = bl.x - radius;
            else if ([self collidePossibleForDot:d withPoint:tl havingRadius:0]) {
                center.y = tl.y + radius;
            } else if([self collidePossibleForDot:d withPoint:br havingRadius:0]) {
                center.y = br.y - radius;
            } else if ([self collidePossibleForDot:d withPoint:tr havingRadius:0]) {
                center.x = tr.x + radius;
    [d setCenter:center];
    if ([self collidePossibleForDot:d withPoint:[myMaze getEnd] havingRadius:radius/2]) {
        [myView doWin];

- (BOOL) collidePossibleForDot:(Dot*)d withPoint:(NSPoint) p havingRadius:(float) radius
    p = [myView scalePoint:p];
    return [self distanceBetween:[d getCenter] and:p] <= radius + [d getRadius];

- (float) distanceBetween:(NSPoint) a and:(NSPoint)b
    float x1, x2, y1, y2;
    x1 = a.x; x2 = b.x; y1 = a.y; y2 = b.y;
    return sqrt((x1 - x2) * (x1-x2) + (y1 - y2) * (y1 -y2));

- (BOOL) collidePossibleWithOtherRect:(NSRect) r ThisRect:(NSRect) temp
    return !((temp.origin.y + temp.size.height < r.origin.y) ||
        (r.origin.y + r.size.height < temp.origin.y) ||
         (temp.origin.x + temp.size.width < r.origin.x) ||
         (r.origin.x + r.size.width < temp.origin.x));

- (BOOL) Value:(float)val isBetweenA:(float)a andB:(float)b
    return val > a && val < b;
Quote this message in a reply
Posts: 1,403
Joined: 2005.07
Post: #2
Quote:When the ball strikes a wall at a low speed, it stops, but if it's at a high speed, it passes right through.

if you were doing point against a wall (line in this example) collision for example, intersect the line from the point's origional position to the current position with the wall.

I would recommend cleaning up your code style its awfuly hard to read the collideDot function, and when things are clearer your problems will probably jump out at you Smile

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Post: #3
unknown Wrote:I would recommend cleaning up your code style its awfuly hard to read the collideDot function, and when things are clearer your problems will probably jump out at you Smile

This is loosely based on some tutorial code I dug up. I'm rewriting it to use some temporary boolean variables instead of those crazy ifs.

But that is the algorithm I'm using.
Quote this message in a reply
Posts: 1,563
Joined: 2003.10
Post: #4
It looks like you're using a simple intersection test to check for collisions. For fast-moving and/or very small objects, this will not work reliably. Your moving object is probably passing completely through the wall between two of your collision checks, in which case an intersection test at both points would return false.

What you'll need to do is somehow take into account the movement of your object between the two positions at which you perform your collision tests. Since you're working with a sphere, one thing you could do is extrude it into a capped cylinder, and test intersection between the cylinder and the walls. Another option would be to do multiple intersection tests per frame, each one working with a small enough timeslice that the object doesn't move far enough to pass completely through the wall.

I sympathize with you, because this is a somewhat difficult problem... In my free time, I'm working on implementing something very similar. I may write a tutorial on it at some point if I'm successful.

My time-based animation tutorial may also be of some use to you:
Quote this message in a reply
Post: #5
What I've done to fix the go through walls is capped the ball's speed lower, and increased the refresh rate- it's still using one-frame-per-update, but the updates are going a lot faster, and the graphics aren't really heavy, and the ball just moves less distance per update. It balances out.

It still has a flaw where walls overlap- the solution that I'll implement in the near future- I'm going to make the walls not overlap. Ever.
Quote this message in a reply
Posts: 196
Joined: 2002.04
Post: #6
Here's some good links for collision detection:
This explains what A x + B y + C z + D = 0 is:
This explains how to find the exact point that it will be on the plane at the bottom of the page
To turn the plane into a square just use two more planes that intersect the first one. Then use A x + B y + C z + D on the intersecting planes to find if the point is within the square. This is a little more complex than you really need but it finds the exact place the point will pass through.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Elastic Collisions in Objective C Mattonaise 4 9,709 May 13, 2011 11:40 PM
Last Post: Lazer
  More Collisions Nick 7 6,716 Oct 12, 2004 08:41 AM
Last Post: Nick
  Avoiding Collisions DM6 4 5,455 Jul 31, 2004 11:31 AM
Last Post: FCCovett