terrain.h - a naive C implementation

terrain.h

#define NW 0
#define NE 1
#define SW 2
#define SE 3

#include <math.h>
#include <limits.h>
#include <stdlib.h>

#include <EXTERN.h>
#include <perl.h>


double
constrain(const double num)
{
    return   num < 0. ? 0.
           : num > 1. ? 1.
           : num;
}

double
displace(const double cur_size, const double full_size, const double roughness)
{
    const double max = cur_size / full_size * roughness;
    return ( (double)rand()/(double)INT_MAX - 0.5 ) * max;
}


void
subdivide(const double *corners,
          const double roughness,
          const unsigned int full_size,
          const unsigned int x,
          const unsigned int y,
          const unsigned int height,
          const unsigned int width,
          double **points)
{
    if ( height > 1 || width > 1 ) {
        double new_corners[4];
        const unsigned int new_height  = floor( (double)height / 2. );
        const unsigned int new_width = floor( (double)width / 2. );

        const double middle = constrain(
            (corners[0] + corners[1] + corners[2] + corners[3]) / 4.
            + displace(new_height + new_width, full_size, roughness)
        );

        const double edge_1 = constrain(0.5 * (corners[NW] + corners[NE]));
        const double edge_2 = constrain(0.5 * (corners[NE] + corners[SW]));
        const double edge_3 = constrain(0.5 * (corners[SW] + corners[SE]));
        const double edge_4 = constrain(0.5 * (corners[SE] + corners[NW]));

        /* do it again for each of the four new grids. */
        new_corners[0] = corners[NW];
        new_corners[1] = edge_1;
        new_corners[2] = middle;
        new_corners[3] = edge_4;
        subdivide(&new_corners[0], roughness, full_size, x, y, new_height, new_width, points);

        new_corners[0] = edge_1;
        new_corners[1] = corners[NE];
        new_corners[2] = edge_2;
        new_corners[3] = middle;
        subdivide(&new_corners[0], roughness, full_size, x + new_height, y,
                  height - new_height, new_width, points);

        new_corners[0] = middle;
        new_corners[1] = edge_2;
        new_corners[2] = corners[SW];
        new_corners[3] = edge_3;
        subdivide(&new_corners[0], roughness, full_size, x + new_height, y + new_width,
                  height - new_height, width - new_width, points);

        new_corners[0] = edge_4;
        new_corners[1] = middle;
        new_corners[2] = edge_3;
        new_corners[3] = corners[SE];
        subdivide(&new_corners[0], roughness, full_size, x, y + new_width,
                  new_height, width - new_width, points);
    }
    else /* this is the "base case," where each grid piece is less than the size of a pixel. */
    {
        /* the corners of the grid piece will be averaged and drawn as a single pixel. */
        const double c = (corners[0] + corners[1] + corners[2] + corners[3]) / 4.;

        points[x][y] = c;

        if (height == 2)
            points[ x + 1 ][y] = c;

        if (width == 2)
            points[x][ y + 1 ] = c;

        if (height == 2 && width == 2)
            points[ x + 1 ][ y + 1 ] = c;
    }

    return;
}


SV *
create_terrain(pTHX_ unsigned int height, unsigned int width, double roughness)
{
    /* $roughness ||= .5; */
    const unsigned int full_size = height + width;
    double corners[4];
    unsigned int i, j;
    double **points;
    AV *retval;

    /* seed the four corners of the grid with random color values */
    corners[0] = (double)rand()/(double)INT_MAX;
    corners[1] = (double)rand()/(double)INT_MAX;
    corners[2] = (double)rand()/(double)INT_MAX;
    corners[3] = (double)rand()/(double)INT_MAX;

    points = (double **)malloc(width * sizeof(double *));
    for (i = 0; i < width; ++i)
      points[i] = (double *)malloc(height * sizeof(double));

    subdivide(&corners[0], roughness, full_size, 0, 0, height, width, points);

    retval = newAV();
    av_extend(retval, width-1);
    for (i = 0; i < width; ++i) {
        const double *row = points[i];
        AV *iav = newAV();
        av_extend(iav, height-1);
        av_store(retval, i, newRV_noinc((SV *)iav));
        for (j = 0; j < height; ++j) {
            av_store(iav, j, newSVnv(row[j]));
        }
        free((void *)row);
    }
    free(points);

    return sv_2mortal(newRV((SV *)retval));
}

test.pl

#!/usr/bin/env perl
use 5.12.0;
use warnings;
use Data::Dumper;
use blib;

use XS::TCC qw(tcc_inline);

tcc_inline
  package => 'Terrain',
  q{
    #include "terrain.h"
    SV *create_terrain(pTHX_ unsigned int height, unsigned int width, double roughness);
    void srand(unsigned int seed);
  };

Terrain::srand(int(rand(2**31)));
print Dumper Terrain::create_terrain(500, 500, 0.5);