mazy.py

import tkinter as tk
import random


class Maze:
    def __init__(self, root):
        self.root = root
        self.size = 8
        self.w = self.size * 60
        self.h = self.size * 60
        self.canvas = tk.Canvas(self.root, width=self.w,
                                height=self.h, borderwidth=2, relief="solid")
        self.canvas.pack()
        self.cells = []
        self.current = None
        self.stack = []
        self.visited = 0
        self.done = False

    def build(self):
        for i in range(0, self.size):
            self.cells.append([])
            for j in range(0, self.size):
                self.cells[i].append(Cell(self.canvas, i, j, self.size))

    def cell_at(self, x, y):
        if x < 0 or y < 0 or x >= self.size or y >= self.size:
            return None
        return self.cells[x][y]

    def shuffle(self):
        import random
        neighbours = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        random.shuffle(neighbours)
        for n in neighbours:
            next = self.cell_at(self.current.x + n[0], self.current.y + n[1])
            if next and not next.visited:
                next.make_door(self.current)
                self.stack.append(self.current)
                self.current = next
                self.shuffle()

    def dfs(self):
        neighbours = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        random.shuffle(neighbours)
        for n in neighbours:
            next = self.cell_at(self.current.x + n[0], self.current.y + n[1])
            if next and not next.visited:
                next.make_door(self.current)
                self.stack.append(self.current)
                self.current = next
                self.visited += 1
                if self.visited == self.size * self.size:
                    self.done = True
                self.dfs()

    def bfs(self):
        queue = []
        queue.append(self.current)
        while len(queue) > 0:
            c = queue.pop(0)
            c.visited = True
            neighbours = [(0, -1), (0, 1), (-1, 0), (1, 0)]
            random.shuffle(neighbours)
            for n in neighbours:
                next = self.cell_at(c.x + n[0], c.y + n[1])
                if next and not next.visited:
                    next.make_door(c)
                    queue.append(next)

    def solve(self, algo):
        self.build()
        if algo == "dfs":
            self.current = self.cells[0][0]
            self.current.visited = True
            self.visited = 1
            self.dfs()
        elif algo == "bfs":
            self.current = self.cells[0][0]
            self.bfs()
        else:
            self.current = self.cells[0][0]
            self.shuffle()

    def draw(self):
        for i in range(0, self.size):
            for j in range(0, self.size):
                self.cells[i][j].draw()


class Cell:
    def __init__(self, canvas, x, y, size):
        self.canvas = canvas
        self.x = x
        self.y = y
        self.size = size
        self.walls = [True, True, True, True]
        self.visited = False

    def show(self):
        x = self.x * self.size
        y = self.y * self.size
        self.canvas.create_rectangle(
            x, y, x + self.size, y + self.size, outline="#fff", fill="#fff", width=2)

    def highlight(self):
        x = self.x * self.size
        y = self.y * self.size
        self.canvas.create_rectangle(
            x, y, x + self.size, y + self.size, outline="#000", fill="#000", width=2)

    def is_valid(self):
        if self.x >= 0 and self.x < self.size and self.y >= 0 and self.y < self.size:
            return True
        return False

    def has_all_walls(self):
        if self.walls[0] == True and self.walls[1] == True and self.walls[2] == True and self.walls[3] == True:
            return True
        return False

    def draw(self):
        if self.has_all_walls():
            self.show()
        else:
            self.highlight()

    def make_door(self, c):
        x = self.x - c.x
        y = self.y - c.y
        if x == 1:
            self.walls[3] = False
            c.walls[1] = False
        elif x == -1:
            self.walls[1] = False
            c.walls[3] = False
        if y == 1:
            self.walls[0] = False
            c.walls[2] = False
        elif y == -1:
            self.walls[2] = False
            c.walls[0] = False

    def get_neighbours(self):
        neighbours = []
        top = self.canvas.cell_at(self.x, self.y - 1)
        right = self.canvas.cell_at(self.x + 1, self.y)
        bottom = self.canvas.cell_at(self.x, self.y + 1)
        left = self.canvas.cell_at(self.x - 1, self.y)
        if top and not top.visited:
            neighbours.append(top)
        if right and not right.visited:
            neighbours.append(right)
        if bottom and not bottom.visited:
            neighbours.append(bottom)
        if left and not left.visited:
            neighbours.append(left)
        return neighbours

    def __str__(self):
        return "(" + str(self.x) + "," + str(self.y) + ")"


if __name__ == "__main__":
    root = tk.Tk()
    root.title("Maze Solver")
    maze = Maze(root)
    maze.solve("dfs")
    maze.draw()