Я пытаюсь создать бесконечную карту как таковую. Я делаю это на Python и не могу заставить библиотеки шума работать правильно (похоже, они никогда не находят мой VS2010, а делать это на необработанном Python было бы слишком медленно). Поэтому я пытаюсь использовать алгоритм Diamond-Square.
Можно ли каким-то образом сделать это технически бесконечным?
Если нет, должен ли я просто вернуться к попытке заставить работать одну из привязок шума Python?
Это можно сделать. Разделите свой ландшафт на «тайлы» и примените алгоритм смещения средней точки (как я предпочитаю его называть) внутри каждого тайла.
Каждая плитка должна быть достаточно большой, чтобы высота в одном углу существенно не зависела от высоты в другом. Таким образом, вы можете создавать и уничтожать плитки на лету, устанавливая высоту вновь появляющихся углов на независимое случайное значение.
Это значение (а также случайность внутри плитки) должно быть получено из позиции плитки, чтобы вы каждый раз получали одну и ту же плитку.
Последняя версия модуля шума (по адресу http://pypi.python.org/pypi/noise/1.0b3) упоминается, что он «устранил проблемы, возникающие при компиляции с помощью Visual C++ в Windows» — вы можете попробовать еще раз. У меня он устанавливается и работает правильно (Python 2.7.1, MinGW, Windows 7).
Если вы разместите плитки в сетке x,y и запустите генератор случайных чисел для каждой плитки, например random.seed((x,y)), то каждый раз, когда вы вернетесь в один и тот же участок мира, он будет воссоздавать один и тот же местность.
В алгоритме «ромб-квадрат» две стороны каждой плитки зависят от соседних плиток; однако зависимость не распространяется на всю плитку. Если вы позволите каждой плитке зависеть от плиток, предшествующих ей (т. е. сверху и слева), и напишете функцию create_fake_tile, которая предполагает, что все значения предыдущей плитки равны 0, вы получите «плохую» плитку, в которой правый столбец и нижняя часть row — это правильные значения, от которых зависит следующая плитка. Если вы рисуете каждый экран, начиная со строки и столбца плитки, предшествующих первой строке и столбцу на экране, то видимая часть вашего мира будет правильной.
Я решил алгоритм Diamond Squared для бесконечных ландшафтов. И на самом деле нашел этот вопрос, проявляя должную осмотрительность. да. Хотя приведенные здесь ответы в основном неверны, это вполне можно сделать. Концептуально вам нужно рассматривать каждую итерацию алгоритма как бесконечное поле, а базовый случай — как бесконечное поле совершенно случайных чисел. Таким образом, каждая итерация является версией предыдущей в квадрате алмаза.
И чтобы решить диапазон скажем плитки [100-200][100-200] на итерации 7, вам нужен весь блок вдвое меньшего размера (~ четверть размера h * w) на итерации 6 плюс одно дополнительное ребро на каждая сторона. Итак, если у вас есть функция, которая решает для данной плитки:
getTerrain(x0,y0,x1,y1,iteration)... вы можете решить это для этой плитки, если у вас есть [49,101][49,101] на итерации 6. Затем вы просто применяете ромб в квадрате везде, где можете, что не будет работать на края, но будет работать везде и предоставит вам ровно столько данных, сколько нужно для решения тайла [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).
Короче говоря, если у вас есть бесконечное поле для вашего базового случая, у вас действительно может быть бесконечное поле, итерации просто определяют, насколько смешаны ваши вещи. И если вы используете что-то детерминированное для псевдослучайного введенного смещения, у вас в значительной степени будет очень быстрый генератор бесконечного ландшафта.
и вот демонстрация этого в 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/
Вы можете щелкнуть и перетащить шум вокруг.
Можно ли применить смещение средней точки снизу вверх? Допустим, вы работаете с дискретной сеткой и хотите создать регион MxN. Получите весовую функцию w(i). Начните с применения случайного смещения с весом w(0) к каждой точке. Затем примените случайное смещение с весом w(1) к каждой другой точке и распространите смещение на промежуточные точки. Затем сделайте каждую четвертую точку с w (2), снова распространяя. Теперь вы можете создать сетку любого размера, не имея никаких исходных предположений о размере.
Если есть какое-то N, для которого w(i > N) = 0, то вы можете остановить генерацию, когда нажмете на нее — что очень важно, если вы хотите, чтобы генерация когда-либо прекращалась! Вероятно, вам нужна функция w, которая начинается с 1, увеличивается до некоторого значения, а затем падает до нуля; Увеличивающийся бит моделирует степенную неровность местности в масштабе до 100 км или около того, а убывающий бит моделирует тот факт, что целые планеты имеют более или менее сферическую форму. Если бы вы занимались Марсом, а не Землей, вы бы хотели, чтобы w(i) пошла дальше из-за выпуклости Фарсиды.
Теперь замените случайную функцию случайной, но детерминированной функцией координат точки (например, введите координаты в хэш SHA1). Теперь всякий раз, когда вы создаете определенную часть сетки, она будет выглядеть одинаково.
Вы должны быть в состоянии сделать ромбовидный квадрат примерно так же, как это; вам просто нужно чередовать форму смещения.
