import random, time, math
from tkinter import *
from queue import PriorityQueue, Queue

class Maze:
    """
    An object representing a maze that features various path-finding algorithims
    to solve it.
    
    Attributes:
        root (root): The root in which everything happens.
        canvas (canvas): The canavs to draw everything on.
        size (int): The width/height of the maze.
        cell_size (int): The width/height of the individual cells.
        handles (list): A list of handles referring to the objects drawn onto
            the canvas.
        delay (int): The delay used between drawing each square to give the
            illusion of motion when path-finding.
        start (tuple): A tuple of ints representing the starting point in the
            maze
        end (tuple): A tuple of ints representing the ending point in the maze
        visited_cells (list): A two-dimensional list of booleans indicating 
            whether or not the specified cell has been visited yet.
        cell_north_wall (list): A two-dimensional list of booleans indicating
            whether or not the specified cell has a wall to its north side.
        cell_east_wall (list): A two-dimensional list of booleans indicating
            whether or not the specified cell has a wall to its east side.
        cell_south_wall (list): A two-dimensional list of booleans indicating
            whether or not the specified cell has a wall to its south side.
        cell_west_wall (list): A two-dimensional list of booleans indicating
            whether or not the specified cell has a wall to its west side.
        cell_distances (list): A two-dimensional list of ints (and sometimes
            doubles) representing the current shortest path from the starting
            cell to each cell. Used in Dijkstra's Algorithm and A* search.
        solved_path (list): A list of tuples representing the cells crossed in
            the solution generated by the path finding algorithim.
        solved (boolean): whether or not the maze has been solved yet.
    """
    
    def __init__(self, root, canvas, size, delay, **kw):
        """
        Creates a new maze instance.
        
        Arguments:
            root (root): The root of the maze.
            canvas (canvas): The canvas of the maze.
            size (int): The width/height of the maze.
            delay (int): The delay used between drawing each square to give the
            illusion of motion when path-finding.
            kw arguments:
                start (tuple): An int tuple representing the starting position
                    of the maze.
                end (tuple): An int tuple representing the ending position
                    of the maze.
        """
        assert "start" in kw.keys() and "end" in kw.keys()
        assert type(kw["start"]) == tuple and type(kw["end"]) == tuple
        self.start = kw["start"]
        self.end = kw["end"]
        
        
        self.root = root
        self.canvas = canvas
        self.size = size
        self.cell_size = 600 / size
        self.delay = delay
        self.handles = []
        self.visited_cells = [[False for i in range(size + 2)] for j in range(size + 2)]
        
        self.visited_cells[0] = [True] * (size + 2)
        self.visited_cells[size + 1] = [True] * (size + 2)
        for i in range(size + 2):
            self.visited_cells[i][0] = True
            self.visited_cells[i][size + 1] = True
        
        self.cell_north_wall = [[True for i in range(size + 2)] for j in range(size + 2)]
        self.cell_east_wall = [[True for i in range(size + 2)] for j in range(size + 2)]
        self.cell_south_wall = [[True for i in range(size + 2)] for j in range(size + 2)]
        self.cell_west_wall = [[True for i in range(size + 2)] for j in range(size + 2)]
        self.solved_path = []
        self.solved = False
        
        self.cell_distances = [[size ** 2 for i in range(size + 2)] for j in range(size + 2)]
        self.cell_distances[self.start[0]][self.start[1]] = 0
        
        
    def new_maze(self):
        """
        Creates a new maze by changing the arrangement of walls. It does this by
        setting every wall to exist and then calling "create_maze" which
        destroys some of them. In theory this results in a solvable maze 100%
        of the time.
        """
        self.start = random_coord(self.size)
        self.end = random_coord(self.size)
        
        
        self.handles = []
        self.canvas.delete("all")
        self.visited_cells = [[False for i in range(self.size + 2)] for j in range(self.size + 2)]
        
        self.visited_cells[0] = [True] * (self.size + 2)
        self.visited_cells[self.size + 1] = [True] * (self.size + 2)
        for i in range(self.size + 2):
            self.visited_cells[i][0] = True
            self.visited_cells[i][self.size + 1] = True
        
        self.cell_north_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.cell_east_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.cell_south_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.cell_west_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.solved_path = []
        self.solved = False        
        self.create_maze(self.start[0], self.start[1])
        self.draw_maze()  
        
    def new_broken_maze(self):
        """
        Creates a new "broken maze" which is like the normal maze but it has 
        potnetially multiple paths to the ending cell.
        """
        self.start = random_coord(self.size)
        self.end = random_coord(self.size)
        
        
        self.handles = []
        self.canvas.delete("all")
        self.visited_cells = [[False for i in range(self.size + 2)] for j in range(self.size + 2)]
        
        self.visited_cells[0] = [True] * (self.size + 2)
        self.visited_cells[self.size + 1] = [True] * (self.size + 2)
        for i in range(self.size + 2):
            self.visited_cells[i][0] = True
            self.visited_cells[i][self.size + 1] = True
        
        self.cell_north_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.cell_east_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.cell_south_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.cell_west_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.solved_path = []
        self.solved = False        
        self.create_broken_maze(self.start[0], self.start[1])
        self.draw_maze()          
    
    def new_empty_maze(self):
        """
        Creates an "empty maze" which is a board with no walls in the way.
        """
        self.start = random_coord(self.size)
        self.end = random_coord(self.size)
        
        
        self.handles = []
        self.canvas.delete("all")
        self.visited_cells = [[False for i in range(self.size + 2)] for j in range(self.size + 2)]
        
        self.visited_cells[0] = [True] * (self.size + 2)
        self.visited_cells[self.size + 1] = [True] * (self.size + 2)
        for i in range(self.size + 2):
            self.visited_cells[i][0] = True
            self.visited_cells[i][self.size + 1] = True
        
        self.cell_north_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.cell_east_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.cell_south_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.cell_west_wall = [[True for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.solved_path = []
        self.solved = False       
        
        for i in range(1, self.size + 1):
            for j in range(1, self.size + 2):
                if j != 1:
                    self.cell_north_wall[i][j] = False
                if i != 1:
                    self.cell_west_wall[i][j] = False
                if j != self.size:
                    self.cell_south_wall[i][j] = False
                if i != self.size:
                    self.cell_east_wall[i][j] = False
                
        self.draw_maze()          
    
    
    def create_maze(self, x, y):
        """
        Recursively creates the maze by randomly destroying walls. As long as
        there are unvisited cells it randomly destorys at least two walls in a
        cell and marks it as visited. It will not revisit visited cells.
        
        Arguments:
            x (int): The x coordinate of the current position.
            y (int): The y coordinate of the current position.
        """
        
        self.visited_cells[x][y] = True
        
        while not self.visited_cells[x][y + 1]\
	      or not self.visited_cells[x + 1][y]\
	      or not self.visited_cells[x][y - 1]\
              or  not self.visited_cells[x - 1][y]:
            r = random.choice("nesw")
            if r == "s" and not self.visited_cells[x][y + 1]:
                self.cell_south_wall[x][y] = False
                self.cell_north_wall[x][y + 1] = False              
                self.create_maze(x, y + 1)
                
            elif r == "e" and not self.visited_cells[x + 1][y]:
                self.cell_east_wall[x][y] = False
                self.cell_west_wall[x + 1][y] = False
                self.create_maze(x + 1, y)
                
            elif r == "n" and not self.visited_cells[x][y - 1]:
                self.cell_north_wall[x][y] = False
                self.cell_south_wall[x][y - 1] = False
                self.create_maze(x, y - 1)
                
            elif r == "w" and not self.visited_cells[x - 1][y]:
                self.cell_west_wall[x][y] = False
                self.cell_east_wall[x - 1][y] = False
                self.create_maze(x - 1, y)
            
    def create_broken_maze(self, x, y):
        """
        Similar to create_maze but it can revisit visited cells. It still runs
        until every cell has been visited.
        
        Arguments:
            x (int): The x coordinate of the current position.
            y (int): The y coordinate of the current position.
        """
        self.visited_cells[x][y] = True
        
        while not self.visited_cells[x][y + 1]\
	      or not self.visited_cells[x + 1][y]\
	      or not self.visited_cells[x][y - 1]\
              or  not self.visited_cells[x - 1][y]:
            r = random.choice("nesw")
            
            if r == "s" and y + 1 in range(1, size + 1):
                self.cell_south_wall[x][y] = False
                self.cell_north_wall[x][y + 1] = False              
                self.create_broken_maze(x, y + 1)
                
            elif r == "e" and x + 1 in range(1, size + 1):
                self.cell_east_wall[x][y] = False
                self.cell_west_wall[x + 1][y] = False
                self.create_broken_maze(x + 1, y)
                
            elif r == "n" and y - 1 in range(1, size + 1):
                self.cell_north_wall[x][y] = False
                self.cell_south_wall[x][y - 1] = False
                self.create_broken_maze(x, y - 1)
                
            elif r == "w" and x - 1 in range(1, size + 1):
                self.cell_west_wall[x][y] = False
                self.cell_east_wall[x - 1][y] = False
                self.create_broken_maze(x - 1, y)             
        
    def fill_cell(self, x, y, **kw):
        """
        Draws a colored square in the grid at the given coordinates.
        
        Arguments:
            x (int): The x coordinate.
            y (int): The y coordinate.
            kw arguments:
                color (str): The color of the square.
        """
        assert len(kw) == 1
        assert "color" in kw.keys()
        if kw["color"] == "blue":
            c = "#1f5ba7"
        elif kw["color"] == "gray":
            c = "#b7adae"
        elif kw["color"] == "red":
            c = "#ff0000"
        elif kw["color"] == "green":
            c = "#10b07a"        
        elif kw["color"] == "yellow":
            c = "#ebeb32"
        else:
            c - kw["color"]
        
        x1 = 100 + (self.cell_size * (x - 1)) + 5
        y1 = 100 + (self.cell_size * (y - 1)) + 5
        x2 = 100 + (self.cell_size * (x)) - 5
        y2 = 100 + (self.cell_size * (y)) - 5
        handle = self.canvas.create_rectangle(x1, y1, x2, y2,
                        fill=c, outline=c)
        
        self.handles.append(handle)
    
    def draw_maze(self):
        """
        Draw the walls of the maze and the starting and ending cells.
        """
        self.fill_cell(self.end[0], self.end[1], color = "red")
        self.fill_cell(self.start[0], self.start[1], color = "green")        
        
        
        line_color = "#000000"
        for i in range(1, self.size + 1):
            for j in range(1, self.size + 1):
                time.sleep(.001)
                self.root.update()
                
                if self.cell_north_wall[i][j]:
                    x1 = 100 + (self.cell_size * (i - 1))
                    x2 = 100 + (self.cell_size * (i))
                    y = 100 + (self.cell_size * (j - 1))
                    self.canvas.create_line(x1, y, x2, y, fill = line_color,\
                                            width = self.cell_size / 10)
                    
                if self.cell_east_wall[i][j]:
                    x = 100 + (self.cell_size * (i))
                    y1 = 100 + (self.cell_size * (j - 1))
                    y2 = 100 + (self.cell_size * (j))
                    self.canvas.create_line(x, y1, x, y2, fill = line_color,\
                                            width = self.cell_size / 10)
                    
                if self.cell_south_wall[i][j]:
                    x1 = 100 + (self.cell_size * (i - 1))
                    x2 = 100 + (self.cell_size * (i))
                    y = 100 + (self.cell_size * (j))
                    self.canvas.create_line(x1, y, x2, y, fill = line_color,\
                                            width = self.cell_size / 10)
                    
                if self.cell_west_wall[i][j]:
                    x = 100 + (self.cell_size * (i - 1))
                    y1 = 100 + (self.cell_size * (j - 1))
                    y2 = 100 + (self.cell_size * (j))
                    self.canvas.create_line(x, y1, x, y2, fill = line_color,\
                                            width = self.cell_size / 10)
                
            
    def dfs(self):
        """
        Solve the maze using depth-first search.
        """
        self.clear()
        self.solved = False
        self.visited_cells = [[False for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.solve_maze_dfs(self.start[0], self.start[1])
        self.show_path()
        
    
    def solve_maze_dfs(self, i, j):
        """
        Solves maze recursively using depth-first search. I used i and j because
        that's what we used in the APCS project this is based on.
        
        Arguments:
            i (int): The x coordinate of the current position.
            j (int): The y coordinate of the current position.
        """    
        if (i == 0 or j == 0 or i == self.size + 1 or j == self.size + 1):
            return
        if self.solved or self.visited_cells[i][j]:
            return
        self.visited_cells[i][j] = True;
        
        pos = (i, j)
        self.solved_path.append(pos)
        
        if not (i == self.end[0] and j == self.end[1]) \
           and not (i == self.start[0] and j == self.start[1]):
            self.fill_cell(i, j, color = "blue")
            time.sleep(self.delay)
            self.root.update()                

        if i == self.end[0] and j == self.end[1]:
            self.solved = True
        
        for neighbor in self.get_neighbors(pos):
            x2 = neighbor[0]
            y2 = neighbor[1]
            if not self.visited_cells[x2][y2]:
                self.solve_maze_dfs(x2, y2)

        if self.solved:
            return
        
        time.sleep(self.delay)
        self.root.update()         
        self.solved_path.remove(pos)
        self.fill_cell(i, j, color = "gray")
    
    def bfs(self):
        """
        Solve the maze using breadth-first search
        """
        self.clear()
        self.solved = False
        self.visited_cells = [[False for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.solve_maze_bfs()
        self.solved_path.reverse()
        self.show_path()
    
    def solve_maze_bfs(self):
        """
        Solves the maze iteratively using breadth-first search.
        """
        worklist = Queue()
        worklist.put(self.start)
        previous_cell = [[self.start for i in range(self.size + 2)] for j in range(self.size + 2)]
        seen = [[False for i in range(self.size + 2)] for j in range(self.size + 2)]
        seen[self.start[0]][self.start[1]] = True
        
        while not worklist.empty():
            curr = worklist.get()
            x = curr[0]
            y = curr[1]
            
            self.visited_cells[x][y] = True;
            
            if not (x == self.end[0] and y == self.end[1]) \
               and not (x == self.start[0] and y == self.start[1]):
                self.fill_cell(x, y, color = "blue")
                time.sleep(self.delay)
                self.root.update()                
    
            if x == self.end[0] and y == self.end[1]:
                self.solved = True
                break
            
            for neighbor in self.get_neighbors(curr):
                x2 = neighbor[0]
                y2 = neighbor[1]
                if not self.visited_cells[x2][y2] and not seen[x2][y2]:
                    worklist.put(neighbor)
                    previous_cell[x2][y2] = curr
                    seen[x2][y2] = True
            
        self.solved_path.append(self.end)
        current = previous_cell[self.end[0]][self.end[1]]
        while not current == self.start:
            self.solved_path.append(current)
            current = previous_cell[current[0]][current[1]]
        self.solved_path.append(self.start)
        
    
    def dijkstras(self):
        """
        Solve the maze using dijkstras algorithm.
        """
        self.clear()
        self.solved = False
        self.visited_cells = [[False for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.cell_distances = [[size ** 2 for i in range(size + 2)] for j in range(size + 2)]
        self.cell_distances[self.start[0]][self.start[1]] = 0
        self.solve_maze_dijkstras()
        
        self.solved_path.reverse()
        self.show_path()
    
    def solve_maze_dijkstras(self):
        worklist = PriorityQueue()
        for i in range(1, size + 1):
            for j in range(1, size + 1):
                if not self.visited_cells[i][j]:
                    worklist.put((self.cell_distances[i][j], (i, j)))
        
        previous_cell = [[self.start for i in range(self.size + 2)] for j in range(self.size + 2)]
        
        while not worklist.empty():
            current = worklist.get()[1]
            x = current[0]
            y = current[1]
            
            if current == self.end:
                self.solved = True
                break
            
            if not (x == self.end[0] and y == self.end[1]) \
               and not (x == self.start[0] and y == self.start[1]):
                self.fill_cell(x, y, color = "blue")        
            
                time.sleep(self.delay)
                self.root.update()
                
            for neighbor in self.get_neighbors(current):
                x2 = neighbor[0]
                y2 = neighbor[1]
                if not self.visited_cells[x2][y2]:
                    new_dist = self.cell_distances[x][y] + 1
                    old_dist = self.cell_distances[x2][y2]
                    if new_dist < old_dist:
                        self.cell_distances[x2][y2] = new_dist
                        previous_cell[x2][y2] = current
                        worklist.put((new_dist, neighbor))
            
            self.visited_cells[x][y] = True
            
        self.solved_path.append(self.end)
        current = previous_cell[self.end[0]][self.end[1]]
        while not current == self.start:
            self.solved_path.append(current)
            current = previous_cell[current[0]][current[1]]
        self.solved_path.append(self.start)            
            
            
    def a_star(self):
        """
        Solve the maze using A* Search.
        """
        self.clear()
        self.solved = False
        self.visited_cells = [[False for i in range(self.size + 2)] for j in range(self.size + 2)]
        self.cell_distances = [[size ** 4 for i in range(size + 2)] for j in range(size + 2)]
        self.cell_distances[self.start[0]][self.start[1]] = 0
        self.solve_maze_a_star()
        
        self.solved_path.reverse()
        self.show_path()         
    
    def solve_maze_a_star(self):
        worklist = PriorityQueue()
        for i in range(1, size + 1):
            for j in range(1, size + 1):
                if not self.visited_cells[i][j]:
                    worklist.put((self.cell_distances[i][j], (i, j)))
        
        previous_cell = [[self.start for i in range(self.size + 2)] for j in range(self.size + 2)]
        norm_cell_distances = [[size ** 4 for i in range(size + 2)] for j in range(size + 2)]
        norm_cell_distances[self.start[0]][self.start[1]] = 0           
        
        while not worklist.empty():
            current = worklist.get()[1]
            x = current[0]
            y = current[1]
            
            if current == self.end:
                self.solved = True
                break
            
            if not (x == self.end[0] and y == self.end[1]) \
               and not (x == self.start[0] and y == self.start[1]):
                self.fill_cell(x, y, color = "blue")        
            
                time.sleep(self.delay)
                self.root.update()
                
            for neighbor in self.get_neighbors(current):
                x2 = neighbor[0]
                y2 = neighbor[1]
                if not self.visited_cells[x2][y2]:
                    new_dist = norm_cell_distances[x][y] + 1 + self.dis((x2, y2), self.end)
                    old_dist = self.cell_distances[x2][y2]
                    if new_dist < old_dist:
                        self.cell_distances[x2][y2] = new_dist
                        norm_cell_distances[x2][y2] = norm_cell_distances[x][y] + 1
                        previous_cell[x2][y2] = current
                        worklist.put((new_dist, neighbor))                     
            
            self.visited_cells[x][y] = True
            
        self.solved_path.append(self.end)
        current = previous_cell[self.end[0]][self.end[1]]
        while not current == self.start:
            self.solved_path.append(current)
            current = previous_cell[current[0]][current[1]]
        self.solved_path.append(self.start)          
    
    
    def dis(self, start, end):
        """
        Calculates the distance between two points.
        
        Arguments:
            start (tuple): The first point.
            end (tuple): The second point.
            
        Returns:
            dis (double): The distance between the two points.
        """
        dis = abs((end[0] - start[0])) + abs((end[1] - start[1]))
        return dis
    
    
    def clear(self):
        """
        Clears the maze of all the blue and gray dots.
        """
        for i in range(2, len(self.handles)):
            self.canvas.delete(self.handles[i])
        self.handles = self.handles[:2]
        self.solved_path = []
        self.root.update()
    
    def show_path(self):
        """
        Shows the path created from the path-finding algorithim.
        """
        
        for i in range(1, len(self.solved_path)):
            previous = self.solved_path[i - 1]
            current = self.solved_path[i]
            x1 = 100 + (self.cell_size * (previous[0])) - self.cell_size / 2
            y1 = 100 + (self.cell_size * (previous[1])) - self.cell_size / 2
            x2 = 100 + (self.cell_size * (current[0])) - self.cell_size / 2
            y2 = 100 + (self.cell_size * (current[1]))  -  self.cell_size / 2         
            self.handles.append(self.canvas.create_line(x1, y1, x2, y2, fill = "#ebeb32", \
                                    width = self.cell_size / 2))

            time.sleep(self.delay)
            self.root.update()
            
        
    def get_neighbors(self, pos):
        """
        Returns a lsit of neighbors that can be accessed from a given point.
        
        Arguments:
            pos (tuple): the position.
            
        Returns:
            neighbors (list): a list of tuples represeing the neighbors.
        """
        neighbors = []
        x = pos[0]
        y = pos[1]
        
        if y - 1 in range(1, self.size + 1) and not self.cell_north_wall[x][y]:
            neighbors.append((x, y - 1))
        if y + 1 in range(1, self.size + 1) and not self.cell_south_wall[x][y]:
            neighbors.append((x, y + 1))     
        if x - 1 in range(1, self.size + 1) and not self.cell_west_wall[x][y]:
            neighbors.append((x - 1, y))
        if x + 1 in range(1, self.size + 1) and not self.cell_east_wall[x][y]:
            neighbors.append((x + 1, y))               
            
        return neighbors

#
# Helper Functions
#

def random_coord(size):
    """
    Generates a random coordinate in the range from 1 to size + 1.
    
    Arguments:
        size (int): The largest possible value.
        
    Returns:
        (tuple): The random coordinate
    """
    return (random.randrange(1, size + 1), random.randrange(1, size + 1))



if __name__ == "__main__":
    sys.setrecursionlimit(2000)
    root = Tk()
    root.geometry('800x800')
    buttons = Canvas(root, width = 800, height = 100)
    buttons.pack()
    canvas = Canvas(root, width=800, height=800)
    canvas.pack()
    
    size = 25
    delay = .02
    start = random_coord(size)
    center = (size // 2 + size % 2, size // 2 + size % 2)
    end = random_coord(size)
    
    m = Maze(root, canvas, size, delay, start = start, end = end)
    
    clear_button = Button(buttons, text = "Clear Maze", command = m.clear)
    clear_button.pack(side = LEFT)
    new_button = Button(buttons, text = "New Maze", command = m.new_maze)
    new_button.pack(side = LEFT)  
    new_broken_button = Button(buttons, text = "New Broken Maze", command = m.new_broken_maze)
    new_broken_button.pack(side = LEFT)    
    new_empty_button = Button(buttons, text = "New Empty Maze", command = m.new_empty_maze)
    new_empty_button.pack(side = LEFT)        
    dfs_button = Button(buttons, text = "Depth-first Search", command = m.dfs)
    dfs_button.pack(side = LEFT)  
    bfs_button = Button(buttons, text = "Breadth-first Search", command = m.bfs)
    bfs_button.pack(side = LEFT)      
    dijkstras_button = Button(buttons, text = "Dijkstras Algorithm", command = m.dijkstras)
    dijkstras_button.pack(side = LEFT)  
    a_star_button = Button(buttons, text = "A* Search", command = m.a_star)
    a_star_button.pack(side = LEFT)      
    
    m.create_maze(1, 1)
    m.draw_maze()
    
    root.mainloop()    
    
    