Combinando um pedaço do mundo gerado processualmente com um pedaço do outro mundo

18

Você leu The Chronicles of Amber de Roger Zelazny?

Imagine-se jogando no jogo MMO da terceira pessoa. Você cria no mundo e começa a passear. Depois de algum tempo, quando você pensa que aprendeu o mapa, percebe que está em um lugar que nunca viu antes. Você volta ao último lugar que tinha certeza de que conhece e ele ainda está lá. Mas o resto do mundo mudou e você nem percebeu como isso aconteceu.

Eu li sobre a geração processual mundial. Eu li sobre o ruído e as oitavas de Perlin, o ruído simplex, o algoritmo de diamante quadrado, sobre a simulação de placas tectônicas e a erosão hídrica. Acredito que tenho uma vaga compreensão da abordagem geral na geração processual mundial.

E com esse conhecimento, não tenho idéia de como você pode fazer algo como o escrito acima. Toda idéia que me vem à cabeça encontra alguns problemas teóricos. Aqui estão algumas idéias em que posso pensar:

1) Geração mundial "reversível" com um número inicial como entrada e algum número totalmente descritivo para um pedaço

Duvido que seja até possível, mas imagino uma função que receba uma semente e produza uma matriz de números sobre a qual os pedaços são construídos. E para cada número único, há um pedaço único. E uma segunda função, que obtém esse número de bloco exclusivo e produz uma semente, que contém esse número. Eu tentei fazer um esquema na imagem abaixo:

insira a descrição da imagem aqui

2) Tornar os pedaços completamente aleatórios e fazer uma transição entre eles.

Como Aracthor sugeriu. Os benefícios dessa abordagem é que é possível e não requer uma função mágica :)

Os contras que essa abordagem tem na minha opinião é que provavelmente não é possível ter um mundo diverso. Se você digitou o arquipélago e um continente representado por apenas um número e seus pedaços adjacentes, o tamanho de um pedaço não seria igual ao continente. E duvido que seja possível fazer uma transição bonita entre os pedaços. Estou esquecendo de algo?

Então, em outras palavras, você está desenvolvendo um MMO com o mundo gerado processualmente. Mas, em vez de ter um mundo, você tem muitos . Qual abordagem você adotaria para gerar mundos e como você implementaria a transição do jogador de um mundo para outro sem o jogador perceber a transição.

Enfim, acredito que você tenha uma ideia geral. Como você teria feito isso?

não-alcoólico
fonte
Então, eu tenho alguns problemas com as respostas aqui. @ Aracthor Eu já falei com você sobre variedades suaves antes, esse tipo de coisa se aplica aqui. No entanto, existem 2 respostas bastante elevado assim que eu estou querendo saber se há um ponto ...
Alec Teal
@AlecTeal se você tiver algo a acrescentar, faça. Eu ficaria feliz em ouvir quaisquer idéias e sugestões.
Netaholic 28/09/2015

Respostas:

23

Use uma fatia do ruído de ordem superior. Se você usou o ruído 2D em um mapa de altura antes, use o ruído 3D com a última coordenada fixa. Agora você pode alterar lentamente a posição na última dimensão para modificar o terreno. Como o ruído Perlin é contínuo em todas as dimensões, você obterá transições suaves, desde que altere suavemente a posição em que mostra a função de ruído.

Se você deseja alterar apenas o terreno longe da distância do jogador, como deslocamento, por exemplo. Você também pode armazenar o deslocamento para cada coordenada no mapa e apenas aumentar, mas nunca diminuí-lo. Dessa forma, o mapa só fica mais novo, mas nunca mais antigo.

Essa idéia também funciona se você já estiver usando ruído 3D, basta experimentar a partir de 4D. Além disso, dê uma olhada no ruído Simplex. É a versão aprimorada do ruído Perlin e funciona melhor em mais dimensões.

danijar
fonte
2
Isto é interessante. Entendi corretamente que você sugere gerar um ruído 3D, usar uma fatia xy em certos z como um mapa de altura e fazer uma transição suave para outra fatia alterando a coordenada z à medida que a distância do jogador aumenta?
Netaholic 28/09/2015
@netaholic Exatamente. Descrevê-lo como uma fatia é uma intuição muito boa. Além disso, você pode acompanhar o valor mais alto da última coordenada em qualquer lugar do mapa e apenas aumentá-lo, mas nunca diminuí-lo.
danijar 28/09/2015
11
Essa é uma ideia brilhante. Basicamente, seu mapa do terreno seria uma fatia parabólica (ou outra curva) através de um volume 3D.
Nome falso
Esta é uma ideia muito inteligente.
user253751
5

Sua idéia de dividir o mundo em vários pedaços não é ruim. É apenas incompleto.

O único problema são junções entre os pedaços. Por exemplo, se você usar ruído perlin para gerar alívio e uma semente diferente para cada pedaço, e arriscar que isso aconteça:

Bug de alívio de pedaço

Uma solução seria gerar alívio de partes não apenas a partir da sua semente de ruído Perlin, mas também de outras partes ao seu redor.

O algoritmo Perlin usa valores de mapa aleatório ao seu redor para "suavizar" a si mesmos. Se eles usassem um mapa comum, eles seriam suavizados.

O único problema é que se você alterar uma semente de pedaço para torná-lo diferente quando o jogador retroceder, será necessário recarregar os pedaços também, porque suas bordas também devem mudar.

Isso não mudaria o tamanho dos pedaços, mas aumentaria a distância mínima do jogador para ser carregado / descarregado, porque um pedaço deve ser carregado quando o jogador o vê e, com esse método, os pedaços adjacentes devem ser muito grandes. .

ATUALIZAR:

Se cada parte do seu mundo é de um tipo diferente, o problema aumenta. Não se trata apenas de alívio. Uma solução cara seria a seguinte:

Pedaços cortados

Vamos supor que pedaços verdes sejam mundos florestais, arquipélagos azuis e desertos planos amarelos.
A solução aqui é criar zonas de "transição", nas quais a natureza do relevo e do solo (assim como os objetos aterrados ou qualquer outra coisa que você queira) passaria progressivamente de um tipo para outro.

E como você pode ver nesta foto, a parte mais difícil de codificar seria pequenos quadrados nos cantos dos pedaços: eles precisam fazer um link entre quatro pedaços, naturezas potencialmente diferentes.

Portanto, para esse nível de complexidade, acho que as gerações clássicas do mundo 2D como o Perlin2D simplesmente não podem ser usadas. Refiro-lhe a resposta @danijar para isso.

Aracthor
fonte
Você sugere gerar "centro" de um pedaço de uma semente e suas bordas "suavizadas" com base em pedaços adjacentes? Faz sentido, mas aumentará o tamanho de um pedaço, já que deve ser o tamanho de uma área, que o jogador pode observar mais o dobro da largura de uma área de transição para pedaços adjacentes. E a área do pedaço se torna ainda maior, quanto mais diversificado o mundo é.
Netaholic 28/09/2015
@ netaholic Não seria maior, mas mais ou menos. Eu adicionei um parágrafo nele.
Aracthor 28/09/2015
Eu atualizei minha pergunta. Tentei descrever algumas idéias que eu tenho
netaholic
Portanto, a outra resposta aqui usa (mais ou menos) uma terceira dimensão como gráficos. Além disso, você também vê o avião como uma variedade, e eu gosto das suas idéias. Para estender um pouco mais, você realmente quer um coletor suave. Você precisa garantir que suas transições sejam suaves. Você pode aplicar um borrão ou ruído a isso e a resposta seria perfeita.
Alec Teal
0

Embora a ideia de danijar seja bastante sólida, você pode acabar armazenando muitos dados, se quiser ter a área local igual e a mudança de distância. E solicitando mais e mais fatias de ruído cada vez mais complexo. Você pode obter tudo isso de uma maneira 2D mais padrão.

eu desenvolvi um algoritmo para gerar procedimentalmente o ruído aleatório do fractal, em parte com base no algoritmo do quadrado do diamante que consertei para ser infinito e determinístico. Assim, o quadrado de diamante pode criar uma paisagem infinita, bem como meu próprio algoritmo bastante bloqueado.

A ideia é basicamente a mesma. Mas, em vez de amostrar um ruído dimensional mais alto, é possível iterar valores em diferentes níveis iterativos.

Portanto, você ainda armazena os valores solicitados anteriormente e os armazena em cache (esse esquema pode ser usado independentemente para acelerar um algoritmo já super-rápido). E quando uma nova área é solicitada, ela é criada com um novo valor y. e qualquer área não solicitada nessa solicitação é removida.

Então, em vez de procurar em diferentes espaços em dimensões adicionais. Armazenamos um pouco mais de dados monotônicos para misturar diferentes (em quantidades progressivamente maiores em diferentes níveis).

Se o usuário viaja em uma direção, os valores são movidos de acordo (e em cada nível) e novos valores são gerados nas novas arestas. Se a semente iterativa principal for alterada, o mundo inteiro será mudado drasticamente. Se a iteração final receber um resultado diferente, o valor da alteração será muito menor que o bloco + -1. Mas, a colina ainda estará lá e o vale etc., mas os cantos e recantos terão mudado. A menos que você vá longe o suficiente, e então a colina desaparecerá.

Portanto, se armazenarmos 100x100 partes de valores a cada iteração. Então, nada poderia mudar a 100x100 do player. Mas, em 200x200, as coisas podem mudar em 1 bloco. Em 400x400, as coisas podem mudar em 2 blocos. A 800x800 de distância, as coisas poderão mudar em 4 blocos. Então as coisas vão mudar e vão mudar cada vez mais à medida que você avança. Se você voltar, eles serão diferentes; se você for longe demais, eles serão completamente mudados e completamente perdidos, pois todas as sementes serão abandonadas.

Adicionar uma dimensão diferente para fornecer esse efeito estabilizador certamente funcionaria, mudando o y à distância, mas você armazenaria muitos dados para muitos blocos quando não deveria. Nos algoritmos determinísticos de ruído fractal, você pode obter esse mesmo efeito adicionando um valor variável (em uma quantidade diferente) à medida que a posição se move além de um determinado ponto.

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>

Tatarize
fonte