python3.4.3diamondsquare算法产生了奇怪的结果

Question

我现在被代码中的一个伪制品所困扰。它似乎在网格模式中产生了非常尖锐的点，这些点对它们的邻居有着显著的价值差异。在

我正在关注http://www.bluh.org/code-the-diamond-square-algorithm/上的博客文章，并从他们使用的任何一种语言（假设是C或Java）进行转换，并仔细检查了我所做的是否匹配。在

有没有可能有人可以浏览一下，看看我做错了什么？我已经在更小的层次上进行了研究，并在算法的特定迭代中停止了它（通过展开顶部循环，显式地将算法称为一组次数），直到我们到达最后一组点/像素为止，一切似乎都在工作。在

我使用一个类（称为Matrix）访问列表，并包装任何越界值。在

算法代码如下：

class World :
def genWorld (self, numcells, cellsize, seed):
    random.seed(seed)
    self.dims = numcells*cellsize
    self.seed = seed
    self.cells = Matrix(self.dims, self.dims)

    # set the cells at cellsize intervals
    half = cellsize/2
    for y in range(0, self.dims, cellsize):
        for x in range(0, self.dims, cellsize):
            self.cells[x,y] = random.random()

    scale = 1.0
    samplesize = cellsize
    while samplesize > 1:
        self._diamondSquare(samplesize, scale)
        scale *= 0.8
        samplesize = int(samplesize/2)

    # I need to sort out the problem with the diamond-square algo that causes it to make the weird gridding pattern

def _sampleSquare(self, x, y, size, value):
    half = size/2
    a = self.cells[x-half, y-half]
    b = self.cells[x+half, y-half]
    c = self.cells[x-half, y+half]
    d = self.cells[x+half, y+half]

    res = min(((a+b+c+d+value)/5.0), 1.0)
    self.cells[x, y] = res

def _sampleDiamond(self, x, y, size, value):
    half = size/2
    a = self.cells[x+half, y]
    b = self.cells[x-half, y]
    c = self.cells[x, y+half]
    d = self.cells[x, y-half]

    res = min(((a+b+c+d+value)/5.0), 1.0)
    self.cells[x, y] = res

def _diamondSquare(self, stepsize, scale):
    half = int(stepsize/2)
    for y in range(half, self.dims+half, stepsize):
        for x in range(half, self.dims+half, stepsize):
            self._sampleSquare(x, y, stepsize, random.random()*scale)

    for y in range(0, self.dims, stepsize):
        for x in range(0, self.dims, stepsize):
            self._sampleDiamond(x+half, y, stepsize, random.random()*scale)
            self._sampleDiamond(x, y+half, stepsize, random.random()*scale)

被称为：

^{pr2}$

然后保存到文件以检查结果：

^{3}$

结果是：

{1美元^

编辑：好的，看来我设法让它工作起来了。我从使用函数来计算菱形和正方形的步骤，改为在_diamondSquare（）函数中完成所有步骤，但这不是唯一的事情。我也发现了随机。随机（）提供的值在[0.0->；1.0）范围内，而我期望值在范围[-1.0->；1.0）内。在我纠正这一点之后，一切都开始正常工作，这让我松了一口气。在

感谢大家的建议，以下是工作代码，以防其他人遇到类似问题：

随机函数

# since random.random() gives a value in the range [0.0 -> 1.0), I need to change it to [-1.0 -> 1.0)
def rand():
    mag = random.random()
    sign = random.random()
    if sign >=0.5:
        return mag
    return mag * -1.0

矩阵类

class Matrix:
    def __init__(self, width, height):
        self.cells = [0 for i in range(width*height)]
        self.width = width
        self.height = height
        self.max_elems = width*height

    def _getsingleindex(self, ind):
        if ind < 0:
            ind *= -1
        while ind >= self.max_elems:
            ind -= self.max_elems
        return ind

    def _getmultiindex(self, xind, yind):
        if xind < 0:
            xind *= -1
        if yind < 0:
            yind *= -1

        while xind >= self.width:
            xind -= self.width
        while yind >= self.height:
            yind -= self.height
        return xind + (yind*self.height)

    def __getitem__(self, inds):
        # test that index is an integer, or two integers, and throw an indexException if not
        if hasattr(inds, "__len__"):
            if len(inds) > 1:
                return self.cells[self._getmultiindex(int(inds[0]), int(inds[1]))]
        return self.cells[self._getsingleindex(int(inds))]

    def __setitem__(self, inds, object):
        # test that index is an integer, or two integers, and throw an indexException if not
        if hasattr(inds, "__len__"):
            if len(inds) > 1:
                self.cells[self._getmultiindex(int(inds[0]),int(inds[1]))] = object
                return self.cells[self._getmultiindex(int(inds[0]),int(inds[1]))]
        self.cells[self._getsingleindex(int(inds))] = object
        return self.cells[self._getsingleindex(int(inds))]

    def __len__(self):
        return len(self.cells)

实际生成的钻石方块

# performs the actual 2D generation
class World:
    def genWorld (self, numcells, cellsize, seed, scale = 1.0):
        random.seed(seed)
        self.dims = numcells*cellsize
        self.seed = seed
        self.cells = Matrix(self.dims, self.dims)
        mountains = Matrix(self.dims, self.dims)

        # set the cells at cellsize intervals
        for y in range(0, self.dims, cellsize):
            for x in range(0, self.dims, cellsize):
                # this is the default, sets the heights randomly
                self.cells[x,y] = random.random()


        while cellsize > 1:
            self._diamondSquare(cellsize, scale)
            scale *= 0.5
            cellsize = int(cellsize/2)

        for i in range(len(mountains)):
            self.cells[i] = self.cells[i]*0.4 + (mountains[i]*mountains[i])*0.6

    def _diamondSquare(self, stepsize, scale):
        half = int(stepsize/2)
        # diamond part
        for y in range(half, self.dims+half, stepsize):
            for x in range(half, self.dims+half, stepsize):
                self.cells[x, y] = ((self.cells[x-half, y-half] + self.cells[x+half, y-half] + self.cells[x-half, y+half] + self.cells[x+half, y+half])/4.0) + (rand()*scale)

        # square part
        for y in range(0, self.dims, stepsize):
            for x in range(0, self.dims, stepsize):
                self.cells[x+half,y] = ((self.cells[x+half+half, y] + self.cells[x+half-half, y] + self.cells[x+half, y+half] + self.cells[x+half, y-half])/4.0)+(rand()*scale)
                self.cells[x,y+half] = ((self.cells[x+half, y+half] + self.cells[x-half, y+half] + self.cells[x, y+half+half] + self.cells[x, y+half-half])/4.0)+(rand()*scale)

主功能（为完整性而添加）

# a simple main function that uses World to create a 2D array of diamond-square values, then writes it to a file
def main():
    w = World()
    w.genWorld(20, 16, 1)

    mi = min(w.cells.cells)
    ma = max(w.cells.cells) - mi

    # save the resulting matrix to an image file
    file = io.open("sample.raw",'wb')
    maxed = [(i-mi)/ma for i in w.cells.cells]
    arr = [int(i * 255) for i in maxed]

    file.write(bytearray(arr))
    file.close()