from synchrod import *

pathfind_d = (-16, +16, -1, +1, GO_UP, GO_DOWN, GO_LEFT, GO_RIGHT)

def pathfind(board, start, end):
    n = len(board)
    parent = [-1]*n
    directions = list(parent)
    queue = [start]
    parent[start] = start
    cell = -1

    while queue:
        cell = queue.pop(0)
        if cell == end:
            break
        for i in range(4):
            d = cell+pathfind_d[i]
            if board[d] != 101 and parent[d] < 0:
                parent[d] = cell
                directions[d] = pathfind_d[i+4]
                queue.append(d)

    if cell == end:
        path = []
        while cell != start:
            path = [directions[cell]] + path
            cell = parent[cell]
        return path

calculer_chemin = pathfind