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 whe开发者_开发百科n 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()

---

Based on the description in http://gameprogrammer.com/fractal.html#diamond I think the problem is that you make the wrong decision on square versus diamond if x==0 or y==0.

I think you can code the correct decision as:

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

or even simpler as:

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