Python Diamond Square Algorithm Implementation

Question

I have attempted creating a diamond square algorithm based on this javascript because it is readable and makes sense too me. I am having a few issues that I cannot seem to solve however.

When running the code, the desired output is some random value populating each position of the 2D array that is different from the initial array initialization. The issue that I am having is that the result 2D array isn't being completely populated and when increasing the grid size above 3, I get a IndexError: list index out of range error.

Here is the code:

class DiamondSquare:

    def __init__(self, size, roughness):

        self.size = (size ** 2) + 1
        self.max = self.size - 1
        self.roughness = roughness
        self.grid = self.make_grid(self.size)
        self.divide(self.max)
        print(self.grid)

    def divide(self, size):

        x = size / 2
        y = size / 2
        half = size / 2
        scale = self.roughness * size

        if (half < 1):
            return

        # Squares
        for y in range(half, self.max, size):
            for x in range(half, self.max, size):
                s_scale = random.uniform(0, 1) * scale * 2 - scale
                self.square(x, y, half, s_scale)

        # Diamonds
        for y in range(0, self.max, half):
            for x in range((y + half) % size, self.max, size):
                d_scale = random.uniform(0, 1) * scale * 2 - scale
                self.diamond(x, y, half, d_scale)

        self.divide(size / 2)

    def square(self, x, y, size, scale):

        """
            TL      TR

                X       

            BL      BR
        """

        tl = self.grid[x - size][y - size]
        tr = self.grid[x + size][y - size]
        bl = self.grid[x + size][y + size]
        br = self.grid[x - size][y + size]

        average = ((tl + tr + bl + br) / 4) + scale
        self.grid[x][y] = average

    def diamond(self, x, y, size, scale):

        """
                T

            L   X   R

                B
        """

        t = self.grid[x][y - size]
        r = self.grid[x + size][y]
        b = self.grid[x][y + size]
        l = self.grid[x - size][y + size]

        average = ((t + r + b + l) / 4) + scale
        self.grid[x][y] = average

    def make_grid(self, size):

        grid = []
        for y in range(size):
            temp = []
            for x in range(size):
                temp.append(-1)
            grid.append(temp)

        grid[0][0] = self.max
        grid[self.max][0] = self.max / 2
        grid[self.max][self.max] = 0
        grid[0][self.max] = self.max / 2

        return grid

    def get_grid(self):
        return self.grid

When trying to increase the size variable (in init) to a value above 2, I get the following traceback:

Traceback (most recent call last):
  File "C:\Users\user\Documents\Development\Python\Fractal\diamond_square.py", line 150, in 
    a = DiamondSquare(5, 0.7)
  File "C:\Users\user\Documents\Development\Python\Fractal\diamond_square.py", line 14, in __init__
    self.divide(self.max)
  File "C:\Users\user\Documents\Development\Python\Fractal\diamond_square.py", line 35, in divide
    self.diamond(x, y, half, d_scale)
  File "C:\Users\user\Documents\Development\Python\Fractal\diamond_square.py", line 68, in diamond
    r = self.grid[x + size][y]
IndexError: list index out of range

I am honestly not sure why this is happening and I can't figure it out at all. I am using the following code to produce this error:

a = DiamondSquare(x, 0.7)

Where x is any integer above 2 and the second parameter is the roughness.

Also regarding the grid error, trying to create a grid from DiamondSquare.divide(), produces the following:

[[4, 1.0649105908291359, 1.234026481506731, 0.07818244918327344, 2], 
[0.43855022217756057, 0.4659935454877355, 1.283183468707215, 0.28019876872734906, -1], 
[-0.4946413746345607, -1.1327574166276582, 0.45804405178511276, -1.4905717022572778, -1], 
[-1.4175095415414622, -0.660055583070249, -0.8017056243549873, -0.18216161649389495, -1], 
[2, -1, -1, -1, 0]]

Where the -1's are, there should be other random numbers as with the rest of the grid. The -1's make up the mid point of the bottom and the right hand side. I believe it is something to do with my diamonds for loop but I am not sure where I am going wrong.

I achieve this grid, I use the following code:

a = DiamondSquare(2, 0.7)

where the first parameter is the size and the second is the roughness.

Could I please have some help resolving the issues stated above? Thank you in advance!

Brandyn · Accepted Answer

I managed to solve it by removing the 2D list and simply using a 1D list instead which is what I should have done in the first place but I didn't because I misread the original code.

class DiamondSquare:

    def __init__(self, size, roughness):

        self.size = (2 ** size) + 1
        self.max = self.size - 1
        self.roughness = roughness
        self.make_grid(self.size)
        self.divide(self.max)

    # Sets x,y position in self.grid
    def set(self, x, y, val):
        self.grid[x + self.size * y] = val;

    # Get's value of x, y in self.grid
    def get(self, x, y):
        if (x < 0 or x > self.max or y < 0 or y > self.max):
            return -1
        return self.grid[x + self.size * y]

    def divide(self, size):

        x = size / 2
        y = size / 2
        half = size / 2
        scale = self.roughness * size

        if (half < 1):
            return

        # Square
        for y in range(half, self.max, size):
            for x in range(half, self.max, size):
                s_scale = random.uniform(0, 1) * scale * 2 - scale
                self.square(x, y, half, s_scale)

        # Diamond
        for y in range(0, self.max + 1, half):
            for x in range((y + half) % size, self.max + 1, size):
                d_scale = random.uniform(0, 1) * scale * 2 - scale
                self.diamond(x, y, half, d_scale)

        self.divide(size / 2) 

    def square(self, x, y, size, scale):

        top_left = self.get(x - size, y - size)
        top_right = self.get(x + size, y - size)
        bottom_left = self.get(x + size, y + size)
        bottom_right = self.get(x - size, y + size)

        average = ((top_left + top_right + bottom_left + bottom_right) / 4)
        self.set(x, y, average + scale)

    def diamond(self, x, y, size, scale):

        """
                T

            L   X   R

                B
        """

        top = self.get(x, y - size)
        right = self.get(x + size, y)
        bottom = self.get(x, y + size)
        left = self.get(x - size, y)

        average = ((top + right + bottom + left) / 4)
        self.set(x, y, average + scale)



    def make_grid(self, size):

        self.grid = []

        for x in range(size * size):
            self.grid.append(-1)

        self.set(0, 0, self.max)
        self.set(self.max, 0, self.max /2 )
        self.set(self.max, self.max, 0)
        self.set(0, self.max, self.max / 2)

    def get_grid(self):
        return self.grid

a = DiamondSquare(3, 0.5)
print(a.get_grid())

Python Diamond Square Algorithm Implementation

Answers (2)

Related Questions