Construisez vous même des labyrinthes aléatoires.
Dans un labyrinthe à seuil, chaque case est tirée aléatoirement. Un seuil donne la probabilité pour qu'une case soit infranchissable (noire ou false) : un nombre tiré aléatoirement entre 0 et 1 indiquera que la case est franchissable (blanche ou true) s'il est supérieur au seuil. Les cases d'entrée et de sortie, ainsi que (1,1) sont systématiquement franchissables.
final static int CASE = 11 ;
static void imprimeCaseNoire (int x, int y) {
Rect r = new Rect (x*CASE, y*CASE, (x+1)*CASE, (y+1)*CASE) ;
MacLib.paintRect (r) ;
}
static void initGraphique (int l, int h) { // pour l par h cases
MacLib.initQuickDraw () ;
Rect r = new Rect (50, 50, 50 + l*CASE, 50 + h*CASE) ;
MacLib.setDrawingRect (r) ;
MacLib.showDrawing () ; // normalement pas utile
}
Vous pourrez tester votre méthode à l'aide de la variable :
boolean[][] petitLab = {{false, true, false, false, false, false},
{false, true, true, true, true, false},
{false, true, false, false, false, false},
{false, true, true, true, true, false},
{false, false, false, false, true, false}};
Le résultat devrait être :
Écrivez une méthode static boolean[][] creeSeuil (int largeur, int hauteur, double seuil) qui crée un labyrinthe aléatoire de taille largeur x hauteur (plus les bords). seuil est la probabilité qu'une case soit infranchissable. On utilisera la fonction Math.random() qui retourne un double entre 0 et 1.
On veut maintenant produire un labyrinthe aléatoire où toutes les cases blanches sont reliées entre elles et où il y a un maximum de cases noires. En termes mathématiques, les cases blanches forment donc une partie connexe minimale, soit un arbre...
On part d'une grille (largeur/2+1) x (hauteur/2+1) dont les points sont sur les coordonnées impaires de 1 à largeur et de 1 à hauteur (en supposant largeur et hauteur impaires) :
Chaque arête de la grille est associé à un mur de trois cases. Par exemple, l'arête horizontale (1,1)--(3,1) est associée au mur de cases (2,0), (2,1) et (2,2). Ou encore, l'arête verticale (5,3)--(5,5) est associée au mur de cases (4,4), (5,4) et (6,4). Remarquons que la case du centre d'un mur suffit à coder ce mur puisque la parité de l'abscisse de la case permet de déterminer s'il s'agit d'un mur horizontal ou vertical.
Pour construire un labyrinthe aléatoire, il suffit de construire un arbre couvrant aléatoire de la grille, c'est-à-dire conserver un ensemble minimal d'arêtes de la grille de sorte que les noeuds de la grille soient toujours connectés. Voici par exemple un arbre couvrant et le labyrinthe associé (le pourtour sauf l'entrée et la sortie sont toujours en noir) :
Pour construire un tel ensemble minimal d'arêtes, on peut procéder ainsi : on prend une à une toutes les arêtes de la grille dans un ordre aléatoire. Quand on prend une arête, on teste si ses deux extrémités restent connectées par les arêtes restantes si on retire l'arête. Si c'est le cas, on retire l'arête, sinon on la garde. Et ainsi de suite pour chaque arête de la grille. Pour travailler directement sur le labyrinthe, on peut travailler sur les murs de trois cases.
Écrire une méthode qui renvoie un tableau contenant tous les murs de trois cases associés à une arête de la grille. (Un mur ne sera stocké que par les coordonnées de sa case centrale.)
Écrire une méthode pour mélanger le tableau de murs de sorte à obtenir une permutation aléatoire des murs. On pourra par exemple permuter le premier élément du tableau avec un autre pris au hasard dans tous le tableau, puis le second avec un autre pris au hasard dans la partie du tableau contenant le deuxième élément et la suite du tableau, et ainsi de suite.
Écrire une méthode permettant de tester si le retrait d'un mur déconnecte les deux cases de chaque côté du mur. On pourra pour cela faire un parcours en partant d'une des deux cases et tester si on atteint l'autre case.
Programmer la génération aléatoire de labyrinthe décrite plus haut : prendre les murs de 3 cases un à un dans un ordre aléatoire. Si l'ajout d'un mur ne déconnecte pas les deux cases de part et d'autre du mur, on ajoute le mur dans le labyrinthe. Pour que les parcours de test de déconnexion ne détruisent pas le labyrinthe en cours de construction, on sera amené à faire des copies du labyrinthe en cours.
S'il vous reste un peu de temps à tuer :
