Issue with "inside-out" implementation of diamond-square fractal
I'm working on a Python script that generates a (wrapping) diamond-square fractal in the reverse of the usual order: Instead of starting from the outside corners and subdividing into smaller squares, it starts from an arbitrary point and works recursively outward, generating only the points on which the final value depends. Here’s the function I've written to determine how to treat each point:

    def stepinfo(x, y):
        y1 = y-(y&(y-1))
        x1 = x-(x&(x-1))
        sum = x1 + y1
        return [((sum&(sum-1)) == 0), min(y1, x1)]

The first value returned is a boolean specifying whether the point should be generated by a diamond or a square step; and the second value specifies the grid size of the step. It works great, except when x or y is zero—then the returned step size is zero and the script loops. However, if I tile the fractal into a 2x2 grid and specify points by clicking in the lower-right copy of the tile (i.e., away from the window's zero axes), the entire fractal will generate perfectly. But I can’t seem to "fake" this result by adding a multiple of the tile size to the mouse coordinates, or anything along those lines.

Any suggestions?


Here's the complete script (I've avoided the endless loops by halting the recursion if x or y = 0, but it still generates artifacts at the missing points):

    MAPEXPONENT = 8
    
    import pygame
    import random
    
    MAPSIZE = 2**int(MAPEXPONENT)
    MAP = [[[None] for col in range(MAPSIZE)] for row in range(MAPSIZE)]
    
    def point(x, y):
        return MAP[x%MAPSIZE][y%MAPSIZE]
    
    def displace(value, scale):
        displaced = (value + (random.random()-.5) * scale * 12)
        if displaced > 1 or displaced < 0: displaced = 1-displaced%1
        return displaced
    
    def average(values):
        realvalues = []
        for value in values:
            if value <> None: realvalues.append(value)
        if realvalues: return float(sum(realvalues, 0)) / len(realvalues)
        else: return 0
    
    def color_point(x, y, array):
        pixel = point(x, y)[0]
        green = pixel*255
        red = pixel**.5*255
        blue = 255-green
        array[x%MAPSIZE][y%MAPSIZE] = [min(255, max(0, int(red))),
                                       min(255, max(0, int(green))),
                                       min(255, max(0, int(blue)))]
    
    def stepinfo(x, y):
        y1 = y-(y&(y-1))
        x1 = x-(x&(x-1))
        sum = x1 + y1
        return [((sum&(sum-1)) == 0), min(y1, x1)]
    
    def makepoint(x, y, map_array):
        midpoint = point(x, y)
        if midpoint[0] == None:
            step = stepinfo(x, y)
            size = step[1]
            scale = float(size)/MAPSIZE
            heights = []
            if step[0]: points = [[x-size, y-size], [x+size, y-size],
                                  [x-size, y+size], [x+size, y+size]]
            else:       points = [[x, y-size],      [x, y+size],
                                  [x-size, y],      [x+size, y]]
            for p in points:
                if point(p[0], p[1])[0] == None and p[0] and p[1]:
                    makepoint(p[0], p[1], map_array)
                heights.append(point(p[0], p[1])[0])
            midpoint[0] = displace(average(heights), scale)
            color_point(x, y, map_array)
        return midpoint
    
    pygame.init()
    screen = pygame.display.set_mode((2*MAPSIZE, 2*MAPSIZE))
    map_surface = pygame.surface.Surface((MAPSIZE, MAPSIZE))
    brush = 4+MAPSIZE/32
    
    map_surface_array = pygame.surfarray.pixels3d(map_surface)
    MAP[0][0][0] = random.random()
    color_point(0, 0, map_surface_array)
    del map_surface_array
    
    running = True
    while running:
        event = pygame.event.wait()
        if event.type == pygame.MOUSEBUTTONDOWN:
            while event.type <> pygame.MOUSEBUTTONUP:
                event = pygame.event.wait()
                x0, y0 = pygame.mouse.get_pos()
                map_surface_array = pygame.surfarray.pixels3d(map_surface)
                for x in range(x0-brush, x0+brush):
                    for y in range(y0-brush, y0+brush):
                        if (x-x0)**2+(y-y0)**2 < brush**2:
                            makepoint(x, y, map_surface_array)
                del map_surface_array
                for x, y in [(0,0), (MAPSIZE,0), (0,MAPSIZE), (MAPSIZE,MAPSIZE)]:
                    screen.blit(map_surface, (x, y))
                pygame.display.update()
        elif event.type == pygame.QUIT:
            running = False
    pygame.quit()


Issue with "inside-out" implementation of diamond-square fractal
===

I'm working on a Python script that generates a (wrapping) diamond-square fractal in the reverse of the usual order: Instead of starting from the outside corners and subdividing into smaller squares, it starts from an arbitrary point and works recursively outward, generating only the points on which the final value depends. Here’s the function I've written to determine how to treat each point:

    def stepinfo(x, y):
        y1 = y-(y&(y-1))
        x1 = x-(x&(x-1))
        sum = x1 + y1
        return [((sum&(sum-1)) == 0), min(y1, x1)]

The first value returned is a boolean specifying whether the point should be generated by a diamond or a square step; and the second value specifies the grid size of the step. It works great, except when x or y is zero—then the returned step size is zero and the script loops. However, if I tile the fractal into a 2x2 grid and specify points by clicking in the lower-right copy of the tile (i.e., away from the window's zero axes), the entire fractal will generate perfectly. But I can’t seem to "fake" this result by adding a multiple of the tile size to the mouse coordinates, or anything along those lines.

Any suggestions?


Here's the complete script (I've avoided the endless loops by halting the recursion if x or y = 0, but it still generates artifacts at the missing points):

    MAPEXPONENT = 8
    
    import pygame
    import random
    
    MAPSIZE = 2**int(MAPEXPONENT)
    MAP = [[[None] for col in range(MAPSIZE)] for row in range(MAPSIZE)]
    
    def point(x, y):
        return MAP[x%MAPSIZE][y%MAPSIZE]
    
    def displace(value, scale):
        displaced = (value + (random.random()-.5) * scale * 12)
        if displaced > 1 or displaced < 0: displaced = 1-displaced%1
        return displaced
    
    def average(values):
        realvalues = []
        for value in values:
            if value <> None: realvalues.append(value)
        if realvalues: return float(sum(realvalues, 0)) / len(realvalues)
        else: return 0
    
    def color_point(x, y, array):
        pixel = point(x, y)[0]
        green = pixel*255
        red = pixel**.5*255
        blue = 255-green
        array[x%MAPSIZE][y%MAPSIZE] = [min(255, max(0, int(red))),
                                       min(255, max(0, int(green))),
                                       min(255, max(0, int(blue)))]
    
    def stepinfo(x, y):
        y1 = y-(y&(y-1))
        x1 = x-(x&(x-1))
        sum = x1 + y1
        return [((sum&(sum-1)) == 0), min(y1, x1)]
    
    def makepoint(x, y, map_array):
        midpoint = point(x, y)
        if midpoint[0] == None:
            step = stepinfo(x, y)
            size = step[1]
            scale = float(size)/MAPSIZE
            heights = []
            if step[0]: points = [[x-size, y-size], [x+size, y-size],
                                  [x-size, y+size], [x+size, y+size]]
            else:       points = [[x, y-size],      [x, y+size],
                                  [x-size, y],      [x+size, y]]
            for p in points:
                if point(p[0], p[1])[0] == None and p[0] and p[1]:
                    makepoint(p[0], p[1], map_array)
                heights.append(point(p[0], p[1])[0])
            midpoint[0] = displace(average(heights), scale)
            color_point(x, y, map_array)
        return midpoint
    
    pygame.init()
    screen = pygame.display.set_mode((2*MAPSIZE, 2*MAPSIZE))
    map_surface = pygame.surface.Surface((MAPSIZE, MAPSIZE))
    brush = 4+MAPSIZE/32
    
    map_surface_array = pygame.surfarray.pixels3d(map_surface)
    MAP[0][0][0] = random.random()
    color_point(0, 0, map_surface_array)
    del map_surface_array
    
    running = True
    while running:
        event = pygame.event.wait()
        if event.type == pygame.MOUSEBUTTONDOWN:
            while event.type <> pygame.MOUSEBUTTONUP:
                event = pygame.event.wait()
                x0, y0 = pygame.mouse.get_pos()
                map_surface_array = pygame.surfarray.pixels3d(map_surface)
                for x in range(x0-brush, x0+brush):
                    for y in range(y0-brush, y0+brush):
                        if (x-x0)**2+(y-y0)**2 < brush**2:
                            makepoint(x, y, map_surface_array)
                del map_surface_array
                for x, y in [(0,0), (MAPSIZE,0), (0,MAPSIZE), (MAPSIZE,MAPSIZE)]:
                    screen.blit(map_surface, (x, y))
                pygame.display.update()
        elif event.type == pygame.QUIT:
            running = False
    pygame.quit()

