def create_graph(maze):
    """
    compute the graph representation of the map
    """
    graph = {}
    for x in range(len(maze)):
        for i in range(len(maze[x])):
            if maze[x][i] == 1:
                field_location = str(x) + ":" + str(i)
                field_edges = []
                try:
                    if maze[x][i-1] == 1:
                        edge_left = str(x) + ":" + str(i-1)
                        field_edges.append(edge_left)
                except IndexError:
                    pass
                try:
                    if maze[x][i+1] == 1:
                        edge_right = str(x) + ":" + str(i+1)
                        field_edges.append(edge_right)
                except IndexError:
                    pass
                try:
                    if maze[x-1][i] == 1:
                        edge_bottom = str(x-1) + ":" + str(i)
                        field_edges.append(edge_bottom)
                except IndexError:
                    pass
                try:
                    if maze[x+1][i] == 1:
                        edge_top = str(x+1) + ":" + str(i)
                        field_edges.append(edge_top)
                except IndexError:
                    pass
                field = {field_location: set(field_edges)}
                graph.update(field)
    return graph

graph = create_graph(maze)
print(graph)


def bfs_paths(graph, position, goal):
    queue = [(position, [position])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))

ways = list(bfs_paths(graph, "1:1", "7:7"))



def shortest_path(graph, position, goal):
    try:
        return next(bfs_paths(graph, position, goal))
    except StopIteration:
        return None
shortest = shortest_path(graph, "1:1", "7:7")

def update(position):
    """Updated ax, bzw. fügt einen Kries kinzu"""
    global ax
    ax.add_patch(Circle((position[0], position[2]), .3, color='green', alpha=1))

for x in range(len(shortest)):
    update(position)