Matching a chunk of procedurally generated world to a chunk of other world

Question

Have you read The Chronicles of Amber by Roger Zelazny?

Imagine yourself playing in 3rd person MMO game. You spawn in the world and start to wander around. After some time, when you think, that you've learned the map, you realize, that you are in a place, that you have never seen before. You go back to the last place you were sure you know and it is still there. But the rest of the world has changed and you didn't even notice how did it happen.

I've read about procedural world generation. I've read about Perlin noise and octaves, Simplex noise, Diamond-square algorithm, about simulation of tectonic plates and water erosion. I believe I have some vague understanding of general approach in procedural world generation.

And with this knowledge I have no idea on how can you do something like written above. Every idea that comes to my mind encounters some theoretical problems. Here are some ideas I can think of:

1) "Reversible" world-generation with a seed number as input and some fully-describing-a-chunk-number

I doubt that it is even possible, but I imagine a function, that will receive a seed and produce a matrix of numbers, upon which chunks are built. And for each unique number there is an unique chunk. And a second function, that gets this unique chunk number and produces a seed, that contains this number. I've tried to make a scheme in the picture below:

2) Making chunks completely random and make a transition between them.

As Aracthor suggested. The benefits of this approach is that it is possible and it doesn't require a magic fuction :)

The cons this approach has in my opinion, is that it's likely not possible to have a diverse world. If you have let's say both archipelago and a continent represented by just one number and it's adjacent chunks, then wouldn't the size of a chunk be equal to continent. And I doubt that it is possible to make good-looking transition between chunks. Am I missing something?

So, in other words, you are developing a MMO with procedurally generated world. But instead of having one world, you have many. What approach would you take to generate worlds and how would you implement transition of player from one world to another without player noticing the transition.

Anyway, I believe you've got the general idea. How would you have done it?

Answer 1

Use a slice of higher-order noise. If you used 2d noise for a height-map before, use 3D noise with the last coordinate fixed instead. Now you can slowly change the position in the last dimension to modify the terrain. Since Perlin noise is continuous in all dimensions, you'll get smooth transitions as long as you smoothly change the position where you sample the noise function.

If you want to only change the terrain far from the player, you could store the offset for every coordinate on the map and only increase but never decrease it. This way the map only gets newer but never older.

Also, take a look at Simplex noise. It's the improved version of Perlin noise and works better for more dimensions.

Answer 2

Your idea to split the world into several chunks is not bad. It is just incomplete.

The only problem is junctions between chunks. For instance, if you use perlin noise to generate relief, and a seed different for each chunk, and risk this to happen:

A solution would be to generate chunk relief not only from its Perlin noise seed, but as well from other chunks around it.

Perlin algorithm use values of random map around them to "smooth" themselves. If they use a common map, there would be smoothed together.

The only problem is if you change a chunk seed to make it different when the player recede, you'll have to reload chunks around too, because their borders should change as well.

This wouldn't change the size of chunks, but It would increase the minimal distance from the player to being loaded/unloaded, because a chunk must be loaded when the player see it, and, with this method, as adjacent chunks must be too.

UPDATE:

If each chunk of your world is of a different type, the problem grows up. This is not just about relief. An costly solution would be the following:

Let's suppose green chunks are forest worlds, blue ones archipelagos and yellow ones flat deserts.
The solution here is to create "transition" zones, where your relief and ground nature (as well as objects grounded, or anything else you want) would progressively turn from one type to another.

And as you can see on this picture, the hell part to code would be little squares in chunk corners: they have to make a link between 4 chunks, potentially different natures.

So for this complexity level, I think classic 2D-world generations like Perlin2D just cannot be used. I refer you to @danijar answer for that.

Answer 3

While danijar's idea is pretty solid, you could end up storing a lot of data, if you wanted to have the local area the same and the distance shift. And requesting more and more slices of more and more complex noise. You can get all of these in a more standard 2d fashion.

I developed an algorithm for procedurally generating random fractal noise, in part based on the diamond square algorithm that I fixed to be both infinite, and deterministic. So diamond-square can create an infinite landscape, as well as my own fairly blocky algorithm.

The idea is basically the same. But, rather than sampling higher dimensional noise, you can iterate values at different iterative levels.

So you still store the values you requested before, and cache them (this scheme independently could be used to speed up an already super-fast algorithm). And when new area is requested, it is created with a new y value. and any area not requested in that request is removed.

So rather than scoping through different space in an additional dimensions. We store an extra bit of monotonic data to mix in different (at progressively larger amounts at different levels).

If the user travels in a direction the values are moved accordingly (and at each level) and new values are generated at the new edges. If the top iterative seed is changed, the entire world will be drastically shifted. If the final iteration is given a different result, then the change amount will be very minor +-1 block or so. But, the hill will still be there and the valley etc, but the nooks and crannies will have changed. Unless you go far enough, and then the hill will be gone.

So if we stored 100x100 chunk of values each iteration. Then nothing could change at 100x100 from the player. But, at 200x200 things could change by 1 block. At 400x400 things could change by 2 blocks. At 800x800 away things will be able to change by 4 blocks. So things will change and they will change more and more the further you go. If you go back they will be different, if you go too far they will be completely changed and completely lost as all the seeds would be abandoned.

Adding a different dimension to provide this stabilizing effect, would certainly work, shifting the y at distance, but you'd be storing a lot of the data for a great many blocks when you shouldn't have to. In deterministic fractal noise algorithms you can get this same effect by adding a changing value (at a different amount) as the position moves beyond a certain point.

https://jsfiddle.net/rkdzau7o/

var SCALE_FACTOR = 2;
//The scale factor is kind of arbitrary, but the code is only consistent for 2 currently. Gives noise for other scale but not location proper.
var BLUR_EDGE = 2; //extra pixels are needed for the blur (3 - 1).
var buildbuffer = BLUR_EDGE + SCALE_FACTOR;

canvas = document.getElementById('canvas');
ctx = canvas.getContext("2d");
var stride = canvas.width + buildbuffer;
var colorvalues = new Array(stride * (canvas.height + buildbuffer));
var iterations = 7;
var xpos = 0;
var ypos = 0;
var singlecolor = true;


/**
 * Function adds all the required ints into the ints array.
 * Note that the scanline should not actually equal the width.
 * It should be larger as per the getRequiredDim function.
 *
 * @param iterations Number of iterations to perform.
 * @param ints       pixel array to be used to insert values. (Pass by reference)
 * @param stride     distance in the array to the next requestedY value.
 * @param x          requested X location.
 * @param y          requested Y location.
 * @param width      width of the image.
 * @param height     height of the image.
 */

function fieldOlsenNoise(iterations, ints, stride, x, y, width, height) {
  olsennoise(ints, stride, x, y, width, height, iterations); //Calls the main routine.
  //applyMask(ints, stride, width, height, 0xFF000000);
}

function applyMask(pixels, stride, width, height, mask) {
  var index;
  index = 0;
  for (var k = 0, n = height - 1; k <= n; k++, index += stride) {
    for (var j = 0, m = width - 1; j <= m; j++) {
      pixels[index + j] |= mask;
    }
  }
}

/**
 * Converts a dimension into the dimension required by the algorithm.
 * Due to the blurring, to get valid data the array must be slightly larger.
 * Due to the interpixel location at lowest levels it needs to be bigger by
 * the max value that can be. (SCALE_FACTOR)
 *
 * @param dim
 * @return
 */

function getRequiredDim(dim) {
  return dim + BLUR_EDGE + SCALE_FACTOR;
}

//Function inserts the values into the given ints array (pass by reference)
//The results will be within 0-255 assuming the requested iterations are 7.
function olsennoise(ints, stride, x_within_field, y_within_field, width, height, iteration) {
  if (iteration == 0) {
    //Base case. If we are at the bottom. Do not run the rest of the function. Return random values.
    clearValues(ints, stride, width, height); //base case needs zero, apply Noise will not eat garbage.
    applyNoise(ints, stride, x_within_field, y_within_field, width, height, iteration);
    return;
  }

  var x_remainder = x_within_field & 1; //Adjust the x_remainder so we know how much more into the pixel are.
  var y_remainder = y_within_field & 1; //Math.abs(y_within_field % SCALE_FACTOR) - Would be assumed for larger scalefactors.

  /*
  Pass the ints, and the stride for that set of ints.
  Recurse the call to the function moving the x_within_field forward if we actaully want half a pixel at the start.
  Same for the requestedY.
  The width should expanded by the x_remainder, and then half the size, with enough extra to store the extra ints from the blur.
  If the width is too long, it'll just run more stuff than it needs to.
  */

  olsennoise(ints, stride,
    (Math.floor((x_within_field + x_remainder) / SCALE_FACTOR)) - x_remainder,
    (Math.floor((y_within_field + y_remainder) / SCALE_FACTOR)) - y_remainder,
    (Math.floor((width + x_remainder) / SCALE_FACTOR)) + BLUR_EDGE,
    (Math.floor((height + y_remainder) / SCALE_FACTOR)) + BLUR_EDGE, iteration - 1);

  //This will scale the image from half the width and half the height. bounds.
  //The scale function assumes you have at least width/2 and height/2 good ints.
  //We requested those from olsennoise above, so we should have that.

  applyScaleShift(ints, stride, width + BLUR_EDGE, height + BLUR_EDGE, SCALE_FACTOR, x_remainder, y_remainder);

  //This applies the blur and uses the given bounds.
  //Since the blur loses two at the edge, this will result
  //in us having width requestedX height of good ints and required
  // width + blurEdge of good ints. height + blurEdge of good ints.
  applyBlur(ints, stride, width + BLUR_EDGE, height + BLUR_EDGE);

  //Applies noise to all the given ints. Does not require more or less than ints. Just offsets them all randomly.
  applyNoise(ints, stride, x_within_field, y_within_field, width, height, iteration);
}



function applyNoise(pixels, stride, x_within_field, y_within_field, width, height, iteration) {
  var bitmask = 0b00000001000000010000000100000001 << (7 - iteration);
  var index = 0;
  for (var k = 0, n = height - 1; k <= n; k++, index += stride) { //iterate the requestedY positions. Offsetting the index by stride each time.
    for (var j = 0, m = width - 1; j <= m; j++) { //iterate the requestedX positions through width.
      var current = index + j; // The current position of the pixel is the index which will have added stride each, requestedY iteration
      pixels[current] += hashrandom(j + x_within_field, k + y_within_field, iteration) & bitmask;
      //add on to this pixel the hash function with the set reduction.
      //It simply must scale down with the larger number of iterations.
    }
  }
}

function applyScaleShift(pixels, stride, width, height, factor, shiftX, shiftY) {
  var index = (height - 1) * stride; //We must iteration backwards to scale so index starts at last Y position.
  for (var k = 0, n = height - 1; k <= n; n--, index -= stride) { // we iterate the requestedY, removing stride from index.
    for (var j = 0, m = width - 1; j <= m; m--) { // iterate the requestedX positions from width to 0.
      var pos = index + m; //current position is the index (position of that scanline of Y) plus our current iteration in scale.
      var lower = (Math.floor((n + shiftY) / factor) * stride) + Math.floor((m + shiftX) / factor); //We find the position that is half that size. From where we scale them out.
      pixels[pos] = pixels[lower]; // Set the outer position to the inner position. Applying the scale.
    }
  }
}

function clearValues(pixels, stride, width, height) {
  var index;
  index = 0;
  for (var k = 0, n = height - 1; k <= n; k++, index += stride) { //iterate the requestedY values.
    for (var j = 0, m = width - 1; j <= m; j++) { //iterate the requestedX values.
      pixels[index + j] = 0; //clears those values.
    }
  }
}

//Applies the blur.
//loopunrolled box blur 3x3 in each color.
function applyBlur(pixels, stride, width, height) {
  var index = 0;
  var v0;
  var v1;
  var v2;

  var r;
  var g;
  var b;

  for (var j = 0; j < height; j++, index += stride) {
    for (var k = 0; k < width; k++) {
      var pos = index + k;

      v0 = pixels[pos];
      v1 = pixels[pos + 1];
      v2 = pixels[pos + 2];

      r = ((v0 >> 16) & 0xFF) + ((v1 >> 16) & 0xFF) + ((v2 >> 16) & 0xFF);
      g = ((v0 >> 8) & 0xFF) + ((v1 >> 8) & 0xFF) + ((v2 >> 8) & 0xFF);
      b = ((v0) & 0xFF) + ((v1) & 0xFF) + ((v2) & 0xFF);
      r = Math.floor(r / 3);
      g = Math.floor(g / 3);
      b = Math.floor(b / 3);
      pixels[pos] = r << 16 | g << 8 | b;
    }
  }
  index = 0;
  for (var j = 0; j < height; j++, index += stride) {
    for (var k = 0; k < width; k++) {
      var pos = index + k;
      v0 = pixels[pos];
      v1 = pixels[pos + stride];
      v2 = pixels[pos + (stride << 1)];

      r = ((v0 >> 16) & 0xFF) + ((v1 >> 16) & 0xFF) + ((v2 >> 16) & 0xFF);
      g = ((v0 >> 8) & 0xFF) + ((v1 >> 8) & 0xFF) + ((v2 >> 8) & 0xFF);
      b = ((v0) & 0xFF) + ((v1) & 0xFF) + ((v2) & 0xFF);
      r = Math.floor(r / 3);
      g = Math.floor(g / 3);
      b = Math.floor(b / 3);
      pixels[pos] = r << 16 | g << 8 | b;
    }
  }
}


function hashrandom(v0, v1, v2) {
  var hash = 0;
  hash ^= v0;
  hash = hashsingle(hash);
  hash ^= v1;
  hash = hashsingle(hash);
  hash ^= v2;
  hash = hashsingle(hash);
  return hash;
}

function hashsingle(v) {
  var hash = v;
  var h = hash;

  switch (hash & 3) {
    case 3:
      hash += h;
      hash ^= hash << 32;
      hash ^= h << 36;
      hash += hash >> 22;
      break;
    case 2:
      hash += h;
      hash ^= hash << 22;
      hash += hash >> 34;
      break;
    case 1:
      hash += h;
      hash ^= hash << 20;
      hash += hash >> 2;
  }
  hash ^= hash << 6;
  hash += hash >> 10;
  hash ^= hash << 8;
  hash += hash >> 34;
  hash ^= hash << 50;
  hash += hash >> 12;
  return hash;
}


//END, OLSEN NOSE.



//Nuts and bolts code.

function MoveMap(dx, dy) {
  xpos -= dx;
  ypos -= dy;
  drawMap();
}

function drawMap() {
  //int iterations, int[] ints, int stride, int x, int y, int width, int height
  console.log("Here.");
  fieldOlsenNoise(iterations, colorvalues, stride, xpos, ypos, canvas.width, canvas.height);
  var img = ctx.createImageData(canvas.width, canvas.height);

  for (var y = 0, h = canvas.height; y < h; y++) {
    for (var x = 0, w = canvas.width; x < w; x++) {
      var standardShade = colorvalues[(y * stride) + x];
      var pData = ((y * w) + x) * 4;
      if (singlecolor) {
        img.data[pData] = standardShade & 0xFF;
        img.data[pData + 1] = standardShade & 0xFF;
        img.data[pData + 2] = standardShade & 0xFF;
      } else {
        img.data[pData] = standardShade & 0xFF;
        img.data[pData + 1] = (standardShade >> 8) & 0xFF;
        img.data[pData + 2] = (standardShade >> 16) & 0xFF;
      }
      img.data[pData + 3] = 255;
    }
  }
  ctx.putImageData(img, 0, 0);
}

$("#update").click(function(e) {
  iterations = parseInt($("iterations").val());
  drawMap();
})
$("#colors").click(function(e) {
  singlecolor = !singlecolor;
  drawMap();
})

var m = this;
m.map = document.getElementById("canvas");
m.width = canvas.width;
m.height = canvas.height;

m.hoverCursor = "auto";
m.dragCursor = "url(data:image/vnd.microsoft.icon;base64,AAACAAEAICACAAcABQAwAQAAFgAAACgAAAAgAAAAQAAAAAEAAQAAAAAAAAEAAAAAAAAAAAAAAgAAAAAAAAAAAAAA////AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAD8AAAA/AAAAfwAAAP+AAAH/gAAB/8AAAH/AAAB/wAAA/0AAANsAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA//////////////////////////////////////////////////////////////////////////////////////gH///4B///8Af//+AD///AA///wAH//+AB///wAf//4AH//+AD///yT/////////////////////////////8=), default";
m.scrollTime = 300;

m.mousePosition = new Coordinate;
m.mouseLocations = [];
m.velocity = new Coordinate;
m.mouseDown = false;
m.timerId = -1;
m.timerCount = 0;

m.viewingBox = document.createElement("div");
m.viewingBox.style.cursor = m.hoverCursor;

m.map.parentNode.replaceChild(m.viewingBox, m.map);
m.viewingBox.appendChild(m.map);
m.viewingBox.style.overflow = "hidden";
m.viewingBox.style.width = m.width + "px";
m.viewingBox.style.height = m.height + "px";
m.viewingBox.style.position = "relative";
m.map.style.position = "absolute";

function AddListener(element, event, f) {
  if (element.attachEvent) {
    element["e" + event + f] = f;
    element[event + f] = function() {
      element["e" + event + f](window.event);
    };
    element.attachEvent("on" + event, element[event + f]);
  } else
    element.addEventListener(event, f, false);
}

function Coordinate(startX, startY) {
  this.x = startX;
  this.y = startY;
}

var MouseMove = function(b) {
  var e = b.clientX - m.mousePosition.x;
  var d = b.clientY - m.mousePosition.y;
  MoveMap(e, d);
  m.mousePosition.x = b.clientX;
  m.mousePosition.y = b.clientY;
};

/**
 * mousedown event handler
 */
AddListener(m.viewingBox, "mousedown", function(e) {
  m.viewingBox.style.cursor = m.dragCursor;

  // Save the current mouse position so we can later find how far the
  // mouse has moved in order to scroll that distance
  m.mousePosition.x = e.clientX;
  m.mousePosition.y = e.clientY;

  // Start paying attention to when the mouse moves
  AddListener(document, "mousemove", MouseMove);
  m.mouseDown = true;

  event.preventDefault ? event.preventDefault() : event.returnValue = false;
});

/**
 * mouseup event handler
 */
AddListener(document, "mouseup", function() {
  if (m.mouseDown) {
    var handler = MouseMove;
    if (document.detachEvent) {
      document.detachEvent("onmousemove", document["mousemove" + handler]);
      document["mousemove" + handler] = null;
    } else {
      document.removeEventListener("mousemove", handler, false);
    }

    m.mouseDown = false;

    if (m.mouseLocations.length > 0) {
      var clickCount = m.mouseLocations.length;
      m.velocity.x = (m.mouseLocations[clickCount - 1].x - m.mouseLocations[0].x) / clickCount;
      m.velocity.y = (m.mouseLocations[clickCount - 1].y - m.mouseLocations[0].y) / clickCount;
      m.mouseLocations.length = 0;
    }
  }

  m.viewingBox.style.cursor = m.hoverCursor;
});

drawMap();

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<canvas id="canvas" width="500" height="500">
</canvas>
<fieldset>
  <legend>Height Map Properties</legend>
  <input type="text" name="iterations" id="iterations">
  <label for="iterations">
    Iterations(7)
  </label>
  <label>
    <input type="checkbox" id="colors" />Rainbow</label>
</fieldset>