LABYRINTHE

Soit un labyrinthe simple pour illustrer un algorithme simple.

 

La démarche consiste a partir de « D » dans le coin nord-ouest et de se rendre au « F » dans le coin sud-est en marchant sur le « gazon » bleu, le noir étant un mur « infranchissable ». Y a-t-il un algorityme récursif pour effectuer ce périple : en effet. Le coeur du code

###########################################

def resout(x,y):
   if y > len(maze) or x > len(maze[y]):
       return False   # une erreur
   if maze[y][x] == "F":
       return True    # rendu à destination
   if  maze[y][x] != " ":
       return False   # frappé un mur
   if resout(x+1,y) == True :  #droite
       maze[y][x] = ">"
       return True
   if resout(x,y+1) == True :  #bas
       maze[y][x] = "v"
       return True
   if resout(x-1,y) == True :  #gauche
       maze[y][x] = "<"
       return True
   if resout(x,y-1) == True :  #haut
       maze[y][x] = "^"
       return True
   #reculer
   maze[y][x] = " "
   return False

###########################################

Cependant pour « voir » ce qui se passe il faut bourrer le code à chaque tournant. Un delai pour ralentir et nous laisser comprendre et afficher des messages sur la console. L’énoncé « pygame.event.wait() » arrête l’exécution du code et attende une action de l’utilisateur : clavier, mouvement de la souris. Ça donne le code suivant :

###################################################

def resout(niv,x,y):
   print("entrée niv=",niv)
   pg.event.wait()
   time.sleep(delai)
   if y > len(maze) or x > len(maze[y]):
       print("sortie niv=", niv,"Erreur")
       return False

   if maze[y][x] == "F":
       print("sortie niv=", niv,"terminé, chemin de retour")
       time.sleep(5*delai)
       return True

   if  maze[y][x] != " ":
       print("sortie niv=", niv,"pas d'espace, on recul")
       return False


   #marquage
   maze[y][x] = "o"
   affMaze(win,maze)

    if resout(niv+1,x+1,y) == True :  #droite
       maze[y][x] = ">"
       affMaze(win, maze)
       time.sleep(delai)
       print("sortie niv=", niv,"droite")
       return True
   if resout(niv+1,x,y+1) == True :  #bas
       maze[y][x] = "v"
       affMaze(win, maze)
       time.sleep(delai)
       print("sortie niv=", niv,"bas")
       return True
   if resout(niv+1,x-1,y) == True :  #gauche
       maze[y][x] = "<"
       affMaze(win, maze)
       time.sleep(delai)
       print("sortie niv=", niv,"gauche")
       return True
   if resout(niv+1,x,y-1) == True :  #haut
       maze[y][x] = "^"
       affMaze(win, maze)
       time.sleep(delai)
       print("sortie niv=", niv,"haut")
       return True

   #recul
   maze[y][x] = " "
   affMaze(win,maze)
   print("sortie niv=", niv, "recul")
   return False

###########################################