Bonjour,
L'algorithme "Fusion aléatoire de chemins" (en anglais "Randomized Kruskal's algorithm") utilise la propriété des labyrinthes parfaits suivante: chaque élément est relié de manière unique à tous les autres.
Il suit une approche ascendante en fusionnant progressivement les chemins depuis le simple élément jusqu'à l'obtention d'un chemin unique et complet.
a) On commence par initialiser les murs intérieurs
Sud et
Est à 1 (existe) et les chemins
set au numéro de l'élément;
b) Puis on construit un array
mur avec tous les murs intérieurs horizontaux
Sud existants, et tous les murs intérieurs verticaux
Est existants.
c) Pour distinguer les murs, on utilise pour les horizontaux le numéro de l'élément et pour les verticaux ce numéro augmenté de
ne (nombre d'éléments).
d) On effectue une permutation aléatoire sur l'ensemble de murs
mur.
e) Pour chaque mur (en commençant par le dernier):
e1) On ne fait rien si deux voisins ont le même numéro de set (même chemin).
e2) Sinon, on abat le mur et on réunit les deux sets.
Laby.prototype.Fusi=function() { // mur: murs à traiter, set: numéro du chemin
var e,o,r,v,m,nc=this.Nc,nl=this.Nl,ne=nc*nl,nm=2*ne-nc-nl;
var mur=new Uint32Array(nm),set=new Uint32Array(ne);
var sud=this.Sud,est=this.Est;
for (e=0; e<ne; ++e) {est[e]=sud[e]=1; set[e]=e;} // init
for (e=0,m=0; e<ne-nc; e++) mur[m++]=e; // murs horizontaux
for (e=0; e<ne; e++) // ajoute murs verticaux
if ((e%nc)!=(nc-1)) mur[m++]=e+ne; // ici, on a m=nm
do { // fait une permutation aléatoire des m=NM éléments de mur
r=Math.floor(m*Math.random()); // 0 <= r < m (aléatoire)
e=mur[r]; mur[r]=mur[--m]; mur[m]=e;
} while (m); // voir RandPermut ci-dessous
m=nm; do {
e=mur[--m];
if (e<ne) { // horizontal (sud)
o=set[e]; v=set[e+nc];
if (o!=v) sud[e]=0;
} else { // vertical (est)
e-=ne; o=set[e]; v=set[e+1];
if (o!=v) est[e]=0;
}
if (o!=v) // fusion
for (e=0; e<ne; ++e)
if (set[e]==v) set[e]=o;
} while (m);
}
Dans le fichier
Fusi.js, on trouve une version plus concentrée:
Laby.prototype.Fusi=function() { // mur: murs à traiter, set: numéro du chemin
var e,o,r,v,m,nc=this.Nc,nl=this.Nl,ne=nc*nl,nm=2*ne-nc-nl;
var mur=new Uint32Array(nm),set=new Uint32Array(ne);
for (e=0; e<ne; ++e) {this.Est[e]=this.Sud[e]=1; set[e]=e;} // init
for (e=0,m=0; e<ne-nc; e++) mur[m++]=e; // murs horizontaux + verticaux
for (e=0; e<ne; e++) if ((e%nc)!=(nc-1)) mur[m++]=e+ne; // ici, on a m=nm
do {e=mur[r=~~(m*Math.random())]; mur[r]=mur[--m]; mur[m]=e;} while (m);
m=nm; do {
e=mur[--m];
if (e<ne) {if ((o=set[e])!=(v=set[e+nc])) this.Sud[e]=0;} // horizontal
else {e-=ne; if ((o=set[e])!=(v=set[e+1])) this.Est[e]=0;} // vertical
if (o!=v) for (e=0; e<ne; ++e) if (set[e]==v) set[e]=o; // fusion
} while (m);
} // William VOIROL, Switzerland, Dec 2016
Javascript nous enseigne que
0.0 <= Math.random() < 1.0 (1.0 non compris).
Pour choisir au hasard un index
i d'un array de n éléments, c'est-à-dire un entier entre 0 et n-1, il suffit d'écrire:
i = Math.floor(n*Math.random()); // on a alors
0 <= i <= n-1, uniformément répartis.
Ceci est utilisé pour adapter une permutation aléatoire, correspondant au code
C tiré du lien "CodeS-SourceS: Permutations aléatoires":
void Rand_Permut(int *ent, int n) { // ent[] contient déjà une permutation
for (int i=n-1; i>=0; --i) {
int r=rand()%(i+1);
int e=ent[r];
ent[r]=ent[i];
ent[i]=e;
}
}
void RandPermut(int *ent, int n) { // ent[] contient déjà une permutation
for (int r, i=n; i>0;) {int e=ent[r=rand()%i]; ent[r]=ent[--i]; ent[i]=e;}
}
En exécutant
Fusi.html, on constate qu'il fournit un labyrinthe dont l'arbre est assez bien équilibré.
L'algorithme favorise l'apparition de bifurcations; et les tronçons (entre bifurcations) sont plutôt courts.
La rapidité peut être testée à l'aide de
TimeFusi.html:
Labyrinthes: 1-Fusion aléatoire de chemins: Times
4x4 = 16, time = 0 ms.
8x4 = 32, time = 0 ms.
8x8 = 64, time = 0 ms.
16x8 = 128, time = 0 ms.
16x16 = 256, time = 1 ms.
32x16 = 512, time = 2 ms.
32x32 = 1024, time = 1 ms.
64x32 = 2048, time = 5 ms.
64x64 = 4096, time = 14 ms.
128x64 = 8192, time = 53 ms.
128x128 = 16384, time = 191 ms.
256x128 = 32768, time = 742 ms.
Les temps d'exécution augmentent pratiquement avec le carré du nombre d'éléments.
Cette "lenteur" peut s'expliquer par l'utilisation d'une méthode "simpliste" de la dernière instruction (fusion) du code.
Malgré cela, la génération est quasiment instantanée pour un nombre "raisonnable" de cellules (Ne <= 100x100 = 10000).
J'ai encore ajouté le test
Murs() du fichier
Murs.js qui teste si le nombre de murs intérieurs restants est égal à (nc-1)*(nl-1) pour un labyrinthe parfait.
Une fois le logiciel testé, les instructions concernées peuvent être supprimées.
Laby.prototype.Murs=function() {
var e,l,c,m=0,nl=this.Nl,nc=this.Nc;
for (l=1,e=0; l<nl; ++l)
for (c=0; c<nc; ++c) m+=this.Sud[e++];
for (l=0,e=0; l<nl; ++l,++e)
for (c=1; c<nc; ++c) m+=this.Est[e++];
if (m!=(nc-1)*(nl-1)) alert('Murs incorrects: '+m);
}
La représentation (voir
Draw.js), a aussi été "améliorée".
Le
Zip fait 3 Ko !
Liens
CodeS-SourceS: Labyrinthes: 0-Bases et affichage
CodeS-SourceS: Permutations aléatoires fonction RandPermut.
La génération de labyrinthes
WikipédiA: Modélisation mathématique d'un labyrinthe
WikipediA: Maze (labyrinth) generation algorithm
Maze Classification. Maze Creation Algorithms
Modélisation et Création d’un Labyrinthe Rectangulaire en Deux Dimensions
Perfect Maze algorithm
What are the algorithms to generate a random maze?
Maze Generation: Algorithm Recap
Prochains articles:
- Labyrinthes: 2-Exploration exhaustive
- Labyrinthes: 3-Algorithme randomisé de Prim
- ...
- Labyrinthes: ?-Représentation en arbre
- Labyrinthes: ?-Recherche de chemin
- ...
Bonne lecture ...
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.