#527398 by Denis Defreyne (ddfreyne)

Theme:
#import <Alpaca/Model/ALMap_TerrainGeneration.h>

@implementation ALMap (TerrainGeneration)

- (void)equalizeHeightmap:(double **)aHeightmap
{
    // Calculate total weight
    double weight = 0.0;
    for(int x = 0; x < width; ++x)
        for(int y = 0; y < height; ++y)
            weight += aHeightmap[x][y];

    // Calculate shift
    double shift = weight/(width*height);

    // Shift map
    for(int x = 0; x < width; ++x)
        for(int y = 0; y < height; ++y)
            aHeightmap[x][y] -= shift;
}

- (void)smoothHeightmap:(double **)aHeightmap
{
    // Create blurred heightmap
    double **smoothedHeightmap = malloc(width*sizeof(double *));
    for(int x = 0; x < width; ++x)
        smoothedHeightmap[x] = malloc(height*sizeof(double));

    // Blur
    for(int x = 0; x < width; ++x)
    {
        for(int y = 0; y < height; ++y)
        {
            UInt8   count = 0;
            double  sum = 0;

            // TL
            if(x > 0 && y > 0)
            {
                ++count;
                sum += aHeightmap[x-1][y-1];
            }

            // TC
            if(y > 0)
            {
                ++count;
                sum += aHeightmap[x][y-1];
            }

            // TR
            if(x < width-1 && y > 0)
            {
                ++count;
                sum += aHeightmap[x+1][y-1];
            }

            // ML
            if(x > 0)
            {
                ++count;
                sum += aHeightmap[x-1][y];
            }

            // MC
            if(1)
            {
                ++count;
                sum += aHeightmap[x][y];
            }

            // MR
            if(x < width-1)
            {
                ++count;
                sum += aHeightmap[x+1][y];
            }

            // BL
            if(x > 0 && y < height-1)
            {
                ++count;
                sum += aHeightmap[x-1][y+1];
            }

            // BC
            if(y < height-1)
            {
                ++count;
                sum += aHeightmap[x][y+1];
            }

            // BR
            if(x < width-1 && y < height-1)
            {
                ++count;
                sum += aHeightmap[x+1][y+1];
            }

            // Calculate average
            smoothedHeightmap[x][y] = sum/(double)count;
        }
    }

    // Copy heightmap
    for(int x = 0; x < width; ++x)
        for(int y = 0; y < height; ++y)
            aHeightmap[x][y] = smoothedHeightmap[x][y];
}

- (double)randomNumberWithWeight:(double)aWeight
{
    return ((((double)random()) / (double)INT_MAX) - 0.5l) * aWeight;
}

- (void)randomizeHeightmapUsingSquares:(double **)aHeightmap
{
    UInt16  iterations = 1000;
    UInt8   maxSize = 100;
    double  weightModifier = 0.01;

    // Clear
    for(int x = 0; x < width; ++x)
        for(int y = 0; y < height; ++y)
            aHeightmap[x][y] = 0.0;

    for(int i = 0; i < iterations; ++i)
    {
        int randomX         = (int)((((double)random()) / (double)INT_MAX) * width);
        int randomY         = (int)((((double)random()) / (double)INT_MAX) * height);
        int randomSize      = (int)((((double)random()) / (double)INT_MAX) * maxSize);
        double randomWeight = weightModifier * (((((double)random()) / (double)INT_MAX) - 0.5l) * maxSize);

        for(int x = randomX - randomSize; x < randomX + randomSize; ++x)
        {
            if(x < 0)       continue;
            if(x >= width)  continue;

            for(int y = randomY - randomSize; y < randomY + randomSize; ++y)
            {
                if(y < 0)       continue;
                if(y >= height) continue;

                aHeightmap[x][y] += randomWeight * ((randomX + randomY) - (x + y));
            }
        }
    }
}

- (void)randomizeHeightmapUsingMPD:(double **)aHeightmap
{
    // Clear
    for(int x = 0; x < width; ++x)
        for(int y = 0; y < height; ++y)
            aHeightmap[x][y] = 0.0;

    // Set corner heights
    aHeightmap[0][0]                = ((((double)random()) / (double)INT_MAX) - 0.5l) * 300.0;
    aHeightmap[0][height-1]         = ((((double)random()) / (double)INT_MAX) - 0.5l) * 300.0;
    aHeightmap[width-1][0]          = ((((double)random()) / (double)INT_MAX) - 0.5l) * 300.0;
    aHeightmap[width-1][height-1]   = ((((double)random()) / (double)INT_MAX) - 0.5l) * 300.0;

    // Randomize
    [self randomizeHeightmapUsingMPD:aHeightmap from:MOMakePoint(0, 0) to:MOMakePoint(width-1, height-1)];
}

- (void)randomizeHeightmapUsingMPD:(double **)aHeightmap from:(MOPoint)aSrc to:(MOPoint)aDst
{
    [self randomizeHeightmapUsingMPD:aHeightmap from:aSrc to:aDst depth:0];
}

- (void)randomizeHeightmapUsingMPD:(double **)aHeightmap from:(MOPoint)aSrc to:(MOPoint)aDst depth:(UInt8)aDepth
{
    // Get relevant X coords
    UInt16 lX = aSrc.x;
    UInt16 mX = (aSrc.x + aDst.x)/2;
    UInt16 rX = aDst.x;

    // Get relevant Y coords
    UInt16 tY = aSrc.y;
    UInt16 mY = (aSrc.y + aDst.y)/2;
    UInt16 bY = aDst.y;

    // Get width/height
    UInt16 w = aDst.x - aSrc.x + 1;
    UInt16 h = aDst.y - aSrc.y + 1;

    // Configuration
    double weight = 300.0;

    // Get shortcut
    double **hm = aHeightmap;

    // Calculate center
    if(w >= 3 && h >= 3)
    {
        hm[mX][mY] = (hm[lX][tY] + hm[rX][tY] + hm[rX][bY] + hm[lX][bY])/4;
        hm[mX][mY] += [self randomNumberWithWeight:weight / (double)(1 + aDepth*aDepth)];
    }

    // Calculate edges
    if(w >= 3)
    {
        // top
        hm[mX][tY] = (hm[lX][tY] + hm[rX][tY])/2;
        hm[mX][tY] += ((((double)random()) / (double)INT_MAX) - 0.5l) * weight / (double)(1 + aDepth*aDepth);

        // bottom
        hm[mX][bY] = (hm[lX][bY] + hm[rX][bY])/2;
        hm[mX][bY] += ((((double)random()) / (double)INT_MAX) - 0.5l) * weight / (double)(1 + aDepth*aDepth);
    }
    if(h >= 3)
    {
        // right
        hm[rX][mY] = (hm[rX][tY] + hm[rX][bY])/2;
        hm[rX][mY] += ((((double)random()) / (double)INT_MAX) - 0.5l) * weight / (double)(1 + aDepth*aDepth);

        // left
        hm[lX][mY] = (hm[lX][tY] + hm[lX][bY])/2;
        hm[lX][mY] += ((((double)random()) / (double)INT_MAX) - 0.5l) * weight / (double)(1 + aDepth*aDepth);
    }

    // Divide and conquer
    if(w > 3 && h <= 3)
    {
        // Divide vertically
        [self randomizeHeightmapUsingMPD:hm from:MOMakePoint(lX, tY) to:MOMakePoint(mX, bY) depth:aDepth+1];
        [self randomizeHeightmapUsingMPD:hm from:MOMakePoint(mX, tY) to:MOMakePoint(rX, bY) depth:aDepth+1];
    }
    else if(w <= 3 && h > 3)
    {
        // Divide horizontally
        [self randomizeHeightmapUsingMPD:hm from:MOMakePoint(lX, tY) to:MOMakePoint(rX, mY) depth:aDepth+1];
        [self randomizeHeightmapUsingMPD:hm from:MOMakePoint(lX, mY) to:MOMakePoint(rX, bY) depth:aDepth+1];
    }
    else if(w > 3 && h > 3)
    {
        // Divide in four
        [self randomizeHeightmapUsingMPD:hm from:MOMakePoint(lX, tY) to:MOMakePoint(mX, mY) depth:aDepth+1];
        [self randomizeHeightmapUsingMPD:hm from:MOMakePoint(mX, tY) to:MOMakePoint(rX, mY) depth:aDepth+1];
        [self randomizeHeightmapUsingMPD:hm from:MOMakePoint(lX, mY) to:MOMakePoint(mX, bY) depth:aDepth+1];
        [self randomizeHeightmapUsingMPD:hm from:MOMakePoint(mX, mY) to:MOMakePoint(rX, bY) depth:aDepth+1];
    }
}

@end