from random import Random
import math

def perlin_noise_2d(width, height, **kwargs):
    (period_x, period_y) = kwargs.get("period", (width,height)) # Period of the noise
    seed = kwargs.get("seed", None) # PRNG seed to use
    interpolation_function = kwargs.get("interpolation_function", lambda x: 3*x**2 - 2*x**3)
    minimum = kwargs.get("minimum", 0)
    maximum = kwargs.get("maximum", 255)

    prng = Random(seed)

    def unit(x,y):
        if x == 0 and y == 0:
            return (0,0)
        abs = math.sqrt(x**2 + y**2)
        x = x / abs
        y = y / abs
        return (x,y)

    gradients = []
    for y in range(height/period_y + 1):
        for x in range(width/period_x + 1):
            gradients.append(unit(prng.random(), prng.random() ))
    def get_noise(x,y):
        x = x / period_x
        y = y / period_y
        return [gradients[x+y*(width/period_x)], # top left
                gradients[x+1+y*(width/period_x)], # top right
                gradients[x+y*(width/period_x+1)], # bottom left
                gradients[x+1+y*(width/period_x+1)] # bottom right
                ]

    def dot ((x0,y0), (x1,y1)):
        return x0*x1 + y0*y1

    values = []
    for y in range(height):
        for x in range(width):
            noise = get_noise(x,y)

            (delta_x, delta_y) = (x % period_x, y % period_y)

            tl = abs(dot(noise[0], unit(delta_x,delta_y)))
            tr = abs(dot(noise[1], unit(1-delta_x,delta_y)))
            bl = abs(dot(noise[2], unit(delta_x,1-delta_y)))
            br = abs(dot(noise[3], unit(1-delta_x,1-delta_y)))


            top = tl*interpolation_function(delta_x) + tr*(1-interpolation_function(delta_x))
            bottom = bl*interpolation_function(delta_x) + br*(1-interpolation_function(delta_x))

            value = top*interpolation_function(delta_y) + bottom*(1-interpolation_function(delta_y))

            if value > 1:
                print "Value: "+str(value)
                print "top: "+str(top)+" bottom: "+str(bottom)
                print "Noise: "+str(noise)
                print "Magnitude of noise: "+str([math.sqrt(x**2+y**2) for (x,y) in noise])
                print "Delta: "+str((delta_x,delta_y))
                print "dot products: "+str((tl,tr,bl,br))
                raise Exception

            values.append(int(value*(maximum-minimum)+minimum))
    return values