Я решил алгоритм Diamond Squared для бесконечных пейзажей. И на самом деле нашел этот вопрос, делая мою должную осмотрительность. Да. Хотя ответы, представленные здесь, в основном неверны, это вполне можно сделать. Концептуально, что вам нужно сделать, это рассматривать каждую итерацию алгоритма как бесконечное поле, а базовый случай - как бесконечное поле из совершенно случайных чисел. Таким образом, каждая итерация является версией предыдущего ромба в квадрате.
И чтобы определить диапазон, скажем, плитки [100-200] [100-200] на итерации 7, вам нужен весь блок, равный половине этого размера (~ четверть размера h * w) на итерации 6 плюс один дополнительный край на каждой стороне. Так что если у вас есть функция, которая решает для данной плитки:
getTerrain (x0, y0, x1, y1, итерация) ... вы можете решить эту проблему для этой плитки, если у вас есть [49,101] [49,101] на итерации 6. Затем вы просто применяете алмаз в квадрате везде, где можете, что выиграло ' t работает на краях, но будет работать везде, и предоставит вам достаточно данных для решения для плитки [100-200] [100-200] на итерации 7.
Чтобы получить этот тайл на итерации 6, он будет запрашивать [23-52] [23-52] с итерации 5. И это будет продолжаться до тех пор, пока итерация 0 не даст вам [-1,3] [- 1,3], которая будет 16 совершенно случайных значений. Если вы запросили плитку настолько большого размера, что итерация 0 еще не достигла этого размера и позиции, вам просто понадобится другая полоска, которая подойдет, потому что вы все равно их составляете.
Таким образом вы полностью избавляетесь от шага заполнения, упрощаете алгоритм, делаете его бесконечным, заставляете его занимать разумный объем памяти. Использование детерминированного псевдослучайного числа, хэшированного из координат, позволит вам генерировать и регенерировать идентичные плитки на лету, потому что вы фактически сгенерировали верхние нижние итерации и просто сделали это целенаправленным образом.
Мой блог содержит больше информации,
http://godsnotwheregodsnot.blogspot.com/2013/11/field-diamond-squared-fractal-terrain.html
На самом деле большая часть сложности алгоритма обусловлена наличием в базовом случае четырех точек в цикле, поскольку это не близко к простейшему случаю. И, по всей видимости, большинству людей удалось избежать того, что вы могли бы даже упростить это, выполнив 1 пункт в цикле (хотя это все еще бессмысленно сложно). Или что-нибудь, что заставляет алгоритм, кажется, иметь по крайней мере 4x4 пункта. Вы можете даже начать с 4x4 точек итерации один раз, отбросить любую строку или столбец с неизвестным значением (все ребра), затем получить блок 5x5, затем блок 7x7, затем блок 11x11 ... (2n-3) x (2n -3). * +1014 *
Короче говоря, если у вас есть бесконечное поле для базового случая, вы можете иметь бесконечное поле, итерации просто определяют, насколько смешаны ваши вещи. И если вы используете что-то детерминированное для псевдослучайного смещения, вы в значительной степени получаете очень быстрый бесконечный генератор ландшафта.
и вот демонстрация этого в javascript,
http://tatarize.nfshost.com/FieldDiamondSquare.htm
Вот реализация в javascript. Это просто дает вам представление о правильном поле на этой итерации, позиции и размере. Вышеупомянутый связанный пример использует этот код в подвижном холсте. Он не хранит данных и пересчитывает каждый кадр.
function diamondSquaredMap(x, y, width, height, iterations) {
var map = fieldDiamondSquared(x, y, x+width, y+height, iterations);
var maxdeviation = getMaxDeviation(iterations);
for (var j = 0; j < width; j++) {
for (var k = 0; k < height; k++) {
map[j][k] = map[j][k] / maxdeviation;
}
}
return map;
function create2DArray(d1, d2) {
var x = new Array(d1),
i = 0,
j = 0;
for (i = 0; i < d1; i += 1) {
x[i] = new Array(d2);
}
return x;
}
function fieldDiamondSquared(x0, y0, x1, y1, iterations) {
if (x1 < x0) { return null; }
if (y1 < y0) { return null; }
var finalwidth = x1 - x0;
var finalheight = y1 - y0;
var finalmap = create2DArray(finalwidth, finalheight);
if (iterations === 0) {
for (var j = 0; j < finalwidth; j++) {
for (var k = 0; k < finalheight; k++) {
finalmap[j][k] = displace(iterations,x0+j,y0+k) ;
}
}
return finalmap;
}
var ux0 = Math.floor(x0 / 2) - 1;
var uy0 = Math.floor(y0 / 2) - 1;
var ux1 = Math.ceil(x1 / 2) + 1;
var uy1 = Math.ceil(y1 / 2) + 1;
var uppermap = fieldDiamondSquared(ux0, uy0, ux1, uy1, iterations-1);
var uw = ux1 - ux0;
var uh = uy1 - uy0;
var cx0 = ux0 * 2;
var cy0 = uy0 * 2;
var cw = uw*2-1;
var ch = uh*2-1;
var currentmap = create2DArray(cw,ch);
for (var j = 0; j < uw; j++) {
for (var k = 0; k < uh; k++) {
currentmap[j*2][k*2] = uppermap[j][k];
}
}
var xoff = x0 - cx0;
var yoff = y0 - cy0;
for (var j = 1; j < cw-1; j += 2) {
for (var k = 1; k < ch-1; k += 2) {
currentmap[j][k] = ((currentmap[j - 1][k - 1] + currentmap[j - 1][k + 1] + currentmap[j + 1][k - 1] + currentmap[j + 1][k + 1]) / 4) + displace(iterations,cx0+j,cy0+k);
}
}
for (var j = 1; j < cw-1; j += 2) {
for (var k = 2; k < ch-1; k += 2) {
currentmap[j][k] = ((currentmap[j - 1][k] + currentmap[j + 1][k] + currentmap[j][k - 1] + currentmap[j][k + 1]) / 4) + displace(iterations,cx0+j,cy0+k);
}
}
for (var j = 2; j < cw-1; j += 2) {
for (var k = 1; k < ch-1; k += 2) {
currentmap[j][k] = ((currentmap[j - 1][k] + currentmap[j + 1][k] + currentmap[j][k - 1] + currentmap[j][k + 1]) / 4) + displace(iterations,cx0+j,cy0+k);
}
}
for (var j = 0; j < finalwidth; j++) {
for (var k = 0; k < finalheight; k++) {
finalmap[j][k] = currentmap[j+xoff][k+yoff];
}
}
return finalmap;
}
// Random function to offset
function displace(iterations, x, y) {
return (((PRH(iterations,x,y) - 0.5)*2)) / (iterations+1);
}
function getMaxDeviation(iterations) {
var dev = 0.5 / (iterations+1);
if (iterations <= 0) return dev;
return getMaxDeviation(iterations-1) + dev;
}
//This function returns the same result for given values but should be somewhat random.
function PRH(iterations,x,y) {
var hash;
x &= 0xFFF;
y &= 0xFFF;
iterations &= 0xFF;
hash = (iterations << 24);
hash |= (y << 12);
hash |= x;
var rem = hash & 3;
var h = hash;
switch (rem) {
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 & 0xFFFF) / 0xFFFF;
}
};
Обновленный, чтобы добавить, я пошел от этого, и сделал мой собственный алгоритм шума, основанный здесь на том же самом алгоритме области действия, вот Jsfiddle для него.
https://jsfiddle.net/rkdzau7o/
Вы можете нажать и перетащить шум вокруг.