Labyrinthes: 0-Bases et affichage

Télécharger le projet
Commenter

Description

Bonjour,

Voici une série d'articles sur les labyrinthes qui abordera principalement quelques algorithmes de leur création.
Un labyrinthe (maze en anglais) est dit parfait s'il ne comporte ni boucles ni ilots.

Pour commencer, nous envisagerons des labyrinthes parfaits avec des cellules (éléments) à quatre cotés (carrés ou rectangles).

En priorité seront traités les deux algos les plus connus:
- Fusion aléatoire de chemins.
- Exploration exhaustive.

L'objet Laby

Il est formé du nombre de colonnes Nc, du nombre de lignes Nl ainsi que des murs intérieurs Est et Sud du labyrinthe: 
var Laby=function(nc,nl) { // objet labyrinthe
  this.Nc=nc; // nombre de colonnes
  this.Nl=nl; // nombre de lignes
  this.Sud=new Uint8Array(nc*nl); // murs intérieurs horizontaux
  this.Est=new Uint8Array(nc*nl); // murs intérieurs verticaux
}

A chaque élément e du labyrinthe rectangulaire correspond un mur horizontal Sud[e] et un mur vertical Est[e].

Pour l'élément e, le mur intérieur:
- "nord" est le mur Sud[e-Nc] de l'élément au dessus (sauf première ligne).
- "ouest" est le mur Est[e-1] de l'élément à gauche (sauf première colonne).

Exemple: 
   Nc=9, Nl=7, Ne=Nc*Nl; (Nombre de Colonnes, Lignes, Eléments)

       c=0  1  2  3  4  5  6  7  8
                                         +-------+               nord
  l=0    0  1  2  3  4  5  6  7  8       |  Ele Est       ouest  ele  est
    1    9 10 11 12 13 14 15 16 17       +--Sud--+               sud
    2   18 19 20 21 22 23 24 25 26
    3   27 28 29 30 31 32 33 34 35       Murs intérieurs:
    4   36 37 38 39 40 41 42 43 44       horizontaux: Nc*(Nl-1) = 9*6 =  54
    5   45 46 47 48 49 50 51 52 53       verticaux:   (Nc-1)*Nl = 8*7 =  56
    6   54 55 56 57 58 59 60 61 62       total:      Nm=2*Nc*Nl-Nc-Nl = 110

On ignore les murs Est de la dernière colonne et Sud de la dernière ligne.

Valeurs de Sud[e] et Est[e] =0: pas de mur; =1: mur existe.

Affichage (Laby.Draw)

Le dessin d'un labyrinthe est composé du rectangle extérieur et des traits de murs intérieurs: 
Laby.prototype.Draw=function(ctx,dx,dy,w) {
  var e,m,x,y,nc=this.Nc,X=nc*dx,Y=this.Nl*dy,sud=this.Sud,est=this.Est;

  ctx.strokeRect(0,0,X,Y);
  for (y=dy,e=0; y<Y; y+=dy) { // horizontal walls optimized
    for (x=0,m=0; x<X; x+=dx,e++)
      if (m!=sud[e]) {if (m=1-m) ctx.moveTo(x-w,y); else ctx.lineTo(x+w,y);}
    if (m) ctx.lineTo(x,y);
    ctx.stroke();
  }
  for (x=dx,l=0; x<X; x+=dx,l++) { // vertical walls optimized
    for (y=0,e=l,m=0; y<Y; y+=dy,e+=nc)
      if (m!=est[e]) {if (m=1-m) ctx.moveTo(x,y-w); else ctx.lineTo(x,y+w);}
    if (m) ctx.lineTo(x,y);
    ctx.stroke();
  }
} // by William VOIROL, Switzerland, Dec 2016

On dessine habituellement les murs à l'aide de boucles contenant des couples (moveTo,lineTo).
Cela engendre pas mal de suites (lineTo,moveTo) au même point, donc inutiles.

L'optimisation consiste à éviter ces instructions superflues:
- on n'exécute que le dernier de plusieurs déplacements moveTo consécutifs.
- les murs qui suivent (en continu) plusieurs éléments sont tracés avec un seul lineTo.

Les éventuelles portes d'entrée et de sortie (trous dans le rectangle extérieur) seront traitées ultérieurement.

Exemple 20x15

Pour tester la représentation graphique, Sud et Est sont (exceptionnellement) initialisés: par les résultats obtenus avec l'algorithme "Fusion aléatoire de chemins": 
  NE=20*15;
  Sud=new Uint8Array(NE); // murs horizontaux
  Est=new Uint8Array(NE); // murs verticaux

  Sud.set([0,1,1,1,0,1,0,1,0,1,1,0,0,0,0,0,1,1,1,0,1,1,1,0,0,0,0,0,0,1
          ,1,0,0,1,1,0,0,1,1,0,0,1,0,1,0,1,0,1,1,1,1,1,1,0,0,0,0,1,1,0
          ,0,0,0,0,0,1,1,0,1,0,0,1,0,1,0,1,1,0,1,0,0,0,0,0,1,0,1,1,1,0
          ,1,0,1,0,0,0,0,1,1,0,0,1,1,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,0,0
          ,1,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,1,0,1,1,1,0,0,0,1,0,0,1,0,0
          ,0,1,1,0,1,0,0,0,0,0,0,0,0,1,1,0,1,1,1,1,0,1,0,0,1,0,0,0,1,1
          ,0,1,1,0,1,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,0,1,0,0,1,1,0,1,1,0
          ,1,0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,0,0,0,1,0,0,1,1,1,0,1,0,0
          ,1,0,0,0,1,0,0,1,1,0,1,1,1,0,0,1,1,0,0,1,0,0,1,1,1,1,0,0,1,0
          ,0,1,1,1,0,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]);
  Est.set([0,0,1,0,1,0,1,0,0,0,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,1,0,0,0
          ,1,1,0,0,1,0,1,0,0,1,1,0,1,0,1,1,0,1,1,0,0,1,1,0,1,1,0,0,1,1
          ,1,1,0,1,1,0,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,0,0,0,1,0,0,0
          ,1,1,1,0,0,0,0,0,1,1,0,1,1,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1
          ,0,0,1,1,1,0,0,0,1,1,0,0,0,1,0,0,1,0,0,1,0,1,1,0,1,0,1,0,1,1
          ,1,1,1,1,0,1,0,1,0,1,0,1,0,0,1,1,1,0,1,0,0,1,1,0,0,1,1,0,1,1
          ,1,0,0,0,1,1,0,1,1,0,1,1,0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,0,0,1
          ,1,0,0,1,1,1,0,0,1,1,0,1,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1
          ,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,0,1,1,0,1,1,0,0,0,1,0,0,0,1,0
          ,0,0,0,1,0,1,0,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0,1,1,0,1]);

Liens

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?

Prochains articles:
- Labyrinthes: 1-Fusion aléatoire de chemins
- Labyrinthes: 2-Exploration exhaustive
- ...
- 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)