CodeS-SourceS
Rechercher un code, un tuto, une réponse

Labyrinthes: 1-Fusion aléatoire de chemins

Soyez le premier à donner votre avis sur cette source.

Vue 1 699 fois - Téléchargée 163 fois

Description

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 ...

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Donnez votre avis

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.