GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Générer un labyrinthe ======

===== Objectif =====
{{ nsi:tds:laby_genarator.png?nolink&200|}}

On souhaite générer automatiquement un labyrinthe sous forme d'un texte.

Prenons par exemple le labyrinthe ci-contre. Le pavage facilite la lecture : on peut le définir sur une grille de 8 cases de large et 5 de haut. Pour la suite on notera :

<code python>
W = 8
H = 5
</code>

<WRAP important>Nous nous référerons toujours à ce pavage dans la suite. Nous appellerons **cellule** une case de ce pavage. Une cellule est localisée par 2 coordonnées x et y.
</WRAP>

Vous pouvez voir qu'ici les murs correspondent aux côtés des cellules.

===== Fichier texte =====

Nous aimerions reproduire ce labyrinthe sous une forme plus simple à exploiter : un fichier texte. Dans ce fichier, on choisirait un caractère -- espace -- pour les couloirs et un autre caractère -- par exemple ''%%*%%'' -- pour les murs.

Le labyrinthe précédent produirait le fichier suivant.

<code lang-none>
*****************
*         *     *
********* ***** *
*       * *   * *
* * ***** * *** *
* *       *     *
* *** ***** *** *
*   *         * *
* * *********** *
* *             *
*****************
</code>

Vous constater un gros changement : puisque les murs et les couloirs sont des caractères, ils ont la même taille. Il s'en suit que pour notre labyrinthe 8 x 5 pour lequel on ne comptait que les cases de couloir, on obtient une grille de 17 x 11 caractères -- c'est à dire 2 x 8 + 1 = 17 et 2 x 5 + 1 = 11.

<WRAP tip>
Une cellule (x ; y) se retrouve donc aux coordonnées (i ; j) avec ''i = 2*x + 1'' et ''j = 2*y + 1''
</WRAP>

===== Construction du labyrinthe =====

L'idée générale est de commencer par créer une grille figurant des cellules murées des 4 côtés :

<code lang-none>
*****************
* * * * * * * * *
*****************
* * * * * * * * *
*****************
* * * * * * * * *
*****************
* * * * * * * * *
*****************
* * * * * * * * *
*****************
</code>

<WRAP tip>
Important à remarquer -- soit i et j les coordonnées de ligne et colonne :
  * le nombre de lignes et colonnes est toujours impair,
  * les cases pour lesquelles i et j sont tous les deux pairs correspondent aux cellules,
  * les cases pour lesquelles i et j sont tous les deux impairs correspondent aux coins des cellules et contiendront toujours le caractère ''%%*%%'',
  * les cases pour lesquelles i et j sont l'un pair, l'autre impair, correspondent aux côtés des cellules, ce sont les murs du labyrinthe, ceux que l'on est susceptible de supprimer pour créer les couloirs du labyrinthe.
</WRAP>

Pour former le labyrinthe, on supprime certains murs -- Je représente ici par + les murs supprimés. Comme mentionné dans l'encadré, ces + sont toujours à des coordonnées (i;j) avec l'un pair, l'autre impair.

<code lang-none>
*****************
* + + + + * + + *
*********+*****+*
* + + + * * + * *
*+*+*****+*+***+*
* * + + + * + + *
*+***+*****+***+*
* + * + + + + * *
*+*+***********+*
* * + + + + + + *
*****************
</code>

===== Algorithme =====

<WRAP important>
Ne perdez pas de vue que notre grille représente en même temps les cellules du labyrinthe, et les murs du labyrinthe. Quand je note (x ; y) je parle des coordonnées des cellules prisent dans le labyrinthe initial. Quand je note (i ; j) je parle des coordonnées dans le tableau contenant à la fois les murs et les cellules. On se rappelle donc que la cellule (x ; y) correspond à la position (i ; j) avec ''%%i = 2*x + 1%%'' et ''%%j = 2*y + 1%%''.
</WRAP>



<code lang-none>
TRAITEMENT
ENTRÉE un nœud
DÉBUT
    le nœud correspond à une cellule en (x ; y)
    marquer cette cellule comme visitée
    chercher tous les voisins non visités
    SI ce nœud n'a aucun voisin non visité ALORS
        retirer ce n
    position courante : (x0 ; y0)
    
    initialiser une liste vide de positions en attente
    TANT QUE il reste des cellule à visiter RÉPÉTER
        marquer position courante comme visitée
        chercher les voisins non visités de la position courante
        SI aucun voisin possible ALORS
            position courante est le prochain parmi la liste des positions en attente
        SINON
            SI plusieurs voisins possibles ALORS
                ajouter à la position courante aux positions en attente
            choisir un des voisins possibles au hasard
            supprimer le mur entre la position courante et la position choisie
            position courante devient la position choisie
        FIN
    FIN
FIN
</code>

===== Les fonctions à réaliser =====

==== initialisation de la grille ====

Écrire une fonction ''%%init_grid(w, h)%%'' créant un tableau de a forme :

<code python>
# exemple pour w = 8, h = 5 -> 17 x 11
[
    ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
    ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
    ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
    ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
    ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
    ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
    ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
    ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
    ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
    ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
    ['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*']
]
</code>

==== Tester si une position est visitée ====

Écrire une fonction ''%%is_visited(x, y, grid)%%''.

''x'' et ''y'' correspondent à une position de cellule.
  * Quand celle ci n'a pas encore été visitée, la grille contient ''%%*%%'' et la fonction renvoie ''False''.
  * Quand elle a été visitée, la grille contient ''%% %%'' et la fonction renvoie ''True''.

==== Chercher les voisins non visités ====

Écrire une fonction ''%%get_unvisited_neighbours(x, y , grid)%%''.

Renvoie une collection contenant les paires ''%%(x,y)%%'' des voisins non visités.

On ne compte que les voisins en haut, à gauche, en bas et à droite. Attention aux cas particuliers des bords du labyrinthe.

==== Supprimer mur ====

Écrire une fonction ''%%delete_wall(x1, y1, x2, y2, grid)%%'' qui modifie la grille en supprimant le mur entre les positions ''%%(x1,y1)%%'' et ''%%(x2,y2)%%''.

On présume que ces positions sont bien voisines.

==== Marquer visitée ====

Écrire une fonction ''%%set_visited(x, y, grid)%%'' qui marque visitée la cellule en ''%%(x,y)%%''.

Cela consiste à modifier le caractère correspondant à cette cellule dans la grille et à écrire un espace.

==== Fonction principale ====

Vous y êtes presque, il ne manque que la fonction principale correspondant à l'algorithme donné.

==== Sauvegarde ====

On aimerait envoyer le résultat dans un fichier texte.

Écrire une fonction ''%%save_to_file(filename, grid)%%'' qui écrit le contenu de la grille sous forme d'un texte dans le fichier de nom ''filename'' fourni à la fonction.