-
Notifications
You must be signed in to change notification settings - Fork 4
/
cube3d.html
1736 lines (1471 loc) · 72.9 KB
/
cube3d.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
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!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>Cube3d</title>
<meta charset="utf-8" />
<meta http-equiv="refresh" content="0; url=https://website-b-bischoff.vercel.app/cube3d" />
<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>Cube3d</h1>
<span class="image main"><img src="images/cube3d/background.png" alt="" /></span>
<h2>Contexte</h2>
<p>
Ce projet de groupe proposé par l'école 42, offre la possibilité de créer un jeu vidéo en vue première personne en langage C.<br>
L'objectif est de pouvoir se déplacer dans un environnement en <b>pseudo 3D</b>.
</p>
<p>
Cube3d est un excellent projet pour découvrir les <u>applications concrètes des mathématiques</u>, mais également pour comprendre <u>l'organisation</u>, qui se trouve derrière le code des jeux vidéos.
</p>
<p>
C'est avec <a href="https://github.com/azanane">Anas Zanane</a> que nous réaliserons ce projet.
</p>
<hr>
<h2>Réalisation</h2>
<h3>Librairie graphique</h3>
<p>
Le sujet impose l'utilisation de la <b>librairie graphique</b> : MiniLibX.<br>
Cette librairie offre la possibilité de créer une fenêtre, gérer différents types d'événements ou encore dessiner sur des images.<br>
</p>
<h4>Création d'une fenêtre</h4>
<p>
Voici la manière la plus simple de créer une fenêtre à partir de la MiniLibX.<br>
La fonction <code>mlx_init</code> renvoie un pointeur qui indique où se trouve l'instance de la <code>mlx</code> dans la mémoire. Le rôle de cette instance, est d'établir une connexion entre notre programme et l'environnement graphique de l'ordinateur.<br>
La fonction <code>mlx_new_window</code> permet de définir la taille de la fenêtre ainsi que son titre.
</p>
<pre><code class="tip" markdown="1">int main(void)
{
void *mlx;
void *mlx_win;
mlx = mlx_init();
mlx_win = mlx_new_window(mlx, 1920, 1080, "A simple window");
mlx_loop(mlx);
}</pre></code>
<p>
C'est la fonction <code>mlx_loop</code> qui s'occupe <b>d'actualiser et d'afficher la fenêtre</b> sur notre écran.<br>
Nous allons à présent rendre cette fenêtre un peu plus intéressante en dessinant dessus.
</p>
<h4>Utilisation des images</h4>
<p>
Il existe la fonction <code>mlx_pixel_put</code> qui permet de placer des pixels sur notre fenêtre, cependant cette fonction est extrêmement lente car elle place le pixel puis actualise directement l'affichage.<br>
Par conséquent, j’ai opté pour un moyen plus optimisé, celui de stocker tous les pixels que l'on souhaite placer (à l'aide d'un buffer), et <b>seulement lorsque tous les pixels sont stockés</b>, la fenêtre met à jour son contenu.
</p>
<p>
Le moyen de stocker les pixels est d'utiliser une <b>image</b>.<br>
Cela implique de déclarer quelques variables supplémentaires comme :<br>
<ul>
<li>Une référence a l'instance de l'image</li>
<li>L'adresse mémoire de l'image</li>
<li>Le nombre de bits que chaque pixel occupe</li>
<li>La taille en mémoire qu'occupe une ligne de l'image</li>
<li>Une indication de quel boutiste (endian en anglais) utiliser</li>
</ul>
</p>
<pre><code>typedef struct s_data {
void *img;
char *addr;
int bits_per_pixel;
int line_length;
int endian;
} t_data;
int main(void)
{
void *mlx;
t_data img;
mlx = mlx_init();
img.img = mlx_new_image(mlx, 1920, 1080);
img.addr = mlx_get_data_addr(img.img, &img.bits_per_pixel, &img.line_length, &img.endian);
}</code></pre>
<p>
Notre image (ici de dimension 1920 par 1080 pixels) est créée grâçe à la fonction <code>mlx_new_image</code><br>
Les informations supplémentaires décrites précédemment sont assignées par la fonction <code>mlx_get_data_addr</code>.
</p>
<h4>Écriture sur une image</h4>
<p>
Le dernier élément manquant est un moyen de <b>placer des pixels</b> sur notre image.<br>
La fonction suivante permet, à partir d'une position dans l'image (une paire de coordonnées x et y), d'écrire une certaine valeur (représentant une couleur) à l'endroit correspondant dans la mémoire de l'image.
</p>
<pre><code>void my_mlx_pixel_put(t_data *data, int x, int y, int color)
{
char *dst;
dst = data->addr + (y * data->line_length + x * (data->bits_per_pixel / 8));
*(unsigned int*)dst = color;
}</code></pre>
<p>
Les informations de l'image sont ici extrêmement utiles, elles nous permettent de trouver le décalage entre la position de chaque pixel et son emplacement dans la mémoire.<br>
</p>
<p>
Il peut également être utile de <b>vérifier la cohérence des coordonnées</b> en début de fonction. Il se peut autrement que le programme aille chercher des données dans un espace mémoire ne lui appartenant pas, ce qui causerait <b>l'arrêt du programme</b>.
</p>
<h4>Affichage de l'image</h4>
<p>
Le moment tant attendu arrive, celui où nous allons voir des couleurs sur notre fenêtre !
A l'aide des notions expliquées jusqu'ici (initialisation d'une fenêtre et d'une image ainsi que la structure <code>data</code>) nous allons appeler <code>my_mlx_pixel_put</code> et afficher le contenu de l'image sur notre fenêtre.
</p>
<pre><code>int main(void)
{
void *mlx;
void *mlx_win;
t_data img;
mlx = mlx_init();
mlx_win = mlx_new_window(mlx, 1920, 1080, "A simple window");
img.img = mlx_new_image(mlx, 1920, 1080);
img.addr = mlx_get_data_addr(img.img, &img.bits_per_pixel, &img.line_length, &img.endian);
my_mlx_pixel_put(&img, 100, 100, 0x00FF0000);
mlx_put_image_to_window(mlx, mlx_win, img.img, 0, 0);
mlx_loop(mlx);
}</code></pre>
<p>
Ce petit code a pour effet de placer un pixel rouge (<a href="https://harm-smits.github.io/42docs/libs/minilibx/colors.html">explications du fonctionnement des couleurs de la MiniLibX</a>) à la position (en pixels) (100, 100) de notre fenêtre.<br>
C'est ensuite <code>mlx_put_image_to_window</code> qui met à jour la fenêtre en affichant le contenu de notre image.
</p>
<h4>Boucles</h4>
<div class="row">
<div class="col-6">
<p>
Pour créer un jeu vidéo avec lequel il est possible d'interagir, il est nécessaire d'implémenter ce qu'on appelle une "<b>game loop</b>".<br>
Une game loop <b>tourne en continu pendant l'exécution du jeu</b>. À chaque tour de boucle, le programme lit les entrées de l'utilisateur, met à jour le contenu du jeu puis actualise l'affichage.
</p>
</div>
<div class="col-2">
<span class="image fit">
<div class="col-3"><span class="image fit"><img src="images/cube3d/game-loop.png" alt="" /></span></div>
<center><sup><i>Schéma de game loop</i></sup></center>
</span>
</div>
</div>
<p>Voyons comment implémenter cette boucle a l'aide de la MiniLibX.</p>
<pre><code>int render_next_frame(void *program_struct);
int main(void)
{
void *mlx;
t_struct program_struct;
mlx = mlx_init();
mlx_loop_hook(mlx, render_next_frame, &program_struct);
mlx_loop(mlx);
}</code></pre>
<p>À chaque frame, la fonction <code>render_next_frame</code> sera appelée avec pour paramètre <code>program_struct</code>.</p>
<h4>Entrées utilisateur</h4>
<p>Un jeu vidéo ne serait pas très intéressant sans possibilités d'interaction.</p>
<p>
La MiniLibX fournit la possibilité d'<b>intercepter différents types d'événements</b>.<br>
Ces événements (par exemple liés à la souris ou au clavier) ne font qu'appeler une fonction quand ils se déclenchent.<br>
Plus concrètement, au début du programme, il faut indiquer à la MiniLibX quels sont les événements à écouter, et quelles fonctions seront appelées à leur déclenchement.
</p>
<p>
Les événements sont représentés par des nombres ; voici une liste (minime) des événements qui nous seront utiles :
<ul>
<li>02 : Touche du clavier pressée</li>
<li>03 : Touche du clavier relâchée</li>
<li>04 : Bouton de la souris pressé</li>
<li>05 : Bouton de la souris relâché</li>
<li>06 : Mouvement de la souris</li>
<li>17 : Clic sur la croix rouge de la fenêtre</li>
</ul>
</p>
<pre><code>int key_press(int keycode, t_struct *program_struct)
{
printf("Key pressed : %d\n", keycode);
return (0);
}
int main(void)
{
void *mlx;
void *mlx_win;
t_struct program_struct;
mlx = mlx_init();
mlx_win = mlx_new_window(mlx, 1920, 1080, "A simple window");
mlx_hook(mlx_win, 2, 0, key_press, &program_struct);
mlx_loop(mlx);
}</code></pre>
<p>
Rappelons que les actions effectuées en fonction des entrées utilisateur (par exemple déplacer le personnage du joueur) <b>se font dans la game loop</b> précédemment implémentée.<br>
Les événements ne vont donc pas agir sur les données du jeu (personnage, carte, interface ou autre), mais uniquement <b>mettre à jour les informations liées aux commandes</b> (état des touches du clavier, position du curseur, état des cliques de la souris).
</p>
<p>
Cela implique pour notre programme d'avoir un moyen de <b>stocker les données des périphériques</b>.<br>
Pour le clavier, il est possible de créer un tableau de booléens (de longueur le nombre de touches du clavier) qui contient pour chaque touche, <code>true</code> si elle est enfoncée, et <code>false</code> sinon.<br>
Voici le code permettant de gérer un tel tableau (d'une taille de 200 booléens) à l'aide des hooks 02 et 03.
</p>
<pre><code>int key_press(int keycode, t_struct *prg_struct)
{
if (keycode < 200)
prg_struct->keyboard[keycode] = 1;
return (0);
}
int key_release(int keycode, t_struct *prg_struct)
{
if (keycode < 200)
prg_struct->keyboard[keycode] = 0;
return (0);
}</code></pre>
<p>Ainsi, dans le game loop il ne reste qu'à vérifier si une touche est enfoncée à l'aide de la case correspondante du tableau pour effectuer une action.</p>
<h3>Définition de raycasting</h3>
<p>
Notamment connu pour les célèbres <u><i>Doom</i></u> et <u><i>Wolfenstein 3D</i></u> (dans les années 1990),
le raycasting 2D est une technique de calcul d'images permettant de <b>naviguer en vue première personne dans un monde 3D, à partir d'une carte en 2D</b>, composée de vides de murs.
<br>
Le principe consiste à tirer une multitude de rayons (depuis la position du joueur), et d'afficher les murs et ennemis, en fonction de la distance d'impact des rayons lancés.
<br>
Cette technique est extrêmement efficace car au lieu de lancer un rayon pour chaque pixel de l'écran, elle ne lance qu'un rayon par tranche verticale de pixel, ce qui réduit drastiquement le nombre de calculs.
</p>
<h3>Fondamentaux</h3>
<h4>Représentation de la carte</h4>
<p>
Comme dit précédemment, le raycasting se base sur un univers en <b>deux dimensions (vu du dessus)</b>.<br>
Voyons, pour commencer, comment représenter informatiquement une carte contenant des espaces vides et des murs.
</p>
<p>
Le moyen le plus simple est d'utiliser un tableau a deux dimensions. Chacune de ses cellules aura une valeur que nous pourrons utiliser pour afficher notre monde (par exemple 1 pour un mur et 0 pour un espace vide).
Un désavantage majeur de ce choix est que nous sommes contraints d'avoir un résultat où toutes les surfaces seront quadrillées.
</p>
<p>
Pour faciliter l'accès à nos données, <b>nous utiliserons une structure nommée <code>data</code></b>. Pour l'instant, elle ne contient que les éléments de la MiniLibX et les données utiles à notre tableau.
</p>
<pre><code>typedef struct s_data {
// MiniLibX
void *mlx;
void *mlx_win;
void *img;
char *addr;
int bits_per_pixel;
int line_length;
int endian;
int win_height;
int win_width;
// Tab
int **tab;
int tab_width;
int tab_height;
} t_data;</pre></code>
<p>
Il est important de dissocier les dimensions de la fenêtre (<code>win_height</code> et <code>win_width</code> qui sont en pixels) des dimensions du tableau
(<code>tab_height</code> et <code>tab_width</code> qui indiquent la hauteur et largeur du tableau <b>en nombre de cellules</b>).
</p>
<p>Voyons maintenant comment créer notre tableau à deux dimensions.</p>
<p>
Par la suite, pour visualiser le contenu du tableau, nous allons mettre <b>un mur toutes les deux cellules</b> (un mur étant la valeur 1).
</p>
<pre><code>int init_tab(t_data *data)
{
// Setting initial tab dimensions
data->tab_height = 15;
data->tab_width = 20;
// Allocating tab
data->tab = malloc(sizeof(int *) * data->tab_height);
if (data->tab == NULL) // Checking allocation error
return (1);
for (int y = 0; y < data->tab_height; y++)
{
data->tab[y] = malloc(sizeof(int) * data->tab_width);
if (data->tab[y] == NULL) // Checking allocation error
return (1);
// Putting values in tab
for (int x = 0; x < tab_width; x++)
{
data->tab[y][x] = (y % 2 + x) % 2;
}
}
return (0);
}</pre></code>
<h4>Affichage de la carte</h4>
<p>
L'objectif est désormais <b>d'afficher sur notre fenêtre</b> le contenu du tableau tout juste créé.<br>
Ici la difficulté est de passer des coordonnées dans le tableau aux coordonnées en pixels dans la fenêtre.
La première chose à faire est de définir la taille (en pixel) que prendront nos cellules sur l'écran. Cette variable, ici nommée <code>cell_size</code>, est stockée dans notre structure <code>data</code>.<br>
Dans tous les exemples se trouvant sur cette page, <code>cell_size</code> est prise égale à 40.
</p>
<pre><code>void print_grid(t_data *data)
{
for (int y = 0; y < tab_height; y++)
{
for (int x = 0; x < tab_width; x++)
{
// Calculating square coordinates
t_vector2_d top_left = {
x * data->cell_size, // x
y * data->cell_size // y
};
t_vector2_d bottom_right = {
top_left.x + data->cell_size,
top_left.y + data->cell_size
};
// Drawing square
if (data->tab[y][x] == 1) // If the cell is a wall
{
draw_rect_color(data, top_left, bottom_right, PINK);
}
}
}
}</code></pre>
<div class="row">
<div class="col-5">
<span class="image fit">
<div class="col-3"><span class="image fit"><img src="images/cube3d/basic_grid.png" alt="" /></span></div>
<center><sup><i>tableau de 20 x 15</i></sup></center>
</span>
</div>
<div class="col-5">
<p>Voici le résultat obtenu lorsque l'on affiche le tableau précédemment généré. Le damier provient de la formule <i>b = (y % 2 + x) % 2</i> appliquée à chaque cellule (où <i>b</i> est la valeur donnée à la cellule de coordonnées (<i>x</i>, <i>y</i>)), utilisée lors de la création du tableau. Je vous invite cependant à utiliser d'autres formules d'initialisation pour créer différents motifs.
</p>
</div>
</div>
<h4>Modification de la carte</h4>
<p>
Maintenant que nous avons la possibilité de visualiser le tableau, nous pouvons essayer de <b>le modifier pendant l'exécution du programme</b>.<br>
À la fin, nous pourrons placer des murs à l'aide du clic gauche, et les supprimer avec le clic droit de la souris.
</p>
<p>Cette fois-ci, le problème est de convertir la position de la souris sur la fenêtre (qui est en pixels) en coordonnées de cellules.</p>
<p>Encore une fois, c'est <code>cell_size</code> qui va nous nous aider à résoudre ce problème.</p>
<pre><code>void set_grid_cell(t_data *data, int x, int y)
{
// Converting pixel coordinates into tab coordinates
t_vector2_d tab_pos = {
x / data->cell_size, // x
y / data->cell_size // y
};
// Checking out of range coordinates
if (x < 0 || x >= data->tab_width || y < 0 || y >= data->tab_height)
return;
// Changing cell value according to mouse button
if (data->mouse_button == LMB)
data->tab[tab_pos.y][tab_pos.x] = 1;
else if (data->mouse_button == RMB)
data->tab[tab_pos.y][tab_pos.x] = 0;
}</code></pre>
<div class="row">
<div class="col-5">
<p>
Cette fonctionnalité nous sera très utile pour <b>tester l'implémentation de notre premier lancer de rayons.</b><br>
Il va consister à analyser la collision entre un mur et un rayon (défini par une droite tracée depuis la position du joueur et suivant une direction, elle-même définie par un autre point sur la carte).
</p>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/cube3d/set_grid.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de l'ajout et de la suppression de murs</i></sup></center>
</span>
</div>
</div>
<h4>Détection de collision</h4>
<div class="row">
<div class="col-5">
<p>
Pour aborder les choses simplement, commençons par <b>créer un rayon</b> allant du centre de la fenêtre à la position du curseur.<br>
Rien de plus simple, à l'aide d'une fonction de tracé de segments (l'algorithme de Bresenham dans l'exemple), on relie le centre de l'écran et la souris.
</p>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/cube3d/mouse_segment.mp4" type="video/webm">
</video>
<center><sup><i>démonstration du tracé de segment</i></sup></center>
</span>
</div>
</div>
<p>
L'idée ici est <b>d'afficher l'endroit où le rayon entre en collision avec un mur</b>.</p>
<p>
Il existe de nombreux moyens de faire ceci. Le moyen le plus simple serait de vérifier pour chaque pixel sur lequel passe le rayon, si celui-ci appartient à un mur.<br>
Cependant, dès que le nombre de rayons augmente, cette option devient extrêmement coûteuse et inutilisable en pratique.
</p>
<p>
Une méthode un peu plus élégante et adaptée à notre situation est <b>l'analayseur différentiel numérique (plus connu sous son acronyme anglais : DDA)</b>.<br>
Cet algorithme est utilisé pour faire varier des données depuis un point de départ, suivant une direction donnée par un point d'arrivée sur la carte.
</p>
<h4>Explications détaillées de la DDA</h4>
<p>
L'objectif est de <b>parcourir toutes les cellules sur une droite</b> partant de la position du joueur, selon une direction définie par un autre point sur la carte. Le rayon s'arrête lors d'une collision avec un mur détectée par la DDA<br>
Grace à ces deux points, nous pouvons <b>déterminer le chemin à emprunter</b> ; la difficulté est de pouvoir passer d'une cellule
à l'autre de manière optimisée (ne pas scruter deux fois le même endroit ou ne pas rater de cellules).
</p>
<p>
Nous voulons également être le plus précis possible étant donné que la position du joueur sera définie par des nombres à virgule.
</p>
<p>Comme on évolue sur une grille carrée, on se déplace sur un rayon depuis la position du joueur par <b>pas de 1 pixel</b>, selon la verticale ou l'horizontale.</p>
<p>
Pour ne rater aucune des cellules sur lesquelles passe notre rayon, il faut avancer à chaque pas suivant l'axe qui occasionne <b>le plus petit avancement sur le rayon</b>.<br>
Mesurer l'avancement sur un segment se fait en utilisant les propriétés du triangle rectangle.<br>
Il est possible de calculer la longueur parcourue sur une droite avec une direction quelconque pour un avancement de 1 pixel (selon l'axe horizontal ou selon l'axe vertical) en utilisant la pente de la droite, connue.<br>
La dernière étape est d'avancer selon l'axe qui fait parcourir la plus petite distance sur la droite, et réitérer jusqu'à rencontrer une collision.
</p>
<p>
Comme indiqué précédemment, la position de notre joueur n'aura pas forcément des coordonnées entières. Il faut donc initialement <b>calculer l'écart entre
la position de départ et les coordonnées entières les plus proches</b>.
</p>
<p>
Les deux morceaux de code qui suivent proviennent de la page <a href="https://lodev.org/cgtutor/raycasting.html"><i>Lode's Computer Graphics Tutorial</i></a> ainsi que du tutoriel de <a href="https://www.youtube.com/watch?v=NbSee-XM7WA"><i>javidx9</i></a>
sur le raycasting que vous pouvez consulter pour avoir les détails des calculs.
</p>
<p>La première étape de la DDA consiste à <b>initialiser toutes les données</b> dont nous avons besoin.</p>
<pre><code>t_vector2_f dda(t_data *data, t_vector2_f dest)
{
t_vector2_d origin = {win_width / 2, win_height / 2};
t_vector2_d map = origin; // Position used to check tab value
t_vector2_f dir = {dest.x - origin.x, dest.y - origin.y};
t_vector2_f side_dist; // Origin point offset to the nearest int positon
t_vector2_f delta_dist; // Length of the hyptenuse
delta_dist.x = (dir.x == 0) ? 1e30 : fabs(1.0f / dir.x); // 1e30 is a large value
delta_dist.y = (dir.y == 0) ? 1e30 : fabs(1.0f / dir.y);
t_vector2_d step;
if (dir.x < 0)
{
step.x = -1; // Calculating X step (depending on the direction)
side_dist.x = (origin.x - map.x) * delta_dist.x; // Calculating X gap to the nearest integer coordinate
}
else
{
step.x = 1;
side_dist.x = (map.x + 1.0f - origin.x) * delta_dist.x;
}
if (dir.y < 0)
{
step.y = -1; // Calculating Y step (depending on the direction)
side_dist.y = (origin.y - map.y) * delta_dist.y; // Calculating Y gap to the nearest integer coordinate
}
else
{
step.y = 1;
side_dist.y = (map.y + 1.0f - origin.y) * delta_dist.y;
}
}</code></pre>
<p>
Maintenant que nous savons comment parcourir un rayon, il est temps de partir à la <b>recherche d'une collision</b>.<br>
Voici une version extrêmement simple de la DDA.
</p>
<p><i>Le code suivant est la suite de la fonction DDA</i></p>
<pre><code>while (1)
{
if (side_dist.x < side_dist.y)
{
side_dist.x += delta_dist.x;
map.x += step.x;
}
else
{
side_dist.y += delta_dist.y;
map.y += step.y;
}
// Converting pixel coordinates to tab coordinates
t_vector2_d cell = {
map.x / data->cell_size,
map.y / data->cell_size
};
if (data->tab[cell.y][cell.x] == 1) // Is a wall
{
return (vector_d_to_f(map));
}
}
</code></pre>
<div class="row">
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/cube3d/ray_collision.mp4" type="video/webm">
</video>
<center><sup><i>démonstration de la détection de collision</i></sup></center>
</span>
</div>
<div class="col-5">
<p>
La vidéo suivante montre une démonstration de la DDA. A partir d'un point de départ (ici le centre de l'écran) le programme va prendre comme
direction la position du curseur. Il va alors parcourir toutes les cellules dans cette direction jusqu'à <b>rencontrer une collision, représentée par un cercle vert</b>.
</p>
</div>
</div>
<p>
Bien évidemment, si la carte n'est pas entourée de murs, <b>le programme continuera ses calculs à l'infini</b> (causant un magnifique plantage de l'application).<br>
Il faut donc bien faire attention à deux choses :
</p>
<ul>
<li>Imposer une <b>distance maximale</b> de recherche de collision</li>
<li>Vérifier que les coordonnées (en pixels) soient dans la <b>portée du tableau</b> (sous peine de créer une erreur de segmentation)</li>
</ul>
<p>
Dans le cas où la DDA ne rencontre pas de collision, il faut définir quelle valeur celle-ci retourne.<br>
Étant donné que les coordonnées de notre tableau sont exclusivement positives, <b>la valeur retournée par une "non-collision" sera un vecteur de (-1, -1)</b>.
</p>
<p>
Voici donc une version améliorée de la DDA. La recherche de collision est désormais <b>limitée par une distance maximale</b>, et <b>l'accès au tableau est sécurisé</b>.<br>
L'utilisation de l'instruction <code>continue</code> permet de détecter des collisions malgré le fait que le joueur soit hors de la carte.
</p>
<pre><code>// Using squared values is faster than using square root function
float ray_length = get_vector_d_length_squared(origin, map);
while (ray_length < data->view_dst * data->view_dst)
{
if (side_dist.x < side_dist.y)
{
side_dist.x += delta_dist.x;
map.x += step.x;
}
else
{
side_dist.y += delta_dist.y;
map.y += step.y;
}
ray_length = get_vector_d_length_squared(origin, map);
// Converting pixel coordinates to tab coordinates
t_vector2_d cell = {
map.x / data->cell_size,
map.y / data->cell_size
};
if (cell.x < 0 || cell.x >= data->win_width)
continue;
if (cell.y < 0 || cell.y >= data->win_height)
continue;
if (data->tab[cell.y][cell.x] == 1) // Is a wall
{
return (vector_d_to_f(map));
}
}</code></pre>
<h4>Utilisation d'une structure "rayon"</h4>
<p>Tout le concept du raycasting gravite autour de "rayons". Ils permettent à partir de notre monde 2D, d'afficher un résultat semblable à de la 3D.</p>
<p>Le champs de vision du joueur ne sera ni plus ni moins qu'<b>un ensemble de rayons</b>, ayant pour but de représenter à l'écran le monde environnant à partir des informations qu'il contient.</p>
<p>
La dernière vidéo illustre une version extrêmement basique d'un rayon.<br>
Cependant, comme il est nécessaire de stocker plusieurs informations pour un seul rayon, ils seront représentés par <b>une structure</b>.
</p>
<p>Pour le moment, les informations dont nous avons besoin sont les suivantes :</p>
<div class="row">
<div class="col-4">
<pre><code>typedef struct t_ray {
t_vector2_f hit_point;
t_vector2_d cell;
double length;
int side_hit;
double angle;
} t_ray;</code></pre>
</div>
<div class="col-7">
<ul>
<li>
<code>hit_point</code> : Cette variable va premièrement indiquer dans quelle <b>direction</b> chercher une collision (de la même manière que la souris dans l'exemple précédent).
Sa valeur sera mise à jour si une collision a été trouvée.
</li>
<li>
<code>cell</code> : <b>La position de la cellule</b> sur laquelle a eu lieu l'impact est conservée dans le vecteur <code>cell</code> en coordonées de cellules.
</li>
<li>
<code>length</code> : Pour afficher par la suite une portion de mur dans la phase de rendu, il est important de connaître <b>la longueur du rayon</b> (entre le joueur et le point d'impact du rayon).
</li>
<li>
<code>side_hit</code> : <b>Le côté du mur qui a été touché</b>, cette valeur allant de 0 à 3 va nous permettre d'afficher une couleur différente pour chaque orientation du mur.
</li>
<li>
<code>angle</code> : L'<b>angle en radians du rayon</b>, par rapport à une direction fixe (en l'occurence l'horizontale).
</li>
</ul>
</div>
</div>
<p>
L'utilisation de cette structure permet de garder en mémoire ces données pour les réutiliser plus tard.
Cela nécessite d'<b>allouer un tableau de N rayons</b> (stocké dans <code>data</code>) à l'initilisation de notre programme.
</p>
<p>
Certaines valeurs (comme <code>side_hit</code> ou <code>cell</code>) peuvent d'ores et déjà être obtenues depuis la fonction DDA.<br>
Pour mettre à jour les données d'un rayon au sein même de cette fonction, il faut modifier ses paramètres pour lui <b>passer une référence à un rayon</b>.
</p>
<p>Voici à quoi ressemble désormais le prototype de la fonction <code>dda</code></p>
<pre><code>t_vector2_f dda(t_data *data, t_ray *ray)</code></pre>
<p>
Il ne reste qu'à assigner <code>ray->cell</code> et <code>ray->side_hit</code> (ce dernier pouvant être determiné grâce à <code>side_dist</code>).
Mais surtout ! <b>Remplacer <code>dest</code> par <code>ray->hit_point</code></b> qui est calculé dans la partie suivante.
</p>
<h4>Création d'un cône de vision</h4>
<p>
Ce champ de vision du joueur sera constitué d'une multitude de rayons. On souhaite pouvoir modifier le <b>nombre de rayons</b>, la <b>largeur</b>, mais également la <b>distance maximale</b> de ce champ de vision.<br>
L'astuce est d'utiliser un segment afin de savoir où seront placés nos rayons. La position et la dimension de ce segment seront définies par la distance de vision ainsi que la largeur du champ de vision.
</p>
<p>Nous allons commencer par limiter la longueur du segment [centre de l'écran ; curseur] par une distance maximale, <code>view_dst</code> stockée dans dans notre structure <code>data</code></p>
<pre><code>void create_rays(t_data *data)
{
t_vector2_d origin = {
data->win_width / 2,
data->win_height / 2
};
// Getting the angle (in radian) of mouse position according to the origin
double angle = get_angle(origin, data->mouse_pos);
t_vector2_d view_dst_pos = create_vector_d_from_origin(origin, angle, data->view_dst);
draw_circle_color(data, direction, GREEN);
}</code></pre>
<div class="row">
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/cube3d/ray_max_length.mp4" type="video/webm">
</video>
<center><sup><i>affichage de </i><code>view_dst_pos</code></sup></center>
</span>
</div>
<div class="col-5">
<p>
L'utilisation d'une distance maximale de vision permet de rendre <b>les capacités visuelles du joueur adaptables</b> à différents scénarios.<br>
Elle permet également de <b>ne pas tirer un rayon à l'infini</b> si aucun obstacle ne se trouve sur son chemin.
</p>
</div>
</div>
<p>
La fonction <code>create_vector_d_from_origin</code> permet depuis une position de départ, de créer un vecteur dans une direction spécifique (donnée par un angle en radians) et d'une longueur donnée (en pixels).
</p>
<div class="row">
<div class="col-7">
<p>
Nous voilà avec le centre de la base du cône de vision. Pour trouver la longueur de la base du cône, le plus simple est de considérer que nous travaillons sur 2 triangles rectangles.
</p>
<p>
Ici nous voulons définir la largeur de notre champ de vision à partir d'un angle. Rien de plus facile, il suffit d'utiliser la formule (tout droit tirée de SOH-CAH-TOA) qui dit : <br>
Le côté opposé d'un triangle rectangle est égal à la tangente de l'angle multiplié par son côté adjacent.<br>
Attention cependant, dans notre cas, l'angle est divisé par deux car nous avons séparé notre cône en deux triangles rectangles.
</p>
</div>
<div class="col-4">
<span class="image fit">
<span class="image fit"><img src="images/cube3d/schema-cone.png" alt="" /></span>
</span>
</div>
</div>
<p>
Il ne reste qu'à placer les deux points à la base de notre cône.<br>
Le plus pratique est de réutiliser la fonction <code>create_vect_d_from_origin</code>, et depuis <code>view_dst_pos</code> créer un vecteur de la longueur du côté opposé.<br>
L'angle du premier point sera la direction du joueur +45° et -45° pour le second (soit + ou - π / 4 en radians).
</p>
<pre><code>void create_rays(t_data *data)
{
t_vector2_d origin = {data->win_width / 2, data->win_height / 2};
// Getting the angle (in radian) of mouse position according to the origin
double angle = get_angle(origin, data->mouse_pos);
t_vector2_d view_dst_pos = create_vector_d_from_origin(origin, angle, data->view_dst);
draw_circle_color(data, view_dst_pos, GREEN);
int opposite_length = tan(degree_to_radian(data->fov / 2)) * data->view_dst;
t_vector2_f opposite_vect[2] = {
create_vector_f_from_origin(vector_d_to_f(view_dst_pos), angle + PI / 2, opposite_length),
create_vector_f_from_origin(vector_d_to_f(view_dst_pos), angle - PI / 2, opposite_length)
};
draw_circle_color(data, opposite_vect[0], BLUE);
draw_circle_color(data, opposite_vect[1], RED);
}</code></pre>
<div class="row">
<div class="col-5">
<p>
Il est important de noter que l'angle total du champ de vision <b>ne pourra jamais atteindre (ni dépasser) les 180°</b>.<br>
En effet, dans ce cas la base du cône serait plus longue que le champ de vision ne serait large. À 180°, la longueur de la base du cône est analytiquement infinie (ce qui déplaira certainement à votre ordinateur).
</p>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/cube3d/cone_base.mp4" type="video/webm">
</video>
<center><sup><i>démonstration avec </i><code>view_dst</code> <i>= 100 pixels et </i><code>fov</code><i> = 90°</i></sup></center>
</span>
</div>
</div>
<p>La dernière étape est de générer les directions de N rayons entre les deux vecteurs de la base du cône.</p>
<p>
La méthode de l'<b>interpolation linéaire</b> permet de résoudre ce problème.<br>
Son utilité est de pouvoir <b>trouver les valeurs entre un minimum et un maximum</b>.<br>
Cette fonction prend trois paramètres : un minimum, un maximum et une valeur d'interpolation (entre 0 et 1).
</p>
<p>
Si la valeur d'interpolation est égale à 0, la valeur minimale sera retournée, à l'inverse, si elle est égale à 1, la valeur maximale sera renvoyée. Enfin, si la valeur d'interpolation est égale à 0,5 la valeur retournée sera l'exact milieu entre le minimum et le maximum, et il en est de même de manière proportionnelle pour toute les valeurs entre 0 et 1.
</p>
<p>
Pour appliquer ce concept à des vecteurs il faut simplement faire <b>une interpolation linéaire par composante du vecteur</b> (une pour X et une autre pour Y).<br>
</p>
<p>Il suffit de calculer l'espacement des points à interpoler en fonction du nombre de rayons et le tour est joué.</p>
<p>Le code suivant est la suite de la fonction <code>create_rays</code></p>
<pre><code>double increment = 1.0f / (data->rays_nb - 1.0f);
for (int i = 0; i < data->rays_nb; i++)
{
t_vector2_f vector = vector_f_lerp(opposite_vect[0], opposite_vect[1], increment * i);
bresenham(data, origin, vector, YELLOW);
data->rays[i].angle = get_angle_f(origin, vector); // Set ray angle
data->rays[i].hit_point = vector; // Set ray direction
}</code></pre>
<div class="row">
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/cube3d/rays_interpolation.mp4" type="video/webm">
</video>
<center><sup><i>démonstration avec </i><code>view_dst</code><i> = 250 pixels, </i><code>fov</code><i> = 90° et 5 rayons</i></sup></center>
</span>
</div>
<div class="col-5">
<p>
Nous possédons maintenant plusieurs rayons simulant notre champ de vision. Cependant, si vous essayez de placer des murs devant eux, <b>tous passeront au travers</b>.<br>
Fort heureusement nous possédons déja l'algorithme de DDA permettant de <b>détecter une collision</b> à partir d'une position de départ et d'un rayon.
</p>
</div>
</div>
<p>
Nous aurons plus tard besoin de connaître la longueur des rayons ayant touché un mur, il faut donc un moyen d'indiquer quand les rayons n'ont pas heurté de mur.<br>
De la même manière que pour la DDA, <b>nous symboliserons une "non-collision" par une longueur de -1</b>.
</p>
<pre><code>void calculate_collisions(t_data *data)
{
t_vector2_d origin = {data->win_width / 2, data->win_height / 2};
for (int i = 0; i < data->rays_nb; i++)
{
t_vector2_f res = dda(data, &data->rays[i]); // Passing ray reference
if (res.x != -1 && res.y != -1) // Hit
{
data->rays[i].hit_point = res; // Update ray hit point
data->rays[i].length = get_vector_f_length(origin, res);
}
else
{
data->rays[i].length = -1;
}
bresenham(data, origin, data->rays[i].hit_point, YELLOW);
}
}</code></pre>
<div class="row">
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/cube3d/calculate_collisions.mp4" type="video/webm">
</video>
<center><sup><i>démonstration des collisions avec 100 rayons et une distance maximale de 1000 pixels</i></sup></center>
</span>
</div>
<div class="col-5">
<p>
Voici le résultat obtenu une fois tous les rayons passés dans la DDA.<br>
N'oubliez pas d'<b>afficher uniquement le résultat à partir de cette fonction</b>, ou bien de tracer les traits d'une couleur différentes de ceux de la fonction <code>create_rays</code>.
</p>
</div>
</div>
<p>
Dans la vidéo un peu plus bas, la distance maximale de vision a été abaissée à 300 pixels.<br>
On constate alors <b>les rayons aux bords du cône de vision traversent parfois les murs</b>.
</p>
<p>
Ce phénomène provient du fait que la DDA cesse de chercher les collisions à partir de la distance maximale de vision.
Cependant, la manière dont nous avons généré nos rayons fait que <b>la distance des rayons aux extremités du cône, est supérieure à cette distance maximale</b>.
</p>
<p>
Pour régler cette imprécision visuelle, il faut normaliser le vecteur que reçoit le rayon à la longeur maximale de vision.<br>
Le cône de vision est désormais une portion de disque, ce qui rend le résutat juste et précis.
</p>
<div class="row">
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/cube3d/bug_collision.mp4" type="video/webm">
</video>
<center><sup><i>démonstration du cône de vision imprécis sur les bords</i></sup></center>
</span>
</div>
<div class="col-5">
<span class="image fit">
<video controls width="100%">
<source src="images/cube3d/bug_collision_fixed.mp4" type="video/webm">
</video>
<center><sup><i>démonstration du cône de vision circulaire</i></sup></center>
</span>
</div>
</div>
<i>partie de code provenant de la fonction </i><code>calculate_collisions</code>
<pre><code>if (res.x != -1 && res.y != -1) // Hit
{
data->rays[i].hit_point = res; // Update ray hit point
data->rays[i].length = get_vector_f_length(data->player.pos, res);
}
else
{
data->rays[i].length = -1;
data->rays[i].hit_point = create_vector_f_from_origin(origin, get_angle_f(origin, vector), data->view_dst);
}</code></pre>
<h4>Déplacements</h4>
<p>Pour rendre notre programme un peu plus interactif essayons de <b>controler la position du joueur</b> avec le clavier.</p>
<p>
Pour ordonner les données, <b>le joueur possèdera sa propre structure</b> contenant ses informations.<br>
Une variable <code>player</code> (de type <code>t_player</code> sera donc ajoutée à la structure <code>data</code>).
</p>
<pre><code>typedef struct s_player {
t_vector2_f pos;
t_vector2_d view_dst_pos;
t_vector2_f dir;
} t_player</code></pre>
<p></p>
<p>
La position du joueur est définie par un vecteur utilisant des nombres flottants. Ce n'est pas obligatoire mais cela permet de rajouter un peu de précision et de fluidité aux déplacements.<br>
Nous avons précédemment utilisé <code>view_dst_pos</code> pour générer les rayons. Il fait sens de rattacher cette variable au joueur étant donné que lui seul l'utilise et que nous en aurons besoin à différents endroits du programme.<br>
Enfin, <code>dir</code> permet de stocker en radians, la direction dans laquelle regarde le joueur (par rapport à l'axe horizontal).
</p>
<p>
Pour détecter et exécuter les entrées utilisateur, nous allons comme indiqué par le concept de <i>gameloop</i>, créer une fonction en début d'<i>update</i> à cet effet.
</p>
<pre><code>int player_input(t_data *data)
{
if (data->keyboard[KEY_A] == 1)
rotate_left(data);
if (data->keyboard[KEY_E] == 1)
rotate_right(data);
return (0);
}</code></pre>
<p>