One of my current endeavors is creating a 2D destructible terrain engine for iOS Cocos2D (See https://github.com/crebstar/PWNDestructibleTerrain ). It is in an infant stages no doubt, but I have made significant progress since starting a couple weeks ago. However, I have run into a bit of a performance road block with calculating surface normals.

Note: For my destructible terrain engine, an alpha of 0 is considered to not be solid ground. 

The method posted below works just great given small rectangles, such as n < 30. Anything above 30 causes a dip in the frame rate. If you approach 100x100 then you might as well read a book while the sprite attempts to traverse the terrain. At the moment this is the best I can come up with for altering the angle on a sprite as it roams across terrain (to get the angle for a sprite's orientation just take dot product of 100 * normal * (1,0) vector).

    -(CGPoint)getAverageSurfaceNormalAt:(CGPoint)pt withRect:(CGRect)area {

    float avgX = 0;
    float avgY = 0;
    ccColor4B color = ccc4(0, 0, 0, 0);
    CGPoint normal;
    float len;
    
    for (int w = area.size.width; w >= -area.size.width; w--) {
        for (int h = area.size.height; h >= -area.size.height; h--) {
            CGPoint pixPt = ccp(w + pt.x, h + pt.y);
            if ([self pixelAt:pixPt colorCache:&color]) {
                if (color.a != 0) {
                    avgX -= w;
                    avgY -= h;
                } // end inner if
            } // end outer if
        } // end inner for
    } // end outer for
    
    len = sqrtf(avgX * avgX + avgY * avgY);
    if (len == 0) {
        normal = ccp(avgX, avgY);
    } else {
        normal = ccp(avgX/len, avgY/len);
    } // end if
    
    return normal;
    } // end get


My problem is I have sprites that require larger rectangles in order for their movement to look realistic. I considered doing a cache of all surface normals, but this lead to issues of knowing when to recalculate the surface normals and these calculations also being quite expensive (also how large should the blocks be?). Another smaller issue is I don't know how to properly treat the case when length is = 0.

So I am stuck... Any advice from the community would be greatly appreciated! Is my method the best possible one? Or should I rethink the algorithm? I am new to game development and always looking to learn new tips and tricks.

**EDIT:** This is a re-work of the getSurfaceNormal function to implement the 2nd algorithm as specified by Nathan. I am putting it here for purposes of feedback and to hopefully show in code what Nathan is talking about.

    -(CGPoint)getSurfaceNormalAt:(CGPoint)pt withSquareWidth:(int)area {
    // This method only looks at surface pixels
    
    int avgX = 0;
    int avgY = 0;
    CGPoint normal;
    float len;
    ccColor4B color = ccc4(0, 0, 0, 0);
    
    for (int w = area; w >= -area; w--) {
        int h = area;
        do {
            if ([self pixelAt:ccp(w + pt.x, h + pt.y) colorCache:&color]) {
                if (color.a != 0) {
                    if (w < 0) {
                        avgX -= w;
                        avgY -= h;
                    } else {
                        avgX += w;
                        avgY += h;
                    }
                    break;
                } // end inner if
            } // end outer if
            h--;
        } while (h >= -area);
    } // end for
    int perpX = -avgY;
    int perpY = avgX;
    len = sqrtf(perpX * perpX + perpY * perpY);
    normal = ccp(perpX/len, perpY/len);

    return normal;
    }