Labyrinthes: 0-Bases et affichage
Soyez le premier à donner votre avis sur cette source.
Vue 7 366 fois - Téléchargée 1 565 fois
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.
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:
Valeurs de Sud[e] et Est[e] =0: pas de mur; =1: mur existe.
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.
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 ...
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 labyrinthesWikipé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 ...
Codes Sources
A voir également
- Labyrinthe rectangulaire
- Bases javascript - Meilleures réponses
- Javascript bases - Meilleures réponses
- Générateur de labyrinthe python - Guide
- Labyrinthe java - Guide
- Labyrinthe javascript - Guide
- Labyrinthe python - Guide
- Algorithme labyrinthe c - Forum - C
Remarque:
Ne vous fiez qu’au versions téléchargées car sous <voir> on ne retrouve pas les deux premiers caractères.
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.