Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Bear with me as this will be a rather lengthy post. For the last month I have been working on an open source Cocos2D, Box2D Destructible Terrain Engine. I have some questions regarding its implementation.

TLDR-> When tracing images, how can I account for a divided image where there is a column or row of alpha separating the sprite? How can I leverage a dynamic programming (or something else) type approach to make this algorithm efficient.

Some Context: In the engine, destructible terrain sprites are created with MutableTextures which allow for direct manipulation of pixel values. An alpha value of zero is considered to be destroyed or non existent terrain.

Now in order to use these mutable texture sprites with Box2D, I need an efficient algorithm to trace the image and create a set of vertices which can be used to define the terrain border. From research, there where two ways I could go about this. I could create many, composite polygons (avoid concave angles) to fill the terrain or just trace the border with EdgeShapes. I opted for EdgeShapes.

-(void)makePhysicsObject:(b2World *)theWorld {
self.physicsObject = YES;
self->world = theWorld;
[self generatePhysicsPoints];

if (body) {
    world->DestroyBody(self->body);
} // end if

b2BodyDef tDef;

tDef.position.Set(0, 0);
self->body = world->CreateBody(&tDef);
gameObjectType = kGroundTypeDynamic;
self->body->SetUserData((__bridge void *) self);

b2EdgeShape shape;

CCLOG(@"Size of simplified before adding verts is %d", imageBorderPointsSimplified.count);
    for (int i =1; i < imageBorderPointsSimplified.count; i++) {
    NSValue * val = [imageBorderPointsSimplified objectAtIndex:i];
    CGPoint endPt = val.CGPointValue;
    NSValue * val2 = [imageBorderPointsSimplified objectAtIndex:i-1];
    CGPoint startPt = val2.CGPointValue;

    b2Vec2 startVert = b2Vec2(startPt.x/PTM_RATIO, startPt.y/PTM_RATIO);
    b2Vec2 endVert = b2Vec2(endPt.x/PTM_RATIO, endPt.y/PTM_RATIO);
    shape.Set(startVert, endVert);
    self->body->CreateFixture(&shape,0);

    if (i == imageBorderPointsSimplified.count - 1) {
        // Connect the end verts
        val = [imageBorderPointsSimplified objectAtIndex:i];
        endPt = val.CGPointValue;
        val2 = [imageBorderPointsSimplified objectAtIndex:0];
        startPt = val2.CGPointValue;
        b2Vec2 startVert = b2Vec2(startPt.x/PTM_RATIO, startPt.y/PTM_RATIO);
        b2Vec2 endVert = b2Vec2(endPt.x/PTM_RATIO, endPt.y/PTM_RATIO);
        shape.Set(startVert, endVert);
        self->body->CreateFixture(&shape,0);

    } // end inner if
} // end for
} // MakePhysics

This turned out to work fairly well and didn't kill the fps. However, what is hurting from a performance and algorithmic perspective, is retracing the image.

The algorithm for tracing the image is posted below where the final array called ImageBorderPointsSimplified contains a set of vertices which can be given to box2d to trace the sprite. On average it contains 15-25 points for a medium sized 800x800 terrain sprite.

-(BOOL)isBoundaryPoint:(CGPoint)pt {
BOOL isBoundary = NO; // assumption

// Is trans... so not boundary
if ([self pixelAt:pt].a == 0) {
    return isBoundary;
}

for (int i = -1; i < 2; i++) {
    for (int j = -1; j < 2; j++) {
        if ([self pixelAt:ccp(pt.x + i, pt.y + j)].a == 0) {
            isBoundary = YES;
            return isBoundary;
        }
    }
}
return isBoundary;
} // end isBoundaryPoint

isBoundaryPoint traverses pixels around a given pixel to see if there is a pixel with alpha = 0. If a pixel has an alpha of 0, then it must be a boundary pixel.

-(void)traceImage {
    // List of visited pixels
    imageBorderPoints = [[NSMutableSet alloc] init];
    // ALL Border points
    imageBorderPointsOrdered = [[NSMutableArray alloc] init];
    // Smoothed with averages
    imageBorderPointsSmoothed = [[NSMutableArray alloc] init];
    // Simplified based on curvature
    imageBorderPointsSimplified = [[NSMutableArray alloc] init];


static int avgCons = 4;
float originX = self.position.x - self.contentSize.width/2;
float originY = self.position.y - self.contentSize.height/2;
float endX = originX + self.contentSize.width;
float endY = originY + self.contentSize.height;
for (int x = originX; x < endX; x++) {
    for (int y = originY; y < endY; y++) {
        if ([self isBoundaryPoint:ccp(x,y)]) {
            CCLOG(@"First boundary point found at %d, %d", x,y);
            [self traverseBoundaryPoints:ccp(x,y)];
            if (imageBorderPointsOrdered.count > 19) {
                // Smooth the points
                for (int i = avgCons; i < imageBorderPointsOrdered.count; i = i + avgCons) {
                    NSMutableArray * tempStore = [[NSMutableArray alloc] init];
                    for (int x = i; x > i - avgCons; x--) {
                        [tempStore addObject:[imageBorderPointsOrdered objectAtIndex:x]];
                    }
                    NSValue * avgVal = [self averageVertices:tempStore];
                    //CCLOG(@"Adding %f, %f to averageArray", avgVal.CGPointValue.x, avgVal.CGPointValue.y);
                    [imageBorderPointsSmoothed addObject:avgVal];
                } // end for to pop avg
                [self simplifyVertices];
            } // end if
            return;
        } // end if
    } // end inner for
} // end outer for
CCLOG(@"MUTTEXTURE :: No boundary points found");
} // end traceImage

-(void)traverseBoundaryPoints:(CGPoint)startPt {

NSValue * startVal = [NSValue valueWithCGPoint:startPt];
[imageBorderPoints addObject:startVal];
NSValue * nextVal = [NSValue valueWithCGPoint:startVal.CGPointValue];
while (true) {

    nextVal = [self findNextBoundaryPixel:nextVal.CGPointValue];
    if (nextVal == nil) {
        CCLOG(@"nextVal is nil... returning");
        return;
    }

    if (CGPointEqualToPoint(startVal.CGPointValue, nextVal.CGPointValue)) {
        CCLOG(@"Start Point equals end point.. Exiting traverseBoundaryPoints");
        return;
    } else {
        [imageBorderPoints addObject:nextVal];
        [imageBorderPointsOrdered addObject:nextVal];
    }

}
}

traverseBoundary points (along with findNextBoundaryPixel) navigates itself around the image pixel by pixel. It stores the visited pixels in a set, and uses the set to check if it has visited there before. It will continue traversing until the start point equals the end point or there are no more pixels left to traverse. This algorithm is the issue tbh... It breaks apart when an image is split in two or there is a linear line of pixels. I could use some suggestions here.

-(NSValue *)findNextBoundaryPixel:(CGPoint)pt {

for (int i = -1; i < 2; i++) {
    for (int j = -1; j < 2; j++) {
        CGPoint ptToCheck = ccp(pt.x + i, pt.y + j);
        if ([self isBoundaryPoint:ptToCheck]) {
            NSValue * val = [NSValue valueWithCGPoint:ptToCheck];
            if ([imageBorderPoints containsObject:val]) {
                // CCLOG(@"imageBorderPoints already contains the border point");
            } else {
                //CCLOG(@"Next boundary found %f, %f", ptToCheck.x, ptToCheck.y);
                return val;
            } // end inner if
        } else {
            //CCLOG(@"Point is not a boundary point %f, %f", ptToCheck.x, ptToCheck.y);
        }
    }
}

return nil;
}


-(NSValue *)averageVertices:(NSMutableArray *)vertices {

CGPoint averagePt = ccp(0,0);
for (NSValue * val in vertices) {
    CGPoint pt = val.CGPointValue;
    averagePt = ccp(averagePt.x + pt.x, averagePt.y + pt.y);
}
averagePt = ccp(averagePt.x/vertices.count, averagePt.y/vertices.count);
NSValue * valToReturn = [NSValue valueWithCGPoint:averagePt];
return valToReturn;
}

findCurvature locates the midpoint between 2 points and compares that midpoint to a point in-between the two outer points. The distance between the midpoint and the middle point gives a measure of curvature. If there is high curvature, more vertices are needed to trace the image accurately. Simplify vertices reduces the amount of points needed to trace the image by looking at the curvature of a set of points. When the total curvature breaks the arbitrary threshhold, it will use the given point for the final trace.

-(float)findCurvature:(CGPoint)pt1 pt2:(CGPoint)pt2 pt3:(CGPoint)pt3 {
// If curv is high, then there is high curvature
// If it is low then there is low curvature
CGPoint mid = ccpMidpoint(pt3, pt1);
return ccpDistance(pt2, mid);
} // end findcurvature

-(void)simplifyVertices {
float lim = 0.5;
float curvature = 0;
float curvatureTotal = 0;
for (int i = 2; i < self->imageBorderPointsSmoothed.count; i++) {
    NSValue * v1 = [imageBorderPointsSmoothed objectAtIndex:i];
    CGPoint pt1 = v1.CGPointValue;
    NSValue * v2 = [imageBorderPointsSmoothed objectAtIndex:i-1];
    CGPoint pt2 = v2.CGPointValue;
    NSValue * v3 = [imageBorderPointsSmoothed objectAtIndex:i-2];
    CGPoint pt3 = v3.CGPointValue;

    curvature = [self findCurvature:pt1 pt2:pt2 pt3:pt3];
    curvatureTotal += curvature;

    if (curvatureTotal > lim) {
        curvatureTotal = 0;
        [imageBorderPointsSimplified addObject:[imageBorderPointsSmoothed objectAtIndex:i-2]];
    }
}

}

In general this is what is happening: Starting from a corner, it traverses the sprite's texture until it finds a non alpha pixel. It then will 'climb' around all the border pixels caching their location until it reaches the same point again. The array of pixels found are then smoothed (averaged) and reduced based on curvature. However, I am running into problems where if a player destroys the terrain to where it is split in half, only half of the image is traced. I can't think of a way to account for this and am asking for help here.

Also the other issue with my current algorithm, is it will become 'stuck' when there is a straight line of pixels as it won't visit already visited pixels again. When this happens the tracing is incomplete (albeit this is a rare edge case)

Lastly, performance... When a player destroys the terrain, I know exactly which columns of the texture are modified. What I would like to figure out is a way I can avoid retracing the unaffected columns and just retrace the altered columns.

Thanks for reading this long post. Any help would be very welcomed

EDIT Here is a video demonstrating the algorithms in action. At the end it of the video it incorrectly draws the edge of the terrain. This is one of the edge cases described above where there is a linear line of pixels. http://www.youtube.com/watch?v=IUsgjYLr6e0&feature=youtu.be

share|improve this question
    
Some visual examples could go a long way in breaking the ice for people to want to dig more into this question. Also summarizing the algorithms into written steps instead of code might help. –  Byte56 Jul 9 '13 at 0:07
1  
I inserted some short descriptions for the algorithms. Also, I posted a video –  Paul Renton Jul 9 '13 at 0:35
add comment

1 Answer

up vote 1 down vote accepted

I'd probably try to do something like the following:

  • Store all your vertices as well as the edges connecting them.

  • When an explosion happens, do the following:

    • Remove all vertices within the explosion radius.

    • Remove all edges within the explosion radius.

    • Flag all vertices with removed edges as "dirty".

  • After an explosion, iterate over all "dirty" vertices and use them as starting points to find shapes/borders till you return to your starting point or you're able to connect it to an existing open edge nearby.

share|improve this answer
    
The idea seems like the way to go, but what prevents me from going forward is dealing with an image that becomes separated by a column or row of alpha. –  Paul Renton Jul 9 '13 at 18:28
    
You mean your solid terrain is split into two halfs? or some pattern you can't detect properly? –  Mario Jul 10 '13 at 12:24
    
Yes exactly. The tracing algorithm I have will only trace one body. If they become split up, it will only trace the first one it finds. Where I am stumped is how to efficiently detect all isolated bodies on the texture. –  Paul Renton Jul 10 '13 at 16:04
    
Getting close to a solution. Will post an update by the weekend. I figured out how to detect all bodies, even if separated by a layer of alpha, and am in the process of implementing the bullets you listed. –  Paul Renton Jul 11 '13 at 5:48
    
Okay, just wanted to suggest that you could just use previous vertices (that are still intact) to start your outline search. At least that's been my initial idea here. –  Mario Jul 11 '13 at 8:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.