import random

width = 10
height = 10

start_pos = (0,0)
liste_visites = [start_pos]
liste_historique = [start_pos]

def next_step():
    global liste_visites
    global liste_historique
    global actual_pos

    direction = [1,1,1,1] #liste de boléen pour [up,right,down,left]

    for i in liste_visites: #
        if i[0] == actual_pos[0] and i[1] == actual_pos[1]-1:
            direction[0] = 0

        if i[0] == actual_pos[0]+1 and i[1] == actual_pos[1]:
            direction[1] = 0

        if i[0] == actual_pos[0] and i[1] == actual_pos[1]+1:
            direction[2] = 0

        if i[0] == actual_pos[0]-1 and i[1] == actual_pos[1]-1:
            direction[3] = 0

        if actual_pos[1] <= 0 :
            direction[0] = 0

        if actual_pos[0] >= width:
            direction[1] = 0

        if actual_pos[1] >= height:
            direction[2] = 0

        if actual_pos[0] <= 0:
            direction[3] = 0


    liste_dir_possibles = []
    for i in range(0,4):
        if direction[i]==1:
            liste_dir_possibles.append(i)

    a = 0
    for i in direction:
        a += i

    if a>0:
        if a>1:
            rand = random.randomint(0,a-1)
        else:
            rand = 0

        liste_historique.append(actual_pos)
        liste_visites.append(actual_pos)

        if list_dir_possibles[rand]==0:
            actual_pos = (actual_pos[0],actual_pos[1]-1)

        if list_dir_possibles[rand]==1:
            actual_pos = (actual_pos[0]+1,actual_pos[1])

        if list_dir_possibles[rand]==2:
            actual_pos = (actual_pos[0],actual_pos[1]+1)

        if list_dir_possibles[rand]==3:
            actual_pos = (actual_pos[0]-1,actual_pos[1])

    else:
        liste_historique.pop(len(liste_historique)-1) #supprime le dernier element de la liste
        actual_pos = liste_historique[len(liste_historique)-1] #actual_pos prend la derniere valeur de l'historique