Big Tuto SFML 2 : Rabidja - Chapitre 25

Big Tuto SFML 2 : Rabidja v. 3.0

Annexe 5 : Collisions lumineuses : la théorie !

Tutoriel présenté par : Skrool
Relecture et corrections : Jérémie F. Bellanger (Jay81)
Date d'écriture : 10 avril 2015
Date de révision : 20 mars 2016

      Introduction

   Maintenant que nous avons nos belles lumières, que diriez-vous de gérer les collisions avec ?  C'est ce que nous allons faire maintenant. Mais attention, c'est loin d'être simple, je vous conseille de relire les chapitres précédents si vous ne les avez pas bien compris, ils possèdent la base de nos lumières.

   Nous allons, dans ce chapitre, et ce avant de nous occuper du code, faire une grosse partie théorie. Il ne faudrait pas que nous ne comprenions pas ce que nous codons, quand même ! 

A la fin de cette grosse annexe : "Et la lumière fut !" (enfin, c'est une façon de parler... )

      La grosse théorie

   Vous vous souvenez du moment où nous avons ajouté un tableau dynamique de triangles à nos lumières ?  Je vous avais dit que nous allions subdiviser nos triangles et déplacer nos points sur nos murs. Il s'agit là des deux seules techniques que nous allons utiliser pour modifier nos lumières.   

   Cela parait simple dit comme ça, mais il ne s'agit que du principe.

   En effet, nous devons d'abord étudier nos cas de figures un par un :

Nos différents cas de figure

   Vous voyez ici nos trois cas de figures possibles :

   - Dans le premier cas, nous avons un mur qui coupe les deux cotés adjacents au centre (O). Ce cas est le plus simple puisqu'il ne nécessite aucune subdivision. Nous pouvons le régler en déplaçant les points p1 et p2 respectivement à l'intersection mur/segment [O p1] et mur/segment [O p2]. Cela se fait simplement en calculant le point d'intersection des droites formé par les segments. 

Cas de figure 1

   - Le second cas est plus complexe. Le mur coupe un côté adjacent et le côté opposé. Il est cette fois-ci nécessaire de subdiviser le triangle au niveau de l'intersection mur/côté opposé, et de replacer le point p1 ou p2 (selon la cas) à l'intersection mur/segment [0 p1] ou mur/segment [0 p2]. Il ne faudra pas oublier de tester les collisions avec le nouveau sous-triangle. 

Cas de figure 2

   - Le dernier cas est le plus difficile à traiter. Ici, une des extrémités du mur de trouve dans les triangles, et le mur ne coupe le triangle qu'une fois. Il s'agit en fait du premier cas que nous devrons tester. Nous allons là aussi subdiviser notre triangle de manière à ce que le coté commun passe par le point se situant dans le triangle. Nous aurons ainsi un effet de trainée lumineuse.

Cas de figure 3

   Avec ces trois cas de figure, nous pourrons gérer les collisions avec tous les murs. Voici un exemple en application :

Exemple 1

Exemple 2

   Comme vous pouvez le voir, la lumière s'arrête au sol et au mur. Les pentes seront gérées aussi, mais les plateformes posent problème. La tile affichée n'est pas carrée, mais la lumière la gère comme un carré, créant ce carré sans lumière. 

   Nous pourrons régler ce problème de deux manières :

- Soit on indique à notre programme les tiles avec lesquelles la lumière réagira différemment,
- Soit on dit au programme "ne teste pas la lumière avec ces tiles".

   Maintenant que nous savons comment couper la lumière, nous allons devoir déterminer avec quoi elle doit être coupée. Nous allons donc partitionner l'espace.

   Derrière ce nom ultra classe , se cache une technique très pratique pour gérer les collisions. Nous allons créer une rectangle autour du triangle, dans lequel nous allons tester toutes les tiles grâce à une double boucle for (comme celle de la fonction draw()), pour voir si elles sont solides, et couper le triangle en conséquent.

   Sur cette représentation de notre partition de l'espace pour un triangle, nous avons notre triangle en jaune, le rectangle crée à partir de la boîte englobante du triangle (la SFML gère la création du rectangle nativement), et notre damier rouge, là où les tiles seront testées. Notez que le damier dépasse notre boite englobante pour pouvoir tester toutes nos tiles.

   Pour chaque tile solide, nous testerons ses quatre côtés. Nous ferons notre partition de l'espace dans la fonction addTriangle(), et nous ajouterons nos triangles avec une autre fonction, du nom de AddShape(), qui sera elle-même appelée par AddTriangle().

   Pourquoi cela ?

   Regardez ce schéma  :

   Avec un système à une fonction, nous avons notre double boucle for qui est appelée à chaque sous-division, ce qui nous prend beaucoup de ressources CPU, alors qu'avec le système à sous-fonction AddShape(), on teste une fois pour toute nos tiles pour notre triangle. Et cela nous permet d'économiser des centaines de doubles boucles for par frame, et c'est notre CPU qui dit merci ! 

   Mais nous allons faire face à un autre problème qui risque d'engendrer de nombreux crashs :

Ce que nous voulons VS ce que nous avons

   Cette image simplifiée nous met face à un gros problème : chaque tile générera une subdivision par triangle. Ce qui fait qu'on se retrouva avec des multitudes de subdivisions, donc des multitudes d'appels à la fonction AddShape(), et notre compilateur nous dit NOOOOOOONNNN !  et fait ce qu'on appelle un dépassement de pile. 

   Un dépassement de pile survient quand une fonction s'appelle elle-même trop de fois, et que le compilateur n'arrive plus à savoir où il en est.  Le nombre d'appels nécessaires pour faire ce joli BAD_ACCESS dépend de l'ordinateur sur lequel est exécuté le programme. 

   Pour régler ce souci, nous allons devoir "fusionner" les côtés alignés des tiles pour, au lieu de faire 15 tests comme sur le schéma précédent, soit 15 subdivisions, faire un unique test, pour une voire 0 subdivision.

   C'est bien joli tout ça, mais on va faire comment pour fusionner ces segments ? 

   Nous allons créer une struct qui comprendra uniquement deux variables sf::Vector2f pt1 et pt2.
   Nous allons nommer cette struct Wall et nous allons créer un tableau dynamique de Walls dans AddTriangle(), que nous remplirons tout d'abord avec chaque côté de tile dans nos boucles for, puis, nous fusionnerons les murs qui seront alignés et côte à côte. Ensuite, dans AddShape(), nous testerons les collisions avec ces Walls. De cette manière, nous réduirons le nombre de subdivisions, ainsi que le nombre de calculs pour notre pauvre CPU. 

   Nous allons aussi passer à notre fonction AddShape() une variable qui indiquera à notre fonction à partir de quel mur, tester les collisions, variable que nous incrémenterons après chaque test de collision. En effet, pas besoin de retester un mur alors qu'il a déjà été testé, c'est du temps perdu. 

   Voilà, c'était tout pour la théorie, maintenant, place au code dans l'annexe suivante ! 

   @ bientôt,

             Skrool.