import time
import math
import random

protectedstart = [0,0]
protectedfinish = [5,5]
sp = [0,5]
fp = [31,31]
timesToGenCircle = 300

class Cell():
    def __init__(self):
        self.val = 0
        self.d = -1
        self.mark = False
        self.path = False

w = 40 # width of each cell

##DECLARATIONS
#obstacles = [[0,20],
             #[1,25],
             #[0,25]


             #]

#for i in range(len(obstacles)):
#    grid[obstacles[i][0]][obstacles[i][1]].val = -1

def neighbourIs(x,y,arr):
    Break = False
    for dx in range(-1,2):
        for dy in range(-1,2):
            if dx+x <=31 and dx+x >= 0 and dy+y <= 31 and dy+y >=0: #look up neighbours: all  dirs + curr
                if grid[dx+x][dy+y].val in arr:
                    Break = True

            if Break == True:
                break
        if Break == True:
            break

    return Break



def drawRandomObstacles():


  width = 1
  height = 1

  ctiles = [[0 for _ in range(height)] for _ in range(width)]
  #lst = []

  for o in range(timesToGenCircle):

    x = random.randint(0,32-width)
    y = random.randint(0,32-height)

    #while neighbourIs(x,y,["finish",-1,"checkpoint"]) == True:
     #   x = random.randint(0,32-width)
      #  y = random.randint(0,32-height)

    for i in range(height):
      for j in range(width):
        ctiles[i][j] = 1





    for dx in range(width):
      for dy in range(height):
          if ctiles[dx][dy] == 1: #and grid[x+dx][y+dy].val == 0:
              grid[x+dx][y+dy].val = -1






def setup():
    size(1280,1280)


def draw():
    x,y = 0,0 # starting position

    for row in grid:
        for col in row:
          if col.val == 1:
              fill(100,0,0) #red
          elif col.val == -1:
              fill(200) #obstacle
          elif col.val == "start":
              fill(255,0,0) #red
          elif col.val == "finish":
              fill(0,255,255) #blue
          elif col.val == "checkpoint":
              fill(120,200,195)
          elif col.val == 2: #cant be changed
              print("A")

          else:
              fill(0,100,0)
              col.val = 0

          if col.d != -1 and col.d!=0 and col.mark == False and col.val!=-1:
              fill(255-col.d,255-col.d*2,0+col.d)

          if col.path == True:
              fill(255)

          rect(y, x, w, w)
          x = x + w  # move right
        y = y + w # move down
        x = 0 # rest to left edge



def drawProtected():
    for row in range(protectedfinish[0]):
        for col in range(protectedfinish[1]):
            grid[row][col].val = -1


def dNeighbours(x, y, d):
    for dx in range(-1,2):
        for dy in range(-1,2):
            if (dx==0) != (dy==0): #look up neighbours: up, down, left, right
                if x+dx >=0 and x+dx <=31 and y+dy>=0 and y+dy<=31:
                    if (grid[x+dx][y+dy].d == -1) and (grid[x+dx][y+dy].val in [0,1]):
                        grid[x+dx][y+dy].d = d + 1
                    if (grid[x+dx][y+dy].val == "finish"): #or (grid[x+dx][y+dy].val == "checkpoint"): <== DON'T ADD
                        grid[x+dx][y+dy].mark = True
                        grid[x+dx][y+dy].d = d + 1
                    #if grid[x+dx][y+dy].d == 2:
                     #   print(x+dx,y+dy,2)



def analyzeSandBuildAWall(x,y, visited):
    fx = -1
    fy = -1
    cc = 0

    for dx in range(-1,2):
        for dy in range(-1,2) :#look up neighbours: 8 incl. current
            cc+=1


            if x+dx >=0 and x+dx <=31 and y+dy>=0 and y+dy<=31:

                if grid[x+dx][y+dy].path != True and grid[x+dx][y+dy].val not in [1,-1,"start","finish","checkpoint"]:
                    #print("BUILT!")
                    grid[x+dx][y+dy].val = -1

                if (dx==0) != (dy==0): #look up neighbours: up, down, left, right
                    #print("cc: ",cc," x:", x," y:",y," path:",grid[x+dx][y+dy].path)
                    #print("dx:",dx," dy:",dy)
                    if (grid[x+dx][y+dy].path == True or grid[x+dx][y+dy].val == "start")  and [x+dx,y+dy] not in visited:
                        #print("added ", [x+dx,y+dy])
                        visited.append([x+dx,y+dy])
                        fx = x+dx
                        fy = y+dy



    if grid[x][y].val in ["start","finish","checkpoint"]:
        for dx in range(-1,2):
            for dy in range(-1,2):
                if (dx==0) != (dy==0): #look up neighbours: up, down, left, right
                    if x+dx >=0 and x+dx <=31 and y+dy>=0 and y+dy<=31:
                        if grid[x+dx][y+dy].val == -1:
                            grid[x+dx][y+dy].val = 1



    if fx == -1 or fy == -1:
        return "error"
    else:
        return fx,fy,visited








def analyzeAndGoToXY(x,y,d):
    Break = False
    for dx in range(-1,2):
        for dy in range(-1,2):
            if (dx==0) != (dy==0) and dx+x <=31 and dx+x >= 0 and dy+y <= 31 and dy+y >=0: #look up neighbours: up, down, left, right
                if grid[x+dx][y+dy].d+1 == d and grid[x+dx][y+dy].path == False:
                    x = x+dx
                    y = y+dy
                    Break = True
                    break

        if Break == True:
               break


    return [x,y,d-1]


def LeesAlg(startingpoint,finishingpoint, CPGen):
    global_err = False

    #def tryToFindAnExit(startingpoint,finishingpoint):
    grid[finishingpoint[0]][finishingpoint[1]].val = "finish"
    x = startingpoint[0]
    y = startingpoint[1]
    d = 0
    tries = 0


    grid[x][y].d = 0
    grid[x][y].val = "start"

    while grid[finishingpoint[0]][finishingpoint[1]].mark == False and tries<500:
        for x in range(32):
            for y in range(32):
                if grid[x][y].d == d:
                    dNeighbours(x, y, d)
        d+=1
        tries+=1

        #return tries, d

    if tries >= 498:
        global_err = True
        print("YOU FAILED!")







    x = finishingpoint[0]
    y = finishingpoint[1]
    tries=0




    if grid[x][y].mark == True:
        while (x != startingpoint[0] or y != startingpoint[1]) and tries<500:
            xydArr = analyzeAndGoToXY(x,y,d)
            x = xydArr[0]
            y = xydArr[1]
            d = xydArr[2]
            grid[x][y].path = True



            #print("Marked ",x,y,d)
            #print(startingpoint[0],startingpoint[1],grid[startingpoint[0]][startingpoint[1]].d)

            #print("Req x:",startingpoint[0],"Req y:",startingpoint[1])
            #print("Arrived at ",x,y)
            tries+=1

        if grid[x][y].val == "start":
            grid[x][y].path = False

        #print("Path finished!")



    #phase: consturct walls along path
    if CPGen >= 0:
        x = finishingpoint[0]
        y = finishingpoint[1]
        visited = []
        tries = 0

        if grid[x][y].mark == True:
            while (x != startingpoint[0] or y != startingpoint[1]) and tries<500:
                try:
                    xyvArr = analyzeSandBuildAWall(x,y,visited)
                except Exception as e:
                    global_err = True
                    print("YOU FAILED! EXCEPTION")

                x = xyvArr[0]
                y = xyvArr[1]
                visited = xyvArr[2]
                tries+=1
        #print("W a l l built")

    #Clearance
    if CPGen >= 0:
        for x in range(32):
            for y in range(32):
                grid[x][y].d = -1

        grid[finishingpoint[0]][finishingpoint[1]].mark = False

    return global_err


def generateRandomCheckpoint(sx,sy,ex,ey):
    gen = False
    while gen == False:
        checkpoint=[random.randint(sx,ex),random.randint(sy,ey)]
        if grid[checkpoint[0]][checkpoint[1]].val == 0:
                #print("found checkpoint ", checkpoint)
                #print("it's val is ", grid[checkpoint[0]][checkpoint[1]].val)
                gen = True

    return checkpoint



orderMatrices = [
                 [1,2,3,6,5,4,7,8,9],
                 [1,2,6,5,4,7,8,9],
                 [1,4,7,8,5,2,3,6,9],
                 [1,4,5,2,3,6,8,9],
                 [1,4,7,5,3,6,8,9],
                 [1,2,3,5,7,8,6,9],
                 [1,2,5,4,7,8,6,9],
                 [1,5,8,6,9]
                 ]




def completeCheckpoints():
    errors = []
    #def Action():
    checkpoints = []
    ABreak = False
    CPGen = 0
    order = orderMatrices[random.randint(0,len(orderMatrices)-1)]

    def getBorderCoords(x):
        if x==1:
            return [[0,0],[11,11]]
        if x==2:
            return [[12,2],[21,11]]
        if x == 3:
            return [[22,2],[31,11]]
        if x == 4:
            return [[1,12],[11,21]]
        if x == 5:
                return [[12,12],[21,21]]
        if x == 6:
                return [[22,12],[31,21]]
        if x == 7:
            return [[1,22],[11,30]]
        if x == 8:
            return [[12,22],[21,30]]
        if x == 9:
            return [[22,22],[30,30]]


    for i in range(len(order)):
        cur_index = order[i]
        da = getBorderCoords(cur_index)
        sx = da[0][0]
        sy = da[0][1]
        ex = da[1][0]
        ey = da[1][1]

        #print("Generating checkpoint at border num ",cur_index)
        checkpoints.append(generateRandomCheckpoint(sx,sy,ex,ey))
        if random.randint(0,100) <= 15:
            checkpoints.append(generateRandomCheckpoint(sx,sy,ex,ey))
            print("Checkpoint mutated!")

        #LeesAlg(sp,[60,56], CPGen)
        #LeesAlg([60,56],[31,31], CPGen)

    errors.append(LeesAlg(sp,checkpoints[0], CPGen))
                #ABreak = True

    CPGen+=1
    #print("Chose random order:", order)

        #if ABreak == False:
    for i in range(len(checkpoints)-1):
        errors.append(LeesAlg(checkpoints[i],checkpoints[i+1],CPGen))
        CPGen += 1

    errors.append(LeesAlg(checkpoints[i+1],fp,CPGen))

    return errors
             #   ABreak = True

        #return ABreak

    #while Action() == True:
    #Action()


Stop = False

while Stop == False:
    grid = [[Cell() for i in range(32)] for j in range(32)] # list comprehension
    grid[sp[0]][sp[1]].val = "start"

    drawRandomObstacles()
    drawProtected()
    errors = completeCheckpoints()

    if True not in errors:
        Stop = True

#LeesAlg(checkpoint,finishingpoint)


    # integer division is good here!