algorithm - 产生异常模式的中点位移二维算法

Question

我在使用 Haxe 的中点位移算法时遇到困难。我正在按照找到的步骤执行此操作 here .

First, create an array that represents a blank map. You begin by giving the four corners a random value.

In this square, create the middle point by averaging the four corners and adding a small 'error', or random value. Then create the midpoints of the 4 sides by averaging the two corners each is between. After these steps, you are left with 4 squares. Repeat the steps:

1. Create the middle point by averaging the four corners and adding a small 'error'.

2. Create the midpoint of each side by averaging the two corners each point is between.

Each iteration, make the range of the RNG smaller. That way the original few points can have pretty large variation, but the later points only get tiny adjustments. This ensures the right amount of detail in an image.

这是我编写的用于执行这些步骤然后对值进行规范化的函数:

public static function generateFloatMatrix(Columns:Int, Rows:Int, RangeModifier:Float = 0.65):Array<Array<Float>>
{
    //Blank 2D Array
    var matrix:Array<Array<Float>> = InitFloatMatrix(Columns, Rows);
    var range:Float = 1;
    
    //Set Values for all four corners
    matrix[0][0] = Math.random() * range;
    matrix[Rows-1][0] = Math.random() * range;
    matrix[0][Columns-1] = Math.random() * range;
    matrix[Rows - 1][Columns - 1] = Math.random() * range;
    
    //Calculates the amount of segments in base 2
    var length = Math.sqrt((Columns * Columns) + (Rows * Rows));
    var power:Int = Std.int(Math.pow(2, Math.ceil(Math.log(length) / Math.log(2))));
    
    //Stores largest calculated value for normalization
    var max:Float = 0;
    
    var width:Int = Std.int(Columns);
    var height:Int = Std.int(Rows);
    
    var i:Int = 1;
    while (i < power)
    {
        //Segment Size
        width = Std.int(Columns / i);
        height = Std.int(Rows / i);
        
        for (y in 0...i)
        {
            for (x in 0...i)
            {
                //Top Left Coordinates per segment
                var left = width * x;
                var top = height * y;
                
                //Find Midpoint
                var xMid = Math.ceil(left + (width / 2));
                var yMid = Math.ceil(top + (height / 2));
                
                //Make sure right and bottom do not go out of bounds
                var right:Int = (left + width < Columns ? left + width : Columns - 1);
                var bottom:Int = (top + height < Rows ? top + height : Rows - 1);
                
                //Sets midpoint value to average of all four corners.
                matrix[yMid][xMid] = 
                    (matrix[top][left] + 
                        matrix[bottom][left] + 
                        matrix[bottom][right] + 
                        matrix[top][right]) / 4;
                        
                //trace ("Top: " + top + " - Left: " + left + " - Bottom: " + bottom + " - Right: " + right);
                
                //Adds random value to midpoint
                matrix[yMid][xMid] += Math.random() * range;
                
                //Set side values to average of adjacent corners
                matrix[top][xMid] = (matrix[top][left] + matrix[top][right]) / 2;
                matrix[bottom][xMid] = (matrix[bottom][left] + matrix[bottom][right]) / 2;
                matrix[yMid][left] = (matrix[top][left] + matrix[bottom][left]) / 2;
                matrix[yMid][right] = (matrix[top][right] + matrix[bottom][right]) / 2;
                
                max = Math.max(matrix[top][left], max);
            }
        }
        
        //Reduces range
        range *= RangeModifier;
        i *= 2;
    }
    
    //Normalizes all values in matrix
    for (y in 0...Rows)
    {
        for (x in 0...Columns)
        {
            matrix[y][x] /= max;
        }
    }
    
    return matrix;
}

如果我使用每个值将每个像素渲染到指定坐标，这些是它生成的图像。所有呈现为白色的像素的值为 0，黑色为值 1。

Answer 1

您的问题是，如果您的 map 尺寸不是 2 的幂，则您不一定会在计算中找到已经填充的像素。例如，如果您的 map 有 30 个单位宽，那么您的网格宽度在第一遍中为 15，在第二遍中为 7，它的计算基于尚未触及的单元 14。

一个解决方案是使用浮点运算进行所有计算，直到您确定单位索引，当然它必须是整数:

while (i < power)
{
    var width:Float = Columns / i;    // Floating-point division
    var height:Float = Rows / i;

    for (y in 0...i)
    {
        for (x in 0...i)
        {
            var left:Int = Math.floor(width * x);
            var top:Int = Math.floor(height * y);

            var xMid:Int = Math.floor(width * (x + 0.5));
            var yMid:Int = Math.floor(height * (y + 0.5));

            var right:Int = Math.floor(width * (x +1));
            var bottom:Int = Math.floor(height * (y + 1));

            //Make sure right and bottom do not go out of bounds
            if (right > Columns - 1) right = Columns - 1;
            if (bottom > Rows - 1) bottom = Rows - 1;

            // Do offset and interpolation stuff
        }
    }
}

这应该会给你一张随机 map 、方格纸效果等等。

(警告:我不熟悉 Haxe，但已经在没有整数类型的 Javascript 中对此进行了测试。我自始至终都使用了 Math-floor，您将在其中想用 Haxe 的方式来做。)

最后，在我看来，您的传球次数太多了。我会将功率基于两个维度的最大值而不是对角线。您也可以跳过宽度接近 1 的最后一步。