Algorithmes utiles

Collisions

English here!

Rectangle Rectangle

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 et en Y.

Par exemple en X, on a 3 cas : trop à gauche, trop à droite, et dans le dernier cas ça touche.


            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
            
Trop à gauche
Trop à droite
Collision

On continuera notre cascade de if/else en nous demandant si il est trop haut et trop bas. Ce qui nous fait 4 conditions à tester.


            # perso 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
            
Un rectangle et ses métriques ainsi que l'appel pygame draw.rect pour en dessiner un.

Pour la 3D, on continuera notre cascade avec trop loin et trop proche. Nous menant à 6 conditions.

Cela peut s'écrire en une seule ligne avec des or.


            if perso.x2 < obj.x1 or perso.x1 > obj.x2 or perso.y2 < obj.y1 or perso.y1 > obj.y2:
                touche
            else:
                ne touche pas
            

Et inverser la condition avec not.


            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
            

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 if/elif.

Point Rectangle

Pour avoir une collision point-rectangle, on peut voir le point comme un rectangle de taille zéro.


            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
            

Cercle Cercle

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 Pythagore.


            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
            
Deux cercles qui ne se touchent pas

Remarquez que vu que la condition distance < rayon1 + rayon2 est la même que distance² < (rayon1 + rayon2)², le calcul peut se faire sans racine carrée :


            dx = centre1x - centre2x
            dy = centre1y - centre2y
            if dx ** 2 + dy ** 2 < (rayon1 + rayon2) ** 2:
                touche
            else:
                ne touche pas
            

Point Cercle

Pour avoir une collision point-cercle, on peut voir le point comme un cercle de rayon zéro.


            dx = centrex - px
            dy = centrey - py
            if dx ** 2 + dy ** 2 < rayon ** 2:
                touche
            else:
                ne touche pas
            

Cercle Rectangle

Voici le code :


            # 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
            

Ce code vient de cette page, chapitre AABB - Circle collision detection.

Remarquez que faire y = min(max(x, m), M) revient à faire :


            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
            

Le site learnopengl.com est un très bon tutoriel pour apprendre de l'opengl moderne (2010) et donc la programmation de shaders.

Rebond

English here!

Quand une balle (ou un rayon de lumière) rebondit sur un mur, il se passe ceci :

Angle

Une manière de voir le rebond est que l'angle change :

On peut également trouver la formule pour quand le mur est à un angle quelquonque α. Pour le mur de droite, nous avions α = 180°, pour le mur du haut nous avions α = 270°.

Vecteur

On peut également voir ça vectoriellement, on cherche à on cherche à calculer le nouveau vecteur vitesse v'.

Cas général

Le cas général, qui marche aussi en 3D, est quand le mur a un vecteur normal n, la formule sera donnée par la loi de la réflexion :


                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 produit scalaire, dot(n,v) = n.x * v.x + n.y * v.y
            

Remarquez que le signe 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 (v et n sont perpendiculaires).

En 3D, nous rebondissons bien-sûr sur un plan, les plans ont également des normales.

Afficher des entiers

English here!

Pour afficher des infos comme le nombre de vies ou les points, on a deux choix :

Supprimer correctement d'une liste

English here!

Souvent dans les jeux, on a besoin de supprimer depuis une liste des éléments selon un critère.

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.

Prenons un exemple plus simple, nous avons une liste de nombre et voulons supprimer tous les nombres plus grand que 5.

L'approche naïve ne marche pas :


            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
            

La boucle sautera un élément. Je vous invite à tester le code dans pythontutor pour voir le problème.

La solution est de ne pas incrémenter le compteur quand l'élement est supprimé :


            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
            

Autre astuce : créer une variable pour se souvenir de la suppression.


            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
            

Autre astuce un peu moins efficace mais probablement plus facile à coder, créer une corbeille :


            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)
            

Monde infini

English here!

Cette technique est utile pour faire un monde de taille bien plus grande que la fenêtre.

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.

Ma fenêtre est de taille (700, 500) mais mon monde est bien plus grand.

L'approche classique est de dessiner la scène comme ceci :


            # 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])
            

Je ne pourrai alors que voir les points entre (0,0) et (700,500) de mon monde.

L'idée est d'avoir une caméra qui se déplace, ici elle est en (0,0) mais si elle était en (50,100), on verrait les points de (50,100) à (750,800).

Un élément dont la position dans le monde vaut (150,270) se verrait alors dessiné sur l'écran en (100,170).

Une caméra déplacée et quatre points avec leurs coordonnées dans le monde (en vert) et à l'écran (rouge).

Nous devons donc dessiner tous nos éléments en (x - camera.x, y - camera.y).


            # personnage
            image_perso.blit(ecran, [charac.x - camera.x, charac.y - camera.x])

            # scène
            for p in liste_piece:
                pygame.draw.circle(ecran, JAUNE, [p.x - camera.x, p.y - camera.x], p.r)
            for e in liste_ennemi:
                pygame.draw.circle(ecran, ROUGE, [e.x - camera.x, e.y - camera.x], e.r)
            for b in liste_batiment:
                pygame.draw.rect(ecran, BLEU, [b.x - camera.x, b.y - camera.x, b.w, b.h])
            

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 :


            # la camera suit automatiquement le perso
            camera.x = perso.x
            camera.y = perso.y
            

Vu que le perso est dessiné en (perso.x - camera.x, perso.y - camera.y), le perso sera toujours dessiné en (0,0), on peut mettre la caméra un peu plus loin pour que le perso soit au milieu de l'écran (350,250) :


            # la camera suit automatiquement le perso
            camera.x = perso.x - 350
            camera.y = perso.y - 250
            

La position à l'écran du perso vaudra donc (perso.x - camera.x, perso.y - camera.y) = (perso.x - (perso.x - 350), perso.y - (perso.y - 250)) = (+350, +250)

Mais libre à vous de faire une caméra plus fantaisiste ! Pour un jeu que j'ai créé, j'ai appliqué un ressort avec frottement linéaire entre la caméra et le joueur et ça donnait très bien !


            # 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)