import pygame
import random
import sys
import random

def buildRelationships(nodeList):
    for a in nodeList:
        for b in a:
            for w in b.wallList:
                if w != None:
                    w.attachedNodes.append(b)


class Wall:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.weight = random.randint(0, 10)
        self.attachedNodes = []

    def startFinish(self):
        return (str(self.start) + " -> " + str(self.end))


class Grid:
    def __init__(self, n):
        self.walls = []
        for y in range(n + 1):
            for x in range(n):
                self.walls.append(Wall((x, y), (x + 1, y)))

            if y < n:
                for x in range(n + 1):
                    self.walls.append(Wall((x, y), (x, y + 1)))


class DualWall:
    def __init__(self, weight, ref):
        self.weight = weight
        self.ref = ref
        self.attachedNodes = []


class DGrid:
    def __init__(self, n, walls):
        self.dWalls = []
        for a in range(n + 1):
            for b in range(n):
                self.dWalls.append(DualWall(walls[(a * ((2 * (n + 1)) + 1) + (n + 1) + 1 + b)].weight,
                                            walls[(a * ((2 * (n + 1)) + 1) + (n + 1) + 1 + b)]))
            if a < n:
                for b in range(n + 1):
                    self.dWalls.append(DualWall(walls[((a + 1) * ((2 * (n + 1)) + 1) + b)].weight,
                                                walls[((a + 1) * ((2 * (n + 1)) + 1) + b)]))


class Node:
    def __init__(self, top, left, right, bottom):
        self.top = top
        self.left = left
        self.right = right
        self.bottom = bottom
        self.wallList = [self.top, self.left, self.right, self.bottom]


class NodeList:
    def __init__(self, n, walls):
        self.nodes = []
        for a in range(n):
            self.nodes.append([])
            for b in range(n):
                if a == 0:
                    top = None
                else:
                    top = walls[(a - 1) * ((2 * (n - 1)) + 1) + b + (n - 1)]

                if a == n - 1:
                    bottom = None
                else:
                    bottom = walls[(a * ((2 * (n - 1)) + 1) + b + (n - 1))]

                if b == 0:
                    left = None
                else:
                    left = walls[(a * ((2 * (n - 1)) + 1) + b - 1)]

                if b == n - 1:
                    right = None
                else:
                    right = walls[(a * ((2 * (n - 1)) + 1) + b)]

                self.nodes[a].append(Node(top,
                                          left,
                                          right,
                                          bottom))

def draw_map(surface,Grid_object,width):
    for wall in Grid_object.walls:
        start = wall.start
        end = wall.end
        pygame.draw.line(surface, (255, 255, 255), (start[0]*width + center, start[1]*width + center), (end[0]*width + center, end[1]*width + center))

def remove(surface,wall):
    start = wall.start
    end = wall.end
    pygame.draw.line(surface, (0,0,0) ,(start[0]*width + center, start[1]*width + center), (end[0]*width + center, end[1]*width + center) )

class Maze:
    def __init__(self, n):
        self.n = n
        self.mainGrid = Grid(n)
        self.dualGrid = DGrid(n - 1, self.mainGrid.walls)
        self.vertices = NodeList(n, self.dualGrid.dWalls).nodes
        buildRelationships(self.vertices)
        self.mainVert = NodeList(n + 1, self.mainGrid.walls).nodes
        buildRelationships(self.mainVert)



        start_finish_index = random.randint(0, n-1)
        self.mainGrid.walls.pop(start_finish_index)
        self.mainGrid.walls.pop(-(start_finish_index + 1))




        availableWalls = []
        visitedNodes = []
        currentNode = random.choice(random.choice(self.vertices))
        while (True):
            for w in currentNode.wallList:
                if w != None:
                    availableWalls.append(w)

            visitedNodes.append(currentNode)

            lowestWall = None
            for x in availableWalls:
                if lowestWall != None:
                    if x.weight < lowestWall.weight:
                        lowestWall = x
                else:
                    lowestWall = x

            nip = lowestWall.attachedNodes
            for x in nip:
                if x not in visitedNodes:
                    nextNode = x

            print(availableWalls)
            for x in availableWalls:
                print(x.weight)
            print("LW: " + str(lowestWall.weight))


            print("AW: " + str(availableWalls))
            print("LW: " + str(lowestWall))
            print("REF: " + str(lowestWall.ref))
            print("LIST: " + str(self.mainGrid.walls))

            availableWalls.remove(lowestWall)
            self.mainGrid.walls.remove(lowestWall.ref)
            self.dualGrid.dWalls.remove(lowestWall)


            print(visitedNodes)
            print("NL: " + str(lowestWall.attachedNodes))

            if nextNode == currentNode:
                break
            nextNode.wallList.remove(lowestWall)

            print('----------------')


            currentNode = nextNode

            print(nextNode)



n = 40

pygame.init()
sizeX = 1200
sizeY = 1200
grid_size = n
width = 25
running = True
center = (sizeX - width*grid_size)/2
screen = pygame.display.set_mode((sizeX,sizeY))


maze = Maze(n)
grid = maze.mainGrid

pygame.display.set_caption("Maze")

draw_map(screen, grid, width)

while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False
            pygame.display.quit()
            pygame.quit()
            sys.exit()
    pygame.display.update()