import random

SIZE = 19
CELL_SIZE = 100 / SIZE
MATRIX_SIZE = SIZE * SIZE

def mset(matrix, point, value):
    matrix[SIZE * point[0] + point[1]] = value

def mget(matrix, point):
    return matrix[SIZE * point[0] + point[1]]

def wall_neighbors(cell):
    x = cell[0]
    y = cell[1]
    n = []
    if x > 2:
        n.append((x - 1, y))
    if y > 2:
        n.append((x, y - 1))
    if x < SIZE - 3:
        n.append((x + 1, y))
    if y < SIZE - 3:
        n.append((x, y + 1))
    return n

def cell_neighbors(wall):
    x = wall[0]
    y = wall[1]
    n = []
    if x % 2 == 0:
        if x > 0:
            n.append((x - 1, y))
        if x < SIZE - 1:
            n.append((x + 1, y))
    else:
        if y > 0:
            n.append((x, y - 1))
        if y < SIZE - 1:
            n.append((x, y + 1))
    return n

def generate_maze():
    maze = [(i % SIZE) % 2 == 0 or (i * SIZE) % 2 == 1 for i in range(MATRIX_SIZE)]
    walls = set()
    visited = set()
    point = (1, 1)
    visited.add(point)
    walls.update(wall_neighbors(point))
    while len(walls) > 0:
        wall = random.sample(walls, 1)[0]
        walls.remove(wall)
        count = 0
        for n in cell_neighbors(wall):
            if n in visited:
                count += 1
            else:
                unvisited = n
        if count == 1:
            mset(maze, wall, False)
            visited.add(unvisited)
            walls.update(wall_neighbors(unvisited))
    return maze

def draw_map(maze):
    for x in range(SIZE):
        for y in range(SIZE):
            color = 'black' if mget(maze, (x, y)) else 'white'
            Rectangle(width=CELL_SIZE,height=CELL_SIZE,x=(x+.5)*CELL_SIZE,y=(y+.5)*CELL_SIZE,color=color)
    
def maze_neighbors(maze, point):
    x = point[0]
    y = point[1]
    n = []
    if x > 1 and not mget(maze, (x - 1, y)):
        n.append((x - 1, y))
    if y > 1 and not mget(maze, (x, y - 1)):
        n.append((x, y - 1))
    if x < SIZE - 2 and not mget(maze, (x + 1, y)):
        n.append((x + 1, y))
    if y < SIZE - 2 and not mget(maze, (x, y + 1)):
        n.append((x, y + 1))
    return n

def find_distances(maze, player, target):
    distances = [MATRIX_SIZE for _ in range(MATRIX_SIZE)]
    visited = set()
    visited.add(target)
    todo = [target]
    todo_index = 0
    mset(distances, target, 0)
    found = False
    while not found and todo_index < len(todo):
        point = todo[todo_index]
        todo_index += 1
        if point == player:
            found = True
        else:
            value = mget(distances, point)
            for n in maze_neighbors(maze, point):
                if n not in visited:
                    visited.add(n)
                    mset(distances, n, value + 1)
                    todo.append(n)
    return distances

def find_next(maze, distances, point):
    best = MATRIX_SIZE
    top = None
    for n in maze_neighbors(maze, point):
        distance = mget(distances, n)
        if distance < best:
            best = distance
            top = n
    return top

center = (SIZE // 2, SIZE // 2)
targets = [(SIZE - 2, 1), (SIZE - 2, SIZE - 2), (1, SIZE - 2), (1, 1), center]
for _ in range(5):
    x = random.randint(1, SIZE // 2) * 2 - 1
    y = random.randint(1, SIZE // 2) * 2 - 1
    targets.append((x, y))
random.shuffle(targets)

target = targets[0]
player = targets[-1]
maze = generate_maze()
draw_map(maze)

player_circle = Circle(width=CELL_SIZE,height=CELL_SIZE,x=(player[0]+.5)*CELL_SIZE,y=(player[1]+.5)*CELL_SIZE,color='red')
target_circle = Circle(width=CELL_SIZE,height=CELL_SIZE,x=(target[0]+.5)*CELL_SIZE,y=(target[1]+.5)*CELL_SIZE,color='blue')

for target in targets:
    distances = find_distances(maze, player, target)

    with animation(duration = 0.001):
        target_circle.x = (target[0]+.5)*CELL_SIZE
        target_circle.y = (target[1]+.5)*CELL_SIZE

    while player != target:
        with animation(duration = 0.25):
            player = find_next(maze, distances, player)
            player_circle.x = (player[0]+.5)*CELL_SIZE
            player_circle.y = (player[1]+.5)*CELL_SIZE