Random Terrain, Joints, Version Control

Terrain Development

I spent some time this week fooling around with my random terrain generator to try and come up with something more varied for driving. I will have to switch to hand-authored terrain soon but want to put it off as long as possible so I can focus on getting the vehicle to feel right.

The terrain generator produces a one-dimensional array of elevation values (since this is a 2D game). It puts in seed values at a large interval (every 256th element, currently), then subdivides by powers of two. The general idea is to subdivide and smooth (using a Loop-type subdivision scheme), then add random offsets which are scaled to the current step size. The subdivision smoothing is very simple: new points that fall halfway between the old points just get the average of their two adjacent old points. New points that fall on the old points get 1/8 of each of the two neighboring old points, plus 3/4 of the old point directly under them.

To make the terrain more interesting, I generate a second height map beforehand which I call the roughness map. When generating the actual height map, I scale the random offsets by the roughness value for that spot. This breaks the map up into smooth, rounded areas and rough, jagged areas.

Here's the code:

const int height_field_size = 1024;
static float height[height_field_size];
static float height_old[height_field_size];

void generate_height_field()
{
    int mask = height_field_size - 1;

    // Generate a height field that represents surface roughness.

    const int initial_roughness_step_size = 32;

    float roughness[height_field_size];
    float roughness_old[height_field_size];

    for (int i = 0; i < height_field_size; i += initial_roughness_step_size)
    {
        roughness[i] = frand();
    }

    for (int step_size = initial_roughness_step_size; step_size > 1; step_size /= 2)
    {
        memcpy(roughness_old, roughness, sizeof(roughness_old));

        for (int i = 0; i < height_field_size; i += step_size)
        {
            float h0 = roughness_old[(i + (height_field_size - step_size)) & mask];
            float h1 = roughness_old[i];
            float h2 = roughness_old[(i + step_size) & mask];

            float h1_new = h0 * 0.125f + h1 * 0.75f + h2 * 0.125f;
            float h3_new = h1 * 0.5f + h2 * 0.5f;

            roughness[i] = h1_new;
            roughness[i + step_size / 2] = h3_new;
        }
    }

    // Generate the actual height field, scaling the randomness by the
    // roughness at each point.

    const int initial_step_size = 256;

    for (int i = 0; i < height_field_size; i += initial_step_size)
    {
        height[i] = grand() * 20.0f;
    }

    for (int step_size = initial_step_size; step_size > 1; step_size /= 2)
    {
        memcpy(height_old, height, sizeof(height_old));

        float range = float(step_size) * 0.1f;

        for (int i = 0; i < height_field_size; i += step_size)
        {
            float h0 = height_old[(i + (height_field_size - step_size)) & mask];
            float h1 = height_old[i];
            float h2 = height_old[(i + step_size) & mask];

            float h1_new = h0 * 0.125f + h1 * 0.75f + h2 * 0.125f;
            float h3_new = h1 * 0.5f + h2 * 0.5f;

            h1_new += range * grand() * roughness[i];
            h3_new += range * grand() * roughness[i + step_size / 2];

            height[i] = h1_new;
            height[i + step_size / 2] = h3_new;
        }
    }
}

I've got an extremely simple random number generator right now since I don't care much about quality. frand() generates uniform values from 0 to 1, and grand() generates Gaussian (i.e. normal-distributed) random values with a mean of 0 and a standard deviation of 1:

float frand()
{
    return float(rand()) / float(RAND_MAX);
}

float grand()
{
    float x1, x2, w;

    do
    {
        x1 = 2.0f * frand() - 1.0f;
        x2 = 2.0f * frand() - 1.0f;
        w = x1 * x1 + x2 * x2;
    }
    while (w >= 1.0f);

    w = sqrtf((-2.0f * logf(w)) / w);

    float y1 = x1 * w;
//    float y2 = x2 * w;

    return y1;
}

The grand() algorithm actually generates two Gaussian random numbers per call; I'm being lazy and throwing out the second one.

I've done a lot of thinking about what kind of hand-authored terrain would work best. Currently I'm leaning toward a subdivision curve (like subdivision surfaces but in 2D). This is because it's easy to author rounded things, and you're not constrained to work at a particular scale. I've thought about a tiled landscape but I don't think that will give me the control I need to get surfaces that are fun to drive. Height fields can't handle overhangs or vertical cliffs; not horrible limitations, but I think I might like to have some cliffs.

Vehicle Development

Regarding the vehicle, I have been experimenting with different combinations of friction, elasticity, torque, and top speed. I am also writing a new joint type for the suspension since none of the joints provided with Chipmunk do exactly what I need. The new joint will constrain the wheel to move along a line segment relative to the vehicle chassis.

Version Control

In other news, the computer I've been using as my version control server died a horrible death. It's amazingly inconvenient. I've been using Perforce since in general it's awesome (albeit expensive for more than two users), but have been having second thoughts about my situation. Since I'm working from a laptop I spend a fair amount of time disconnected from the server, and with Perforce that means you can't check files out to work on them, or diff them to see what you've changed. I may switch to Subversion (since I have experience with that), or something else that is aimed at distributed development. I dislike having version-control-related files strewn about in my codebase, though. Subversion (like its older brother CVS) keeps entire duplicate directories of your source code, for diffing purposes. If it kept them off in some version-control directory I wouldn't mind but it keeps them as subdirectories of the real directories, so I have to wade around them in Explorer.