1
\$\begingroup\$

I am learning game design, and wanted to know how one can automatically generate spiky terrain (something like this: Cavernaut, notice, the terrain at the sides?). I have heard about midpoint displacement algorithm. But How can I apply that to my problem, given that I would also like to increase/decrease the randomness of the terrain.

Also, Is there any helpful library for this in libgdx?enter image description here

\$\endgroup\$
2
\$\begingroup\$

To generate a random terrain, i find the 'fractal'-ish approach the most effective.
Generate a first set of spikes, with a given amplitude and frequency, then add to this another set, having lesser amplitude and higher frequency, and iterate...
By choosing 'wisely' the frequency/amplitude/phase parameters you should get the terrain that you wish.

Find below a small example i copy-pasted from one of my project, it is not randomized but it's not that hard to randomize it. I might explain more if you're interested.

// Canvas setup
var cv = document.getElementById('cv');
var ctx = context = cv.getContext('2d');
var canvasWidth = cv.width,
  canvasHeight = cv.height;
var mountain = null;

window.onresize = resize;

resize();

function resize() {
    canvasWidth = cv.width = window.innerWidth;
    canvasHeight = cv.height = window.innerHeight;
    mountain = new Mountain(canvasHeight / 5, canvasHeight / 2, 600, canvasHeight);
  }
  //

var xo = 0,
  yo = 0;

function animate() {
  requestAnimationFrame(animate);
  // clear screen
  ctx.clearRect(0, 0, canvasWidth, canvasHeight);
  xo += 0.2;
  mountain.draw(xo, yo);
}

animate();

//
function Mountain(baseY, amplitude, basePeriod, yEnd) {
  this.mountainGradient = createGradient([0, 0, 0, amplitude], [
    0, '#FFF',
    0.12, '#EEE',
    0.26, '#DDD',
    0.4, '#BBB',
    1, '#555'
  ]);
  this.endGradient = createGradient([0, amplitude-1, 0, yEnd - baseY], [
    0, '#555',
    1, '#000'
  ]);
  this.baseY = baseY;
  this.amplitude = amplitude;
  amplitude /= (1 + 0.8 + 0.16 + 0.18);
  var mainMountain = buildTriangleFunc(basePeriod, amplitude, 280);
  var secMountain = buildTriangleFunc(basePeriod * 0.52341247, amplitude * 0.8, 230);
  var spikes = buildTriangleFunc(basePeriod * 0.083479532, amplitude * 0.16, 10);
  var spikes2 = buildTriangleFunc(basePeriod * 0.144797531, amplitude * 0.18, 10, 15);
  this.mountainFunction = function(x) {
    return (mainMountain(x) + secMountain(x) + spikes(x) + spikes2(x));
  }
  this.draw = function(xOffset, yOffset) {
    xOffset = xOffset || 0;
    yOffset = yOffset || 0;
    var xMargin = 30;
    var mountainFunction = this.mountainFunction;
    var step = 20;
    var x = 0;
    var xOR = xOffset % step;
    var xBase = xOffset - xOR;
    ctx.save();
    ctx.translate(-xOR, this.baseY + yOffset);
    ctx.beginPath();
    ctx.moveTo(0, mountainFunction(xBase + 0));
    for (; x < canvasWidth + 2 * step; x += step) {
      ctx.lineTo(x, mountainFunction(x + xBase));
    }
    x -= step;
    ctx.lineTo(x, this.amplitude);
    ctx.lineTo(0, this.amplitude);
    ctx.closePath();
    ctx.lineWidth = 5;
    ctx.strokeStyle = '#000';
    ctx.fillStyle = this.mountainGradient;
    ctx.stroke();
    ctx.fill();
    ctx.fillStyle = this.endGradient;
    ctx.fillRect(0, this.amplitude-1, canvasWidth + step, yEnd - baseY);
    ctx.restore();
  }
}

function createGradient(coords, stops) {
  var gd = ctx.createLinearGradient.apply(ctx, coords);
  for (var i = 0; i < stops.length; i += 2) {
    gd.addColorStop(stops[i], stops[i + 1]);
  }
  return gd;
}

function buildTriangleFunc(period, amp, phase) {
  var halfPeriod = period / 2;
  amp /= halfPeriod;
  phase = phase || 0;
  phase += period;
  return function(x) {
    x += phase;
    x = x % period;
    if (x > halfPeriod) x = period - x;
    return x * amp;
  }
}
<canvas id='cv'></canvas>

\$\endgroup\$
1
\$\begingroup\$

A good, though not particularly fast, algorithm for this is called "midpoint displacement."

In midpoint displacement, you start with a flat terrain, then find the midpoint between the edges and move the midpoint up or down by a random amount. You then repeat this process, taking the midpoints on either side of the previous midpoint, and move it up or down again, repeating until you have reached some maximum number of iterations. The problem with this approach is it scales very poorly, it's O(n^3), however it is easy to implement and understand.

It's important to play with the amount of jitter each midpoint is allowed at each step in the iteration. Early on you want larger swings, but as you get smaller and smaller segments in the higher iterations you probably want to have smaller swings. The amount that the midpoint is allowed to vary at each iteration controls how "spiky" the final product is.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I agree that midpoint displacement can solve the problem, but dispute your run time analysis. For each midpoint is determined using a fixed number of edge points (2 in the case of OP's problem), therefore the number of operations is linear with respect to the final number of points. \$\endgroup\$
    – Pikalek
    Feb 29 '16 at 18:27
  • 1
    \$\begingroup\$ +1 This is the way to do it. And really, don't worry - Pikalek is right - this is a fast algorithm, even in 3D. I'm not sure how you came to O(n^3)! \$\endgroup\$
    – Engineer
    Mar 11 '16 at 8:19
0
\$\begingroup\$

One (not very good way) would be to generate lots of random y coords, increase the x by, say, 50px every y coord and generate a polygon from that. Hard to explain but if you want I could do a picture.

\$\endgroup\$
1
  • \$\begingroup\$ Midpoint displacement does similar but in a much more controlled manner. \$\endgroup\$
    – Engineer
    Mar 11 '16 at 8:21

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.