from cell import Cell
import time
import random

class Maze:
    def __init__(
            self,
            x1,
            y1,
            num_rows,
            num_cols,
            cell_size_x,
            cell_size_y,
            win=None,
            seed=None
    ):
        self._cells = []
        self._x1 = x1
        self._y1 = y1
        self._num_rows = num_rows
        self._num_cols = num_cols
        self._cell_size_x = cell_size_x
        self._cell_size_y = cell_size_y
        self._win = win
        if seed:
            random.seed(seed)

        self._create_cells()
        self._break_entrance_and_exit()
        self._rec_break_walls(0, 0)
        self._reset_cells_visited()

    def _create_cells(self):
        self._cells = [[Cell(self._win) for i in range(self._num_rows)] for j in range(self._num_cols)]
        # for i in range(self._num_cols):
        #     col_cells = []
        #     for j in range(self._num_rows):
        #         col_cells.append(Cell(self._win))
        #     self._cells.append(col_cells)
        
        [[self._draw_cell(i, j) for j in range(self._num_rows)] for i in range(self._num_cols)]
        # for i in range(self._num_cols):
        #     for j in range(self._num_rows):
        #         self._draw_cell(i, j)

    def _draw_cell(self, i, j):
        if self._win is None:
            return
        x1 = self._x1 + i * self._cell_size_x
        y1 = self._y1 + j * self._cell_size_y
        x2 = x1 + self._cell_size_x
        y2 = y1 + self._cell_size_x
        self._cells[i][j].draw(x1, y1, x2, y2)
        self._animate()

    def _animate(self):
        self._win.redraw()
        time.sleep(0.01)

    def _break_entrance_and_exit(self):
        self._cells[0][0].twall = False
        self._draw_cell(0, 0)
        self._cells[-1][-1].bwall = False
        self._draw_cell(self._num_cols-1, self._num_rows-1)

    def _rec_break_walls(self, i, j):
        self._cells[i][j].visited = True

        while True:
            next_index = []
            # look for next cell to visit
            # left
            if i > 0 and not self._cells[i - 1][j].visited:
                next_index.append((i - 1, j))
            # up
            if j > 0 and not self._cells[i][j - 1].visited:
                next_index.append((i, j - 1))
            # right
            if i < self._num_cols - 1 and not self._cells[i + 1][j].visited:
                next_index.append((i + 1, j))
            # down
            if j < self._num_rows - 1 and not self._cells[i][j + 1].visited:
                next_index.append((i, j + 1))

            # if no further cell to go, then draw and return
            if len(next_index) == 0:
                self._draw_cell(i, j)
                return

            # choose next direction to go in
            direction_index = random.randrange(len(next_index))
            next = next_index[direction_index]

            # break walls between this and next cell
            # left
            if next[0] == i - 1:
                self._cells[i][j].lwall = False
                self._cells[i - 1][j].rwall = False
            # up
            if next[1] == j - 1:
                self._cells[i][j].twall = False
                self._cells[i][j - 1].bwall = False
            # right
            if next[0] == i + 1:
                self._cells[i][j].rwall = False
                self._cells[i + 1][j].lwall = False
            # down
            if next[1] == j + 1:
                self._cells[i][j].bwall = False
                self._cells[i][j + 1].twall = False

            self._rec_break_walls(next[0], next[1])

    def _reset_cells_visited(self):
        for col in self._cells:
            for cell in col:
                cell.visited = False

    def _rec_solve(self, i, j):
        self._animate()
        
        self._cells[i][j].visited = True
        
        if i == self._num_cols - 1 and j == self._num_rows - 1:
            return True

        # try moving left
        if (
                i > 0
                and not self._cells[i][j].lwall
                and not self._cells[i - 1][j].visited
        ):
            self._cells[i][j].draw_move(self._cells[i - 1][j])
            if self._rec_solve(i - 1, j):
                return True
            else:
                self._cells[i][j].draw_move(self._cells[i - 1][j], True)
        # try moving up
        if (
                j > 0
                and not self._cells[i][j].twall
                and not self._cells[i][j - 1].visited
        ):
            self._cells[i][j].draw_move(self._cells[i][j - 1])
            if self._rec_solve(i, j - 1):
                return True
            else:
                self._cells[i][j].draw_move(self._cells[i][j - 1], True)
        # try moving right
        if (
                i < self._num_cols - 1
                and not self._cells[i][j].rwall
                and not self._cells[i + 1][j].visited
        ):
            self._cells[i][j].draw_move(self._cells[i + 1][j])
            if self._rec_solve(i + 1, j):
                return True
            else:
                self._cells[i][j].draw_move(self._cells[i + 1][j], True)
        # try moving down
        if (
                j < self._num_rows - 1
                and not self._cells[i][j].bwall
                and not self._cells[i][j + 1].visited
        ):
            self._cells[i][j].draw_move(self._cells[i][j + 1])
            if self._rec_solve(i, j + 1):
                return True
            else:
                self._cells[i][j].draw_move(self._cells[i][j + 1], True)

        # went wrong way -> backtrack
        return False

    def solve(self):
        return self._rec_solve(0, 0)