# генератор лабиринтов с помощью обхода в глубину
from tkinter import *
import random
import time

start = time.time()

window = Tk()
window.title("Генератор лабиринтов")
window.resizable(width='False', height='False')

w = 30
h = 30

c = Canvas(window, width=20*w + 29, height=20*h + 29, bg='white')
c.focus_set()
c.pack()

lab = []  # лабиринт (хранит координаты клеток)
visited = []  # массив посещенных клеток
stack = []  # стек для пути по лабиринту
# структура лабиринта (у каждой клетки все границы)
for y in range(2*h + 3):
    new = []
    for x in range(2*w + 3):
        if x == 0 or x == 2*w + 2 or y == 0 or y == 2*h + 2:
            new.append('s')
            visited.append((y, x))
        elif (y % 2 == 0 and x % 2 == 0):
            new.append('')
        else:
            new.append('s')
            visited.append((y, x))
    lab.append(new)


def neighbours(i, j):  # возвращает непосещенных соседей
    n = []
    if ((i + 2, j) not in visited):
        n.append((i + 2, j))
    if ((i - 2, j) not in visited):
        n.append((i - 2, j))
    if ((i, j + 2) not in visited):
        n.append((i, j + 2))
    if ((i, j - 2) not in visited):
        n.append((i, j - 2))
    return n


def remove_wall(i, j, i2, j2):  # удаление стенки между двумя клетками
    if (i + 2, j) == (i2, j2):
        lab[i + 1][j] = ''
    if (i - 2, j) == (i2, j2):
        lab[i - 1][j] = ''
    if (i, j + 2) == (i2, j2):
        lab[i][j + 1] = ''
    if (i, j - 2) == (i2, j2):
        lab[i][j - 1] = ''

visited.append((2, 2))  # отметили как посещенную
i = 2
j = 2
flag = False
while len(visited) != (2*w + 3) * (2*h + 3):  # пока обошли не все клетки
    if len(neighbours(i, j)) != 0:  # проверили, что есть непосещенные соседи
        stack.append((i, j))
        # рандомно выбрали направление движения
        a = random.choice(neighbours(i, j))
        remove_wall(i, j, a[0], a[1])
        # сделали клетку текущей
        i = a[0]
        j = a[1]
        visited.append(a)
    elif len(stack) != 0:
        # спускаемся по стеку вниз
        b = stack.pop()
        i = b[0]
        j = b[1]


def build():  # построение лабиринта в канвасе
    x = 0
    y = 0
    for k in lab:
        for q in k:
            if q == 's':
                c.create_rectangle(x, y, x + 10, y + 10,
                                   fill='black', outline='black')
            x += 10
        x = 0
        y += 10

build()

p = c.create_rectangle(20, 20, 30, 30, fill='red', outline='black')


def right(event):
    if lab[int(c.coords(p)[1] / 10)][int(c.coords(p)[0] / 10) + 1] == '':
        c.move(p, 10, 0)


def left(event):
    if lab[int(c.coords(p)[1] / 10)][int(c.coords(p)[0] / 10) - 1] == '':
        c.move(p, -10, 0)


def up(event):
    if lab[int(c.coords(p)[1] / 10) - 1][int(c.coords(p)[0] / 10)] == '':
        c.move(p, 0, -10)


def down(event):
    if lab[int(c.coords(p)[1] / 10) + 1][int(c.coords(p)[0] / 10)] == '':
        c.move(p, 0, 10)

c.bind('<Up>', up)
c.bind('<Down>', down)
c.bind('<Left>', left)
c.bind('<Right>', right)


print(time.time() - start)
window.mainloop()