Hacer coincidir una parte del mundo generado por procedimientos con una parte del otro mundo

18

¿Has leído Las crónicas de Amber de Roger Zelazny?

Imagínese jugando en un juego MMO en tercera persona. Engendras en el mundo y comienzas a deambular. Después de un tiempo, cuando piensas, que has aprendido el mapa, te das cuenta de que estás en un lugar, que nunca has visto antes. Regresas al último lugar que estabas seguro de conocer y todavía está allí. Pero el resto del mundo ha cambiado y ni siquiera te diste cuenta de cómo sucedió.

He leído sobre la generación procesal mundial. He leído sobre el ruido y las octavas de Perlin, el ruido Simplex, el algoritmo Diamond-square, sobre la simulación de placas tectónicas y la erosión hídrica. Creo que tengo una vaga comprensión del enfoque general en la generación procesal mundial.

Y con este conocimiento, no tengo idea de cómo puedes hacer algo como lo escrito anteriormente. Cada idea que se me ocurre encuentra algunos problemas teóricos. Aquí hay algunas ideas que se me ocurren:

1) Generación mundial "reversible" con un número de semilla como entrada y algún número que describe completamente un fragmento

Dudo que sea posible, pero imagino una función que recibirá una semilla y producirá una matriz de números, sobre la cual se construyen los fragmentos. Y para cada número único hay un fragmento único. Y una segunda función, que obtiene este número de fragmento único y produce una semilla, que contiene este número. Intenté hacer un esquema en la imagen a continuación:

ingrese la descripción de la imagen aquí

2) Hacer trozos completamente al azar y hacer una transición entre ellos.

Como sugirió Aracthor . Los beneficios de este enfoque es que es posible y no requiere una función mágica :)

Los inconvenientes que tiene este enfoque en mi opinión, es que probablemente no sea posible tener un mundo diverso. Si tiene, digamos, tanto el archipiélago como un continente representado por un solo número y son fragmentos adyacentes, entonces el tamaño de un fragmento no sería igual al continente. Y dudo que sea posible hacer una transición atractiva entre fragmentos. ¿Me estoy perdiendo de algo?

En otras palabras, estás desarrollando un MMO con un mundo generado por procedimientos. Pero en lugar de tener un mundo, tienes muchos . ¿Qué enfoque tomaría para generar mundos y cómo implementaría la transición del jugador de un mundo a otro sin que el jugador se dé cuenta de la transición?

De todos modos, creo que tienes la idea general. ¿Cómo lo habrías hecho?

netaholic
fuente
Entonces tengo algunos problemas con las respuestas aquí. @Aracthor Te he hablado sobre variedades suaves antes, ese tipo de aplica aquí. Sin embargo, hay 2 respuestas bastante altas, así que me pregunto si hay un punto ...
Alec Teal
@AlecTeal si tiene algo que agregar, por favor hágalo. Estaré encantado de escuchar cualquier idea y sugerencia.
netaholic

Respuestas:

23

Use una porción de ruido de orden superior. Si utilizó ruido 2D para un mapa de altura antes, utilice ruido 3D con la última coordenada fija en su lugar. Ahora puede cambiar lentamente la posición en la última dimensión para modificar el terreno. Dado que el ruido Perlin es continuo en todas las dimensiones, obtendrá transiciones suaves siempre que cambie suavemente la posición donde muestrea la función de ruido.

Si solo desea cambiar el terreno lejos de la distancia al jugador como compensación, por ejemplo. También puede almacenar el desplazamiento para cada coordenada en el mapa y solo aumentarlo pero nunca disminuirlo. De esta manera, el mapa solo se vuelve más nuevo pero nunca más antiguo.

Esta idea también funciona si ya está usando ruido 3D, solo muestree a partir de 4D. Además, eche un vistazo al ruido Simplex. Es la versión mejorada del ruido Perlin y funciona mejor para más dimensiones.

danijar
fuente
2
Esto es interesante. ¿Entiendo correctamente que sugieres generar un ruido 3D, usar un corte xy en cierta z como mapa de altura y hacer una transición suave a otro corte cambiando la coordenada z a medida que aumenta la distancia del jugador?
netaholic
@netaholic Exactamente. Describirlo como una porción es una muy buena intuición. Además, puede realizar un seguimiento del valor más alto para la última coordenada en todo el mapa y solo aumentarlo, pero nunca disminuirlo.
danijar
1
Esta es una idea brillante. Básicamente, su mapa de terreno sería un corte parabólico (u otra curva) a través de un volumen 3D.
Nombre falso
Esta es una idea realmente inteligente.
user253751
5

Tu idea de dividir el mundo en varios trozos no es mala. Es solo incompleto.

El único problema son las uniones entre trozos. Por ejemplo, si usa ruido de perlin para generar alivio y una semilla diferente para cada fragmento, y corre el riesgo de que esto suceda:

Error de alivio de trozos

Una solución sería generar un alivio del fragmento no solo de su semilla de ruido Perlin, sino también de otros fragmentos a su alrededor.

El algoritmo de Perlin utiliza valores de mapas aleatorios a su alrededor para "suavizarse". Si usan un mapa común, se suavizarían juntos.

El único problema es que si cambias una semilla de trozos para que sea diferente cuando el jugador retrocede, también tendrás que volver a cargar trozos, porque sus bordes también deberían cambiar.

Esto no cambiaría el tamaño de los fragmentos, pero aumentaría la distancia mínima desde el jugador hasta la carga / descarga, ya que un fragmento debe cargarse cuando el jugador lo ve y, con este método, los fragmentos adyacentes también deben estar cargados. .

ACTUALIZAR:

Si cada parte de tu mundo es de un tipo diferente, el problema crece. No se trata solo de alivio. Una solución costosa sería la siguiente:

Trozos cortados

Supongamos que los trozos verdes son mundos forestales, los azules archipiélagos y los amarillos desiertos planos.
La solución aquí es crear zonas de "transición", donde su relieve y la naturaleza terrestre (así como los objetos conectados a tierra o cualquier otra cosa que desee) cambien progresivamente de un tipo a otro.

Y como puede ver en esta imagen, la parte infernal del código serían pequeños cuadrados en las esquinas de los fragmentos: tienen que hacer un enlace entre 4 fragmentos, naturalezas potencialmente diferentes.

Entonces, para este nivel de complejidad, creo que las generaciones clásicas del mundo 2D como Perlin2D simplemente no se pueden usar. Me remito a la respuesta de @danijar para eso.

Aracthor
fuente
¿Sugiere generar el "centro" de un fragmento a partir de una semilla y sus bordes "suavizados" en base a los fragmentos adyacentes? Tiene sentido, pero aumentará el tamaño de un fragmento, ya que debe ser del tamaño de un área, que el jugador puede observar más el doble del ancho de un área de transición a fragmentos adyacentes. Y el área de trozos se vuelve aún más grande cuanto más diverso es el mundo.
netaholic
@netaholic No sería más grande, sino más o menos. Agregué un párrafo al respecto.
Aracthor
He actualizado mi pregunta. Intenté describir algunas ideas que tengo
netaholic
Entonces, la otra respuesta aquí usa (más o menos) una tercera dimensión como gráficos. También ves el avión como una variedad, y me gustan tus ideas. Para extenderlo un poco más, realmente quieres un colector suave. Debe asegurarse de que sus transiciones sean suaves. Entonces podría aplicar un desenfoque o ruido a esto y la respuesta sería perfecta.
Alec Teal
0

Si bien la idea de danijar es bastante sólida, podría terminar almacenando una gran cantidad de datos, si quisiera tener el área local igual y el cambio de distancia. Y solicitando más y más rebanadas de ruido cada vez más complejo. Puede obtener todo esto de una manera 2D más estándar.

Desarrollé un algoritmo para generar ruido fractal aleatorio de procedimiento, en parte basado en el algoritmo de diamante cuadrado que fijé para ser tanto infinito como determinista. Entonces, el diamante cuadrado puede crear un paisaje infinito, así como mi propio algoritmo bastante bloqueado.

La idea es básicamente la misma. Pero, en lugar de muestrear ruido dimensional superior, puede iterar valores en diferentes niveles iterativos.

Por lo tanto, aún almacena los valores que solicitó anteriormente y los almacena en caché (este esquema de forma independiente podría usarse para acelerar un algoritmo ya súper rápido). Y cuando se solicita una nueva área, se crea con un nuevo valor y. y cualquier área no solicitada en esa solicitud se elimina.

Entonces, en lugar de explorar diferentes espacios en dimensiones adicionales. Almacenamos un bit extra de datos monótonos para mezclar en diferentes (en cantidades progresivamente más grandes en diferentes niveles).

Si el usuario viaja en una dirección, los valores se mueven en consecuencia (y en cada nivel) y se generan nuevos valores en los nuevos bordes. Si se cambia la semilla iterativa superior, el mundo entero cambiará drásticamente. Si a la iteración final se le da un resultado diferente, entonces la cantidad de cambio será muy menor + -1 bloque más o menos. Pero, la colina todavía estará allí y el valle, etc., pero los rincones y grietas habrán cambiado. A menos que vayas lo suficientemente lejos, entonces la colina se habrá ido.

Entonces, si almacenamos una porción de valores de 100x100 en cada iteración. Entonces nada podría cambiar a 100x100 del jugador. Pero, a 200x200, las cosas podrían cambiar en 1 bloque. A 400x400 las cosas podrían cambiar en 2 bloques. A 800x800 de distancia, las cosas podrán cambiar en 4 bloques. Entonces las cosas cambiarán y cambiarán cada vez más a medida que avance. Si regresas, serán diferentes, si vas demasiado lejos, se cambiarán por completo y se perderán por completo, ya que se abandonarían todas las semillas.

Agregar una dimensión diferente para proporcionar este efecto estabilizador, sin duda funcionaría, cambiando la y a la distancia, pero estaría almacenando una gran cantidad de datos para una gran cantidad de bloques cuando no debería tener que hacerlo. En los algoritmos deterministas de ruido fractal, puede obtener este mismo efecto agregando un valor cambiante (en una cantidad diferente) a medida que la posición se mueve más allá de cierto punto.

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>

Tatarizar
fuente