#!/usr/local/bin/python3.1

#Created by Jared Gray and Travis Singer
#Havill
#CS 111
#27 October 2010

#Project 5 - Diffusion-Limited Aggregation

import math, cTurtle, random

def distance(p, q):
    '''Return the distance between points p and q. The input of this function
       must be two lists/tuples, each containing a coordinate value.'''

    x1 = p[0]
    x2 = q[0]
    y1 = p[1]
    y2 = q[1]

    return math.sqrt((x2-x1)**2+(y2-y1)**2)   #distance formula

def findCoordinate(r, angle, origin):
    '''Determines the location of a coordinate r units away from
       the origin at angle'''

    x = origin[0]+(math.cos(math.radians(angle))*r)
    y = origin[1]+(math.sin(math.radians(angle))*r)

    return [int(round(x, 1)), int(round(y, 1))]    #rounds and makes the coordinate an integer, thus usable in the matrix (introduces error)

def adjacent(grid, x, y):
    '''Returns the value True if the particle is adjacent to a particle in the cluster
       and False otherwise.'''

    if abs(x) >= len(grid)-1 or abs(y) >= len(grid)-1:   #used to circumvent errors casued by large indeces
        return False

    if grid[x+1][y] == 1:
        return True
    elif grid[x][y+1] == 1:
        return True
    elif grid[x+1][y+1] == 1:
        return True
    elif grid[x-1][y] == 1:
        return True
    elif grid[x][y-1] == 1:
        return True
    elif grid[x-1][y-1] == 1:
        return True
    elif grid[x+1][y-1] == 1:
        return True
    elif grid[x-1][y+1] == 1:
        return True

    return False

def makeList(size):
    '''Creates a list of size number of zeros'''

    mylist = []
    for i in range(size):
        mylist.append(0)
    return mylist

def makeMatrix(rows, columns):
    '''Creates a 2D matrix as a list of rows number of lists
       where the lists are columns'''

    matrix = []
    for i in range(rows):
        matrix.append(makeList(columns))
    return matrix

def randomWalk(start):
    '''Returns a coordinate for a particle randomly moving ONCE
       from its original location (start)'''

    #initializes coordinate values
    x = start[0]
    y = start[1]

    determinant = random.randrange(1,5)

    if determinant == 1:
        y = y+1
    elif determinant == 2:
        y = y-1
    elif determinant == 3:
        x = x+1
    else:
        x = x-1

    return [x, y]

def numSticks(Matrix):
    '''Counts the number of  particles (ones) in a given matrix'''

    count = 0

    for row in range(len(Matrix)):
        for column in range(len(Matrix[row])):
            if Matrix[row][column] == 1:
                count = count+1

    return count

def dla(particles):

    #1. Initialize your turtle graphics window and your matrix.
    t = cTurtle.Turtle()
    t.setWorldCoordinates(0,0,199,199)
    t.up()
    t.color('blue')
    t.hideturtle()
    mx = makeMatrix(200, 200)   #creates a matrix 200-by-200 and assigns it to mx
    origin = [len(mx)//2, len(mx)//2]

    #2. Place a seed particle at the origin (both in your matrix and graphically), and set the radius R of the cluster to be 0.
    mx[len(mx)//2][len(mx)//2] = 1
    t.goto(origin[0],origin[1])
    t.dot()
    r = 0

    for particle in range(particles):

        #3. Release a new particle in a random position at a distance of R + 1 from the origin.
        newPos = origin
        while distance(origin, newPos) != r+1:   #while loop overcomes some error in rounding
            angle = random.randrange(0, 360)
            newPos = findCoordinate(r+1, angle, origin)

        #4a. Let the new particle perform a random walk. If, at any step, the particle comes in contact with an existing particle, it "sticks".
        i = 0
        row = newPos[0]
        column = newPos[1]

        #4b. Abandon the particle when it wanders outside of a circle with radius that is some function of R.
        while distance(newPos, origin)<2*(r+1) and (adjacent(mx, newPos[0], newPos[1])==False) and row<len(mx) and column<len(mx) and mx[row][column] != 1:   #randomly moves particle until it sticks or goes too far away (includes outside of matrix)
            i = i+1
            newPos = randomWalk(newPos)
            row = newPos[0]
            column = newPos[1]

        #4c. Update your matrix, draw a dot at this location, and update R if this particle is further from the origin than the previous radius.
        if distance(newPos, origin)<2*(r+1) and row<len(mx) and column<len(mx):   #if while loop terminated early, signifying a "stick," show where the particle stuck
            if distance(origin, newPos) > r:
                r = r+1
            t.goto(row,column)
            t.dot()
            mx[row][column] = 1
        #5. Repeat the previous two steps for particles particles.

    print("Sticks:", numSticks(mx))
    t.exitOnClick()

def main():
    dla(1000)
main()