Générer un labyrinthe

Objectif

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 :

W = 8
H = 5

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.

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.

*****************
*         *     *
********* ***** *
*       * *   * *
* * ***** * *** *
* *       *     *
* *** ***** *** *
*   *         * *
* * *********** *
* *             *
*****************

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.

Une cellule (x ; y) se retrouve donc aux coordonnées (i ; j) avec i = 2*x + 1 et j = 2*y + 1

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 :

*****************
* * * * * * * * *
*****************
* * * * * * * * *
*****************
* * * * * * * * *
*****************
* * * * * * * * *
*****************
* * * * * * * * *
*****************

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.

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.

*****************
* + + + + * + + *
*********+*****+*
* + + + * * + * *
*+*+*****+*+***+*
* * + + + * + + *
*+***+*****+***+*
* + * + + + + * *
*+*+***********+*
* * + + + + + + *
*****************

Algorithme

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.

ENTRÉE (x0 ; y0) position initiale
DÉBUT
    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

Les fonctions à réaliser

initialisation de la grille

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

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

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.