How To Make A Game Like Fruit Ninja With Box2D and Cocos2D – Part 2

Splitting Polygons

Splitting the polygons may be the most complicated part of the tutorial, mostly because there are a lot of calculations to do, and a lot of Box2D rules to follow.

But don’t worry, this is probably the coolest part also, and I’ll walk you through it bit by bit!

Switch to HelloWorldLayer.h and make the following changes:

// Add to top of file
#define calculate_determinant_2x2(x1,y1,x2,y2) x1*y2-y1*x2
#define calculate_determinant_2x3(x1,y1,x2,y2,x3,y3) x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1

// Add after the properties
-(b2Vec2*)arrangeVertices:(b2Vec2*)vertices count:(int)count;
-(void)splitPolygonSprite:(PolygonSprite*)sprite;
-(BOOL)areVerticesAcceptable:(b2Vec2*)vertices count:(int)count;
-(b2Body*)createBodyWithPosition:(b2Vec2)position rotation:(float)rotation vertices:(b2Vec2*)vertices vertexCount:(int32)count density:(float)density friction:(float)friction restitution:(float)restitution;

Switch to HelloWorldLayer.mm and add this method:

-(void)splitPolygonSprite:(PolygonSprite*)sprite
{
    //declare & initialize variables to be used for later
    PolygonSprite *newSprite1, *newSprite2;
    
    //our original shape's attributes
    b2Fixture *originalFixture = sprite.body->GetFixtureList();
    b2PolygonShape *originalPolygon = (b2PolygonShape*)originalFixture->GetShape();
    int vertexCount = originalPolygon->GetVertexCount();
    
    //our determinant(to be described later) and iterator
    float determinant;
    int i;
    
    //you store the vertices of our two new sprites here
    b2Vec2 *sprite1Vertices = (b2Vec2*)calloc(24, sizeof(b2Vec2));
    b2Vec2 *sprite2Vertices = (b2Vec2*)calloc(24, sizeof(b2Vec2));
    b2Vec2 *sprite1VerticesSorted, *sprite2VerticesSorted;
    
    //you store how many vertices there are for each of the two new sprites here
    int sprite1VertexCount = 0;
    int sprite2VertexCount = 0;
    
    //step 1:
    //the entry and exit point of our cut are considered vertices of our two new shapes, so you add these before anything else
    sprite1Vertices[sprite1VertexCount++] = sprite.entryPoint;
    sprite1Vertices[sprite1VertexCount++] = sprite.exitPoint;
    sprite2Vertices[sprite2VertexCount++] = sprite.entryPoint;
    sprite2Vertices[sprite2VertexCount++] = sprite.exitPoint;
    
    //step 2:
    //iterate through all the vertices and add them to each sprite's shape
    for (i=0; i<vertexCount; i++)
    {
        //get our vertex from the polygon
        b2Vec2 point = originalPolygon->GetVertex(i);
        
        //you check if our point is not the same as our entry or exit point first
        b2Vec2 diffFromEntryPoint = point - sprite.entryPoint;
        b2Vec2 diffFromExitPoint = point - sprite.exitPoint;
        
        if ((diffFromEntryPoint.x == 0 && diffFromEntryPoint.y == 0) || (diffFromExitPoint.x == 0 && diffFromExitPoint.y == 0))
        {
        }
        else 
        {
            determinant = calculate_determinant_2x3(sprite.entryPoint.x, sprite.entryPoint.y, sprite.exitPoint.x, sprite.exitPoint.y, point.x, point.y);
            
            if (determinant > 0)
            {
                //if the determinant is positive, then the three points are in clockwise order
                sprite1Vertices[sprite1VertexCount++] = point;
            }
            else
            {
                //if the determinant is 0, the points are on the same line. if the determinant is negative, then they are in counter-clockwise order
                sprite2Vertices[sprite2VertexCount++] = point;
                
            }//endif
        }//endif
    }//endfor
    
    //step 3:
    //Box2D needs vertices to be arranged in counter-clockwise order so you reorder our points using a custom function
    sprite1VerticesSorted = [self arrangeVertices:sprite1Vertices count:sprite1VertexCount];
    sprite2VerticesSorted = [self arrangeVertices:sprite2Vertices count:sprite2VertexCount];
    
    //step 4:
    //Box2D has some restrictions with defining shapes, so you have to consider these. You only cut the shape if both shapes pass certain requirements from our function
    BOOL sprite1VerticesAcceptable = [self areVerticesAcceptable:sprite1VerticesSorted count:sprite1VertexCount];
    BOOL sprite2VerticesAcceptable = [self areVerticesAcceptable:sprite2VerticesSorted count:sprite2VertexCount];
    
    //step 5:
    //you destroy the old shape and create the new shapes and sprites
    if (sprite1VerticesAcceptable && sprite2VerticesAcceptable)
    {
        //create the first sprite's body        
        b2Body *body1 = [self createBodyWithPosition:sprite.body->GetPosition() rotation:sprite.body->GetAngle() vertices:sprite1VerticesSorted vertexCount:sprite1VertexCount density:originalFixture->GetDensity() friction:originalFixture->GetFriction() restitution:originalFixture->GetRestitution()];
        
        //create the first sprite
        
        newSprite1 = [PolygonSprite spriteWithTexture:sprite.texture body:body1 original:NO];
        [self addChild:newSprite1 z:1];
        
        //create the second sprite's body
        b2Body *body2 = [self createBodyWithPosition:sprite.body->GetPosition() rotation:sprite.body->GetAngle() vertices:sprite2VerticesSorted vertexCount:sprite2VertexCount density:originalFixture->GetDensity() friction:originalFixture->GetFriction() restitution:originalFixture->GetRestitution()];
        
        //create the second sprite
        newSprite2 = [PolygonSprite spriteWithTexture:sprite.texture body:body2 original:NO];
        [self addChild:newSprite2 z:1];
        
        //you don't need the old shape & sprite anymore so you either destroy it or squirrel it away
        if (sprite.original)
        {   
            [sprite deactivateCollisions];
            sprite.position = ccp(-256,-256);   //cast them faraway
            sprite.sliceEntered = NO;
            sprite.sliceExited = NO;
            sprite.entryPoint.SetZero();
            sprite.exitPoint.SetZero();
        }
        else 
        {
            world->DestroyBody(sprite.body);
            [self removeChild:sprite cleanup:YES];
        }
    }
    else
    {
        sprite.sliceEntered = NO;
        sprite.sliceExited = NO;
    }
    
    //free up our allocated vectors
    free(sprite1VerticesSorted);
    free(sprite2VerticesSorted);
    free(sprite1Vertices);
    free(sprite2Vertices);
}

Wow, that’s a lot to take in at once. Compile and make sure your syntax is correct, then let’s tackle this method step by step:

Preparation Step
Declares the variables. The most important thing here is that you declare two new PolygonSprites, and two arrays that will store their polygon’s vertices.

Step 1
You start populating the array of vertices for each shape by adding the intersection points to both arrays.

This makes sense when you visualize cutting a polygon:

The intersection points are present as vertices in both shapes.

Step 2
You assign the remaining vertices of the original shape. You know that the shape will always be cut into two parts, and the two new shapes will be on opposite sides of the cutting line.

You just need a rule to determine which shape each of the original polygon’s points should belong to.

Imagine you had a way to tell if any given three points were a clockwise rotation, or a counterclockwise rotation. If you had that, you could take the start point, end point, and one of the original points in the polygon and say:

“If these points are a clockwise rotation, add the original point to shape 2. Otherwise, add shape 1!”

Well good news – there’s a way to “determine” this, by using a mathematical concept called determinants!

In Geometry, determinants are “mathemagical” functions that can determine the direction a line takes to move from one point to another based on its resulting sign (positive, negative, or 0).

You use the determinant equation defined in HelloWorldLayer.h, and plug in the coordinates of our entry point, exit point, and each of the original vertices.

If the result is positive, then the 3 points are in clockwise order. If it is negative, then the 3 points are in counter-clockwise order. If the result happens to be 0, then the 3 points are on the same line.

You add all points clockwise to the first sprite, and the rest to the second sprite.

Step 3
Box2D expects vertices to be arranged in a counter-clockwise order, so you rearrange the vertices for the two new sprites using the arrangeVertices method.

Step 4
This makes sure that the arranged vertices adhere to all of Box2D’s rules on defining polygons. If the areVerticesAcceptable method decides that the vertices are unacceptable, then it removes the slice information from the original sprite.

Step 5
This initializes two new PolygonSprites and creates their Box2D body using the createBody method. The new sprites inherit properties from the original sprite.

If an original sprite is cut, it is reset and stored away. If a piece is cut, then it is destroyed and removed from the scene.

Whew…still with me? Good. There’s just a few more things to add before you run the program!

Still in HelloWorldLayer.mm, make the following changes:

// Add before the @implementation
int comparator(const void *a, const void *b) {
    const b2Vec2 *va = (const b2Vec2 *)a;
    const b2Vec2 *vb = (const b2Vec2 *)b;
    
    if (va->x > vb->x) {
        return 1;
    } else if (va->x < vb->x) {
        return -1;
    }
    return 0;    
}

// Add these methods
-(b2Body*)createBodyWithPosition:(b2Vec2)position rotation:(float)rotation vertices:(b2Vec2*)vertices vertexCount:(int32)count density:(float)density friction:(float)friction restitution:(float)restitution
{
    b2BodyDef bodyDef;
    bodyDef.type = b2_dynamicBody;
    bodyDef.position = position;
    bodyDef.angle = rotation;
    b2Body *body = world->CreateBody(&bodyDef);
    
    b2FixtureDef fixtureDef;
    fixtureDef.density = density;
    fixtureDef.friction = friction;
    fixtureDef.restitution = restitution;
    
    b2PolygonShape shape;
    shape.Set(vertices, count);
    fixtureDef.shape = &shape;
    body->CreateFixture(&fixtureDef);
    
    return body;
}

-(b2Vec2*)arrangeVertices:(b2Vec2*)vertices count:(int)count
{
    float determinant;
    int iCounterClockWise = 1;
    int iClockWise = count - 1;
    int i;
    
    b2Vec2 referencePointA,referencePointB;
    b2Vec2 *sortedVertices = (b2Vec2*)calloc(count, sizeof(b2Vec2));
    
    //sort all vertices in ascending order according to their x-coordinate so you can get two points of a line
    qsort(vertices, count, sizeof(b2Vec2), comparator);
    
    sortedVertices[0] = vertices[0];
    referencePointA = vertices[0];          //leftmost point
    referencePointB = vertices[count-1];    //rightmost point
    
    //you arrange the points by filling our vertices in both clockwise and counter-clockwise directions using the determinant function
    for (i=1;i<count-1;i++)
    {
        determinant = calculate_determinant_2x3(referencePointA.x, referencePointA.y, referencePointB.x, referencePointB.y, vertices[i].x, vertices[i].y);
        if (determinant<0)
        {
            sortedVertices[iCounterClockWise++] = vertices[i];
        }
        else 
        {
            sortedVertices[iClockWise--] = vertices[i];
        }//endif
    }//endif
    
    sortedVertices[iCounterClockWise] = vertices[count-1];
    return sortedVertices;
}

-(BOOL)areVerticesAcceptable:(b2Vec2*)vertices count:(int)count
{
    return YES;
}

Here is a breakdown of the methods you just created:

• createBody: This creates active Box2D bodies that can instantly collide with one another.
• arrangeVertices: This arranges vertices in a counter-clockwise order. It uses a qsort function to arrange them in ascending order according to x-coordinates, then uses determinants to make the final arrangement.
• comparator: This is the function used by qsort. It does the comparison and gives the result to qsort.
• areVerticesAcceptable: For now, it assumes all vertices are acceptable.

That's it! In theory, you can now split a polygon into two pieces. But wait..it would help to use the methods you just created! :]

Still in HelloWorldLayer.mm, add these changes:

// Add this method
-(void)checkAndSliceObjects
{
    double curTime = CACurrentMediaTime();
    for (b2Body* b = world->GetBodyList(); b; b = b->GetNext())
    {
        if (b->GetUserData() != NULL) {
            PolygonSprite *sprite = (PolygonSprite*)b->GetUserData();
            
            if (sprite.sliceEntered && curTime > sprite.sliceEntryTime) 
            {
                sprite.sliceEntered = NO;
            }
            else if (sprite.sliceEntered && sprite.sliceExited)
            {
                [self splitPolygonSprite:sprite];
            }
        }
    }
}

// Add this in the update method
[self checkAndSliceObjects];

Compile and run, and try cutting your Watermelon.

Wait for it...

It works! Who knew Math could cut fruits!

Note: Don't worry if the game suddenly crashes. It will be fixed once you implement the areVerticesAcceptable method.