让菱形方形分形算法变得无穷大

Question

我正在尝试生成一个无限的地图。我在 Python 中执行此操作，但无法让噪声库正常工作（它们似乎从未找到我的 VS2010，并且在原始 Python 中执行此操作会太慢）。因此，我尝试使用 Diamond-Square 算法。

是否有可能以某种方式使其在技术上无限？

如果没有，我是否应该返回尝试让 Python 噪声绑定之一正常工作？

Answer 1

这是可以做到的。将您的景观划分为“图块”，并在每个图块中应用中点位移算法（我更喜欢这样称呼它）。

每块瓷砖必须足够大，以便一个角的高度不会明显依赖于另一个角的高度。通过这种方式，您可以动态创建和销毁图块，将新出现的角点的高度设置为独立的随机值。

该值（以及图块内的随机性）必须从图块的位置播种，以便您每次都获得相同的图块。

Answer 2

最新版本的噪声模块（位于 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 是下一个图块所依赖的正确值。如果您从屏幕上第一行和第一列之前的平铺行和列开始绘制每个屏幕，那么您的世界的可见部分将是正确的。

Answer 3

你能从下往上应用中点位移吗？假设您正在处理离散网格，并且想要生成 MxN 区域。给自己一个加权函数 w(i)。首先对每个点应用权重为 w(0) 的随机位移。然后将权重为 w(1) 的随机位移应用于每隔一个点，并将位移传播到中间点。然后用 w(2) 做每第四个点，再次传播。您现在可以生成任意大小的网格，而无需对大小进行任何初始假设。

如果有某个 N 的 w(i > N) = 0，那么您可以在达到它时停止生成 - 如果您希望生成终止，这一点相当重要！您可能想要 aw 函数从 1 开始，增加到某个值，然后下降到零；递增的位模拟了高达 100 公里左右尺度的地形的幂律粗糙度，而递减的位则模拟了整个行星或多或少是球形的事实。如果你在火星而不是地球上进行拍摄，你会希望 w(i) 走得更远，因为塔尔西斯凸起。

现在，将随机函数替换为看似随机但具有确定性的点坐标函数（例如，将坐标输入 SHA1 哈希值）。现在，每当您生成网格的某个特定部分时，它看起来都是一样的。

您应该能够以与此大致相同的方式进行菱形方形；你只需要改变位移的形状。

Answer 4

我解决了无限景观的钻石平方算法。

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 次迭代中一系列瓦片 [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/

您可以单击并拖动噪声。