-
Notifications
You must be signed in to change notification settings - Fork 1
/
algos.html
568 lines (463 loc) · 23.2 KB
/
algos.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
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<link href="python.png" rel="icon" type="image/png"/>
<title>Algos</title>
<link rel="stylesheet" type="text/css" href="base.css" />
<script src="https://code.jquery.com/jquery-2.1.4.js"></script>
<script src="animations.js"></script>
<script src="utils.js"></script>
<script src="slides.js"></script>
<style>
body {
background: url('diamond.jpg');
}
img:not(.free), pre {
max-width: 100%;
}
pre {
overflow-x: auto;
border: 1px solid #ccc;
}
section[name=rebond] img:not([src^=flag]) {
background-color: white;
border: 2px solid black;
padding: 5px;
}
section[name=rebond] .slideshow .slide.next {
cursor: pointer;
}
section[name=rebond] figure, section[name=rebond] img:not([src^=flag]) {
width: 500px;
text-align: center;
}
:not(pre) > code {
border: 1px solid #ccc;
display: inline-block;
padding: 2px;
}
</style>
<link id="stylesheet" rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/8.9.1/styles/default.min.css">
<script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/8.9.1/highlight.min.js"></script>
<script>
$(function(){
utils.dedentPreCode()
hljs.initHighlightingOnLoad()
utils.makeTitleLinks()
utils.smoothLinks()
})
</script>
</head>
<body class="algos">
<div id="wrapper">
<h1 class="nocontent"><!--
--><a class="homeicon" href="index.html"></a><!--
--><span class="text"> Algorithmes utiles </span><!--
--></h1>
<nav>
<a href="algos.en.html"><img src="flag-en.png" /></a>
</nav>
<nav>
<a href="projets.html"> Projets </a>
</nav>
<nav>
<a href="#collisions">Collisions</a>
<a href="#afficherint"> Afficher des entiers </a>
<a href="#rebond"> Rebond </a>
<a href="#supprimer"> Supprimer </a>
<a href="#monde-infini"> Monde infini </a>
</nav>
<h2 id="collisions">Collisions</h2>
<section name="collisions">
<div><em><a href="algos.en.html" lang="en" hreflang="en"><img style="vertical-align:middle; margin-right: 5px;" src="flag-en.png"/>English here!</a></em></div>
<h3 id="rectangle-rectangle">Rectangle Rectangle</h3>
<p>
Pour détecter une collision rectangle-rectangle, il faut comparer la collision en X et en Y. Il y a collision si il y a collision en X <strong>et</strong> en Y.
</p>
<p>
Par exemple en X, on a 3 cas : <em>trop à gauche</em>, <em>trop à droite</em>, et dans le dernier cas ça touche.
<pre style="display:inline-block; vertical-align: middle;"><code class="python">
if le premier rectangle est totalement à gauche du deuxième:
ne touche pas
else:
if le premier rectangle est totalement à droite du deuxième:
ne touche pas
else:
touche
</code></pre>
<figure style="display:inline-block; vertical-align: middle;"><!--
--><div class="element"><img src="collision-intervalles-cas-1.png" /> <figcaption>Trop à gauche</figcaption></div>
<div class="element"><img src="collision-intervalles-cas-2.png" /> <figcaption>Trop à droite</figcaption></div>
<div class="element"><img src="collision-intervalles-cas-3.png" /> <figcaption>Collision</figcaption></div><!--
--></figure>
<p>
On continuera notre cascade de <code>if/else</code> en nous demandant si il est <em>trop haut</em> et <em>trop bas</em>. Ce qui nous fait 4 conditions à tester.
</p>
<pre style="display:inline-block; vertical-align: middle;"><code class="python">
# perso (personnage) et obj (objet) sont des rectangles définis par x1, y1, x2, y2 (voir figure)
if perso.x2 < obj.x1: # perso est trop à gauche
ne touche pas
elif perso.x1 > obj.x2: # perso est trop à droite
ne touche pas
elif perso.y2 < obj.y1: # perso est trop en haut
ne touche pas
elif perso.y1 > obj.y2: # perso est trop en bas
ne touche pas
else:
touche
</code></pre>
<figure style="display:inline-block; vertical-align: middle;">
<img height="400" src="collision-rectangle-shape-clean.svg" />
<figcaption>
Un rectangle et ses métriques ainsi que l'appel pygame <code>draw.rect</code> pour en dessiner un.
</figcaption>
</figure>
<p>
Pour la 3D, on continuera notre cascade avec <em>trop loin</em> et <em>trop proche</em>, nous menant à 6 conditions.
</p>
<p>
Cela peut s'écrire en une seule ligne avec des <em>or</em>.
</p>
<pre><code class="python">
if perso.x2 < obj.x1 or perso.x1 > obj.x2 or perso.y2 < obj.y1 or perso.y1 > obj.y2:
ne touche pas
else:
touche
</code></pre>
<p>
Et inverser la condition avec <em>not</em>.
</p>
<pre><code class="python">
if not(perso.x2 < objet.x1 or perso.x1 > objet.x2 or perso.y2 < objet.y1 or perso.y1 > objet.y2):
touche
else:
ne touche pas
</code></pre>
<p>
Pour certains jeux, on traite les collisions différemment en fonction du côté de collision, par exemple dans Mario, une collision par le haut d'un ennemi le tue, alors qu'une collision par le côté tue Mario. On gardera donc la cascade de <code>if/elif</code>.
</p>
<h3 id="point-rectangle">Point Rectangle</h3>
<p>
Pour avoir une collision point-rectangle, on peut voir le point comme un rectangle de taille zéro.
</p>
<pre><code class="python">
if not(perso.x2 < obj.x or perso.x1 > obj.x or perso.y2 < obj.y or perso.y1 > obj.y):
touche
else:
ne touche pas
</code></pre>
<h3 id="cercle-cercle">Cercle Cercle</h3>
<p>
Pour une collision cercle-cercle, il y a collision si la distance entre les deux centres est plus petite que la somme des rayons. Pour calculer la distance entre deux points, utilisez <a href="math.fr.html#pythagore">Pythagore</a>.
</p>
<pre style="display:inline-block; vertical-align: middle;"><code class="python">
distance = pythagore(centre1X - centre2X, centre1Y - centre2Y) # = sqrt(a*a + b*b) = sqrt(a**2 + b**2)
if distance < rayon1 + rayon2:
touche
else:
ne touche pas
</code></pre>
<figure style="display:inline-block; vertical-align: middle;"><!--
--><div class="element"><img src="collision-circle.png" /> <figcaption>Deux cercles qui ne se touchent pas</figcaption></div><!--
--></figure>
<p>
Remarquez que vu que la condition <em>distance < rayon1 + rayon2</em> est la même que <em>distance² < (rayon1 + rayon2)²</em>, le calcul peut se faire sans racine carrée :
</p>
<pre><code class="python">
dx = centre1x - centre2x
dy = centre1y - centre2y
if dx ** 2 + dy ** 2 < (rayon1 + rayon2) ** 2:
touche
else:
ne touche pas
</code></pre>
<h3 id="point-cercle">Point Cercle</h3>
<p>
Pour avoir une collision point-cercle, on peut voir le point comme un cercle de rayon zéro.
</p>
<pre><code class="python">
dx = centrex - px
dy = centrey - py
if dx ** 2 + dy ** 2 < rayon ** 2:
touche
else:
ne touche pas
</code></pre>
<h3 id="cercle-rectangle">Cercle Rectangle</h3>
<p>Voici le code :</p>
<pre><code class="python">
# cx,cy = centre du cercle
# rx,ry = centre du rectangle
# w,h = largeur/hauteur du rectangle
hrx, hry = w/2, h/2
clampX = min(max(cx - rx, -hrx), +hrx)
clampY = min(max(cy - ry, -hry), +hry)
closestX = rx + clampX
closestY = ry + clampY
if pythagore((closestX, closestY), (cx,cy)) <= rayon:
touche
else:
ne touche pas
</code></pre>
<p>
Ce code vient de
<a href="https://learnopengl.com/#!In-Practice/2D-Game/Collisions/Collision-detection">cette page</a>,
chapitre <em>AABB - Circle collision detection</em>.
</p>
<p>
Remarquez que faire
<code>y = min(max(x, m), M)</code>
revient à faire :
</p>
<pre><code class="python">
y = x
if y < m: # pas plus petit que le minimum !
y = m
else:
if y > M: # pas plus grand que le maximum !
y = M
</code></pre>
<p>
Le site <a href="http://learnopengl.com">learnopengl.com</a> est un très bon tutoriel pour apprendre de l'opengl <em>moderne</em> (2010) et donc la <em>programmation de shaders</em>.
</p>
</section>
<h2 id="rebond">Rebond</h2>
<section name="rebond">
<div><em><a href="algos.en.html#bounce" lang="en" hreflang="en"><img style="vertical-align:middle; margin-right: 5px;" src="flag-en.png"/>English here!</a></em></div>
<p>
Quand une balle (ou un rayon de lumière) rebondit sur un mur, il se passe ceci :
</p>
<figure>
<img class="slide" src="reflexion.state-Presentation.svg" />
</figure>
<h3>Angle</h3>
<p>
Une manière de voir le rebond est que <em>l'angle change</em> :
</p>
<figure class="slideshow">
<img class="slide next" src="reflexion.state-Angle X.svg" />
<img class="slide next" src="reflexion.state-Angle Y.svg" />
<div>
<button class="goto" s="1">Droite – Gauche</button>
<button class="goto" s="2">Haut – Bas</button>
</div>
</figure>
<ul>
<li>
Quand la balle rebondit sur le mur de droite (ou gauche), on a donc <em>θ' = 180° − θ</em>.
</li>
<li>
Quand la balle rebondit sur le mur du bas (ou du haut), on a donc <em>θ' = − θ</em>.
</li>
</ul>
<p>
On peut également trouver la formule pour quand le mur est à un angle quelquonque <em>α</em>. Pour le mur de droite, nous avions <em>α = 180°</em>, pour le mur du haut nous avions <em>α = 270°</em>.
</p>
<h3>Vecteur</h3>
<p>
On peut également voir ça <a href="math.html#vecteurs">vectoriellement</a>, on cherche à on cherche à calculer le nouveau <em>vecteur vitesse v'</em>.
</p>
<figure>
<img class="slide next" src="reflexion.state-Vector Elements.svg" />
</figure>
<ul>
<li>
Pour le mur de gauche (ou de droite), on a donc
<em>x' = − x</em> et <em>y' = y</em>.</li>
<li>
Pour le mur du haut (ou du bas), on a donc
<em>y' = − y</em> et <em>x' = x</em>.</li>
</ul>
<h3>Cas général</h3>
<p>
Le cas général, qui marche aussi en 3D, est quand le mur a un <em>vecteur normal</em> <strong>n</strong>, la formule sera donnée par la loi de la réflexion :
</p>
<pre><code class="py">
n = n / norm(n) # on normalise n, norm(n) = sqrt(n.x ** 2 + n.y ** 2)
nouveau_v = v + 2 * dot(n, v) * n # dot est le <a href="math.html#produit-scalaire">produit scalaire</a>, dot(n,v) = n.x * v.x + n.y * v.y
</code></pre>
<figure class="slideshow">
<img class="slide next" src="reflexion.state-Vector X.svg" />
<img class="slide next" src="reflexion.state-Reflexion.svg" />
<div>
<button class="goto" s="1">Normale</button>
<button class="goto" s="2">Réflexion</button>
</div>
</figure>
<p>
Remarquez que le <strong>signe</strong> du produit scalaire présent dans la formule permet de savoir si la balle rentre dans le mur (produit négatif) ou non (produit positif), si le produit est nul, elle avance paralèlement au mur (<strong>v</strong> et <strong>n</strong> sont perpendiculaires).
</p>
<p>
En 3D, nous rebondissons bien-sûr sur un <strong>plan</strong>, les plans ont également des <em>normales</em>.
</p>
</section>
<h2 id="afficherint">Afficher des entiers</h2>
<section name="afficherint">
<div><em><a href="algos.en.html#displayint" lang="en" hreflang="en"><img style="vertical-align:middle; margin-right: 5px;" src="flag-en.png"/>English here!</a></em></div>
<p>
Pour afficher des infos comme le nombre de vies ou les points, on a deux choix :
</p>
<ul>
<li>
Soit sous forme de nombre. Voir <a href="pygame8_texte.py.html">pygame8_texte.py</a> et <a href="theorie2_liste_while.py.html">theorie2 (en savoir plus)</a>.
</li>
<li>
Soit afficher une étoile par point gagné/vie restante. Cela fera travailler les boucles !
</li>
</ul>
</section>
<h2 id="supprimer">Supprimer correctement d'une liste</h2>
<section name="supprimer">
<div><em><a href="algos.en.html#delete" lang="en" hreflang="en"><img style="vertical-align:middle; margin-right: 5px;" src="flag-en.png"/>English here!</a></em></div>
<p>
Souvent dans les jeux, on a besoin de supprimer depuis une liste des éléments selon un critère.
</p>
<p>
Par exemple, on veut supprimer toutes les pièces qui sont en contact avec le joueur, ou o aimerait enlever de la liste des joueurs tout ceux qui n'ont plus de vie.
</p>
<p>
Prenons un exemple plus simple, nous avons une liste de nombre et voulons supprimer tous les nombres plus grand que 5.
</p>
<p>
L'approche naïve ne marche pas :
</p>
<pre><code class="py">
L = [1,2,7,8,1,3,6,7]
i = 0
while i < len(L):
if L[i] > 5:
del L[i]
i = i + 1
</code></pre>
<p>
La boucle <em>sautera</em> un élément. Je vous invite à tester le code dans <a href="pythontutor.html">pythontutor</a> pour voir le problème.
</p>
<p>
La solution est de ne pas incrémenter le compteur quand l'élement est supprimé :
</p>
<pre><code class="py">
L = [1,2,7,8,1,3,6,7]
i = 0
while i < len(L):
if L[i] > 5:
del L[i]
else:
i = i + 1
</code></pre>
<p>
Autre astuce : créer une variable pour se souvenir de la suppression.
</p>
<pre><code class="py">
L = [1,2,7,8,1,3,6,7]
i = 0
while i < len(L):
to_delete = False
if L[i] > 5:
to_delete = True
if to_delete:
del L[i]
else:
i = i + 1
</code></pre>
<p>
Autre astuce un peu moins efficace mais probablement plus facile à coder, créer une corbeille :
</p>
<pre><code class="py">
L = [1,2,7,8,1,3,6,7]
corbeille = []
for x in L:
if i > 5:
corbeille.append(x)
for y in corbeille:
L.remove(y)
</code></pre>
</section>
<h2 id="monde-infini">Monde infini</h2>
<section name="monde-infini">
<div><em><a href="algos.en.html#infinite-world" lang="en" hreflang="en"><img style="vertical-align:middle; margin-right: 5px;" src="flag-en.png"/>English here!</a></em></div>
<p>
Cette technique est utile pour faire un monde de taille bien plus grande que la fenêtre.
</p>
<p>
Imaginez avoir un personnage (image), des pièces (cercles), des ennemis (cercles) et des batiments (rectangles), chacun ont leur classe, leur position (x,y), largeur (w), hauteur (h), rayon (r) et sont tous dans leur listes respective.
</p>
<p>
Ma fenêtre est de taille <code>(700, 500)</code> mais mon monde est bien plus grand.
</p>
<p>
L'approche classique est de dessiner la scène comme ceci :
</p>
<pre><code class="py">
# personnage
image_perso.blit(ecran, [charac.x, charac.y])
# scène
for p in liste_piece:
pygame.draw.circle(ecran, JAUNE, [p.x, p.y], p.r)
for e in liste_ennemi:
pygame.draw.circle(ecran, ROUGE, [e.x, e.y], e.r)
for b in liste_batiment:
pygame.draw.rect(ecran, BLEU, [b.x, b.y, b.w, b.h])
</code></pre>
<p>
Je ne pourrai alors que voir les points entre <code>(0,0)</code> et <code>(700,500)</code> de mon monde.
</p>
<p>
L'idée est d'avoir une <em>caméra</em> qui se déplace, ici elle est en <code>(0,0)</code> mais si elle était en <code>(50,100)</code>, on verrait les points de <code>(50,100)</code> à <code>(750,800)</code>.
</p>
<p>
Un élément dont la <em>position dans le monde</em> vaut <code>(150,270)</code> se verrait alors dessiné sur l'écran en <code>(100,170)</code>.
</p>
<figure style="max-width:500px; text-align:center">
<img src="camera.svg" height=300 />
<figcaption>
Une caméra déplacée et quatre points avec leurs coordonnées dans le monde (en vert) et à l'écran (rouge).
</figcaption>
</figure>
<p>
Nous devons donc dessiner tous nos éléments en <code>(x - camera.x, y - camera.y)</code>.
</p>
<pre><code class="py">
# personnage
image_perso.blit(ecran, [charac.x <mark>- camera.x</mark>, charac.y <mark>- camera.x</mark>])
# scène
for p in liste_piece:
pygame.draw.circle(ecran, JAUNE, [p.x <mark>- camera.x</mark>, p.y <mark>- camera.x</mark>], p.r)
for e in liste_ennemi:
pygame.draw.circle(ecran, ROUGE, [e.x <mark>- camera.x</mark>, e.y <mark>- camera.x</mark>], e.r)
for b in liste_batiment:
pygame.draw.rect(ecran, BLEU, [b.x <mark>- camera.x</mark>, b.y <mark>- camera.x</mark>, b.w, b.h])
</code></pre>
<p>
Pour un rpg, le plus simple est généralement qu'à chaque tick, la caméra soit sur le joueur. Nous rajouterons donc la logique suivante à chaque tick :
</p>
<pre><code class="py">
# la camera suit automatiquement le perso
camera.x = perso.x
camera.y = perso.y
</code></pre>
<p>
Vu que le perso est dessiné en <code>(perso.x - camera.x, perso.y - camera.y)</code>, le perso sera toujours dessiné en <code>(0,0)</code>, on peut mettre la caméra un peu plus loin pour que le perso soit au milieu de l'écran (<code>350,250</code>) :
</p>
<pre><code class="py">
# la camera suit automatiquement le perso
camera.x = perso.x - 350
camera.y = perso.y - 250
</code></pre>
<p>
La position à l'écran du perso vaudra donc <code>(perso.x - camera.x, perso.y - camera.y)</code> <code> = (perso.x - (perso.x - 350), perso.y - (perso.y - 250)) </code><code> = (+350, +250)</code>
</p>
<p>
Mais libre à vous de faire une caméra plus fantaisiste ! Pour <a href="http://robertvandeneynde.be/jeu3D">un jeu que j'ai créé</a>, j'ai appliqué un <a href="physique.html#ressort">ressort</a> avec <a href="physique.html#frottement-lineaire">frottement linéaire</a> entre la caméra et le joueur et ça donnait très bien !
</p>
<pre><code class="py">
# la camera suit automatiquement le perso mais avec un peu de retard
alpha = 0.80 # 80% du déplacement est pris à chaque tick
camera.x = camera.x + alpha * (perso.x - 350 - camera.x)
camera.y = camera.y + alpha * (perso.y - 250 - camera.y)
</code></pre>
</section>
</div>
</body>
</html>