Coding: Bring the Noise

%26lt;0011 Em

2D random terrain: iterative diamond-square algorithm

leave a comment »

A year and a half ago, I created a simple application that allowed one to specify a folder of column-wise data, which axes to plot, a color scheme, and then with those parameters ran over the files and created an avi file from the data.  This was for my university’s CSUMS program, and while I was excited to release it to my peers, no one really understood what it did, or why they should care.

I needed some examples.  Since I wanted to start working on terrain generation and I was on a minecraft kick at the time, I read up on the Diamond-Square Algorithm and went with an iterative version of that.  The following is a mostly-cleaned-up version of that code.  I’m posting it today because this post reminded me of it, and I want to adapt it to C#/XNA and then implement my alternating directions implicit diffusion algorithm, so that I can see just how fast I can run that in a shader.

Implementation note: this wraps edges, so that you can tile the output seamlessly.

Here’s the code.   (You’ll need numpy and matplotlib.)

import numpy
import random

import matplotlib
matplotlib.use("Agg")
import matplotlib.pylab
import matplotlib.colors

def make_height_func(noise_func, noisemin, noise_max):
    def height_func(i):
        return noise_func(noise_min*2**-i, noise_max*2**-i)
    return height_func

def make_space(width, height, height_func):
    space = numpy.zeros((width,height))
    corner = height_func(0)
    space[0,0] = corner
    space[0,-1] = corner
    space[-1,0] = corner
    space[-1,-1] = corner
    return space

def avg(*args):
    return sum(args)/len(args)

def distort_space(space, height_func):
    print "Distorting..."
    x_max,y_max = space.shape
    x_min = y_min = 0
    x_max -= 1; y_max -= 1

    side = x_max
    squares = 1
    i = 0

    while side > 1:
        for x in range(squares):
            for y in range(squares):
                #Locations
                x_left = x*side
                x_right = (x+1)*side
                y_top = y*side
                y_bottom = (y+1)*side

                dx = side/2
                dy = side/2

                xm = x_left + dx
                ym = y_top + dy

                #Diamond step- create center avg for each square
                space[xm,ym] = avg(space[x_left, y_top],
                space[x_left, y_bottom],
                space[x_right, y_top],
                space[x_right, y_bottom])
                space[xm,ym] += height_func(i)

                #Square step- create squares for each diamond
                #Top Square
                if (y_top - dy) < y_min:
                    temp = y_max - dy
                else:
                    temp = y_top - dy
                space[xm,y_top] = avg(space[x_left,y_top],
                                      space[x_right,y_top],
                                      space[xm,ym],
                                      space[xm,temp])
                space[xm,y_top] += height_func(i)

                #Top Wrapping
                if y_top == y_min:
                    space[xm,y_max] = space[xm,y_top]

                #Bottom Square
                if (y_bottom + dy) > y_max:
                    temp = y_top + dy
                else:
                    temp = y_bottom - dy
                space[xm, y_bottom] = avg(space[x_left,y_bottom],
                                          space[x_right,y_bottom],
                                          space[xm,ym],
                                          space[xm,temp])
                space[xm, y_bottom] += height_func(i)

                #Bottom Wrapping
                if y_bottom == y_max:
                    space[xm,y_min] = space[xm,y_bottom]

                #Left Square
                if (x_left - dx) < x_min:
                    temp = x_max - dx
                else:
                    temp = x_left - dx
                space[x_left, ym] = avg(space[x_left,y_top],
                                        space[x_left,y_bottom],
                                        space[xm,ym],
                                        space[temp,ym])
                space[x_left, ym] += height_func(i)

                #Left Wrapping
                if x_left == x_min:
                    space[x_max,ym] = space[x_left,ym]

                #Right Square
                if (x_right + dx) > x_max:
                    temp = x_min + dx
                else:
                    temp = x_right + dx
                space[x_right, ym] = avg(space[x_right,y_top],
                                         space[x_right,y_bottom],
                                         space[xm,ym],
                                         space[temp,ym])
                space[x_right, ym] += height_func(i)

                #Right Wrapping
                if x_right == x_max:
                    space[x_min,ym] = space[x_right,ym]

        #Refine the pass
        side /= 2
        squares *= 2
        i += 1
        print "Pass {0} complete.".format(i)

def decay_space(space, step, folder):
    bottom = min(space.flat)
    top = max(space.flat)
    norm = matplotlib.colors.Normalize(bottom,top)
    n = int(1.0/step)
    step = float(top-bottom)/n

    x,y = space.shape
    print "Generating ",n,"images."
    matplotlib.pylab.clf()
    fig = matplotlib.pylab.gcf()
    ax = fig.gca()
    for i in xrange(n):
        ScalarMap = ax.pcolorfast(space, norm = norm)
        if i == 0:
            fig.colorbar(ScalarMap)
        ax.axis('image')
        fig.savefig(folder+"%05d"%i+".png", dpi = 100)
        print "Saved image {0}/{1}".format(i+1,n)
        ax.cla()

        top -= step
        for x_ in xrange(x):
            for y_ in xrange(y):
                space[x_,y_] = min(top, space[x_,y_])

if __name__ == "__main__":
    fps = 30
    sec = 1.0
    frame_count = sec * fps
    step = 1.0/frame_count
    folder = "C:\\DIAMOND_SQUARE\\"

    passes = 9
    width = height = 2**passes + 1

    noise_func = random.uniform
    noise_min = -1.0
    noise_max = 1.0
    height_func = make_height_func(noise_func, noise_min, noise_max)

    #Initialize the space with random values
    space = make_space(width, height, height_func)

    #Square-Diamond Method
    distort_space(space, height_func)

    #Lowers the ceiling on the heightmap over time, saving each iteration to the folder.
    #Will always fade to flat over whatever time is specified
    decay_space(space, step, folder)
Advertisements

Written by delwinna

April 30, 2012 at 10:35 pm

Posted in Python

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: