我正在尝试生成一个无限地图。我在 Python 中执行此操作，但无法让噪声库正常工作（它们似乎永远找不到我的 VS2010，并且在原始 Python 中执行此操作会太慢）。因此，我正在尝试使用Diamond-Square Algorithm。
是否有可能以某种方式使这在技术上无限？
如果没有，我是否应该回到尝试让 Python 噪声绑定之一工作？
问问题
5625 次
4 回答
1
这是可以做到的。将您的景观划分为“图块”，并在每个图块中应用中点置换算法（我更喜欢这样称呼它）。
每块瓷砖都必须足够大，这样一个角落的高度不会显着依赖于另一个角落的高度。这样，您可以动态创建和销毁图块，将新出现的角处的高度设置为独立的随机值。
该值（以及图块内的随机性）必须从图块的位置播种，以便您每次都获得相同的图块。
于 2011-02-12T13:41:01.930 回答
1
最新版本的噪声模块（位于http://pypi.python.org/pypi/noise/1.0b3）提到它“修复了在 Windows 上使用 Visual C++ 编译的问题”——您可能想再试一次。它为我安装并正常工作（Python 2.7.1、MinGW、Windows 7）。
如果你将你的瓦片排列在一个 x,y 网格中，并为每个瓦片生成随机数生成器，例如 random.seed((x,y))，那么每次你返回同一个世界补丁时，它都会重新创建相同的地形。
使用菱形正方形算法，每个图块的两侧依赖于相邻的图块；但是，依赖关系不会一直传播到整个图块。如果您让每个图块依赖于它前面的图块（即上方和左侧）并编写一个 create_fake_tile 函数，假设所有之前的图块值都是 0，那么您会得到一个“坏”图块，其中右列和底部row 是下一个图块所依赖的正确值。如果您从屏幕上第一行和第一列之前的磁贴行和列开始绘制每个屏幕，那么您的世界的可见部分将是正确的。
于 2011-02-22T00:38:23.023 回答
0
我解决了无限景观的 Diamond Squared 算法。
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;
map[j][k] = (map[j][k] + 1) / 2;
}
}
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;
}
};
//CANVAS CONTROL
window.onload = terrainGeneration;
function terrainGeneration() {
"use strict";
var mapDimension,
roughness,
iterations,
mapCanvas = document.getElementById('canvas');
var update = document.getElementById('update');
var xpos = 0;
var ypos = 0;
mapDimension = 512;
mapCanvas.width = mapDimension;
mapCanvas.height = mapDimension;
var updatefunction = function() {
var elIterations = document.getElementById('iterations');
iterations = parseInt(elIterations.value, 10);
iterations = iterations || 6;
MoveMap(10,0);
}
update.onclick = updatefunction;
updatefunction();
function MoveMap(dx, dy) {
xpos -= dx;
ypos -= dy;
var map = diamondSquaredMap(xpos, ypos, mapDimension, mapDimension, iterations);
drawMap(mapDimension, "canvas", map);
}
var m = this;
m.map = document.getElementById("canvas");
m.width = mapDimension;
m.height = mapDimension;
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 drawMap(size, canvasId, mapData) {
var canvas = document.getElementById(canvasId),
ctx = canvas.getContext("2d"),
x = 0,
y = 0,
colorFill,
img = ctx.createImageData(canvas.height, canvas.width);
for (x = 0; x < size; x++) {
for (y = 0; y < size; y++) {
colorFill = {r: 0, g: 0, b: 0};
var standardShade = Math.floor(mapData[x][y] * 250);
colorFill = {r: standardShade, g: standardShade, b: standardShade};
var pData = (x + (y * canvas.width)) * 4;
img.data[pData] = colorFill.r;
img.data[pData + 1] = colorFill.g;
img.data[pData + 2] = colorFill.b;
img.data[pData + 3] = 255;
}
}
ctx.putImageData(img, 0, 0);
}
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;
});
}<html><head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Canvas Terrain Generator</title>
<link rel="stylesheet" href="terrain.css" type="text/css">
<style type="text/css"></style><style type="text/css"></style></head>
<body>
Click and Pan.<br>
<div style="cursor: auto; overflow: hidden; width: 512px; height: 512px; position: relative;"><canvas id="canvas" width="512" height="512" style="position: absolute;"></canvas></div>
<br>
<form>
<fieldset>
<legend>Height Map Properties</legend>
<ol class="options">
<li>
<input type="text" name="iterations" id="iterations">
<label for="iterations">
Iterations(6)
</label>
</li>
</ol>
</fieldset>
<input type="button" value="Update" id="update">
</form>
</body></html>https://jsfiddle.net/Tatarize/1Lrj3s2v/3/ 单击并拖动 jsfiddle
并且实际上在尽职调查中发现了这个问题。是的。虽然这里提供的答案大多是错误的，但完全可以做到。从概念上讲，您需要做的是将算法的每次迭代视为无限域，将基本情况视为完美随机数的无限域。所以每次迭代都是前一次迭代的菱形平方版本。
并且要在迭代 7 中解决一系列说 tile [100-200][100-200] 的问题，您需要的是在迭代 6 中整个块的一半大小（〜大小 h*w 的四分之一）加上一个额外的边缘每一面。因此，如果您有一个解决给定图块的函数：
getTerrain(x0,y0,x1,y1,iteration)... 如果您在第 6 次迭代中有 [49,101][49,101] ，则可以为该图块解决此问题。然后您只需在任何可能的地方应用菱形平方，这将不起作用边缘，但可以在其他任何地方工作，并为您提供足够的数据来解决第 7 次迭代中的图块 [100-200][100-200]。
要在第 6 次迭代中获取该图块，它将从第 5 次迭代中请求 [23-52][23-52]。这将一直持续到第 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/
您可以单击并拖动噪音。
于 2013-11-09T16:32:36.410 回答
0
你能从下往上应用中点位移吗？假设您正在处理离散网格，并且想要生成 MxN 区域。给自己一个权重函数 w(i)。首先对每个点应用权重为 w(0) 的随机位移。然后将权重为 w(1) 的随机位移应用于每隔一个点，并将位移传播到中间点。然后用 w(2) 每第四个点做一次，再次传播。您现在可以生成任意大小的网格，而无需对大小进行任何初始假设。
如果有一些 N 的 w(i > N) = 0，那么当你击中它时你可以停止生成 - 如果你希望生成永远终止，这非常重要！您可能希望 aw 函数从 1 开始，增加到某个值，然后下降到零；增加的位模拟了高达 100 公里左右的地形的幂律粗糙度，而减少的位模拟了整个行星或多或少是球形的事实。如果你在火星而不是地球，你会希望 w(i) 走得更远，因为 Tharsis 凸起。
现在将随机函数替换为点坐标的随机但确定性函数（例如，将坐标输入 SHA1 哈希）。现在，每当您生成网格的某个特定部分时，它看起来都是一样的。
您应该能够以与此大致相同的方式进行菱形正方形；你只需要改变位移的形状。
于 2011-02-22T13:05:13.713 回答