"""
 mazey.py

 This shows how graph traversal generates mazes, starting from a 2D
 checkerboard of vertices with horizontal and vertical edges
 connecting out in four directions.

 There are three version of the graph search : 

    breadth-first                  which gives long parallel paths
    depth-first                    which gives many fingers along each path
    random depth-first backtrack   which gives long tunnels

 The first two are both common ways to search graphs, but don't give
 the kind of mazes you'd typically find in a puzzle book. 

 See https://en.wikipedia.org/wiki/Maze_generation_algorithm
 for a description of various maze generation algorithms, including 
 the last one which is one that is used for generating mazes.

 The graph search code is in ./graphutils.py, along with an example
 and a few tests of the breadth-first and depth-first search.
 
 Python's turtle graphics are used to generate images of the search; 
 for their API see https://docs.python.org/3/library/turtle.html .

 Jim Mahoney | cs.bennington.college | MIT License | April 2021
"""
from random import shuffle
from graphutils import get_search_tree, random_backtrack_edges
from turtle import (setup, setworldcoordinates, degrees, speed,
                    colormode, pencolor, bgcolor, width, hideturtle,
                    setposition, setheading, mode, clear,
                    pendown, penup, pensize,
                    forward, backward, left, right)

def initialize_turtle_window(width=400, height=400,
                             xmin=0.0, xmax=10.0, ymin=0.0, ymax=10.0,
                             bg_color=(10,10,10),
                             color=(220,220,220)):
    """ initialize turtle graphics window and settings """
    # (0,0) is bottom left; (x,y) euclidian coords
    # pen will be down by default
    setup(width, height)   # Set window width & height (pixels)
    mode('standard')       # Set heading angles to be euclidian
    degrees(360)           # Set turtle orientation units to degrees.
    setworldcoordinates(xmin, ymin, xmax, ymax)
    colormode(255)         # Set color (r,g,b) units to (0 .. 255).
    speed(0)               # No animation. (1=slow,10=fast; 0=fastest)
    hideturtle()           # Don't show a shape for the turtle itself.
    bgcolor(bg_color)      # Set background color.
    moveto(xmax/2, ymax/2) # Put turtle at window center.
    pencolor(color)        

def initialize_maze(n, window_size=400, color='yellow'):
    """ initialize turtle window for an (n+1)x(n+1) maze """
    initialize_turtle_window(xmin=-1, ymin=-1, xmax=n+1, ymax=n+1,
                             width=window_size, height=window_size)
    linewidth = window_size/(n+1)/2
    pensize(linewidth)
    pencolor(color)
    
def args_to_xy(args):
    """ args is either (x,y) or ((x,y),); either way, return (x,y) """
    return args[0] if len(args)==1 else args

def turnto(angle):
    """ set turtle heading to given angle """
    setheading(angle)

def moveto(*args):
    """ move to position (x,y) without drawing a line; args is x,y or (x,y)"""
    (x,y) = args_to_xy(args)
    penup()
    setposition(x,y)
    pendown()

def lineto(*args):
    """ draw a line from current position to (x,y); args is x,y or (x,y)"""
    (x,y) = args_to_xy(args)
    setposition(x,y)
    
# -----------------------
# geometry & utility functions for 2D xy=(x,y) pairs
#
# xy is an (x,y) 2D point.
#
# The "grid" is a rectangular n x n grid of points,
# at x and y coordinates 0 through n, so for n = 2
#
#    2,0  2,1  2,2
#    1,0  1,1  1,2    n=2 grid
#    0,0  0,1  0,2
#
# The functions are 
#
#  name(point1)             a short identifying string for the point
#  add(vector1, vector2)    vector addition of two vectors (or points)
#  scale(s, vector)         scalar multiply, number times vector or point
#  in_grid(point, n)        True if point is within (0,0) to (n,n) grid
#  get_neighbors(xy, n)     return [p1, p2, ...] points adjacent to xy

(east, north, west, south) = (0, 90, 180, 270)    # four headings
offsets = ((0,1), (0,-1), (1,0), (-1,0))          # four directions

def name(xy): return f"{xy[0]},{xy[1]}"
def add(xy1, xy2): return (xy1[0]+xy2[0], xy1[1]+xy2[1])  # vector addition
def scale(s, xy): return (s*xy[0], s*xy[1])               # scalar multiply
def in_grid(xy, n): return xy[0]>=0 and xy[1]>=0 and xy[0]<=n and xy[1]<=n

def get_neighbor_points(xy, n):
    """ return points adjacent to xy within the 0 to (n-1) grid """
    # For example, neighbors of (0,0) are [(0,1), (1,0)]
    # At the edges of the grid, points have three neighbors.
    # At the corners, they have two neighbors.
    # And elsewhere each has four neighbors.
    neighbors = []
    for offset in offsets:
        neighbor = add(offset, xy)
        if in_grid(neighbor, n):
            neighbors.append(neighbor)
    return neighbors

def get_random_point(n):
    """ return a random point from an (n+1) x (n+1) grid of points """
    from random import randint
    return (randint(0,n+1), randint(0,n-1))

def get_grid(n):
    """ return tuple of (x,y) grid points, (0,0) <= (x,y) <= (n,n) """
    return tuple((x,y) for x in range(n+1) for y in range(n+1))

def draw_grid(n, color='red', linewidth=2, vertexsize=8, vertexcolor='blue'):
    linewidth = pensize()
    pensize(1)
    dx = 1/50
    pencolor(color)
    for x in range(0, n+1):
        moveto(x, 0)
        lineto(x, n)
    for y in range(0, n+1):
        moveto(0, y)
        lineto(n, y)
    pensize(linewidth)
    pencolor(vertexcolor)
    for x in range(0, n+1):
        for y in range(0,n+1):
            moveto(x, y)
            lineto(x, y)

# -- maze -----------------------------------------------------
#
# The idea is to start with a graph made up of
#  (a) vertices are points on a rectangular grid             A - B - C
#  (b) edges connect (up,down,left,right) points             |   |   |
# Then starting at a random point, we simply                 D - E - F
# do a depth-first search and use the tree of                |   |   |
# edges used as the maze : it will be simply                 G - H - I
# connected and acyclic.

def get_maze_edges(n, which):
    """ return edges [(xy1,xy2), (xy3,xy4),...] of an (n+1)x(n+1) maze """
    
    def random_order_neighbors(vertex):
        """ Given a vertex, return its neighbors in a random order. """
        # This is defined within get_maze so that it can see what n is.
        neighbors = get_neighbor_points(vertex, n)
        shuffle(neighbors)
        return neighbors

    def get_grid_neighbors(vertex):
        return get_neighbor_points(vertex, n)
    
    start = get_random_point(n)
    if which == 'depth':
        maze_edges = get_search_tree('depth', start, random_order_neighbors)
    elif which == 'breadth':
        maze_edges = get_search_tree('breadth', start, random_order_neighbors)
    else:
        maze_edges = random_backtrack_edges(start, get_grid_neighbors)
    return maze_edges

def draw_maze(n, which, color='yellow'):
    """ Draw a maze ! """
    edges = get_maze_edges(n, which)
    pencolor(color)
    for (point1, point2) in edges:
        moveto(point1)
        lineto(point2)
        
def main():
    n = 15
    initialize_maze(n, window_size=600)

    draw_grid(n, color='white', )
    wait = input("The graph grid: blue vertices and white edges. OK? ")

    clear()
    draw_maze(n, 'breadth', 'cyan')
    wait = input("The edges followed by breadth-first search. OK? ")

    clear()
    draw_maze(n, 'depth', 'magenta')
    wait = input("The edges followed by depth-first search. OK? ")
    
    clear()
    draw_maze(n, 'backtrack', 'yellow')
    wait = input("The edges followed by random depth-first backtrack. OK? ")
    
if __name__ == '__main__':
    main()