# Maze backtracking example
# Last updated 11/7/22

from cmu_112_graphics import * 
import random
import math



#--------Backtracking solver--------------------------------------------

def solveMaze(app):
    visited = set()
    path = []
    return solve(app, path, visited, 0,0), visited

def solve(app, path, visited, row, col):
    maze = app.maze
    rows, cols = len(maze), len(maze[0])
    targetRow, targetCol = rows-1, cols-1

    # Base case: Return None if we've already been here
    if (row, col) in visited:  
        return None

    # Add the new location
    visited.add((row, col))
    path.append((row, col))

    # Base case: Return visited if we found the solution
    if (row, col)==(targetRow, targetCol): 
        return path

    # Recursive case: Search through next valid directions
    else:
        for drow, dcol in [app.north, app.south, app.east, app.west]:
            if isValid(app, row, col, (drow, dcol)):
                result = solve(app, path, visited, row+drow, col+dcol)
                if result != None:
                    return result

    # Backtrack if no solution found
    #visited.remove((row, col))
    path.pop()
    return None

def isValid(app, row, col, direction):
    # Check if a path exists from this location in this direction
    maze = app.maze
    rows, cols = len(maze), len(maze[0])
    if not (0<=row<rows and 0<=col<cols): return False
    if direction == app.east: 
        return maze[row][col].east
    if direction == app.south: 
        return maze[row][col].south
    if direction == app.west: 
        return maze[row][col-1].east
    if direction == app.north: 
        return maze[row-1][col].south
    assert False



#--------Player controls-------------------------------------------------

def keyPressed(app, event):
    row, col = app.playerSpot
    if app.inHelpScreen:
        app.inHelpScreen = False
    elif event.key == "+":
        reset(app, app.rows+1, app.cols+1, False)
    elif event.key == "-":
        reset(app, app.rows-1, app.cols-1, False)
    elif event.key == "r":
        reset(app, app.rows, app.cols, False)
    elif event.key == "h":
        app.inHelpScreen = True
    elif event.key == "c":
        app.isPolar = not app.isPolar
    elif event.key == "s":
        #toggle solution
        if app.solution == None:
            app.solution, app.searched = solveMaze(app)
        else:
            app.solution = None
    elif event.key == "Up" and isValid(app, row, col, app.north):
        doMove(app, row,col,app.north)
    elif event.key == "Down" and isValid(app, row, col, app.south):
        doMove(app, row,col,app.south)
    elif event.key == "Left" and isValid(app, row, col, app.west):
        doMove(app, row,col,app.west)
    elif event.key == "Right" and isValid(app, row, col, app.east):
        doMove(app, row, col, app.east)


def doMove(app, row, col, direction):
    (drow, dcol) = direction
    maze, path = app.maze, app.path
    rows, cols = len(maze), len(maze[0])
    if not (0<=row<rows and 0<=col<cols): 
        return False
    if ((row+drow, col+dcol)) in path: 
        path.remove((row, col))
    else: 
        path.add((row+drow, col+dcol))
    app.playerSpot = (row+drow, col+dcol)



####### You may safely ignore everything below here! ####################

#--------Maze generator-------------------------------------------------
def appStarted(app):
    app.north = (-1,0)
    app.south = (1,0)
    app.east  = (0,1)
    app.west  = (0,-1)
    app.islandColor = "dark green"
    app.bridgeColor = "white"
    app.pathColor = "blue"
    app.playerColor = "green"
    app.solutionColor = "red"
    app.margin = 5
    rows = 10
    cols = 10
    inHelpScreen = True
    app.isPolar = False
    reset(app, rows, cols, inHelpScreen)

def reset(app, rows, cols, inHelpScreen):
    if (rows < 1): rows = 1
    if (cols < 1): cols = 1
    app.inHelpScreen = inHelpScreen
    app.rows = rows
    app.cols = cols

    app.path = set()
    app.solution = None
    app.searched = None
    app.playerSpot = (0,0)
    app.path.add(app.playerSpot)
    app.cW = (app.width - app.margin)/cols
    app.cH = (app.height - app.margin)/rows
    #make the islands
    app.maze = makeBlankMaze(rows,cols)
    #connect the islands
    connectIslands(app.maze)

class Island():
    def __init__(self, number):
        self.east = False
        self.south = False
        self.number = number

def makeBlankMaze(rows,cols):
    islands = [[0]*cols for row in range(rows)]
    counter = 0
    for row in range(rows):
        for col in range(cols):
            islands[row][col] = Island(counter)
            counter += 1
    return islands

def connectIslands(islands):
    rows, cols = len(islands), len(islands[0])
    for i in range(rows*cols-1):
        makeBridge(islands)

def makeBridge(islands):
    rows, cols = len(islands), len(islands[0])
    while True:
        row, col = random.randint(0, rows-1), random.randint(0, cols-1)
        start = islands[row][col]
        if flipCoin(): #try to go app.east
            if col == cols-1: 
                continue
            target = islands[row][col+1]
            if start.number == target.number: 
                continue
            #the bridge is valid, so 1. connect them and 2. rename them
            start.east = True
            renameIslands(start, target, islands)
        else: #try to go app.south
            if row == rows-1: 
                continue
            target = islands[row+1][col]
            if start.number == target.number: 
                continue
            #the bridge is valid, so 1. connect them and 2. rename them
            start.south = True
            renameIslands(start, target, islands)
        #only got here if a bridge was made
        return

def renameIslands(i1,i2,islands):
    n1, n2 = i1.number, i2.number
    lo, hi = min(n1, n2), max(n1, n2)
    for row in islands:
        for island in row:
            if island.number == hi: 
                island.number = lo

def flipCoin():
    return random.choice([True, False])



#--------View / redrawAll-------------------------------------------------

def redrawAll(app, canvas):
    if app.inHelpScreen: 
        drawHelpScreen(app, canvas)
    else:
        canvas.create_rectangle(0, 0, app.width, app.height, fill = "black")
        drawBridges(app, canvas)
        drawIslands(app, canvas)

        if app.solution!=None:
            drawSolutionPath(app, canvas, app.searched, 'yellow')
            drawSolutionPath(app, canvas, app.solution, 'red')

        drawPlayerPath(app, canvas)

def drawHelpScreen(app, canvas):
    font = "Helvetica 32 bold"
    canvas.create_text(300, 50, text="Maze Solver", font=font)
    font = "Helvetica 24 bold"
    messages = [
                "arrows to solve manually",
                "r to reset (make new maze)",
                "s to toggle solution on/off",
                "c to toggle circular (polar) on/off",
                "+ to increase maze size",
                "- to decrease maze size",
                "h to view this help screen",
                "press any key to continue"
                ]
    for i in range(len(messages)):
        canvas.create_text(300, 150+50*i, text=messages[i], font=font)

def drawIslands(app, canvas):
    islands = app.maze
    rows, cols = len(islands), len(islands[0])
    color = app.islandColor
    r = min(app.cW, app.cH)/6
    for row in range(rows):
        for col in range(cols):
            drawCircle(canvas, islandCenter(app, row, col), r, color)

def drawCircle(canvas, position, r, color):
    (cx, cy) = position
    canvas.create_oval(cx-r, cy-r, cx+r, cy+r, fill=color, width=0)

def islandCenter(app, row, col):
    if app.isPolar:
        cx, cy = app.width/2, app.height/2
        rows, cols = len(app.maze), len(app.maze[0])
        maxR = min(cx, cy)
        r = maxR*(row+1)/(rows+1)
        theta = 2*math.pi*col/cols
        return cx+r*math.cos(theta), cy-r*math.sin(theta)
    else:
        cellWidth, cellHeight = app.cW, app.cH
        return (col+0.5)*cellWidth, (row+0.5)*cellHeight

def drawBridges(app, canvas):
    islands = app.maze
    rows, cols = len(islands), len(islands[0])
    color = app.bridgeColor
    width = min(app.cW, app.cH)/15
    for r in range(rows):
        for c in range(cols):
            island = islands[r][c]
            if (island.east):
                canvas.create_line(islandCenter(app, r, c),
                                   islandCenter(app, r, c+1),
                                   fill=color, width=width)
            if (island.south):
                canvas.create_line(islandCenter(app, r, c),
                                   islandCenter(app, r+1, c),
                                   fill=color, width=width)

def drawPlayerPath(app, canvas):
    path = app.path
    (pRow, pCol) = app.playerSpot
    color = app.pathColor
    r = min(app.cW, app.cH)/6
    width = min(app.cW, app.cH)/15
    for (row, col) in path:
        drawCircle(canvas, islandCenter(app, row, col), r, color)
        if (row+1, col) in path and isValid(app, row, col, app.south):
            canvas.create_line(islandCenter(app, row, col),
                                   islandCenter(app, row+1, col),
                                   fill=color, width=width)
        if (row,col+1) in path and isValid(app, row, col, app.east):
            canvas.create_line(islandCenter(app, row, col),
                                   islandCenter(app, row, col+1),
                                   fill=color, width=width)
    drawCircle(canvas, islandCenter(app, pRow, pCol), r, app.playerColor)
    
def drawSolutionPath(app, canvas, path, color = 'red'):
    #color = app.solutionColor
    r = min(app.cW, app.cH)/6
    width = min(app.cW, app.cH)/15
    for (row, col) in path:
        drawCircle(canvas, islandCenter(app, row, col), r, color)
        if (row+1, col) in path and isValid(app, row, col, app.south):
            canvas.create_line(islandCenter(app, row, col),
                                   islandCenter(app, row+1, col),
                                   fill=color, width=width)
        if (row, col+1) in path and isValid(app, row, col, app.east):
            canvas.create_line(islandCenter(app, row, col),
                                   islandCenter(app, row, col+1),
                                   fill=color, width=width)

#---------------------------------------------------------

runApp(width = 600, height = 600)