Object collision detection in game

[larswik]

So with the game I was building I was using this line of code to detect when 2 object collided which worked, kind of.

if (CGRectIntersectsRect(rock.frame, ship.frame))

I notices that it detected when 2 square frames collided even though the images I used were not square. For instance 2 balls colliding could trigger the if statement even though the actual balls never touched since they are round on a square frame from a CGRectMake();.So the edges of the frames colliding would trigger it.

In searching for a solution I discovered an idea that I adapted to my code. When the collision is detected I call a Class that I created and pass in the 2 objects as UIImageViews that should have collided. I create a new CGBitmapContextCreate and only get the Alpha which I assign to a 50% opacity. I combined both images to the new context.

Each image at 50% alpha opacity would give a pixel value of 127. But when the pixels over lapped that pixel level would increase to over 127 which would indicate a TRUE collision of the object. It is taxing on the system since it must iterate over each pixel but it works with no visual slow down in the game.

Here is the Method that does the job. The for loop was right from the original poster and I get what it is doing. But the part in read I am unsure of.

-(BOOL)checkAlphaCollision:(UIImageView*)ship withRock:(UIImageView*)rock{
    imageCollide = NO;
    int colorBits = 8;

    CGContextRef context = CGBitmapContextCreate(NULL, device_w, device_h, colorBits, 0, NULL, kCGImageAlphaOnly);

    CGRect rect;
    CGImageRef shipRef = ship.image.CGImage;
    CGImageRef rockRef = rock.image.CGImage;
    
    CGContextSetAlpha(context, 0); // create a rect and fill it with the dimensions of the screen.
    rect = CGRectMake(0, 0, device_w, device_h);
    CGContextFillRect(context, rect);
    
    CGContextSetAlpha(context, 0.5); //Adjust the alpha level to 50% and add the ship and rock
    rect = CGRectMake(ship.frame.origin.x, (460 - ship.frame.origin.y) - ship.frame.size.height, ship.frame.size.width, ship.frame.size.height);
    CGContextDrawImage(context, rect, shipRef);
    
    rect = CGRectMake(rock.frame.origin.x, (460 - rock.frame.origin.y) - rock.frame.size.height , rock.frame.size.width, rock.frame.size.height);
    CGContextDrawImage(context, rect, rockRef);
    
    unsigned char* data = CGBitmapContextGetData(context);
    //NSLog(@"%p",data);
    for (size_t i = 0; i<device_w*device_h; i++) {
        //NSLog(@"%d", (int)data[i]);
        if (data[i] > 128) {
            //NSLog(@"collidepoint %d",(int)data[i]);
            imageCollide = YES;
            break;
        }
    }
    return imageCollide;
}

It is an 'unsigned char'? A char only hold a character from what I remember in my pascal class, also why unsigned unless it is to hold more positive values? Also why char if it is holding int values like RGBA, why not an int array? 2. It described it as an array but I don't see the tell signs of the brackets [] like data[] when you declare a char array?

Can someone shed light on the char array line?

Thanks!

[ArtOfWarfare]

Feel free to correct me, anyone, if I'm wrong here, but I'm fairly certain that "real" games never use art assets to determine collisions. You approximate the shapes of all the objects and check if they collide. In a 3D game, you use a few big boxes and spheres, In 2D games you use a few circles or rectangles or lines.

I suspect that a few circles will work best for you, and they're the easiest way to check for collisions.

Just put a point at the center of each object. Assign it a radius. To see if it has collided with another object, do sqrt((x1-x2)^2+(y1-y2)^2)) and compare it against r1+r2. If r1+r2 is greater, they haven't collided, otherwise they have.

If your shape isn't a circle, approximate it with 2 or 3 circles.

[larswik]

Huh, I was not expecting that that kind of collision answer I started to read a game book today but thought I would see how far I got with my existing knowledge in programming.

Like in the little game I am making I have a little x-wing looking ship. I could see using a math equation to find the area of a ball or square would work. But something like an x-wing would be difficult to calculate collision with. You might be right, I don't know and I'm still not a math expert.

I think I will stop and just read the book and see how they handle it. I am guessing there is not just one way.

Thanks!

[ArtOfWarfare]

Looks like the best approximation of that is two rects, one horizontal and going from the back to the nose and one vertical going wingtip to wingtip.

The asteroids could then be circles.

But then you'd need to find a good, quick equation for finding if a circle intercepts a rect. I haven't done that before, but I'm sure if you google it you can find one.

Alternatively, just use three circles:
- 1 in the nose
- 1 in each wing

Size and position to cover the plane as best as possible.

And then you have just circles meaning you can use the equation I shared previously (it just uses Pythagorean's theorem to find the distance between the centers of two circles, and compares it against the sum of the two circle's radii.)

[mfram]

Since there was already a simple circle-collision algorithm discussed, then it would make sense to model the ship as a couple of circles. At the least you'd need 3 circles to model the ship. One for the main body and one for each wing. If you want more granular checking, you could probably model the main body as three circles. That pushes the whole ship to at least 5 circles.

Then you'd check the asteroid circles against all of the ship circles to check for collision with the ship. Increasing the number of ship circles would be more accurate, but slower to check.

[dejo]

larswik, pixel-by-pixel collision detection is rarely done because it causes the game engine to slow down too much. Therefore, optimizations are done. And for most games, such optimizations are sufficient to maintain satisfactory game-play while allowing usable responsiveness as well.

[larswik]

So build the ship out of circles. By circles I am as assuming that you mean a few CGRects where each of the rects (squares) is calculated with a circle's radii to detect collision.The rock is already round that would work.

I get that concept but it still seems to give you a ball park collision range. I roughed out a photo of the image, back boxes for CGRects and white circles that would simulate the calculation range based on circle radii to make sure I understood that concept.

Last night I refined the code to sample just the image area of the ship to check when there is an alpha collision instead of sampling the whole screen. I created a video to show what is happening. I created an RGBA output instead of the alpha only to better show it. http://www.larsapps.com/help/screenCollision.mov

When the collision occurs between 2 CGRect objects it triggers CGRectIntersectsRect. I then generate a frame and for the video, for example, it returns an RGBA to the view just to show what it is doing behind the scene (top left when CGRectIntersectsRect is TRUE.). By assigning both objects, rock and ship and combining them in a CGBitmapContextCreate with an alpha of 0.5 (127) it is easy to detect when you have a true collision because that value of the alpha will increase above 127 when a pixel from the rock overlaps a pixel from the ship.

The ship is 75 x 70 and working with just the alpha channel I am working with 75 * 70 * 1 (correct me if I am wrong) or 5250 pixels in an array to analyze if the value is greater then 127. To me this seems to be more accurate way to calculate true pixel collision of my graphics. But again, learning.

Thanks!

----------

Originally Posted by dejo

larswik, pixel-by-pixel collision detection is rarely done because it causes the game engine to slow down too much. Therefore, optimizations are done. And for most games, such optimizations are sufficient to maintain satisfactory game-play while allowing usable responsiveness as well.

We cross posted. I get that. I am wondering how much less the computer has to calculate collision using something like radii vs. pixel by pixel detection.

Thanks though. I got plenty of information and the book I am reading now. I find this fascinating and when I discover something and it works it is rewarding!

[dejo]

I can easily see using two CGRects to define the "collision area" of your ship, as illustrated in the attached image (which I blew up a bit for the sake of clarity). Wouldn't that be sufficient?

[mfram]

I'm not saying you build the ship out of circles, you can build the ship however you want. You just model it as circles for the purposes of collision detection. How many rocks are you going to have on your screen? Will they ever collide with one another?

The design is that you have an array of data structures which represents each item on the screen. If each item is modeled by a circle, then you are keeping a list of circles whose position gets updated every "tick" (however that works in your app).

Every "tick" or whatever, when you want to advance the rock, you first check to see if it will collide. If so, you a loop through each item and see if it will collide with your rock. If the ship is modeled by 3 circles, then that's an extra three checks.

So you are changing all of your pixel-by-pixel checks to a loop of circle comparisons. Presumably there are less circles to check than pixels. The bottleneck in the algorithm described above is the sqrt() operation which is relatively slow. You'll have to see how slow it really is. Depends on how many things you'll have on your screen.

[larswik]

Yes. But are those 2 boxes (CGRects) in addition to the ship CGRect? so I add my ship to a CGRect and then add these 2 boxes and keep them invisable and use them for collision detection? Or do I break my image (ship) in to 2 parts and ad them to 2 UIImageView?

[larswik]

The way I came up with adding rocks is with a random number generator with limitations so the screen is not over loaded with them. When a rock is added the UIImageView is given a tag number. That tag number is added to an NSMutableArray. At every tic it checks the rockArray for a count above 0. If so, it grabs the view using the tag number and gets the frame information. Then it updates the frame information with the new location and assigns it to the rock which drops it a couple of pixels on the rock.frame.origin.x; when the screen is redrawn.

If the rock is off the screen it then gets removed and that rockArray index is removed.

-(void)moveRockPostion{
    for (int i = 0; i < rockArray.count; i++) {
        int aNum = [[rockArray objectAtIndex:i]intValue];
        float moveAmount;
        
        if (score <= 10) { // adjusts the speed of the rock depending on score
            moveAmount = 2.0;
        }
        
        if (score > 10 && score <= 20) {
            moveAmount = 3.0;
        }
        if (score > 20 ) {
            moveAmount = 4.0;
        }

        UIImageView *rock = (UIImageView*) [self.view viewWithTag: aNum];
        
        CGRect oldFrame = rock.frame;
        if (oldFrame.origin.y > 480) {
            if (rock.alpha == 1.0) {
                rocksMissed += 1;
                missedRocks.text = [NSString stringWithFormat:@"%d", rocksMissed];
                if (rocksMissed >= 10) {
                    gameOver = YES;
                    [self killShip];
                    [self shipDisolve];
                    [self endGame];
                }
            }
            
            [rock removeFromSuperview];
            [rockArray removeObjectAtIndex:i];
            if (rockArray.count == 0) {
                tagRockNumber = 200; // reset the tag numbers if the count is 0;
            }
            NSLog(@"rock array: %d", rockArray.count);
        }
        else{
            CGRect newFrame = CGRectMake(oldFrame.origin.x, oldFrame.origin.y + moveAmount, oldFrame.size.width, oldFrame.size.height);
            rock.frame = newFrame;
        }
    }
}

[Menge]

Stop using the presentation framework (views) to do your logic and physics. The presentation framework should be the last step in your game pipeline, not base for something else.

Just know where those two rectangles are in relation to the ship's position and place them there logically (in the ship representation object, not the ship view) in order to calculate the collisions.

Dissociate:
- Game Logic
- Physics
- Graphics

Or else you'll always run into trouble.

[ArtOfWarfare]

Originally Posted by mfram

The bottleneck in the algorithm described above is the sqrt() operation which is relatively slow. You'll have to see how slow it really is. Depends on how many things you'll have on your screen.

Don't use sqrt(), then. Square both sides of the equation and the sqrt() goes away.

Edit: This doesn't cause an issue, does it? If one side were negative and the other wasn't... But that can't be the case. Both sides are positive lengths. Squaring both sides won't change the results of comparison operators.

[mfram]

Originally Posted by ArtOfWarfare

Don't use sqrt(), then. Square both sides of the equation and the sqrt() goes away.

*facepalm*

Um, I'm going to turn in my 'efficiency expert' badge now.

[Duncan C]

Originally Posted by ArtOfWarfare

Feel free to correct me, anyone, if I'm wrong here, but I'm fairly certain that "real" games never use art assets to determine collisions. You approximate the shapes of all the objects and check if they collide. In a 3D game, you use a few big boxes and spheres, In 2D games you use a few circles or rectangles or lines.

I suspect that a few circles will work best for you, and they're the easiest way to check for collisions.

Just put a point at the center of each object. Assign it a radius. To see if it has collided with another object, do sqrt((x1-x2)^2+(y1-y2)^2)) and compare it against r1+r2. If r1+r2 is greater, they haven't collided, otherwise they have.

If your shape isn't a circle, approximate it with 2 or 3 circles.

Actually, for game code, you skip the square root. (That's a transcendental, which is slow.) Instead, you precalculate the square of the distance, and you compare delta_x^2 + delta_y^2 against distance^2.

[samdev]

Originally Posted by larswik

Can someone shed light on the char array line?
Thanks!

I believe CGBitmapContextGetData() returns a pointer to a 32-bitmap in ARGB format.
Each pixel is 4 bytes.

unsigned char a = data[i+0];
unsigned char r = data[i+1];
unsigned char g = data[i+2];
unsigned char b = data[i+3];

This would be better:

for (size_t i=0; i < device_w*device_h; i++) {
   unsigned char a = data[ 4*i+0 ];
   unsigned char r = data[ 4*i+1 ];
   unsigned char g = data[ 4*i+2 ];
   unsigned char b = data[ 4*i+3 ];
}

But, of course, there are better and faster ways to deal with collision.

[larswik]

HA, yes there seems to be better ways to deal with it, collisions. My goal was to see what I could do with the knowledge that I have gained so far in programming. The game works so far but not as efficiently as it should I guess, lots to learn.

But your answer was at the heart of my original question. I understood everything but that part of the method. So the pointer returns an array with letters for r,g,b,a. I see that now with a char data type for the array.

But is it an array of arrays? So is each pixel value r,g,b,a stored in 1 index of the data[] array, as an array with those values, or is it stored as r,g,b,a,r,g,b,a,r.......? So the first 4 indexes of the array represent the values for 1 pixel and so on?

[samdev]

No, it's just raw byte data. You can call your variable names anything you want.

Indexing depends on the type of pointer you use. If you use a 1-byte pointer (char), then indexing is per byte.
If you use a 4-byte pointer, then you will index 4 bytes at a time. Basic C pointer stuff.

You can even define your own C structure called PIXEL, and use that to index the data, like:

typedef struct PIXEL {

 unsigned char a;
 unsigned char r;
 unsigned char g;
 unsigned char b;

} PIXEL;

PIXEL *data = (PIXEL *)CGBitmapContextGetData(context);
for (size_t i=0; i < device_w*device_h; i++) {

 PIXEL *pixel = data[i];
 // use pixel->a, pixel->r, pixel->g, pixel->b
}

CGBitmapContextGetData() returns a void pointer. You can cast it to any pointer you want.

You should Google for a tutorial on C pointers if you don't know this stuff already.

[larswik]

I did read up on points and addresses when I was reading c. But one thing I always for get is that you are holding pointers to memory locations and not the objects them self's, so I get that. But any time I defined an array in C it would have brackets var[]. I did not see any brackets when I was looking at that code which through me off.

But it is clear now that I can hold a pointer to something like a a struct and things.

Thanks!