Algorithme aléatoire

Cet algorithme est le plus simple à implanter et à comprendre mais globalement le moins efficace. Cependant, il présente l'avantage d'avoir probabilité non nulle de trouver la sortie du labyrinthe, quelque soit la configuration de celui-ci (si une solution existe bien évidemment).

Le principe est le suivant : avant d'effectuer un pas, on prend une décision aléatoire pour décider de la prochaine direction à suivre (une direction valide, pour ne pas entrer dans un mur). On effectue alors un pas dans cette direction.

Exemple :

Algorithme aléatoire bis

Cette version de parcours est légèrement différente de la précédente dans le fait que la décision aléatoire ne se fait pas à chaque pas mais uniquement en cas de présence d'un obstacle empêchant d'avancer plus en avant.

Exemple :

On remarque que dans cet exemple particulier, cette méthode ne permet jamais de trouver la sortie.

Algorithme du suivi de mur

Le principe de cet algorithme est le suivant : à l'entrée dans le labyrinthe, vous poser votre main gauche (ou droite mais toujours la même main) sur le mur à votre gauche et vous suivez ce mur en conservant toujours votre main en contact avec le mur comme dans cette illustration :

Cette méthode présente une limitation, elle n'est utilisable que si le labyrinthe est simplement connecté :  l'entrée et la sortie sont connectés par un mur ininterrompu (pas forcément rectiligne). Dans le cas contraire, l'algorithme va vous faire repasser par le point le départ et tourner en rond indéfiniment.

Exemple :

Algorithme de Pledge

Cet algorithme procède de manière différente du précédent et présente un avantage : l'entrée du labyrinthe peut être n'importe où ;  mais aussi une limitation : la sortie doit se trouver en bordure extérieure.

En effet, cet algorithme, un peu plus complexe que le précédent, permet de lâcher le contact temporairement avec le mur pour attraper un nouveau mur.

Pour cela, il repose sur deux variables : une direction préférentielle et le nombre de rotations effectuées. Le principe est le suivant :

• on avance dans une direction tant qu'on peut (peu importe qu'une main soit en contact ou non avec un mur) ;
• si on rencontre un obstacle on tourne afin d'avoir sa main en contact avec l'obstacle ;
• puis on continue à avancer en conservant la main en contact (la somme des quarts de tour signés effectués est conservée) ;
• si on revient dans la même direction que la fois où on a rencontré l'obstacle et si on a effectué un nombre total nul de rotations alors on quitte l'obstacle et on continue dans la direction initiale.

Cette illustration explique ce principe, pas forcément évident :

Cet algorithme présente un avantage :  on peut débuter le labyrinthe de n'importe où ;  mais aussi une limitation :  la sortie doit se trouver en bordure extérieure.

Exemples d'application sur un même labyrinthe avec deux préférences différentes pour la partie « suivie de mur » (gauche et droite) :

Style de code

Dans les différents modules que vous allez écrire pour ce projet, vous devrez respecter plusieurs contraintes :

• Utilisation de la librairie spéciale pocketnoobj, afin d'utiliser le langage dans un cadre impératif,
• Respect des conventions PEP8 et PEP257.

Ainsi, vous mettrez dans chacun de vos modules (fichier .py) l'instruction import pocketnoobj qui fera apparaître à l'exécution le message Initialisation de l'espace de nommage fait. dans la console.

Modularité et protection des données

Une attention particulière doit être accordée à ce point. Le projet est subdivisé en quatre (4) modules :  grille, parcours, interface et main, ce dernier comprenant le programme principal. Cette subdivision (la modularité) permet de séparer les fonctions de chaque objet :  ce n'est pas le module grille qui doit savoir comment il est représenté graphiquement, c'est le rôle du module interface  ;  par contre c'est le rôle du module grille de savoir si une case est vide ou non.

Par ailleurs, vos modules pouvant être vus comme des librairies pour les autres modules python (comme la librairie math), il serait tout-à-fait illogique de retrouver des appels aux fonctions input() et print() ailleurs que dans des fonctions dont c'est explicitement le but.

Pour chaque module, on peut indiquer que certaines variables et fonctions sont d'un usage interne au module. Pour cela, on préfixera leur nom d'un underscore (_), ce qui signifie dans la philosophie ouverte du langage que l'on ne souhaite pas qu'elles soient visibles (et donc directement utilisables) dans les autres modules. Cette "protection" n'est effective que si l'on effectue une importation au niveau de l'espace des noms global. Exemple :

# module1
_x = 0

def _f():
  pass

# module principal
from module1 import *
_f()  # NameError: name '_f' is not defined

Tests unitaires

Chaque module doit comporter un test unitaire vérifiant l'ensemble de ses fonctionnalités. L'objectif est de pouvoir construire des fonctions reposants sur modules dont on est sûr du comportement et du résultat attendu.

Pour le cas particulier du module de l'interface graphique, le test à effectué serait plutôt l'exécution d'un scénario test que le test de chaque fonctionnalité.

Exemple :

# module 1
def _f(x):
  return x + 1

def g():
  return 2

###########  tests unitaires  ##########

def test_f():
  return _f(1) == 2

def test_g():
  return g() == 2

if __name__ == '__main__':
  print(test_f() == True)
  print(test_g() == True)

Débogage

L’option -O de l’interprète Python, associée à la variable interne __debug__, offre un moyen de commutation des messages de débogage. Exemple :

# désactivé par l'option -O
if __debug__:
  print("mode debug : python lance sans -O")
else:
  print("python lance avec l'option -O")

La grille (grille.py)

Le labyrinthe sera de forme grille et sera représentée avec une matrice de cases sur laquelle seront placés les éléments (mur, point de départ, sortie) et sur laquelle la personne évoluera. Chaque case est ramenée à un point et sera donc identifiable par ses coordonnées dans la grille. La taille de la grille est définie en nombre de cases de l'un de ses côtés (ce sera donc un carré). Cette valeur sera donnée par l'utilisateur ou bien déduite à partir d'un fichier décrivant un labyrinthe. Exemple, une grille de taille 4 :

Chaque case de la grille comporte un code qui indique à tout moment l'état du contenu. Pour cela, vous mettrez en place un ensemble de fonctions de manipulation et d'interrogation dans cet unique fichier (i.e module). On impose le codage des cases suivant :

• _CASE_VIDE = 0
• _CASE_MUR = 1 (\(2^0\))
• _CASE_DEPART = 2 (\(2^1\))
• _CASE_SORTIE = 4 (\(2^2\))
• _CASE_PERSO = 8 (\(2^3\))

Ce codage permet de combiner les états d'une case, quand cela a un sens, sans avoir à définir un nouvel état spécifiquement pour ce cas. Par exemple, si une case est la case de sortie et que la personne est sur cette case, le contenu de la case sera 12 :  CASE_SORTIE + CASE_PERSO. La manipulation est ainsi facilitée et peut se limité à des opérations binaires et et ou entre les valeurs.

Ce module doit comporter au minimum les fonctions suivantes :

• initialisation de la grille,
• modification du contenu d'une case de la grille,
• interrogation du contenu d'une case de la grille,
• interrogation de l'état d'une case: «est-ce qu'une case est vide ? » avec réponse booléenne. Idem pour les autres états (départ, etc),
• lecture d'un fichier contenant la description d'un labyrinthe et initialisation de la grille en conséquence,
• affichage textuel du contenu de la grille (pour le débogage en mode texte).

Les parcours (parcours.py)

Dans ce module, on retrouvera les différentes méthodes de parcours du labyrinthe que vous aurez implémenté. La généricité est importante et donc chaque méthode pourra être interchangeable. Ainsi, elles présenteront une signature de fonction minimale commune avec des paramètres optionnels spécifiques à chacune.

Chaque méthode de parcours devra retourner comme réponse la séquence des cases suivies depuis le point de départ, ainsi que l'indication si la sortie a été atteinte ou non. Il conviendra de veiller à détecter et stopper les méthodes si celles-ci bouclent sans fin possible.

Pour ce module, il vous est très fortement conseillé (voire imposé) d'utiliser des dictionnaires de fonctions afin de résoudre simplement les calculs tels que « quelle sont les coordonnées de la case juste au nord de ma position ? ».

L'interface (interface.py)

Ce module permet de donner une représentation de l'état du labyrinthe et de la progression de la méthode de parcours choisie.

Pour faire ces affichages graphiques, vous utiliserez la bibliothèque spéciale pocketgl qui est installée sur vos postes.

Ce module doit comporter au minimum les fonctions suivantes :

• Initialisation de l'affichage du labyrinthe,
• Rafraîchissement de l'affichage pour montrer l'évolution de méthode de parcours,
• Affichage de messages indiquant l'état et l'évolution du parcours.

Le module principal (main.py)

Dans ce module se trouve l'application en elle-même avec tout le mécanisme pour son déroulement, du début à la fin.

C'est le point central autour duquel s'articule tous les autres modules et le point d'entrée pour exécuter le programme.

Lors du lancement du programme, celui-ci prendra en argument le nom d'un fichier contenant un labyrinthe selon le format de fichier décrit ci-après.

Les autres paramètres possibles seront placés après le nom de fichier(il y aura entre autre la méthode à appliquer).

Format du fichier décrivant un labyrinthe:

Le format du fichier contenant une sauvegarde de partie est simple et est en mode textuel. Il pourra contenir des lignes vides ou des lignes avec des commentaires commençant par le caractère '#'. Ces lignes seront ignorées lors de la lecture du fichier.

Chaque ligne est définie par la succession des valeurs des cases du labyrinthe selon l'encodage utilisé dans la section grille correspondant à une ligne de la grille du labyrinthe. Les labyrinthes étant supposés carré, il y aura autant de lignes que de valeurs sur chaque ligne.

Exemples de fichiers décrivant un labyrinthe :

# labyrinthe simple avec l'entree et la sortie sur les bords horizontaux.
# la taille est de 7x7

1 1 4 1 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 10 1 1

# labyrinthe simple avec l'entree et la sortie sur les bords verticaux.
# la taille est de 7x7

1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
10 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 4
1 1 1 1 1 1 1

# labyrinthe de taille 7x7 un peu moins simple

1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
4 0 0 0 0 0 1
1 0 1 0 1 0 1
1 1 1 1 1 2 1