Bonjour à tous, nous allons aujourd’hui voir comment générer aléatoirement un labyrinthe avec l’algorithme du Growing Tree, puis comment implémenter une solution qui va se charger de déterminer le bon chemin à notre place.

Les règles :

Le labyrinthe généré sera un labyrinthe parfait, ce qui implique quelques caractéristiques : – Tout point à l’intérieur du labyrinthe est accessible depuis n’importe quel autre point de celui-ci. – L’absence de boucle : il n’existe qu’un seul chemin pour accéder à chaque point du labyrinthe.

Le Growing Tree :

L’algorithme du Growing Tree permet donc de générer un labyrinthe parfait. L’idée est de partir d’une grille composée d’éléments inexplorés et d’un élément vide, le point d’entrée. Nous allons prendre aléatoirement un point inexploré adjacent à un point vide, regarder si il est possible de creuser ce point pour en faire un nouveau point vide, sinon en faire un mur. Il va donc s’agir de répéter cette étape, en prenant soin de ne faire qu’un seul point de sortie.

La mise en place :

La première chose à faire est de créer une classe contenant les informations relatives au labyrinthe :

    public class MazeInfo
    {
        public int Width { get; set; }
        public int Height { get; set; }
        public int EntryPositionWidth { get; set; }
        public int ExitPositionWidth { get; set; }
        public SquareType[,] Map { get; set; }
    }

Puis de créer une classe MazeHandler, dont le constructeur prend en compte les dimensions du labyrinthe, qui va se charger d’initialiser son attribut MazeInfo, en déterminant aléatoirement un point d’entrée sur le haut du labyrinthe et en préparant la Map : des murs sur les rebords, un point d’entrée, et les points centraux inexplorés.

La génération :

La fonction Generate va se charger d’appliquer l’algorithme expliqué précédemment :

public void Generate()
{
    Random rnd = new Random();
    MazeInformations.Map[0, MazeInformations.EntryPositionWidth] = SquareType.Free;
    Point entryPoint = new Point(1, MazeInformations.EntryPositionWidth);
    Exposed.Add(entryPoint);
    while (Exposed.Any())
    {
        int rand = rnd.Next(Exposed.Count());
        Point point = Exposed[rand];
        if (Decide(point))
        {
            Dig(point);
        }
        else
        {
            MazeInformations.Map[point.X, point.Y] = SquareType.Wall;
        }
        Exposed.RemoveAt(rand);
    }
}

La liste Exposed correspond à l’ensemble des points adjacents à des points vides sur la Map. La fonction Decide a pour rôle de regarder les 4 points adjacents à celui sélectionné, puis de vérifier qu’il ne touche qu’une seule case vide. Il renvoie vrai si c’est le cas, et cette case sera creusée par la suite, faux sinon et cette case sera transformée en mur. Si la fonction Dig est appelée, elle transforme le point en case vide et regarde les 4 cases adjacentes à ce point : si elles sont inexplorées, elle les ajoute à la liste Exposed pour que leur cas soit par la suite étudié.

if (point.X == MazeInformations.Height -2)
{
    CountToExit += 1;
    if(CountToExit == MazeInformations.Width /2-1)
    {
         MazeInformations.Map[point.X + 1, point.Y] = CharMap.Free;
         this.MazeInformations.ExitPositionWidth = point.Y;
    }
}

Ces lignes situées à la fin de cette fonction permettent de générer une sortie ; l’intérêt de ne pas créer de sortie la première fois que la case étudiée est adjacente à la bordure inférieure du labyrinthe est de permettre d’éloigner sur l’axe horizontal la sortie de l’entrée.

En effet, cet algorithme implique que plus les cases sont proches du point d’entrée, plus vite elles seront explorées, la case de sortie la plus probable serait donc celle située en dessous du point d’entrée, sur la bordure inférieure. Pour éviter cela, j’ai simplement imposé un délai avant la création du point de sortie.

Une fois le labyrinthe généré, on peut obtenir ceci (entre autres nombreuses possibilités) :

Résoudre le labyrinthe :

N’ayant pour ma part jamais aimé les labyrinthes (beaucoup trop laborieux pour être amusant), j’ai donc voulu mettre en place une solution pour trouver la sortie du labyrinthe à ma place. L’emploi dans ce cas de figure d’un algorithme récursif est adapté : la fonction ci-dessous va parcourir le labyrinthe jusqu’à trouver la sortie, puis va marquer le chemin parcouru.

public bool Resolve(int i, int j)
{
    //Le point fourni doit être une case vide.
    if (ResolveMap[i, j] != SquareType.Free) return false;
    //Si oui, il est marqué comme exploré.
    ResolveMap[i, j] = SquareType.Explored;
    //Récursivité sur les cases ajdacentes.
    if ((i == MazeInformations.Height - 1 && j == MazeInformations.ExitPositionWidth) ||
        (i + 1 > 0 && Resolve(i + 1, j)) ||
        (Resolve(i, j - 1)) ||
        (Resolve(i, j + 1)) ||
        (Resolve(i - 1, j)))
    {
        //La case est marqué comme faisant partie de la solution si un de ses chemins enfants mêne à la sortie.
        MazeInformations.Map[i, j] = SquareType.Path;
        return true;
    }
    return false;
}

Cette fonction est initialement appelée en fournissant comme paramètres le point d’entrée du labyrinthe. La variable ResolveMap est une copie de l’attribut Map à son état initial à la fin de la génération et sert à marquer les cases déjà explorées par l’algorithme de résolution, afin que celui-ci ne revienne pas dessus et ne crée pas de boucle infinie.

Une fois appliqué, le labyrinthe est résolu :

Le code complet est disponible sur GitHub.

Merci pour votre attention, et à bientôt.