Projet : Construction d'un labyrinthe

16 mai 2001

Introduction

Le but du projet est d'écrire un programme qui génère des labyrinthes rectangulaires. L'utilisateur donne les dimensions du labyrinthe qu'il veut obtenir et le programme positionne aléatoirement les murs à l'intérieur du labyrinthe en respectant cependant deux conditions :

Il doit toujours exister un chemin entre deux points du labyrinthe.
Il existe au plus un chemin entre deux points du labyrinthe.

En terme de théorie des graphes, la première condition porte le nom de connexité et la seconde d'acyclicité. L'une assure que le labyrinthe a toujours une solution quels que soient les points de départ et d'arrivée, l'autre que l'on ne peut pas tourner en rond indéfiniment. Tout le monde conviendra que ce sont là de bonnes propriétés pour un labyrinthe. La figure 1 est un exemple de ce type de labyrinthe.

Figure 1: Labyrinthe 30 × 30

Pour réaliser ces dessins, on considère qu'un labyrinthe est formé d'un ensemble de cellules carrées séparées par des murs qui peuvent être ouverts ou fermés. C'est-à-dire que l'on considère que deux cellules voisines sont toujours séparées par un mur, mais que le passage de l'une à l'autre n'est possible que si ce mur est ouvert (au lieu de murs ouverts ou fermés on pourrait aussi parler de portes fermées à clé ou non).

Découpage du projet

On va découper le projet en 3 étapes.

Dans la première étape on va définir une classe d'objets Labyrinthe qui posséderont des murs pouvant être ouverts ou fermés ainsi qu'une méthode permettant de les dessiner. Le choix des murs à ouvrir pour obtenir un vrai labyrinthe fait l'objet des étapes 2 et 3.

La deuxième étape va nous amener à considérer les ensembles de Tarjan qui vont nous permettre de gérer les ensembles de cellules connectées. On définira deux méthodes : une pour décider si deux cellules sont connectées entre elles par un chemin, l'autre pour effectivement réaliser la connexion entre deux cellules.

La dernière étape est une mise en commun des produits des deux premières étapes. En effet, après avoir mélangé aléatoirement les murs on en ouvrira autant que nécessaire pour obtenir la première propriété mentionnée ci-dessus (connexité) tout en préservant la deuxième (acyclicité).

Prologue

Tous les fichiers nécessaires pour le projet se trouvent dans le répertoire /home/cremet/projet. Pour les copier sur votre compte, exécutez la commande suivante :

  cp -r /home/cremet/projet .

Cela va créer dans votre répertoire courant un sous-répertoire nommé projet contenant tous les fichiers nécessaires pour le projet. Pour compiler le projet, déplacez-vous dans ce répertoire (en tapant cd projet), puis exécutez la commande gmake.

1 Construction des murs

Cette première étape doit nous amener à la définition d'un labyrinthe et de ses murs. On devra en outre pouvoir imprimer un labyrinthe dans un fichier en utilisant les primitives graphiques disponibles à travers les classes Vecteur, Segment et Dessin (voir annexe). À la fin de cette étape on n'aura cependant pas encore décidé quels murs seront ouverts ou fermés, ce qui est le thème des étapes 2 et 3. Par conséquent, ils seront par convention tous uniformément fermés (graphiquement on obtiendra un simple quadrillage).

1.1 Description

Un labyrinthe rectangulaire (figure 2) est constitué de cellules carrées rangées en lignes et en colonnes, comme sur un échiquier. On appelle largeur et hauteur d'un labyrinthe respectivement le nombre de colonnes et de lignes de ce labyrinthe. Chaque cellule peut être identifiée par un nombre entier, son indice, comme indiqué sur la figure. Un labyrinthe est entouré d'une enceinte avec une ouverture à chaque extrémité. Enfin, deux cellules voisines sont toujours séparées par un mur, celui-ci pouvant être ouvert (permettant le passage) ou fermé. Parmi ces murs, on distingue les murs verticaux et les murs horizontaux.

Figure 2: Structure d'un labyrinthe

1.2 Découpage du problème

On se propose de découper un labyrinthe en deux classes, une classe Mur représentant un mur du labyrinthe, et une classe Labyrinthe représentant le labyrinthe proprement dit.

1.2.1 Classe `Mur`

La classe Mur possèderait les attributs suivants :

un champ cellule_1 et un champ cellule_2, de type entier, contenant les indices des cellules séparées par le mur,
un champ ouvert, de type booléen, qui est vrai si le mur est effectivement ouvert,
un champ segment de type Segment, qui représente le dessin du mur, et enfin,
une fonction dessiner qui prend en argument un objet de type Dessin et qui, si le mur est fermé, ajoute son segment sur le dessin.

Il ne faut naturellement pas oublier un constructeur et un destructeur pour cette classe.

1.2.2 Classe `Labyrinthe`

La classe Labyrinthe possèderait alors les attributs suivants :

un champ largeur et un champ hauteur pour les dimensions du labyrinthe,
un champ nbre_murs égal au nombre de murs du labyrinthe,
un champ murs représentant la liste des murs du labyrinthe, celle-ci pouvant être implantée par un tableau, et enfin,
une fonction dessiner qui prend en argument un objet de type Dessin, puis qui y dessine l'enceinte du labyrinthe, ainsi que chaque mur fermé.

La principale difficulté de cette première étape réside dans le constructeur de la classe Labyrinthe. Etant données une largeur et une hauteur données en argument, il doit en effet construire tous les murs en donnant comme argument au constructeur de la classe Mur les informations nécessaires. C'est-à-dire les indices des cellules séparées par le mur et les coordonneés des deux extrémités du mur sur le dessin.

Pour ce faire, on commence par construire les murs verticaux, puis seulement ensuite, les murs horizontaux. Pour les murs verticaux on utilise une boucle avec deux indices imbriqués X et Y qui vont balayer ligne par ligne, de gauche à droite et de bas en haut, le labyrinthe. On procède de façon analogue pour les murs horizontaux.

1.3 A faire

En vous aidant de la description et du découpage donnés ci-dessus, écrivez les classes Mur et Labyrinthe. Prenez soin de bien séparer l'interface de ces classes (dans un fichier .H) de leur implantation (dans un fichier .C). Ecrivez enfin un petit programme de test qui imprime dans un fichier un labyrinthe dont tous les murs sont fermés.

2 Les ensembles de Tarjan

Comme vous le verrez dans la section suivante, lors de l'ouverture des murs du labyrinthe il est souvent nécessaire de savoir si deux cellules données sont déjà reliées entre elles ou pas. Il est donc important de trouver une technique permettant d'effectuer cela de manière efficace. Une idée qui vient rapidement à l'esprit est de former des ensembles de cellules pour savoir lesquelles sont connectées entre elles. C'est-à-dire que dans un ensemble donné on place toutes les cellules qui sont reliées par un chemin.

Les deux opérations que l'on doit pouvoir effectuer sur ces ensembles sont la comparaison --- pour savoir si deux cellules appartiennent au même ensemble et sont donc connectées --- et la mise en commun (union) de deux ensembles --- lorsqu'on connecte deux cellules.

Une bonne manière de réaliser ces deux opérations sur des ensembles d'éléments a été inventée par Robert Tarjan. L'idée est de désigner pour chaque ensemble un élément qui représente tout l'ensemble. On appelle cet élément le représentant de l'ensemble et, par abus de langage, on dira aussi que le représentant de l'ensemble d'un élément est le représentant de cet élément.

Comparer deux ensembles revient alors à tester si leurs représentants sont identiques, tandis que mettre en commun deux ensembles revient à élire un nouveau représentant commun à ces deux ensembles.

À noter que cette technique fonctionne uniquement avec des ensembles disjoints deux à deux, c'est-à-dire ne possédant aucun élément en commun. Heureusement pour nous, nos ensembles de cellules satisfont cette propriété.

La figure 3 montre un exemple d'ensembles de Tarjan. Chaque élément est représenté par une boîte, qui est grisée pour les représentants. De chaque boîte part une flèche, qui n'est autre que le pointeur vers le parent.

Figure 3: Évolution d'ensembles de Tarjan

Initialement, en (a), les 4 éléments appartiennent tous à des ensembles différents. Chaque élément est donc le représentant de son ensemble. En (b), les ensembles des éléments 1 et 2 sont mis en commun, et l'élément 2 est choisi comme nouveau représentant. En (c), ce sont cette fois les ensembles des éléments 3 et 4 qui sont mis en commun, et 3 est choisi comme nouveau représentant. En (d), les deux ensembles sont mis en commun, et 3 est à nouveau choisi comme représentant. Le contenu des ensembles reste le même en (e), par contre une optimisation d'aplatissement est appliquée afin que l'élément 1 ait le représentant de son ensemble, à savoir 3, comme parent direct. Cela élimine une indirection lors des recherches subséquentes du représentant de l'élément 1.

2.1 Mise en oeuvre

La réalisation des ensembles de Tarjan en C++ se fait au moyen d'une seule classe représentant les éléments de ces ensembles. Nous avons choisi d'appeler cette classe Noeud car les éléments liés entre eux via le lien parent font penser à un graphe.

Chaque noeud contient donc un champ parent qui contient l'adresse du noeud parent, ou NULL si le noeud est le représentant de son ensemble. Il contient de plus deux méthodes publiques : meme_ensemble permet de tester si le noeud appartient au même ensemble qu'un autre tandis que connecte met en commun l'ensemble du noeud avec l'ensemble d'un autre noeud.

Pour rechercher le représentant d'un noeud, on consulte son champ parent. S'il est nul, alors le noeud est son propre représentant. Sinon, on répète l'opération en recherchant le représentant du noeud désigné par le champ parent. Étant donné que le nombre de noeuds est borné et qu'il n'y a pas de cycles, on finira forcément par aboutir au représentant du noeud.

Les noeuds d'un même ensemble forment avec leur champ parent une sorte d'arbre dont la racine est le noeud qui représente l'ensemble. Plus un noeud est éloigné de la racine et plus l'opération de recherche de son représentant est longue, car il faut parcourir un plus grand nombre de noeuds avant d'arriver à la racine.

Une optimisation très importante qui permet d'aplatir cette arbre, c'est-à-dire de réduire la distance entre les noeuds et leur représentant, est la suivante : après chaque opération de recherche du représentant d'un noeud, on parcourt une seconde fois les noeuds que l'on vient de parcourir lors de la recherche et on modifie leur champ parent pour qu'il contienne l'adresse de leur représentant. Ainsi, la prochaine fois que l'on recherchera le représentant de l'un de ces noeuds on l'obtiendra immédiatement sans devoir parcourir d'autre noeuds. Cette optimisation est présentée dans la figure 3 lors du passage de (d) à (e).

Pour réaliser la classe Noeud, commencez par écrire une méthode auxiliaire obtient_representant qui retourne le représentant de l'élément. Pour cela, appliquez l'algorithme de recherche ainsi que l'optimisation décrits ci-dessus.

Grâce à cette méthode auxiliaire la réalisation de la méthode meme_ensemble est immédiate : il suffit de déterminer les représentants des deux noeuds et de les comparer. La méthode connecte n'est pas beaucoup plus compliquée : on commence aussi par déterminer les représentants des deux noeuds puis, s'ils sont différents, on fait pointer l'un des deux sur l'autre en modifiant son champ parent.

2.2 A faire

Lisez le fichier Noeud.H pour voir à quoi ressemble la classe. Ensuite, écrivez le fichier Noeud.C dans son ensemble, en utilisant les algorithmes décrits ci-dessus ; au besoin, complétez le fichier Noeud.H.

Il ne vous est malheureusement pas possible de tester votre mise en oeuvre des ensembles de Tarjan avant d'avoir terminé l'étape suivante, à moins bien entendu d'écrire un programme de test.

3 Ouverture des murs dans le labyrinthe

Le but de cette étape est d'ouvrir un certain nombre de murs du labyrinthe afin de s'assurer qu'il existe un et un seul chemin reliant n'importe quelle cellule du labyrinthe à n'importe quelle autre.

3.1 Algorithme

Pour déterminer les murs à ouvrir, on s'intéresse à tous les murs à tour de rôle, dans un ordre aléatoire ; pour chaque mur, on regarde si les deux cellules qu'il sépare sont déjà connectées par un chemin, et si ce n'est pas le cas, on l'ouvre.

En procédant de cette manière, on s'assure d'une part que toutes les cellules sont connectées entre elles --- étant donné qu'on examine tous les murs à tour de rôle --- et d'autre part que n'importe quelle cellule est reliée à n'importe quelle autre par au plus un chemin --- étant donné qu'on n'ouvre un mur que lorsque les deux cellules qu'il sépare ne sont pas encore connectées.

Le seul petit problème algorithmique posé par cette technique est celui du parcours aléatoire des murs.

De manière générale, une technique simple pour parcourir un ensemble d'éléments dans un ordre aléatoire est de mélanger ces éléments puis de les examiner l'un après l'autre. En C++, on peut par exemple placer les éléments dans un tableau, mélanger ce tableau, puis le parcourir élément par élément.

Reste à savoir comment mélanger les éléments d'un tableau. L'algorithme suivant donne d'excellents résultats en pratique : on parcourt le tableau du premier au dernier élément, et pour chaque élément on en choisit aléatoirement un autre qui se trouve plus en avant dans le tableau, puis on échange les deux éléments.

3.2 Mise en oeuvre

La mise en oeuvre des techniques présentées ci-dessus ne devrait pas poser de difficultés particulières.

Pour produire un nombre aléatoire, il existe une fonction prédéfinie nommée rand qui ne prend aucun argument et qui retourne un nombre aléatoire compris entre 0 et le plus grand entier possible. Pour ramener cette valeur à un intervalle donné, on peut utiliser une judicieuse combinaison d'addition et de calcul de reste de division.

Pour utiliser la fonction rand, pensez à inclure le fichier stdlib.h.

3.3 A faire

Complétez le fichier main.C en écrivant le corps de la fonction ouvre_murs, selon la technique présentée plus haut.

Annexe : Primitives graphiques

Afin de pouvoir dessiner le labyrinthe, nous fournissons les trois classes Vecteur, Segment et Dessin. Ces trois classes sont complètes. A aucun moment vous n'aurez besoin de les modifier. De plus, on vous demande juste de les utiliser. On ne vous demande pas d'en comprendre toute l'implantation. Ne passez donc pas trop de temps sur ces classes maintenant. Sachez simplement qu'elles existent et revenez-y lorsque vous en aurez besoin. Et, dans tous les cas, évitez de perdre du temps maintenant ou plus tard en voulant à tout prix comprendre les moindres détails de leur implantation.

La classe Vecteur (fichier Vecteur.H) décrit un vecteur du plan. Elle est notamment utilisée pour repérer la position des cellules et le sommet des murs. Sa définition surcharge plusieurs opérateurs et il est ainsi possible d'additionner et de soustraire deux vecteurs avec les opérateurs + et - ou de multiplier et diviser un vecteur par un scalaire avec les opérateurs * et /. Cette classe peut donc aussi être utilisée pour faire un peu de calcul vectoriel.

La classe Segment (fichier Segment.H) représente un segment du plan. Elle est utilisée pour repérer la position des murs du labyrinthe.

La classe Dessin (fichiers Dessin.H et Dessin.C) permet de dessiner un ensemble de segments et d'écrire le résultat dans un fichier. La classe translate et redimensionne toujours l'ensemble des segments afin que le dessin final soit centré et occupe la place au maximum. Cela signifie que seule la position relative des segments les uns par rapport aux autres importe. Leur position absolue dans le plan ainsi que la taille du dessin n'ont pas d'importance.

Les dessins sont enregistrés au format PostScript (fichier .ps). Vous pouvez donc directement imprimer le résultat avec la commande lp. Toutefois, pour vos tests, il sera infiniment plus simple, rapide et écologique d'utiliser la commande gv qui permet d'afficher à l'écran le contenu d'un fichier PostScript. Pour cela, exécutez la ligne de commande suivante:

  gv <nom_du_fichier_a_visualiser>

This document was translated from L^AT_EX by H^EV^EA.