3
\$\begingroup\$

Every level in my game needs to have a different mountain landscape background generated automatically (but the landscape must be the same for each level).

How could I generate such a landscape procedurally? Maybe fractals?

Note: I am using LibGDX and Java on Android

\$\endgroup\$
  • 1
    \$\begingroup\$ You're asking for a "side view" of a mountain landscape, right? \$\endgroup\$ – Josh Feb 5 '15 at 20:24
  • \$\begingroup\$ Yes, basically only the external outline \$\endgroup\$ – Randomize Feb 5 '15 at 21:04
3
\$\begingroup\$

About 15 years ago I was quite satisfied with this algorithm for my Scorched Earth clone in Quick Basic (my first proper game).

Generate the landscape from left to right, pixel-column by pixel-column. Start at a random height value between your desired minimum and maximum height and with a random steepness value which is a negative or positive value in horizontal-pixels per vertical-pixel.

When you create the next column, add the current steepness value to the current height. Then change steepness by a random value which can be equally positive or negative.

Both steepness and height should be clipped (when they exceed the maximum or minimum, set them back to it). When you want to avoid plateaus at the minimum and maximum height, multiply the current steepness with -1 whenever the height exceeds the minimum or maximum, because this will create an instant peak/valley.

The larger the maximum steepness, the steeper your mountains will be. The larger the change of the steepness per column, the more jagged your landscape will be.

To make it possible to reproduce the results, use a random number generator which allows you to set a seed value. When you initialize it with the same seed and use the same parameters, it will create the exact same landscape.

Edit: I recreated the algorithm in Javascript. You can run it yourself to see the results. Unfortunately the build-in Javascript random number generator doesn't allow to set a seed, so it will be different everytime you run it.

 // javascript graphics boilerplate
 var canvas = document.getElementById("canvas")
 var context = canvas.getContext("2d");
 
 // parameters - change to your liking
 var STEP_MAX = 2.5;
 var STEP_CHANGE = 1.0;
 var HEIGHT_MAX = canvas.height;

 // starting conditions
 var height = Math.random() * HEIGHT_MAX;
 var slope = (Math.random() * STEP_MAX) * 2 - STEP_MAX;

 // creating the landscape
 for (var x = 0; x < canvas.width; x++) {
      // change height and slope
      height += slope;
      slope += (Math.random() * STEP_CHANGE) * 2 - STEP_CHANGE;

      // clip height and slope to maximum
      if (slope > STEP_MAX) { slope = STEP_MAX };
      if (slope < -STEP_MAX) { slope = -STEP_MAX };
 
      if (height > HEIGHT_MAX) { 
          height = HEIGHT_MAX;
          slope *= -1;
      }
      if (height < 0) { 
          height = 0;
          slope *= -1;
      }
      
      // draw column
      context.beginPath();
      context.moveTo(x, HEIGHT_MAX);
      context.lineTo(x, height);
      context.stroke();
 }
<canvas id="canvas" width=640 height=170> </canvas>

\$\endgroup\$
  • 1
    \$\begingroup\$ Funny how I still remember an algorithm I wrote when I was in middle-school (although the original only used integer math). Also, now I want to go mountain hiking. \$\endgroup\$ – Philipp Feb 6 '15 at 0:36
  • \$\begingroup\$ Thanks for the nice answer but if I repeat the same logic, the level keeps on change as there is a random factor in it \$\endgroup\$ – Randomize Feb 6 '15 at 4:57
  • \$\begingroup\$ @Randomize, that's because (as Philipp has stated) javascript's PRNG, unlike most PRNGs doesn't accept a seed value. Given a specific seed value, a PRNG will always generate the same sequence of values (also as Philipp has stated). \$\endgroup\$ – XNargaHuntress Feb 6 '15 at 13:07
  • \$\begingroup\$ @Randomize This is a quirk specific to Javascript. You didn't say which technology you are using, so I considered a workaround for Javascript to be unlikely to be of much help to you because the default random number generators in most programming languages I have seen allow or even require to set a seed. But when you indeed want a Javascript solution, the stackoverflow question I already posted in my answer has some examples of simple PRNGs with seed in Javascript. \$\endgroup\$ – Philipp Feb 6 '15 at 23:25
0
\$\begingroup\$

The trick is to have an a algorithm that produce something that looks good, while depending on random value from a PRNG (pseudo-random number generator, like srand and rand). Then, just seed the generator with the level number and be sure to not use your random number generator for anything else than the terrain.

Also, be deterministic: don't depend on timing or user input and you'll be fine.

For example, you could separate your terrain into n sections, pick a random point x,y, making sure each is in the i'th of the n section. Then linearly interpolate between each 2 consecutive points in between, in k sub points. Offset each such sub-point by some limited distance.

Then, in a loop, to smooth, randomly pick 3 consecutive points, and move the middle one a bit closer to the center between the two others. This will remove any hard edges.

By adjusting the various settings, number of sections, number of sub point, offset percentage, etc..., you'll get different looks.

From there, you need to tweak for your use-case. Moon-lander ? Add flat spots. Star-Wars, add cave for huge worms, you get the picture...

Also remember that if generating the whole terrain is expensive, you can do it in parts. The level seed can be used to generated sub-seed for each level section. So, in level 4, you use seed 4 to get, say 100 sub-seed. In each 100 parts of level 4, you use one seed to generate the terrain locally. You can nest as deep as you want.

See code and sample results below.

enter image description here enter image description here

#include <iostream>
#include <stdlib.h>
#include <map>
#include <vector>

using namespace std;

const float WIDTH = 10000;
const float HEIGHT = 1000;
const float SHIFT = 200;
const int SECTIONS = 40;
const int SUB = 5;
const int SMOOTH_STEPS = 4000;



int main()
{
    int levelNumber = 42; //for example
    vector<float> xPos;
    vector<float> yPos;
    map<float,float> heights;

    srand(levelNumber);

    xPos.resize(SECTIONS * SUB);
    yPos.resize(SECTIONS * SUB);

    // random points, in a semi-regular fashion
    for(size_t i = 0; i < SECTIONS; i++)
    {
        xPos[i * SUB] = (rand() / (float)RAND_MAX) * (WIDTH / SECTIONS) + i * (WIDTH / SECTIONS);
        yPos[i * SUB] = (rand() / (float)RAND_MAX) * (HEIGHT);
    }

    // add points in between, letting them deviate only partly
    for(size_t i = 0; i < SECTIONS - 1; i++)
    for(size_t j = 1; j < SUB; j++)
    {
        float x = xPos[i * SUB] * (1 - (float)j/SUB) + xPos[(i + 1) * SUB] * ((float)j/SUB); // interpolate
        float y = yPos[i * SUB] * (1 - (float)j/SUB) + yPos[(i + 1) * SUB] * ((float)j/SUB);

       x += (rand() / (float)RAND_MAX) * SHIFT - SHIFT / 2;
       y += (rand() / (float)RAND_MAX) * SHIFT - SHIFT / 2;

       xPos[i * SUB + j] = x;
       yPos[i * SUB + j] = y;
    }

    // make smoother
    for(size_t i = 0; i < SMOOTH_STEPS; i++)
    {
        // pick a point not at an extremity
        size_t index = rand() % (SECTIONS * SUB - 2) + 1;

        float x0 = xPos[index - 1];
        float y0 = yPos[index - 1];
        float x1 = xPos[index];
        float y1 = yPos[index];
        float x2 = xPos[index + 1];
        float y2 = yPos[index + 1];
        xPos[index] = x0 * 0.05 + x2 * 0.05 + x1 * 0.90;
        yPos[index] = y0 * 0.05 + y2 * 0.05 + y1 * 0.90;
    }

    for(size_t i = 0 ; i < SECTIONS * SUB; i++)
    {
        cout << xPos[i] << " " << yPos[i] << endl;
    }
}
\$\endgroup\$
  • \$\begingroup\$ This answer could be drastically improved by actually providing an explanation of such an algorithm; you've effectively only answered half the question (relating to the determinism part). \$\endgroup\$ – Josh Feb 5 '15 at 20:32
  • \$\begingroup\$ Yeah, I plan on elaborating. But this is more involved. Roughly, divide the length you want into n sections. Pick a point in each section, with random height. That gives you a bunch of summits/valleys. In between, each, interpolate linearly in k sections and deviate each point upwards or downward of some % of the max height. Anyway, what look are you after ? Rolling hills, lunar landscape, mostly plains, Mars ? \$\endgroup\$ – Jeffrey Feb 5 '15 at 21:35
  • \$\begingroup\$ Thanks for the nice answer but if I repeat the code for the same level it will keep on change due to thecrandom factor. \$\endgroup\$ – Randomize Feb 6 '15 at 5:00
  • 1
    \$\begingroup\$ Hi, "keep changing" is untrue. "srand(levelNumber);" guarantees the same level will always have the same landscape. srand() resets the random-number-generator to a given state and from there, it behaves deterministically if you don't use it elsewhere. You can also use different random-number generator for different parts of your code if neeeded. \$\endgroup\$ – Jeffrey Feb 6 '15 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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