Labyrinthes: 2-Exploration exhaustive

Télécharger le projet
Commenter

Description

Bonjour,

La génération de labyrinthes parfaits (ni boucles ni ilots) peut se faire rapidement avec l'algorithme d'exploration exhaustive.

Il génère moins de bifurcations que "1-Fusion aléatoire de chemins".
Les tronçons (entre bifurcations) seront donc plus longs.

Description de la méthode:
a) Au début, tous les murs intérieurs sont présents (est.fill(1); sud.fill(1);)
b) On initialise à non visité (unused) un array sur tous les éléments (U.fill(1);).
c) L'élément de départ e est marqué used (U[e]=0;) et mis dans la pile (P[0]=e;).
d) Tant qu'il y a des éléments dans la pile:
d1) Pour la cellule e, on compte le nombre nv de voisins non visités.
d10) Si nv=0, on est arrivé à une impasse: on recule dans la pile.
d11) Si nv=1, on abat le mur et on remplace e par le voisin v.
d12) Si nv>1, on choisit au hasard un voisin v, on abat le mur et on empile e=v.
. . . [pour d11) et d12), on marque aussi v comme visité]

Dans le code du fichier Explo.js, la pile P est gérée explicitement: 
Laby.prototype.Explo=function(e) {
  var nc=this.Nc,nl=this.Nl,ne=nc*nl,sud=this.Sud,est=this.Est;
  var K=[],p=0,P=new Uint32Array(ne),U=new Uint8Array(ne);

  est.fill(1); sud.fill(1); U.fill(1); U[e]=0; P[0]=e; // init
  do {
    var nv=0,l=Math.floor(e/nc),c=e-l*nc;
    if (c && U[e- 1]) K[nv++]=0; // ◄
    if ((c<nc-1) && U[e+ 1]) K[nv++]=1; // ►
    if (l && U[e-nc]) K[nv++]=2; // ▲
    if ((l<nl-1) && U[e+nc]) K[nv++]=3; // ▼
    if (nv==0) {if (p) {e=P[--p]; continue;} else return;} // cul-de-sac
    var r=K[(nv==1)?0:Math.floor(nv*Math.random())]; // choix: ◄,►,▲,▼
    if (r<2) {if (r) {est[e]=0; U[e+= 1]=0;} else est[e-= 1]=U[e]=0;}
    else   {if (r>2) {sud[e]=0; U[e+=nc]=0;} else sud[e-=nc]=U[e]=0;}
    if (nv==1) P[p]=e; else P[++p]=e;
  } while (p>=0);
} // William VOIROL, Switzerland, Dec 2016
On pourrait éviter la gestion de la pile en utilisant une fonction récursive.

Double-cliquez sur Explo.html pour voir instantanément des labyrinthes parfaits.

Le programme TimeExplo.html montre quelques temps d'exécution: 
Labyrinthes: 2-Exploration exhaustive: Times

4x4 = 16, time = 0 ms.
8x4 = 32, time = 0 ms.
8x8 = 64, time = 1 ms.
16x8 = 128, time = 0 ms.
16x16 = 256, time = 1 ms.
32x16 = 512, time = 1 ms.
32x32 = 1024, time = 1 ms.
64x32 = 2048, time = 0 ms.
64x64 = 4096, time = 0 ms.
128x64 = 8192, time = 1 ms.
128x128 = 16384, time = 4 ms.
256x128 = 32768, time = 3 ms.
256x256 = 65536, time = 8 ms.
512x256 = 131072, time = 11 ms.
512x512 = 262144, time = 20 ms.
1024x512 = 524288, time = 32 ms.
1024x1024 = 1048576, time = 63 ms.
2048x1024 = 2097152, time = 127 ms.
2048x2048 = 4194304, time = 247 ms.
4096x2048 = 8388608, time = 487 ms.
4096x4096 = 16777216, time = 973 ms.
8192x4096 = 33554432, time = 1972 ms.
Le temps de calcul est à peu près proportionnel au nombre d'éléments.

Mon laptop I7/2.5GHz peut donc générer en moins d'une seconde un labyrinthe parfait avec 16 millions de cellules !

Liens:
CodeS-SourceS: Labyrinthes: 0-Bases et affichage
CodeS-SourceS: Labyrinthes: 1-Fusion aléatoire de chemins

Prochains articles:
- Labyrinthes: 3-Algorithme randomisé de Prim
- Labyrinthes: ?-Recursive division method
- ...
- Labyrinthes: ?-Représentation en arbre
- Labyrinthes: ?-Recherche de chemin
- ...

Bonne lecture ...
Télécharger le projet

Codes Sources

S'inscrire maintenant

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.

Du même auteur (William VOIROL)