-
Notifications
You must be signed in to change notification settings - Fork 4
/
labyrinthes.html
875 lines (773 loc) · 42.6 KB
/
labyrinthes.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
<!DOCTYPE HTML>
<!--
Phantom by HTML5 UP
html5up.net | @ajlkn
Free for personal and commercial use under the CCA 3.0 license (html5up.net/license)
-->
<html>
<head>
<title>Labyrinthes</title>
<meta charset="utf-8" />
<meta http-equiv="refresh" content="0; url=https://website-b-bischoff.vercel.app/maze" />
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no" />
<link rel="stylesheet" href="assets/css/main.css" />
<noscript><link rel="stylesheet" href="assets/css/noscript.css" /></noscript>
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-CP7YYY7WEF"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-CP7YYY7WEF');
</script>
</head>
<body class="is-preload">
<!-- Wrapper -->
<div id="wrapper">
<!-- Header -->
<header id="header">
<div class="inner">
<!-- Logo -->
<a href="index.html" class="logo">
<span class="symbol"><img src="images/Square-grey.png" alt="" /></span><span class="title">Page principale</span>
</a>
<!-- Nav -->
<nav>
<ul>
<li><a href="#menu">Menu</a></li>
</ul>
</nav>
</div>
</header>
<!-- Menu -->
<nav id="menu">
<h2>Menu</h2>
<ul>
<li><a href="index.html">Projets</a></li>
<li><a href="a-propos.html">À propos</a></li>
<li><a href="contact.html">Contact</a></li>
</ul>
</nav>
<!-- Main -->
<div id="main">
<div class="inner">
<h1>Labyrinthes</h1>
<span class="image main"><img src="images/Maze/11.png" alt="" /></span>
<h2>Contexte</h2>
<p>
Je commence à me rendre compte que la difficulté de tout projet ne provient pas uniquement du fait de coder, mais surtout, de <b>l'organisation</b> et de la structure du projet en lui même.<br>
Le sujet que je compte explorer, <b>la génération de labyrinthes</b> me permettra de m'exercer sur ce point précis, à l'aide du moteur de jeu Unity.
<p>
<p>
De manière plus concrète, l'objectif est de pouvoir générer des labyrinthes avec différentes méthodes et formes, à partir d'une interface utilisateur simple.
</p>
<hr>
<h2>Réalisation</h2>
<h3>Concepts</h3>
<h4>Définition d'un labyrinthe</h4>
<span class="image right"><img src="images/Maze/perfect_maze.png" alt="" /><center><sup><i>labyrinthe parfait</i><sup></center>
<img src="images/Maze/imperfect_maze.png" alt="" /><center><sup><i>labyrinthe imparfait</i><sup></center></span>
<p>
D'après Wikipedia, "Un labyrinthe est un tracé <u>sinueux</u>, muni ou non d'embranchements, <u>d'impasses</u> et de fausses pistes destiné à perdre ou ralentir celui qui cherche à s'y déplacer."
<br>Il y a cependant quelques règles à respecter pour qu'un labyrinthe soit dit "parfait".<br>
Chaque <b>cellule</b> du labyrinthe doit être <b>réliée</b> aux autres et ce, par un <b>chemin unique</b> (on parle de surface connexe).
Il ne doit ainsi pas y a avoir de boucles ou de zones fermées. <br>
</p>
<p>Il existe de nombreuses méthodes pour créer un labyrinthe, une des plus commune est la génération par "<b>suppression de murs</b>".<br>
Le labyrinthe est initialement rempli de murs. Toutes ces zones entourées de murs, sont appelés des cellules.<br>
L'objectif est de relier ces cellules, en supprimant les murs entre elles afin de recréer cette impression de dédale.
</p>
<h4>Cellule</h4>
<p>
Dans sa forme la plus simple, une cellule est <b>composée de murs</b> (quatre pour une cellule de forme carrée).<br>
Elle possède également <b>une position</b>, représentée par une coordonée X (axe des abscisses) et une coordonnée Y (axe des ordonnées). Cette position permet de la différencier des autres cellules du labyrinthe.<br>
Nous verrons que certaines méthodes de génération demandent à ce que les cellules possèdent des propriétés supplémentaires.<br>
Par exemple, une valeur indiquant si cette cellule a été visitée ou bien une donnée séparant les cellules en sous-zones du labyrinthe.
</p>
<blockquote>
<p><b>Précisions techniques</b><br></p>
<p>Le code suivant montre la représentation informatique d'une cellule.<br></p>
<pre><code>1 public class MazeCell
2 {
3 public GameObject[] walls;
4 public int x, y;
5
6 public MazeCell(int x, int y)
7 {
8 this.x = x;
9 this.y = y;
10 }
11 }</code></pre>
On retrouve les entiers X et Y correspondant aux coordonnées de la cellule.<br>
La taille du tableau <i>walls</i> sera fixée et son contenu assigné pendant la génération d'un tableau rempli de cellules.<br>
L'utilisation de <b>classe</b> rend le concept de cellule extrement modulable. Pour chaque méthode de génération, nous pourrons créer une classe <b>héritant</b> de <i>MazeCell</i> et ainsi n'avoir que les données dont nous avons besoin.
</blockquote>
<p>
Maintenant que nous avons défini informatiquement ce qu'est une cellule de labyrinthe, nous pouvons commencer à créer une grille constituée de plusieurs de ces cellules.
</p>
<h4>Tableau de cellules</h4>
<p>
C'est avec des cellules stockées dans un <b>tableau</b> en deux dimensions que l'on peut représenter notre labyrinthe.
</p>
<span class="image right"><img src="images/Maze/topview_5x5.png" alt="" /><center><sup><i>labyrinthe vu de dessus</i><sup></center></span>
<span class="image right"><img src="images/Maze/2d_array_coord.png" alt="" /><center><sup><i>tableau à deux dimensions</i><sup></center></span>
<p>
Dans le cas d'un labyrinthe carré, on voit de manière nette la relation avec sa représentation en tableau deux à dimensions.
<br>
</p>
<p>
Habituellement, la position [0, 0] des tableaux à deux dimensions se situe en haut à gauche.<br>
Afin de simplifier le placement de nos cellules dans l'espaces, la position [0, 0] se trouvera en bas à gauche du tableau dans notre cas.<br>
Il sera ainsi plus aisé de convertir les coordonées des cellules dans le tableau (deux dimensions) en coordonnées dans l'espace (trois dimensions).
<br>
</p>
<span class="image left"><img src="images/Maze/unity_coordinate_system.png" alt="" /><sup><i>repère orthonormé de Unity</i><sup></span>
<span class="image right"><img src="images/Maze/maze_cell.png" alt="" /><center><sup><i>prefab de cellule</i><sup></center></span>
<p>
Maintenant que nous savons comment sont stockées nos cellules dans un tableau, nous pouvons essayer de les placer dans l'espace.<br>
Le plus simple est d'utiliser les <a href="https://docs.unity3d.com/Manual/Prefabs.html">"Unity's Prefabs"</a> qui permettent de <b>créer et configurer</b> à l'avance,
un objet que nous pourrons <b>réutiliser</b> pendant l'éxecution du programme.<br>
Voici donc le prefab de notre cellule carrée.
</p>
<br><br>
<p>
D'après notre tableau à deux dimensions, l'espacement entre chaque cellule est de 1 (sur l'axe X et Y), chaque cellule devrait donc faire une taille de 1 par 1.<br>
Cependant, lorsque l'on crée un labyrinthe avec ces dimensions, certaines parois possèdent des angles peu esthétiques.<br>
Passer la taille des murs à 1,1 (les faisant légèrement dépasser de la cellule) nous permet de résoudre ce problème. Les murs des cellules voisines seront désormais superposés.<br>
Cela ne pose pas de problème mais nous verrons comment les supprimer dans le but d'optimiser les performances du programme.<br>
</p>
<div class="row">
<div class="col-4">
<span class="image fit"><img src="images/Maze/corners.png" alt="" /><center><sup><i>angles disgracieux</i><sup></center></span>
</div>
<div class="col-5">
<p>
Maintenant que nous possédons notre cellule sous forme de prefab, nous pouvons à l'aide d'une <b>longueur</b> et d'une <b>largeur</b>, faire apparaitre nos cellules.<br>
Il faut pour cela, parcourir chaque case du tableau, de la position [0, 0] à la position [longueur - 1, largeur - 1] (-1, car on compte à partir de 0).
</p>
</div>
</div>
<blockquote>
<p><b>Précisions techniques</b><br></p>
<p>
Voici le code permettant de créer un labyrinthe rempli de cellules.
<pre><code>1 MazeCell[,] maze;
2 GameObject cell_prefab;
3 int height, width;
4
5 maze = new MazeCell[height, width];
6
7 for(int y = 0; y < height; y++)
8 {
9 for (int x = 0; x < width; x++)
10 {
11 maze[y, x] = new MazeCell(y, x);
12 Vector3 position = new Vector3(y, 0, x);
13 GameObject cell = Instantiate(cell_prefab, position, Quaternion.identity);
14
15 cell.walls = new GameObject[4];
16 maze[y, x].walls[0] = cell.transform.Find("TopWall").gameObject;
17 maze[y, x].walls[1] = cell.transform.Find("LeftWall").gameObject;
18 maze[y, x].walls[2] = cell.transform.Find("BottomWall").gameObject;
19 maze[y, x].walls[3] = cell.transform.Find("RightWall").gameObject;
21 }
22 } </pre></code>
A l'aide de la fonction <i>Instantiate</i> de Unity, ce code nous permet de créer une cellule pour chaque case de notre tableau à deux dimensions mais également de l'initialiser pour lui donner ses valeurs.
</p>
<div class="row">
<div class="col-5">
<span class="image fit"><img src="images/Maze/topview_5x10.png" alt="" /><center><sup><i>labyrinthe vu de dessus</i></center></sup></span>
</div>
<div class="col-4">
<span class="image fit "><img src="images/Maze/maze_grid.png" alt="" /><center><sup><i>résultat en 3D</i></center></sup></span>
</div>
</div>
</blockquote>
<h4>Suppression de murs entre cellules</h4>
<span class="image right"><img src="images/Maze/wall_connexion.png" alt="" /><center><sup><i>cellules voisines</i><sup></center></span>
<p>
Voyons maintenant comment <b>relier deux cellules</b> voisines.<br>
Relier deux cellules veut en réaliter dire, supprimer les murs qui séparent ces cellules.<br>
Dans l'exemple suivant, nous voulons relier deux cellules voisines horizontalement. Pour ce faire, il faut supprimer le mur de droite de la cellule A et le mur de gauche de la cellule B.
<br>
</p>
<blockquote>
<p><b>Précisions techniques</b><br></p>
<p>
Pour nous simplifier la vie, faisons une fonction qui relie deux cellules voisines.<br>
L'objectif est de supprimer le mur de chaque cellule en fonction de la position de son voisin.
<pre><code>1 void LinkNeighbors(MazeCell cell_1, MazeCell cell_2)
2 {
3 Vector2 dir = new Vector2(cell_1.x - cell_2.x, cell_1.y - cell_2.y);
4
5 if (dir.y == -1)
6 DestroyWalls(cell_1.TopWall, cell_2.BottomWall);
7 else if (dir.y == 1)
8 DestroyWalls(cell_1.BottomWall, cell_2.TopWall);
9 else if (dir.x == -1)
10 DestroyWalls(cell_1.RightWall, cell_2.LeftWall);
11 else
12 DestroyWalls(cell_1.LeftWall, cell_2.RightWall);
13 }
14
15 void DestroyWalls(GameObject wall_1, GameObject wall_2)
16 {
17 Destroy(wall_1);
18 Destroy(wall_2);
19 } </pre></code>
C'est à l'aide de la variable <i>dir</i> que nous pouvons savoir comment sont situées nos deux cellules l'une par rapport à l'autre.<br>
</p>
<div class="box alt">
<div class="row gtr-uniform">
<div class="col-3"><span class="image fit"><img src="images/Maze/neighbors_abs.png" alt="" /></span></div>
<div class="col-3"><span class="image fit"><img src="images/Maze/neighbors_rel.png" alt="" /></span></div>
</div>
</div>
<p>
Voici un exemple expliquant de manière visuelle, comment la variable <i>dir</i> fonctionne et interprète les coordonnées qu'elle calcule.<br>
A gauche on peut voir les <b>coordonées réelles</b> des cellules, tandis qu'à droite, sont affichées les <b>coordonées relatives</b> à la cellule centrale.
</p>
<p>
Maintenant que nous savons identifer les cellules voisines, il suffit de supprimer les murs adéquats avec la fonction <i>Destroy</i> de Unity.
</p>
</blockquote>
<h4>Suppresion des murs superposés</h4>
<p>
Une fois le labyrinthe généré, nous pouvons supprimer les <b>murs superposés</b> restants.<br>
Cela permet d'optimiser l'efficacité du programme en supprimant les murs inutiles.
</p>
<blockquote>
<p><b>Précisions techniques</b><br></p>
<p>
<pre><code>1 for (int y = 0; y < height; y++)
2 {
3 for (int x = 0; x < width; x++)
4 {
5 if (x < width - 1 && _maze[y, x].RightWall != null && _maze[y, x + 1].LeftWall != null)
6 Destroy(_maze[y, x].RightWall);
7 if (y < height - 1 && _maze[y, x].TopWall != null && _maze[y + 1, x].BottomWall != null)
8 Destroy(_maze[y, x].TopWall);
9 }
10 }
</pre></code>
Pour chaque cellule, on vérifie qu'elle ne soit pas en bordure du labyrinthe (afin de ne pas ouvrir le labyrinthe).<br>
Si cette cellule possède un mur droit et que la cellule à sa droite possède un mur gauche. On supprime le mur droit de la cellule actuelle.<br>
Le processus est le même pour le mur du bas. Si la cellule scrutée et celle du dessous possèdent leurs murs voisins, on supprime le mur bas de la cellule actuelle.
</p>
</blockquote>
<p>
Voici donc tous les concepts nécessaires pour créer un labyrinthe.<br>
Avant de présenter les algorithmes de génération, voici une section montrant brièvement comment ces concepts peuvent être réutilisés afin de créer des labyrinthes à cellules hexagonales.<br>
</p>
<h4>Cellules hexagonales</h4>
<p>Un hexagone est un polygone à six sommets et six côtés. On retrouve généralement cette forme géométrique sous deux orientations :</p>
<div class="row">
<div class="col-6">
<span class="image left"><img src="images/Maze/hexagon_pointy.png" alt="" /><center><sup><i>hexagone "pointy"</i></center></sup></span>
</div>
<div class="col-6">
<span class="image left"><img src="images/Maze/hexagon_flat.png" alt="" /><center><sup><i>hexagone "flat"</i></center></sup></span>
</div>
</div>
<p>
La seule différence avec la celulle carrée est le nombre de murs.<br>
La classe précédemment définie (<i>MazeCell </i>) <b>reste utilisable</b>, la seule chose à modifier est l'attribution des murs de la cellule.
<p>
<p>
La dernière question à nous poser est : comment <b>représenter</b> une grille hexagonale dans un tableau à deux dimensions ?<br>
De nombreuses représentations existent déjà avec chacune ses avantages et inconvénients.<br>
La solution choisie ici, est d'utiliser la même méthode que pour les cellules carrées. C'est une représentation simple à mettre en place,
cependant, elle s'avère peu pratique lorsque l'on souhaite relier des cellules entre elles.<br>
</p>
<div class="box alt">
<div class="row gtr-uniform">
<div class="col-3"><span class="image fit"><img src="images/Maze/2d_array_coord.png" alt="" /><center><sup><i>tableau à deux dimensions</i></center></sup></span></div>
<div class="col-3"><span class="image fit"><img src="images/Maze/2d_array_coord_hex_flat.png" alt="" /><center><sup><i>grille d'hexagones "flat"</i></center></sup></span></div>
<div class="col-3"><span class="image fit"><img src="images/Maze/2d_array_coord_hex_pointy.png" alt="" /><center><sup><i>grille d'hexagones "pointy"</i></center></sup></span></div>
</div>
</div>
<blockquote>
<p><b>Précisions techniques</b><br></p>
<p>
Voici la première difficulté des grilles hexagonales. Selon l'orientation de l'hexagone, une cellule sur deux sera <b>décalée</b>.<br>
Sur l'image de gauche on peut constater que sur chaque ligne, un hexagone sur deux se trouve décalé en hauteur.<br>
À droite, ils sont décalés sur l'axe horizontal.
<div class="row">
<div class="col-6">
<span class="image left"><img src="images/Maze/grid_hexaflat.png" alt="" /><center><sup><i>Grille d'hexagones "flat"</i></center></sup></span>
</div>
<div class="col-6">
<span class="image left"><img src="images/Maze/grid_hexapointy.png" alt="" /><center><sup><i>Grille d'hexagones "pointy"</i></center></sup></span>
</div>
</div>
Ce choix de représentation nous force donc à <b>différencier les opérations</b>, en fonction de l'orientation de l'hexagone.<br>
Il existe cependant d'autres moyen de stocker ces hexagones dans un tableau.<br>
Ceux-ci sont présentés sur <a href="https://www.redblobgames.com/grids/hexagons/#map-storage">le guide des hexagones de Red Blob Games</a>
<br>
</p>
</blockquote>
<h3>Algorithmes</h3>
<h4>Backtracker</h4>
<p>
Probablement l'une des plus répandues (car l'une des plus simples), la méthode du backtracker (ou retour arrière en français) permet de systématiquement tester <b>l'ensemble des possibilités</b>.
<br>
Cette famille d'algorithmes est utilisée pour résoudre des problèmes algorithmiques comme de l'optimisation combinatoire ou des jeux, telle que <a href="https://fr.wikipedia.org/wiki/Probl%C3%A8me_des_huit_dames">le problème des huit dames</a> ou la résolution de sudoku.
</p>
<div class="row">
<div class="col-5">
<p>
Appliquée à nos labyrinthes, en partant d'une grille remplie de murs, cette méthode a pour objectif de créer un chemin, en passant par toutes les cellules du labyrinthe.
<br>
De manière plus détaillée :<br>
Chaque cellule du tableau possède un <b>état "visitée" ou non</b> (initialisé à non-visitée). Depuis une cellule de départ, le programme va se déplacer <b>aléatoirement</b> sur une cellule non-visitée, voisine à la sienne (et définir son état comme visitée).
<br>
Dès lors qu'une cellule est entourée de cellules visitées, l'algorithme va revenir sur ses pas jusqu'à retrouver des cellules non-visitées.
<br>
S'il n'en trouve plus, cela veut dire que toutes les cellules ont été parcourues.
</p>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/backtracker.mp4" type="video/webm">
</video>
<center><sup><i>illustration de la méthode du backtracker</i></sup></center>
</span>
</div>
</div>
<div class="row">
<div class="col-6 col-12-medium">
<p>
Pour garder en mémoire les déplacements effectués, on stocke les cellules visitées dans <a href="https://fr.wikipedia.org/wiki/Pile_(informatique)#:~:text=En%20informatique%2C%20une%20pile%20(en,le%20premier%20%C3%A0%20en%20sortir.">une pile</a> (une structure de données informatique).
</p>
</div>
<div class="col-6 col-12-medium">
<span class="image right"><img src="images/Maze/pile.png" alt="" /><center><sup><i>représentation d'une pile</i></center></sup></span>
</div>
</div>
<p>Algorithme :</p>
<pre><code>1 - Choisir une cellule, la marquer comme visitée et l'ajouter à la pile
2 - Tant que la pile n'est pas vide
1 - Prendre la cellule au sommet de la pile et la considérer comme la cellule actuelle
2 - Si la cellule actuelle possède au moins un voisin "non-visité"
1 - Mettre la cellule actuelle au sommet de la pile
2 - Choisir une des cellules voisines non-visitée
3 - Relier la cellule actuelle à la cellule choisie
4 - Définir la cellule choisie comme visitée et la mettre au sommet de la pile</pre></code>
<p>
Cette méthode est extrêmement <b>simple à implémenter</b> et plutôt efficace. Elle peut cependant se révéler <b>gourmande en stockage</b> à cause de la taile de la pile, qui augmente en fonction de la surface du labyrinthe à générer.<br>
Un autre inconvénient est le résultat qui se retrouve quelques fois non pas "labyrinthique" mais juste comme un long chemin tortueux, avec peu d'embranchements. Ceci s'explique par le fait que la méthode explore aussi loin que possible chaque
possibilité, avant de revenir sur ses pas, limitant ainsi le choix des prochains déplacements.
</p>
<div class="row">
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/backtracker_10x10.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la méthode backtracker avec un labyrinthe 10 par 10</i></sup></center>
</span>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/backtracker_30x30.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la méthode backtracker avec un labyrinthe 30 par 30</i></sup></center>
</span>
</div>
</div>
<h4>Kruskal</h4>
<p>
L'algorithme de Kruskal est initialement appliqué dans le domaine des graphes.<br>
Il permet de rechercher un arbre recouvrant le poids minimum dans un graphe.<br>
Des applications concrètes que l'on pourrait lui trouver, seraient de simplifier un câblage ou bien
de supprimer les chemins de transports les moins rentables.
</p>
<div class="row">
<div class="col-5">
<p>
Cette méthode est une <b>version aléatoirisée</b> de l'algorithme d'origine.<br>
Initialement la méthode sélectionne <a href="https://fr.wikipedia.org/wiki/Ar%C3%AAte_(th%C3%A9orie_des_graphes)#:~:text=En%20th%C3%A9orie%20des%20graphes%2C%20une,appel%C3%A9%20ar%C3%AAte%20orient%C3%A9e%20ou%20arc">
<i>les arêtes</i></a> d'un graphe par poids croissant.<br>
Or ici, elles seront séléctionnées de manière aléatoire.
</p>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/kruskal.mp4" type="video/webm">
</video>
<center><sup><i>illustration de la méthode de Kruskal</i></sup></center>
</span>
</div>
</div>
<p>
Plus concrètement, à partir d'un labyrinthe rempli de murs, chaque cellule possède <b>un set</b> (un identifiant unique).<br>
L'objectif est de relier les cellules de sets différents et d'appliquer un <b>set commun</b> aux cellules réliées.
</p>
<p>Algorithme :</p>
<pre><code>1 - Tant que toutes les cellules n'ont pas le même set
1 - Prendre deux cellules voisines avec un set différent
2 - Relier ces deux cellules
3 - Agrandir le set de l'une des deux cellules sélectionnées en affectant ce set à l'autre cellule et aux cellules de son propre set</pre></code>
<p>
Cet méthode est plutôt simple et directe. Elle peut cependant se révéler coûteuse, notamment lorsqu'il faut changer le set d'un groupe de cellules.<br>
La manière la plus simple est d'itérer sur toutes les cellules du labyrinthe. Il est cependant possible d'utiliser des listes chainées ou d'autres structures de données pour isoler les sets
afin <b>d'alléger cette opération</b>.
</p>
<p>Dans sa finalité, l'algorithme de Kruskal créé de nombreuses impasses peu profondes.</p>
<div class="row">
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/kruskal_10x10.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de l'algorithme de Kruskal avec un labyrinthe 10 par 10</i></sup></center>
</span>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/kruskal_30x30.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de l'algorithme de Kruskal avec un labyrinthe 30 par 30</i></sup></center>
</span>
</div>
</div>
<h4>Prim</h4>
<p>
La méthode de Prim a de nombreuses ressemblances avec celle de Kruskal : son objectif est similaire, mais la manière de l'atteindre est fondamentalement différente.<br>
Cet algorithme permet également de trouver un arbre recouvrant le poids minimum dans un graphe.<br>
Là où la méthode de Kruskal sélectionne les arrêtes de poids faibles dans tout le graphe, Prim va, depuit un point de départ, <b>faire croître un abre</b> en sélectionnant les arêtes
de poids faibles incidentes à cet arbre.
</p>
<div class="row">
<div class="col-5">
<p>
Encore une fois, cette méthode est <b>aléatoirisée</b> par rapport à l'algorithme d'origine.<br>
Au lieu de choisir l'arête la plus faible, elle sera choisie de manière aléatoire.
</p>
<p>
Pour appliquer ce concept à nos labyrinthes, il va falloir garder en mémoire :<br>
Premièrement, les <b>cellules visitées</b><br>
Puis, les cellules voisines des cellules visitées (que nous appelerons les cellules "<b>en bordure</b>")
</p>
<p>
A partir d'une cellule de départ, le programme va relier une cellule en bordure à une cellule visitée.<br>
Cela aura pour effet de faire croître une "zone" qui va petit à petit, former notre labyrinthe en supprimant les murs de aléatoirement.
</p>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/prim.mp4" type="video/webm">
</video>
<center><sup><i>illustration de la méthode de Prim</i></sup></center>
</span>
</div>
</div>
<p>Algorithme :</p>
<pre><code>1 - Choisir une cellule de départ et noter cette cellule comme visitée
2 - Noter ses cellules voisines comme bordure
3 - Tant qu'il existe des cellules en bordure
1 - Choisir aléatoirement une des cellules en bordures
2 - La relier à une cellule visitée voisine
3 - Noter cette cellule comme visitée et marquer ses voisines (non-visités) comme bordure</pre></code>
<p>
Sans grande surprise, le résultat est similaire à celui de Kruskal.<br>
Le labyrinthe possède ici aussi de nombreuses impasses peu profondes.<br>
</p>
<div class="row">
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/prim_10x10.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la méthode de Prim avec un labyrinthe 10 par 10</i></sup></center>
</span>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/prim_30x30.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la méthode de Prim avec un labyrinthe 30 par 30</i></sup></center>
</span>
</div>
</div>
<h4>Divisions récursives</h4>
<div class="row">
<div class="col-5">
<p>
Pour la première fois, nous partirons d'un labyrinthe <b>sans murs à l'intérieur</b> !<br>
Cette méthode consiste à découper notre labyrinthe en une multitude de salles (que l'on nommera "chambres").<br>
</p>
<p>
Le concept et son implémentation sont on ne peut plus simples.<br>
Il faut <b>diviser</b> chaque chambre en quatre à l'aide de murs. Pour que les nouvelles chambres ne soient pas inaccessibles, il faut veiller à <b>laisser un passage</b> dans les murs créés.
</p>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/recursive.mp4" type="video/webm">
</video>
<center><sup><i>illustration de la méthode des divisons récursives</i></sup></center>
</span>
</div>
</div>
<p>
Il est possible de rendre le résultat un peu plus intéressant en divisant les chambres, non plus au milieu, mais de manière aléatoire.
</p>
<p>Algorithme :</p>
<pre><code>1 - Depuis la chambre initiale, créer deux murs perpendiculaires (de sorte à créer 4 sous-chambres)
2 - Créer un passage dans trois des quatre murs
3 - Si il est possible de diviser une sous-chambre
1 - Retourner à l'étape 1 pour cette sous-chambre</pre></code>
<p>
Le style de ce labyrinthe est très différent de ceux vus précédemment<br>
Cette méthode a tendance à créer de <b>longs couloirs</b>, ce qui rend la résolution du labyrinthe plus aisée, notamment car les séparations entre les chambres sont </b>extrêmement appararentes.</b>
</p>
<p>
Ce concept si simple, peut être légèrement modifié pour obtenir d'autres résultats.<br>
Il est par exemple possible de mettre une <b>limite de recursivité</b> afin d'obtenir des salles plus grandes.<br>
</p>
<div class="row">
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/recur_10x10.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la méthode récursive avec un labyrinthe 10 par 10</i></sup></center>
</span>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/recur_20x20.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la méthode récursive (aléatoirsée) avec un labyrinthe 20 par 20</i></sup></center>
</span>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/recur_80x80.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la méthode récursive avec un labyrinthe 80 par 80</i></sup></center>
</span>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/recur_100x100.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la méthode récursive (aléatoirisée) avec un labyrinthe 100 par 100</i></sup></center>
</span>
</div>
</div>
<h4>Divisions récursives améliorées</h4>
<p>Pour finir, voici un algorithme de Jamis Buck, reprenant le concept de la méthode récursive.</p>
<p>
L'algorithme précédent, rend les passages entre les zones du labyrinthe <b>extrêmement visibles</b>.<br>
En repérant ce passage, il est possible de faire le chemin à l'envers et de trouver la solution.
</p>
<p>
Il est à noter que tous les labyrinthes possèdent ces passages. S'ils sont facilement repérables ici, c'est à cause des longs murs créés pour séparer les chambres.
</p>
<div class="row">
<div class="col-3">
<span class="image fit"><img src="images/Maze/bottleneck.png" alt="" /><center><sup><i>séparations trop visibles entre les chambres</i></center></sup></span>
</div>
<div class="col-5">
<p>
L'objectif de cette nouvelle méthode est de rendre <b>moins évidente</b> la séparation des zones du labyrinthes, tout en <b>gardant les propriétés</b> de la méthode récursive.
</p>
</div>
</div>
<div class="row">
<div class="col-5">
<p>
La solution trouvée par Jamis Buck consiste a aléatoiriser la forme des chambres. Au lieu d'avoir une surface rectangulaire, la chambre pourra être de <b>n'importe quelle forme</b>.<br>
C'est de cette manière qu'il réussit à "casser" le quadrillage de la méthode récursive basique.
</p>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/better_recur.mp4" type="video/webm">
</video>
<center><sup><i>illustration de la méthode de divisions récursives améliorée</i></sup></center>
</span>
</div>
</div>
<p>
La manière de trouver la forme de la chambre est assez atypique.<br>
La forme d'une chambre est désormais définie par une <b>région</b>.<br>
Une région, est un <b>ensemble de cellules</b>, voisines les unes des autres. (Il ne peut donc pas y avoir de cellule non-reliée à la région).
Initialement, toutes les cellules du labyrinthe forment une région.<br>
Pour séparer cette chambre, il faut créer deux sous-régions.
</p>
<p>
La manière dont ces sous-régions se partagent les cellules de la région principale est la suivante : <br>
Au début, chaque sous région commence depuis une cellule choisie au hasard.<br>
Les sous-régions <b>s'étendent</b> ensuite <b>aléatoirement</b> sur les cellules voisines.<br>
Ce processus se termine dès lors qu'il ne reste plus de cellule non affectée à une sous-région.<br>
C'est ainsi que nous nous retrouvons avec une chambre donc la séparation n'est plus aussi régulière et évidente que précédemment.
</p>
<p>
Le reste est assez similaire à la méthode récursive initiale.<br>
Une fois les sous-régions séparées et le passage entre elles créé, le processus se <b>répète de manière récursive</b> pour chaque sous-région.
</p>
<p>Algorithme :</p>
<pre><code>1 - Former une région contenant toutes les cellules du labyrinthe
2 - Séparer la région de la manière suivante :
1 - Choisir deux cellules de départ dans la région initiale et les assigner à une liste
2 - Choisir au hasard une cellule dans la liste puis la retirer de la liste
3 - Pour tous les voisins de la cellule choisie, si ils n'appartiennet pas déja à une sous-région
1 - Les rajouter à la liste
2 - Assigner chaque voisin à la sous-région de la cellule choisie
4 - Répéter 2.2 et 2.3 jusqu'à ce que la région soit séparéee
3 - Construire un mur séparant les deux sous-régions tout en laissant un passage dedans
4 - Répéter 2 et 3 de manière récursive pour chaque sous région</pre></code>
<p>
En limitant le nombre de récursions, il est possible de faire <b>varier la taille des chambres</b>.
A la place de n'avoir que des couloirs, il est désormais possible d'avoir des "salles" dans le labyrinthe. Ce qui change des générations vues auparavant.
</p>
<p>
En limitant la profondeur de récursivité, il se peut qu'une chambre apparaisse au <b>milieu d'une zone</b> et qu'elle ne soit donc pas connectée au reste des murs du labyrinthe.<br>
Lorsque les deux sous-régions cherchent à s'étendre, il arrive que l'une d'entre elles entoure l'autre, ce qui crée un îlot.<br>
Pour éliminer ces cas, il faut modifier l'étape 2.1 de l'algorithme.<br>
En plus de choisir aléatoirement une cellule depuis la liste, il faut en plus vérifier que celle-ci se trouve en <b>bordure</b> de la région.<br>
Il est désormais impossible que ces îlots se forment car les cellules de départs sont toujours rattachées au reste du labyrinthe.
</p>
<div class="row">
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/better_rec_10x10.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la méthode récursive améliorée avec un labyrinthe 10 par 10</i></sup></center>
</span>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/better_rec_30x30.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la méthode récursive améliorée avec un labyrinthe 30 par 30</i></sup></center>
</span>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/Maze/Demo/better_rec_room_30x30.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la méthode récursive améliorée (profondeur limitée) avec un labyrinthe 30 par 30</i></sup></center>
</span>
</div>
</div>
<h3>Structure du projet</h3>
<p>Comme annoncé au début, l'objectif est de <b>structurer</b> le mieux possible ce projet.</p>
<p>L'idée est d'avoir quelque chose d'extrêmement <b>modulable</b> et <b>améliorable</b>, afin de pouvoir rajouter ou bien modifier des éléments sans détériorer le travail existant.</p>
<p>
Pour l'utilisateur, le plus pratique est d'avoir une interface, offrant la possibilité de sélectionner et modifier :
<ul>
<li>La forme des cellules</li>
<li>Les dimensions du labyrinthe</li>
<li>La méthode de génération</li>
<li>D'autres paramètres, liés à la méthode choisie</li>
</ul>
</p>
<p>C'est cette interface qui, après avoir récolté les entrées de l'utilisateur, va transmettre les informations pour générer le labyrinthe demandé.</p>
<div class="row">
<div class="col-6">
<p>
Dans ce projet, le fait d'avoir <b>plusieurs formes</b> de cellules, oblige à réecrire les méthodes de génération pour chacune.<br>
Le plus simple est donc de créer un <b>intermédiaire</b> pour chacune de ces formes.<br>
Cet intermédiaire aura pour rôle, de transmettre les informations récoltées par l'interface, à la méthode choisie, mais également de générer le labyrinthe rempli de murs (si nécessaire).
</div>
<div class="col-5">
<span class="image fit"><img src="images/Maze/structure.png" alt="" /><center><sup><i>Schéma structure</i></center></sup></span>
</div>
</div>
<p>
Ce modèle permet de rajouter des méthodes de génération pour chaque forme de cellule.<br>
Il permet également d'implémenter de nouvelles formes <b>sans altérer</b> le fonctionnement de ce qui existe déjà.
</p>
<hr>
<h2>Conclusion</h2>
<p>En travaillant sur ce projet les week-ends et quelques heures par semaines il m'a fallu <b>2 mois</b> pour considérer ce projet comme stable et terminé.<br></p>
<p>
Il est cependant possible <b>d'améliorer</b> et <b>d'optimiser</b> certaines méthodes de génération mises en place. Quelques-unes, comme la récursive améliorée ou la méthode
de Kruskal sont assez demandeuses en ressources.
</p>
<p>
Avec du recul, je me rends compte que j'ai seulement gratté la surface de la génération de labyrinthes.<br>
Il existe une infinité de méthodes avec toutes leurs spécificités, avantages et inconvénients.<br>
Pour rendre ce projet un peu plus complet, il est possible de rajouter d'autres méthodes de génération ainsi que d'autres formes de cellules (triangulaires, circulaires, etc ...)
</p>
<p>
Une suite à ce projet pourrait être de <b>résoudre</b> les différents labyrinthes créés.
</p>
<hr>
<h2>Sources</h2>
<h3>Backtracker</h3>
<p>
Wikipedia | Maze generation algorithm : <a href="https://en.wikipedia.org/wiki/Maze_generation_algorithm">https://en.wikipedia.org/wiki/Maze_generation_algorithm</a><br>
Wikipedia | Retour sur trace : <a href="https://fr.wikipedia.org/wiki/Retour_sur_trace">https://fr.wikipedia.org/wiki/Retour_sur_trace</a><br>
Wikipedia | Backtracking : <a href="https://en.wikipedia.org/wiki/Backtracking">https://en.wikipedia.org/wiki/Backtracking</a><br>
The Coding Train | Coding Challenge #10.1: Maze Generator with p5.js - Part 1 : <a href="https://www.youtube.com/watch?v=HyK_Q5rrcr4">https://www.youtube.com/watch?v=HyK_Q5rrcr4</a><br>
Jamis Buck Blog | Recursive Backtracking : <a href="https://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking">https://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking</a>
</p>
<h3>Kruskal</h3>
<p>
Wikipedia | Algorithme de Kruskal : <a href="https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal">https://fr.wikipedia.org/wiki/Algorithme_de_Kruskal</a><br>
Techno Science | Algorithme de Kruskal - Définition et Explications : <a href="https://www.techno-science.net/definition/6472.html">https://www.techno-science.net/definition/6472.html</a><br>
Hurna | Kruskal : <a href="https://hurna.io/academy/algorithms/maze_generator/kruskal_s.html">https://hurna.io/academy/algorithms/maze_generator/kruskal_s.html</a><br>
Jamis Buck Blog | Kruskal's algorithm : <a href="https://weblog.jamisbuck.org/2011/1/3/maze-generation-kruskal-s-algorithm">https://weblog.jamisbuck.org/2011/1/3/maze-generation-kruskal-s-algorithm</a><br>
</p>
<h3>Prim</h3>
<p>
Wikipedia | Maze generation algorithm : <a href="https://en.wikipedia.org/wiki/Maze_generation_algorithm">https://en.wikipedia.org/wiki/Maze_generation_algorithm</a><br>
Wikipedia | Algorithme de Prim : <a href="https://fr.wikipedia.org/wiki/Algorithme_de_Prim">https://fr.wikipedia.org/wiki/Algorithme_de_Prim</a><br>
Jamis Buck Blog | Prims algorithm : <a href="https://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm">https://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm</a>
</p>
<h3>Récursif</h3>
<p>
Wikipedia | Maze generation algorithm : <a href="https://en.wikipedia.org/wiki/Maze_generation_algorithm">https://en.wikipedia.org/wiki/Maze_generation_algorithm</a>
Lauren K. Williams | Recursive Division Maze Generation : <a href="http://www.integral-domain.org/lwilliams/Applets/algorithms/recursivedivision.php">http://www.integral-domain.org/lwilliams/Applets/algorithms/recursivedivision.php</a><br>
Jamis Buck Blog | Recursive Division Algorithm : <a href="http://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm">http://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm</a><br>
</p>
<h3>Récursif amélioré</h3>
<p>
Jamis Buck Blog | Better recursive division : <a href="http://weblog.jamisbuck.org/2015/1/15/better-recursive-division-algorithm.html">http://weblog.jamisbuck.org/2015/1/15/better-recursive-division-algorithm.html</a><br>
</p>
<hr>
<h2>Téléchargement</h2>
<!-- petite liste de 2 collones avec les icone de github et itch-->
<ul class="actions">
<li><a href="https://github.com/B-Bischoff/Maze" class="button icon brands fa-github">Code source</a></li>
<li><a href="https://b-bischoff.itch.io/maze" class="button icon brands fa-itch-io">Exécutable</a></li>
</ul>
</div>
</div>
<!-- Footer -->
<footer id="footer">
<div class="inner">
<ul class="copyright">
<li>Design adapté depuis une création : <a href="http://html5up.net">HTML5 UP</a></li>
<li>Ce site utilise Google Analytics</li>
</ul>
</div>
</footer>
</div>
<!-- Scripts -->
<script src="assets/js/jquery.min.js"></script>
<script src="assets/js/browser.min.js"></script>
<script src="assets/js/breakpoints.min.js"></script>
<script src="assets/js/util.js"></script>
<script src="assets/js/main.js"></script>
</body>
</html>