{"id":185,"date":"2015-11-14T03:57:21","date_gmt":"2015-11-14T02:57:21","guid":{"rendered":"http:\/\/www.cmarzin.fr\/site\/?p=185"},"modified":"2016-01-08T00:14:03","modified_gmt":"2016-01-07T23:14:03","slug":"collisions","status":"publish","type":"post","link":"https:\/\/www.cmarzin.fr\/site\/2015\/11\/14\/collisions\/","title":{"rendered":"Collisions"},"content":{"rendered":"<p><script type=\"text\/javascript\" src=\"[insert_php]echo get_site_url();[\/insert_php]\/content\/tutos\/collisions\/jeu.js\"><\/script><\/p>\n<div class=\"sources\"><i class=\"fa fa-download\"><\/i> <a href=\"[insert_php]echo get_site_url();[\/insert_php]\/content\/tutos\/collisions\/collisions.rar\">Javascript<\/a> <a href=\"[insert_php]echo get_site_url();[\/insert_php]\/content\/tutos\/collisions\/collisionsfla.rar\">Actionscript<\/a>\n<\/div>\n<h2 class=\"bloctitle\">Pr\u00e9sentation<\/h2>\n<div class=\"bloc\">\n<div class=\"captures\">\n\t\t<style type=\"text\/css\">\n\t\t\t#gallery-1 {\n\t\t\t\tmargin: auto;\n\t\t\t}\n\t\t\t#gallery-1 .gallery-item {\n\t\t\t\tfloat: left;\n\t\t\t\tmargin-top: 10px;\n\t\t\t\ttext-align: center;\n\t\t\t\twidth: 25%;\n\t\t\t}\n\t\t\t#gallery-1 img {\n\t\t\t\tborder: 2px solid #cfcfcf;\n\t\t\t}\n\t\t\t#gallery-1 .gallery-caption {\n\t\t\t\tmargin-left: 0;\n\t\t\t}\n\t\t\t\/* see gallery_shortcode() in wp-includes\/media.php *\/\n\t\t<\/style>\n\t\t<div id='gallery-1' class='gallery galleryid-185 gallery-columns-4 gallery-size-thumbnail'><dl class='gallery-item'>\n\t\t\t<dt class='gallery-icon landscape'>\n\t\t\t\t<a href='https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions3.jpg' title=\"\" data-rl_title=\"\" class=\"rl-gallery-link\" data-rl_caption=\"\" data-rel=\"lightbox-gallery-1\"><img width=\"300\" height=\"169\" src=\"https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions3-300x169.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions3-300x169.jpg 300w, https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions3.jpg 462w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a>\n\t\t\t<\/dt><\/dl><dl class='gallery-item'>\n\t\t\t<dt class='gallery-icon landscape'>\n\t\t\t\t<a href='https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions4.jpg' title=\"\" data-rl_title=\"\" class=\"rl-gallery-link\" data-rl_caption=\"\" data-rel=\"lightbox-gallery-1\"><img width=\"300\" height=\"169\" src=\"https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions4-300x169.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions4-300x169.jpg 300w, https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions4.jpg 354w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a>\n\t\t\t<\/dt><\/dl><dl class='gallery-item'>\n\t\t\t<dt class='gallery-icon landscape'>\n\t\t\t\t<a href='https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions21.jpg' title=\"\" data-rl_title=\"\" class=\"rl-gallery-link\" data-rl_caption=\"\" data-rel=\"lightbox-gallery-1\"><img width=\"300\" height=\"169\" src=\"https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions21-300x169.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions21-300x170.jpg 300w, https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions21.jpg 373w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a>\n\t\t\t<\/dt><\/dl><dl class='gallery-item'>\n\t\t\t<dt class='gallery-icon landscape'>\n\t\t\t\t<a href='https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions1.jpg' title=\"\" data-rl_title=\"\" class=\"rl-gallery-link\" data-rl_caption=\"\" data-rel=\"lightbox-gallery-1\"><img width=\"300\" height=\"169\" src=\"https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions1-300x169.jpg\" class=\"attachment-thumbnail size-thumbnail\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions1-300x170.jpg 300w, https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions1.jpg 545w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a>\n\t\t\t<\/dt><\/dl><br style=\"clear: both\" \/>\n\t\t<\/div>\n<\/div>\n<p> Voici une fiche pratique qui r\u00e9sume les diff\u00e9rentes collisions que vous pourrez utiliser dans un jeu. Cette partie du Wiki \u00e9tant d\u00e9di\u00e9e \u00e0 Flash et Actionscript, nous allons travailler dans ce format, cependant les formules qui vont suivre sont valables quel que soit vos outils de programmation.<\/p>\n<p>Les algorithmes sont connus et vous en trouverez de nombreuses repr\u00e9sentations partout sur la toile, en particulier sur ce tutoriel du site du Z\u00e9ro (lui m\u00eame tir\u00e9 d&rsquo;autres tutos, eux m\u00eame tir\u00e9s de bouquins, eux-m\u00eames tir\u00e9s de l&rsquo;apprentissage d&rsquo;autres personnes, etc\u2026.), il n&rsquo;y a pas vraiment d&rsquo;auteur d&rsquo;origine, elles sont pratiquement toutes tir\u00e9es de ce qu&rsquo;on apprend \u00e0 l&rsquo;\u00e9cole en g\u00e9om\u00e9trie\u2026<\/p>\n<p>Je ne suis pas une brute en maths, c&rsquo;est pourtant une discipline indispensable pour g\u00e9rer convenablement des tests de collisions, j&rsquo;ai donc eu du mal sur certaines formules et c&rsquo;est pourquoi je me suis mont\u00e9 ces fiches de r\u00e9vision. Je n&rsquo;entrerai pas forc\u00e9ment dans les d\u00e9tails, si vous souhaitez \u00e9tudier le d\u00e9veloppement des formules de base Wikipedia ou un bouquin de maths seront vos meilleurs amis, on va se contenter de passer en revue les formules utile et une petite impl\u00e9mentation de chacune en AS3.<\/p>\n<p>Vous trouverez \u00e9galement \u00e9norm\u00e9ment d&rsquo;infos, d&rsquo;explications et d&rsquo;astuces compl\u00e9mentaires sur ces liens, dont sont tir\u00e9es la plupart des formules utilis\u00e9es dans cette fiche :<\/p>\n<p>http:\/\/www.siteduzero.com\/informatique\/tutoriels\/theorie-des-collisions<br \/>\nhttp:\/\/tonypa.nicoptere.net\/ <\/p>\n<p>Tout le monde sait ce qu&rsquo;est une collision, selon Wikip\u00e9dia, une collision est un choc entre deux objets, elle peut \u00eatre \u00e9lastique ou in\u00e9lastique. Mais dans le monde r\u00e9el les objets ont une forme, une masse, ils sont r\u00e9gis par des lois physiques complexes, et ce qui peut para\u00eetre \u00e9vident m\u00eame \u00e0 un enfant de 2 ans (boum, \u00e7a fait mal = collision), ne l&rsquo;est pas forc\u00e9ment quand on travaille avec des objets virtuels qui par d\u00e9finition n&rsquo;existent pas dans le monde r\u00e9el.<\/p>\n<p>Alors comment d\u00e9terminer un choc entre deux objets en programmation ?<br \/>\nPour bien faire il nous faut affiner un peu la d\u00e9finition en disant que :<br \/>\nIl y collision entre deux objets lorsque au moins un point de l&rsquo;objet A est en contact avec la surface de l&rsquo;objet B.<\/p>\n<p>Ok on y est, il y a \u201cpoint\u201d et \u201csurface\u201d, de la g\u00e9om\u00e9trie\u2026\u2026. c&rsquo;est des maths !<\/p>\n<p>Fort heureusement, ou pas, il n&rsquo;existe pas qu&rsquo;une m\u00e9thode universelle pour tester une collision, mais diff\u00e9rentes techniques plus ou moins simples et adapt\u00e9es selon les situations, et nous allons commencer par \u2026 mettre les pieds dans le plat et tomber dans le pi\u00e8ge vicieux qu&rsquo;a tendu ce vil Flash \u00e0 tous les d\u00e9butants\u2026<br \/>\n<\/diV><\/p>\n<div class=\"lsep\"><\/div>\n<div class=\"sourcesdown\"><i class=\"fa fa-book\"><\/i> <a href=\"https:\/\/fr.wikipedia.org\/wiki\/D%C3%A9tection_de_collision\" target=\"_blank\">Wikipedia<\/a> <a href=\"http:\/\/forums.mediabox.fr\/wiki\/tutoriaux\/javascript\/divers\/fiche_collisions\" target=\"_blank\">Mediabox<\/a><\/div>\n<h2 class=\"bloctitle\">AABB : Axis Aligned Bounding Box<\/h2>\n<div class=\"bloc\">\nUne Bounding Box (BB) est g\u00e9n\u00e9ralement un rectangle, et tant que celui-ci n&rsquo;a pas subit de transformation dans l&rsquo;espace (par exemple une rotation), on peut le d\u00e9finir simplement \u00e0 l&rsquo;aide de quelques param\u00e8tres.<\/p>\n<p>x = coordonn\u00e9e de d\u00e9part sur l&rsquo;axe x<br \/>\ny = coordonn\u00e9e de d\u00e9part sur l&rsquo;axe y<br \/>\nwidth = largeur de la box<br \/>\nheigth = hauteur de la box<\/p>\n<p>Avec ces quelques coordonn\u00e9es on peut donc d\u00e9finir la surface de la box et la zone qu&rsquo;elle occupe dans le plan. Lorsque la BB est align\u00e9e avec les axes du plan dans lequel vous travaillez (la sc\u00e8ne par exemple pour Flash), elle est dite \u201cAxis Aligned\u201d autrement dit \u201calign\u00e9 avec les axes\u201d, et elle est donc tr\u00e8s facile \u00e0 d\u00e9finir, comme nous venons de le voir, car elle ne n\u00e9cessite aucun calcul math\u00e9matique suppl\u00e9mentaire. C&rsquo;est le type de Bounding Box le plus courant que vous serez amen\u00e9s \u00e0 utiliser dans vos jeux et il s&rsquo;agit tout simplement d&rsquo;un rectangle. Les deux classes de bases qui seront les plus utiles pour les calculs de collision en Actionscript sont Rectangle et Point.<br \/>\n<\/diV><\/p>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">AABB vs Point<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/aabb_vs_point.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>Pour v\u00e9rifier si un point se trouve \u00e0 l&rsquo;int\u00e9rieur d&rsquo;une Bounding Box classique (nomm\u00e9e ci-apr\u00e8s \u201cB\u201d) on peut utiliser la formule suivante :<\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionPointAABB(X, Y, B){\r\n\tif (X&gt;=B.x &amp;&amp; X&lt;B.x+B.width &amp;&amp; Y&gt;=B.y &amp;&amp; Y&lt;B.y+B.height) return true;\r\n\treturn false;\r\n}\r\n<\/pre>\n<p>On s&rsquo;assure alors que la AABB est en contact avec le point sp\u00e9cifi\u00e9 en v\u00e9rifiant si le point ( X,Y ) touche la surface de la box ( B ), c&rsquo;est sommairement ce que fait \u201chitTestPoint\u201d en AS3. Dans l&rsquo;exemple donn\u00e9 ci-dessus je regarde simplement si la souris se trouve dans la AABB en me servant de ses coordonn\u00e9es dans le plan, ce type de collision est utilis\u00e9 dans certains jeux mais aussi pour les menus par exemple, elle peut donc servir aussi pour l&rsquo;interactivit\u00e9 de vos interfaces.<br \/>\n<\/diV><\/p>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">AABB vs AABB<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/aabb_vs_aabb.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>Pour tester la collision entre deux objets on teste la collision entre deux rectangles dont les axes sont align\u00e9s (AABB). Ce genre de d\u00e9tection est utilis\u00e9e dans \u00e9norm\u00e9ment de jeux de tous types, des jeux de plateformes aux Shoot&#8217;em Up en passant par la plupart des jeux \u00e0 base de tuiles. Elle doit \u00eatre rapide car le nombre d&rsquo;objets \u00e0 tester est souvent assez important, imaginez un shoot&#8217;em up plein d&rsquo;ennemis o\u00f9 \u00e7a tire de partout. Et pour \u00eatre rapide il faut simplifier et limiter les calculs, c&rsquo;est l\u00e0 que r\u00e9side toute l&rsquo;astuce, c&rsquo;est pourquoi on ne va pas chercher \u00e0 tester la position de tous les points des surfaces occup\u00e9es par les deux box, mais simplement voir si une box est totalement en dehors d&rsquo;une autre. techniquement cela s&rsquo;exprime ainsi :<\/p>\n<p>Si la box 1 est compl\u00e8tement \u00e0 gauche<br \/>\nou compl\u00e8tement en haut<br \/>\nou compl\u00e8tement \u00e0 droite<br \/>\nou compl\u00e8tement en bas de la box 2, alors elle ne touche pas.<br \/>\nSinon, elle touche.<\/p>\n<p>Ca tombe bien, nous venons de voir comment g\u00e9rer la collision entre une box et une ligne, c&rsquo;est pratiquement la m\u00eame chose ici sauf qu&rsquo;on regarde si il n&rsquo;y a pas collision. Voyons \u00e7a avec deux box que je vais nommer A et B pour rendre la formule plus lisible : <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionBoxBox(A,B){\r\n\tif (A.y+A.height &lt; B.y || A.y &gt; B.y+B.height || A.x &gt; B.x+B.width || A.x+A.width &lt; B.x) return false;\r\n\treturn true;\r\n}\r\n<\/pre>\n<p>Notez qu&rsquo;une simple ligne droite (AA) peut-\u00eatre consid\u00e9r\u00e9e comme un rectangle ayant une largeur ou une hauteur minimale, cette formule marche donc \u00e9galement avec les lignes.<\/p>\n<p>Bien souvent cette solution est \u00e9galement utilis\u00e9e en pr\u00e9mices \u00e0 des collisions plus pr\u00e9cises car elle demande moins de calculs et peut donc \u00eatre utilis\u00e9e avant de tenter une collision fine, on regarde d&rsquo;abord grossi\u00e8rement si les objets sont en contact, puis on affine pour savoir exactement o\u00f9 se trouve le ou les points de contact, nous verrons cela par la suite.<\/p>\n<p>Avant de nous occuper de collisions plus d\u00e9taill\u00e9es, voyons quelques mises en applications avec des grilles et des tuiles. La plupart des jeux utilisent ce syst\u00e8me pour g\u00e9rer les interactions entre le joueur et le monde qui l&rsquo;entoure, cela demande de nombreux tests de collisions, d&rsquo;o\u00f9 ces quelques exemples simples mais bien pratiques.<br \/>\n<\/diV><\/p>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">AABB vs Grille<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/aabb_vs_grille_fermee.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>L&rsquo;univers dans lequel \u00e9volue le joueur est une grille compos\u00e9e de cases, certaines sont solides, d&rsquo;autres non. La box du joueur est un rectangle et il nous faut donc tester sa collision avec les cases solides que l&rsquo;on peut \u00e9galement consid\u00e9rer comme des box. On va commencer par d\u00e9finir le monde, dessiner la grille, placer le joueur et cr\u00e9er le code de gestion des touches pour le d\u00e9placement (voir source pour plus de d\u00e9tail).<\/p>\n<p>Note sur l&rsquo;optimisation : une grille est g\u00e9n\u00e9ralement repr\u00e9sent\u00e9e par un tableau \u00e0 deux dimensions, une liste qui pour chaque ligne contient une liste des cases. C&rsquo;est tr\u00e8s lourd, une solution interm\u00e9diaire consiste \u00e0 utiliser une liste simple et une petite formule pour passer \u00e0 la ligne suivante, c&rsquo;est celle que j&rsquo;utilise pour l&rsquo;exemple, mais il existe d&rsquo;autres solution pour g\u00e9rer des maps, notamment les Bitmaps ou les entier de 32 bits, mais on s&rsquo;\u00e9loigne un peu du sujet sur les collisions et on reparlera de ces optimisations plus tard, donc revenons \u00e0 nos moutons, les collisions. <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionsGrilleAABB(dX,dY,B){\r\n \r\n\tvar C;\r\n\tvar L;\r\n \r\n\tB.x += dX*vitesse;\r\n\tif (dX&lt;0) {\r\n\t\tC = B.x\/taille ;\r\n\t\tfor (L = B.y\/taille; L&lt;(B.y+B.height)\/taille; L++) {\r\n\t\t\tif (map&#x5B;C+L*colonnes]==1) B.x = (C+1)*taille;\r\n\t\t}\r\n\t} else if (dX&gt;0) {\r\n\t\tC = (B.x+B.width)\/taille ;\r\n\t\tfor (L = B.y\/taille; L&lt;(B.y+B.height)\/taille ; L++ ) {\r\n\t\t\tif (map&#x5B;C+L*colonnes]==1) B.x = C*taille-B.width;\r\n\t\t}\r\n\t}\r\n \r\n\tB.y += dY*vitesse;\r\n\tif (dY&lt;0) {\r\n\t\tL = B.y\/taille;\r\n\t\tfor (C=B.x\/taille; C&lt;(B.x+B.width)\/taille; C++) {\r\n\t\t\tif (map&#x5B;C+L*colonnes]==1) B.y = (L+1)*taille;\r\n\t\t}\r\n\t} else if (dY&gt;0) {\r\n\t\tL = (B.y+B.height)\/taille ;\r\n\t\tfor (C=B.x\/taille; C&lt;(B.x+B.width)\/taille; C++) {\r\n\t\t\tif (map&#x5B;C+L*colonnes]==1) B.y = L*taille-B.height;\r\n\t\t}\r\n\t}\t\t\r\n \r\n\treturn {x:B.x, y:B.y};\r\n}\r\n<\/pre>\n<p>Cette formule semble longue et complexe mais il n&rsquo;en est rien, en fait ici notre joueur est plus grand que la taille d&rsquo;une tuile de la map, du coup il faut tester chaque case qu&rsquo;occupe la box du joueur pour d\u00e9terminer la collision, c&rsquo;est \u00e0 \u00e7a que servent les boucles.<\/p>\n<p>On utilise la direction prise par le joueur (dX et dY) pour savoir quel c\u00f4t\u00e9 de la box doit effectuer le test de collision, puis on regarde la case o\u00f9 elle se trouve et si c&rsquo;est un mur infranchissable on replace le joueur devant le mur. <\/p>\n<p>Pr\u00e9cisons enfin que chaque calcul doit \u00eatre fait ind\u00e9pendamment sur chaque axe, d&rsquo;abord X puis Y (ou l&rsquo;inverse) mais jamais les deux en m\u00eame temps, c&rsquo;est \u00e0 la fois une question d&rsquo;optimisation et de pr\u00e9cision.<\/p>\n<p>La fonction renvoie un point, il repr\u00e9sente les coordonn\u00e9es que doit avoir le joueur \u00e0 la fin des tests de collision.<br \/>\n<\/diV><\/p>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">AABB vs Pente<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/aabb_vs_pente.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>Nous avons vus au d\u00e9but de ce document comment g\u00e9rer la collision avec une ligne droite (deux AABB), mais le joueur \u00e9volue alors dans un monde tout en angles droits, quelques pentes pourraient bien agr\u00e9menter un peu le d\u00e9cor et le gameplay, cette fois nous allons donc tester la collision avec une pente et pour cela nous allons utiliser des fonction affines (voir : http:\/\/fr.wikipedia.org\/wiki\/Fonction_affine ). <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionPenteAABB(B){\r\n \r\n\tvar X = B.x+B.width*.5;\r\n\tvar Y = B.y+B.height;\r\n \r\n\tvar PY;\r\n\tvar oldPY;\r\n\tvar p1;\r\n\tvar p2;\r\n \r\n\tfor each (var ligne in lignes) { \r\n\t\tp1 = ligne.p1;\r\n\t\tp2 = ligne.p2;\r\n\t\tif ( X &gt;= p1.x &amp;&amp; X &lt;= p2.x ) {\r\n\t\t\tPY = p1.y+(X-p1.x)*(p2.y-p1.y)\/(p2.x-p1.x); \r\n\t\t\toldPY = p1.y+(oldX-p1.x)*(p2.y-p1.y)\/(p2.x-p1.x); \r\n\t\t\tif ( Y &gt;= PY &amp;&amp; oldY &lt;= oldPY ) B.y = PY-B.height;\r\n\t\t}\r\n\t}\r\n \r\n \toldY = B.y+B.height;\r\n\toldX = X;\r\n \r\n\treturn {x:B.x, y:B.y};\r\n}\r\n<\/pre>\n<p>On d\u00e9place d&rsquo;abord le joueur, puis on regarde o\u00f9 se trouvent ses pieds, on replace ensuite le joueur sur Y en fonction de la pente de la ligne. Afin de simplifier les calculs on ne va pas partir du rep\u00e8re du plan (la sc\u00e8ne) mais d&rsquo;un rep\u00e8re local \u00e0 la pente, son point gauche. La fonction renvoie un nouveau point de coordonn\u00e9es qui est la correction de la position en fonction de la pente. Notez que \u201coldX\u201d et \u201coldY\u201d sont deux variables externes \u00e0 la fonction car nous devons les conserver \u00e0 chaque pas du programme, et que toutes les lignes sont stock\u00e9es dans un tableau sous forme de points (deux points par ligne).<br \/>\n<\/diV><\/p>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">Droite vs Segment<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/droite_vs_segment.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>La diff\u00e9rence entre une droite et un segment de droite, c&rsquo;est que la droite n&rsquo;est pas consid\u00e9r\u00e9e comme finie, alors que le segment poss\u00e8de un d\u00e9but et une fin clairement identifi\u00e9s. Nous allons donc commencer par tester la collision entre une droite et un segment de droite. <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionDroiteSegment(a,b,c,d){\r\n\tvar AB = {x:b.x-a.x,y:b.y-a.y};\t\/\/ vecteur AB\r\n\tvar AD = {x:d.x-a.x,y:d.y-a.y};\t\/\/ vecteur AD\r\n\tvar AC = {x:c.x-a.x,y:c.y-a.y};\t\/\/ vecteur AC\r\n\tif ((AB.x*AD.y - AB.y*AD.x)*(AB.x*AC.y - AB.y*AC.x)&lt;0) return true;\r\n\treturn false;\r\n}\r\n<\/pre>\n<p>Ici on consid\u00e8re les points a,b,c,d o\u00f9 \u201ca\u201d et \u201cb\u201d forment une droite et \u201cc\u201d et \u201cd\u201d forment un segment de droite. Nous allons calculer les vecteurs de chacun et un vecteur peut \u00eatre repr\u00e9sent\u00e9 par un simple point. <\/p>\n<p>Par exemple pour calculer le vecteur de la droite form\u00e9e entre les points \u201ca\u201d et \u201cb\u201d nous avons la formule suivante :<\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nAB = (b.x-a.x, b.y-a.y)\r\n<\/pre>\n<p>Dans cette formule on calcule trois vecteurs, AB, AD, AC.<br \/>\nOn consid\u00e8re que A est le point de d\u00e9part du vecteur et qu&rsquo;il se dirige vers B<\/p>\n<p>On souhaite savoir si les points C et D du segment sont tous deux du m\u00eame c\u00f4t\u00e9 de la droite, auquel cas il n&rsquo;y a pas de collision, en effet il ne peut y avoir collision que si C et D sont chacun d&rsquo;un c\u00f4t\u00e9 de la droite AB.<\/p>\n<p>Les vecteurs AC et AD partent du point A et se dirigent vers le point du segment qui nous int\u00e9resse, on va donc obtenir un chiffre n\u00e9gatif si le vecteur monte et positif si il descend. Il est ainsi possible de d\u00e9terminer si les deux vecteurs sont tous deux positifs ou n\u00e9gatifs (auquel cas les points C et D sont du m\u00eame c\u00f4t\u00e9 de la droite) ou de signe diff\u00e9rents. A l&rsquo;aide d&rsquo;une simple multiplication on s&rsquo;\u00e9vite de tester un \u00e0 un chaque point du segment.<br \/>\n<\/diV><\/p>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">Segment vs Segment<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/segment_vs_segment.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>Nous venons de voir comment tester la collision entre une droite et un segment de droite, int\u00e9ressons nous \u00e0 pr\u00e9sent \u00e0 deux segments et essayons de trouver le point de collision. <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionDroiteSegment(a,b,c,d){\r\n\tvar AB = {x:b.x-a.x,y:b.y-a.y};\t\/\/ vecteur AB\r\n\tvar AD = {x:d.x-a.x,y:d.y-a.y};\t\/\/ vecteur AD\r\n\tvar AC = {x:c.x-a.x,y:c.y-a.y};\t\/\/ vecteur AC\r\n\tif ((AB.x*AD.y - AB.y*AD.x)*(AB.x*AC.y - AB.y*AC.x)&lt;0) return true;\r\n\treturn false;\r\n}\r\n \r\nfunction collisionSegmentSegment(a,b,c,d){\r\n\tif (!collisionDroiteSegment(a,b,c,d)) return false;\r\n\tif (!collisionDroiteSegment(c,d,a,b)) return false;\r\n\treturn true;\r\n}\r\n<\/pre>\n<p>Trouver la collision entre deux segment n&rsquo;est pas plus compliqu\u00e9 qu&rsquo;entre une droite et un segment, il suffit en fait de faire deux fois le test avec des points diff\u00e9rents en consid\u00e9rant \u00e0 chaque test que l&rsquo;un des deux segments est une droite.<\/p>\n<p>Ce qui va donc nous int\u00e9resser ici c&rsquo;est trouver le point d&rsquo;intersection, ceci pouvant servir dans un jeu \u00e0 d\u00e9terminer l&rsquo;angle d&rsquo;un rebond ou tout simplement le point d&rsquo;impact d&rsquo;un projectile ou d&rsquo;un rayon (dans le cas d&rsquo;un raycasting). <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction pointIntersection(a,b,c,d){\r\n\tvar AB = {x:b.x-a.x,y:b.y-a.y};\t\/\/ vecteur AB\r\n\tvar AD = {x:d.x-c.x,y:d.y-c.y};\t\/\/ vecteur AD\r\n\tvar AC = {x:c.x-a.x,y:c.y-a.y};\t\/\/ vacteur AC\r\n\tvar t = (AC.x*AD.y-AC.y*AD.x)\/(AB.x*AD.y-AB.y*AD.x);\r\n\treturn {x:a.x+AB.x*t,y:a.y+AB.y*t}\r\n}\r\n<\/pre>\n<p>Comme je le disait en introduction, j&rsquo;ai mes limites en maths, et m\u00eame si je comprend les formules, si je sent qu&rsquo;il y a un risque de me tromper dans les explications, je pr\u00e9f\u00e8re ne pas m&rsquo;y lancer et vous renvoyer vers une source qui l&rsquo;explique mieux que moi \ud83d\ude09 Donc si vous souhaitez en savoir plus sur la formule qui permet de trouver ce point d&rsquo;intersection jetez un oeil ici : http:\/\/geomalgorithms.com\/a05-_intersect-1.html<\/p>\n<p>Ces collisions entre des lignes et des segments nous \u00e0 permis d&rsquo;introduire rapidement la notion de vecteurs, sans non plus entrer trop dans le d\u00e9tail, c&rsquo;est important car par la suite nous allons \u00e9norm\u00e9ment les utiliser pour simplifier tout un tas de calculs de collision.\n<\/p><\/div>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">Point vs Polygone<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/point_vs_polygone.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>Pour le cas d&rsquo;un polygone on va consid\u00e9rer la forme du polygone comme un ensemble de points contenus dans un tableau. Pour d\u00e9terminer si le point se trouve dans le polygone on va prendre un autre point tr\u00e8s \u00e9loign\u00e9 en dehors de la sc\u00e8ne et tracer un segment entre ce point et le point sur lequel on fait la d\u00e9tection de collision. On va ensuite utiliser une simple d\u00e9tection d&rsquo;intersection entre deux segments. Puis on va compter le nombre d&rsquo;intersections entre le segment et le polygone, si ce nombre est impair alors le point est dans le polygone, si il est pair alors le point est en dehors du polygone. <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionPolygone(tab,nbp,P){\r\n\tvar i;\r\n\tvar I = {x:10000+Math.floor(Math.random()*100),y:10000+Math.floor(Math.random()*100)};\r\n\tvar nbintersections = 0;\r\n\tfor(i=0;i&lt;nbp;i++){\r\n\t\tvar A = tab&#x5B;i];\r\n\t\tvar B;\r\n\t\ti==nbp-1 ? B = tab&#x5B;0] : B = tab&#x5B;i+1];\t\/\/ si c'est le dernier point, on relie au premier sinon on relie au suivant\r\n\t\tvar iseg = intersectSegment(A,B,I,P);\r\n\t\tif (iseg == -1) return collisionPolygone(tab,nbp,P);  \/\/ cas limite, on relance la fonction.\r\n\t\tnbintersections+=iseg;\r\n\t}\r\n\tif (nbintersections%2==1) return true; \/\/ nbintersections est-il impair ?\r\n\treturn false;\r\n}\r\n \r\nfunction intersectSegment(A,B,I,P) {\r\n\tvar AB = {x:B.x-A.x,y:B.y-A.y};\r\n\tvar IP = {x:P.x-I.x,y:P.y-I.y};\r\n\tvar denom = AB.x*IP.y-AB.y*IP.x;\r\n\tif (denom==0) return -1;   \/\/ erreur, cas limite\r\n\tvar t = - (A.x*IP.y-I.x*IP.y-IP.x*A.y+IP.x*I.y) \/ denom;\r\n\tif (t&lt;0 || t&gt;=1) return 0;\r\n\tvar u = - (-AB.x*A.y+AB.x*I.y+AB.y*A.x-AB.y*I.x) \/ denom;\r\n\tif (u&lt;0 || u&gt;=1) return 0;\r\n\treturn 1;\r\n}\r\n<\/pre>\n<p>Il existe des cas particulier par exemple pour le point de d\u00e9part et le point d&rsquo;arriv\u00e9 de la forme du polygone, qui sont les m\u00eames, dans ce cas on exclu un des deux points de la d\u00e9tection.<\/p>\n<p>Le point al\u00e9atoire est \u00e9galement susceptible de poser des probl\u00e8mes, le segment entre les deux points peut dans certains cas se retrouver parall\u00e8le et strictement sur une ligne du polygone, dans ce cas il faut signaler l&rsquo;exception et retirer un autre point, puis recommencer la d\u00e9tection.\n<\/p><\/div>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">Cercle vs Point<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/cercle_vs_point.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>Pour savoir si un point se trouve dans un cercle il suffit de calculer la distance qui s\u00e9pare le point au centre du cercle, si elle est inf\u00e9rieure ou \u00e9gale au rayon alors le point touche le cercle.<\/p>\n<p>Une distance entre deux points \u201ca\u201d et \u201cb\u201d se calcule normalement de la mani\u00e8re suivante : <\/p>\n<p>distance = racine carr\u00e9 de ((b.x-a.x)*(b.x-a.x) + (b.y-a.y)* (b.y-a.y))<\/p>\n<p>Mais les calculs de racine carr\u00e9es sont tr\u00e8s lourds, c&rsquo;est pourquoi on va essayer de l&rsquo;\u00e9viter. Tout ce que nous souhaitons savoir pour ce type de collision c&rsquo;est si le point est plus proche du centre du cercle que la longueur du rayon, si on prend la distance au carr\u00e9 entre le point et le centre du cercle et le rayon au carr\u00e9, on saura tout autant si l&rsquo;une est inf\u00e9rieure \u00e0 l&rsquo;autre qu&rsquo;avec la racine carr\u00e9e, on peut donc se passer de la racine et calculer directement les carr\u00e9s des deux longueurs, ce qui nous donne : <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionCerclePoint(X,Y,C){\r\n\tvar cX = C.x+C.rayon;\r\n\tvar cY = C.y+C.rayon;\r\n\tvar distance = (X-cX)*(X-cX) + (Y-cY)*(Y-cY);\r\n   \tif (distance&lt;C.rayon*C.rayon) return true;\r\n\treturn false;\r\n}\r\n<\/pre>\n<p>La fonction renvoie un bool\u00e9en si le point touche le cercle. Attention, vous noterez que c&rsquo;est le centre du cercle que l&rsquo;on souhaite tester, or il se trouve que les objets ont en g\u00e9n\u00e9ral leur point de rep\u00e8re de position dans le coin sup\u00e9rieur gauche. Pour trouver le centre du cercle (cX, cY) il faut donc ajouter le rayon de celui-ci \u00e0 la fois \u00e0 la hauteur et \u00e0 la largeur du point de rep\u00e8re de position. Il en sera de m\u00eame pour tous les tests sur les cercles que nous allons effectuer.\n<\/p><\/div>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">Cercle vs Cercle<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/cercle_vs_cercle.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>L\u00e0 encore c&rsquo;est assez simple, il suffit de regarder la distance qui s\u00e9pare les centres des cercles et de v\u00e9rifier si elle est inf\u00e9rieure \u00e0 la somme des rayons, et cela marche avec des cercles de n&rsquo;importe quelle taille. <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionCercleCercle(A,B){\r\n \r\n\tvar AX = A.x+A.rayon;\r\n\tvar AY = A.y+A.rayon;\r\n\tvar BX = B.x+B.rayon;\r\n\tvar BY = B.y+B.rayon;\r\n \r\n\tvar distance = (AX-BX)*(AX-BX) + (AY-BY)*(AY-BY);\r\n   \tif (distance &lt; (A.rayon+B.rayon)*(A.rayon+B.rayon)) return true;\r\n\treturn false;\r\n}\r\n<\/pre>\n<p>Les jeux qui utilisent le plus ce type de collision sont les jeux de billard par exemple.\n<\/p><\/div>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">Cercle vs Ligne<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/cercle_vs_ligne.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>Pour calculer la collision entre un cercle et une droite il faut projeter un point sur la droite de mani\u00e8re \u00e0 ce que le segment repr\u00e9sent\u00e9 par le point projet\u00e9 et le centre du cercle forme un angle droit avec la droite, puis calculer la longueur du segment ainsi trouv\u00e9 pour savoir si elle est plus petite que le rayon du cercle, auquel cas il y a collision.<\/p>\n<p>Nous ne connaissons pas encore le point projet\u00e9 sur la droite \u00e0 partir du centre du cercle, mais nous connaissons la position du centre du cercle (C), et au moins un point de la droite (A). Nous savons \u00e9galement que le segment entre le centre du cercle et le point projet\u00e9 (B) doit faire un angle droit avec la droite. Tout ceci forme un triangle rectangle, on se tourne donc vers Pythagore, ce qui nous donne avec des vecteurs : <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionCercleDroite(a,b,c){\r\n \r\n\tvar cX = c.x+c.rayon;\r\n\tvar cY = c.y+c.rayon;\r\n \r\n\tvar AB =  \t\t{x:b.x-a.x, y:b.y-a.y}; \t\t\/\/ Vecteur AB\r\n\tvar AC = \t\t{x:cX-A.x, y:cY-a.y};\t\t\t\/\/ Vecteur AC\r\n\tvar numerateur = \tMath.abs(AB.x*AC.y-AB.y*AC.x);   \t\/\/ numerateur\r\n\tvar denominateur = \tMath.sqrt(AB.x*AB.x + AB.y*AB.y);  \t\/\/ denominateur\r\n \r\n\tif (numerateur\/denominateur&lt;c.rayon) return true;\r\n\treturn false;\r\n}\r\n<\/pre>\n<p>Pour en savoir plus sur le th\u00e9or\u00e8me de Pythagore : <a href= \"http:\/\/fr.wikipedia.org\/wiki\/Th%C3%A9or%C3%A8me_de_Pythagore\">http:\/\/fr.wikipedia.org\/wiki\/Th%C3%A9or%C3%A8me_de_Pythagore<\/a>\n<\/div>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">Cercle vs Segment<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/cercle_vs_segment.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>A partir d&rsquo;ici \u00e7a se complique un peu car il va nous falloir faire des produits scalaire, pas de panique on va survoler \u00e7a, mais avant de nous jeter dans les calculs on va se simplifier un peu la vie. Il y a tout un tas de collisions simples que nous pouvons tester avant de plonger dans des calculs complexes, en effet on peut d\u00e9j\u00e0 v\u00e9rifier que le cercle ne touche pas la droite, si c&rsquo;est le cas il ne touchera pas le segment, ensuite on peut v\u00e9rifier si le cercle touche un des deux points du segment, auquel cas la solution est simple,. On va donc utiliser deux m\u00e9thodes que nous avons d\u00e9j\u00e0 vues, la collision avec un point et avec une droite, si ces deux conditions ne sont pas remplies on passe aux calculs. <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionCercleSegment(a,b,c){\r\n  \tif (!collisionCercleDroite(a,b,c)) \treturn false;  \t\/\/ ne touche pas la droite\r\n\tif (collisionCerclePoint(a,c)) \t\treturn true;\t\/\/ A dans le cercle\r\n\tif (collisionCerclePoint(b,c)) \t\treturn true; \t\/\/ B dans le cercle\r\n\tvar cX = c.x+c.rayon;\r\n\tvar cY = c.y+c.rayon;\r\n\tvar AB = {x:b.x-a.x,y:b.y-a.y}; \t\t\t\/\/ Vecteur AB\r\n\tvar AC = {x:cX-a.x,y:cY-a.y}; \t\t\t\t\/\/ Vecteur AC\r\n\tvar BC = {x:cX-b.x,y:cY-b.y}; \t\t\t\t\/\/ Vecteur BC\r\n\tvar S1 = AB.x*AC.x + AB.y*AC.y;  \t\t\t\/\/ produit scalaire AB AC\r\n\tvar S2 = -AB.x*BC.x - AB.y*BC.y;  \t\t\t\/\/ produit scalaire AB BC\r\n\tif (S1&gt;=0 &amp;&amp; S2&gt;=0)\t\t\treturn true;  \t\/\/ entre A et B\r\n\treturn false;\r\n}\r\n \r\nfunction collisionCercleDroite(a,b,c){\r\n\tvar cX = c.x+c.rayon;\r\n\tvar cY = c.y+c.rayon;\r\n\tvar AB = {x:b.x-a.x, y:b.y-a.y}; \t\t\t\/\/ vecteur AB\r\n\tvar AC = {x:cX-a.x, y:cY-a.y};\t\t\t\t\/\/ vecteur AC\r\n\tvar numerateur = Math.abs(AB.x*AC.y-AB.y*AC.x);   \t\/\/ numerateur\r\n\tvar denominateur = Math.sqrt(AB.x*AB.x + AB.y*AB.y);  \t\/\/ denominateur\r\n\tif (numerateur\/denominateur&lt;c.rayon) return true;\r\n\treturn false;\r\n}\r\n \r\nfunction collisionCerclePoint(p,c){\r\n\tvar cX = c.x+c.rayon;\r\n\tvar cY = c.y+c.rayon;\r\n\tvar distance = (p.x-cX)*(p.x-cX) + (p.y-cY)*(p.y-cY);\r\n   \tif (distance&lt;c.rayon*c.rayon) return true;\r\n\treturn false;\r\n}\r\n<\/pre>\n<p>Le produit scalaire c&rsquo;est quoi ?<\/p>\n<p>Un petit tour par Wikipedia vous donnera une d\u00e9finition exacte : <a href=\"http:\/\/fr.wikipedia.org\/wiki\/Produit_scalaire\">http:\/\/fr.wikipedia.org\/wiki\/Produit_scalaire<\/a><\/p>\n<p>Notre objectif pour savoir si il y a une collision entre le cercle et le segment, est de savoir si le point projet\u00e9 (du centre du cercle sur le segment, via le rayon) se trouve bien entre les bornes du segment, \u00e0 savoir ici A et B. Pour cela on a besoin de deux produits scalaires, un entre AB et AC, o\u00f9 AC est le vecteur entre le point A et le centre du cercle, et un entre BA et BC, B \u00e9tant le second point du segment. Si ces deux produits scalaires nous renvoient une valeur strictement sup\u00e9rieure \u00e0 z\u00e9ro, alors le point projet\u00e9 est bien sur le segment.\n<\/p><\/div>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">Cercle vs Segment &#8211; Point d&rsquo;impact<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/cercle_vs_segment_-_point_d_impact.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>Essayons \u00e0 pr\u00e9sent de trouver le point d&rsquo;impact entre le cercle et le segment, pour cela on va utiliser une projection du centre du cercle sur le segment, comme ceci : <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction pointImpact(a,b,c){\r\n\tvar cX = c.x+c.rayon;\r\n\tvar cY = c.y+c.rayon;\r\n\tvar AB = {x:b.x-a.x,y:b.y-a.y}; \t\/\/ vecteur AB\r\n\tvar AC = {x:cX-a.x,y:cY-a.y}; \t\t\/\/ vecteur AC\r\n\tvar t = (AC.x*AB.x+AC.y*AB.y)\/(AB.x*AB.x + AB.y*AB.y);\t\r\n\treturn new Point(a.x+AB.x*t,a.y+AB.y*t);\r\n}\r\n<\/pre>\n<p>Vous noterez que le point d&rsquo;impact est cal\u00e9 sur le centre du cercle. Dans mon exemple lorsque la collision \u00e0 lieu sur un des bords du segment, le point de projection sur le segment est toujours au centre du cercle et non sur le bord du segment. C&rsquo;est une r\u00e9action normale puisque nous ne prenons pas en compte le rayon du cercle dans nos calculs mais son centre.\n<\/p><\/div>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">Cercle vs AABB<\/h2>\n<div class=\"bloc\">\n<p>[swf src=\u00a0\u00bbhttp:\/\/www.cmarzin.fr\/site\/content\/tutos\/collisions\/cercle_vs_aabb.swf\u00a0\u00bb width=480 height=480]<\/p>\n<p>Et nous attaquons la m\u00e9thode la plus compl\u00e8te concernant ces formes simples (dites primitives) que sont les lignes, les segments, les rectangles et les cercles. Ici il s&rsquo;agit de tester la collision entre un cercle et une AABB, et comme nous l&rsquo;avons fait plus haut pour le cercle et le segment, nous allons utiliser ici presque toutes les m\u00e9thodes de collisions appliqu\u00e9es \u00e0 un cercle que nous avons vues. <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionCercleAABB(C,B){\r\n \r\n   var B1 = new Rectangle(C.x, C.y, C.width, C.height);\r\n   var B2 = new Rectangle(B.x, B.y, B.width, B.height);\r\n \r\n   if (!collisionBoxBox(B1,B2)) return false; \r\n \r\n   if (collisionCerclePoint(B2.x,B2.y,C)\r\n    || collisionCerclePoint(B2.x,B2.y+B2.height,C)\r\n    || collisionCerclePoint(B2.x+B2.width,B2.y,C)\r\n    || collisionCerclePoint(B2.x+B2.width,B2.y+B2.height,C))\r\n   return true;  \r\n \r\n   if (collisionPointAABB(C.x+C.rayon,C.y+C.rayon,B2)) return true;   \r\n \r\n   var PV = projectionSurSegment(B1.x+C.rayon,B1.y+C.rayon,B2.x,B2.y,B2.x,B2.y+B2.height);\r\n   var PH = projectionSurSegment(B1.x+C.rayon,B1.y+C.rayon,B2.x,B2.y,B2.x+B2.width,B2.y);\r\n   if (PV || PH) return true; \r\n   return false; \r\n}\r\n \r\nfunction projectionSurSegment(Cx,Cy,Ax,Ay,Bx,By){\r\n   var ACx = Cx-Ax;\r\n   var ACy = Cy-Ay;\r\n   var ABx = Bx-Ax;\r\n   var ABy = By-Ay;\r\n   var BCx = Cx-Bx;\r\n   var BCy = Cy-By;\r\n   var s1 = (ACx*ABx) + (ACy*ABy);\r\n   var s2 = (BCx*ABx) + (BCy*ABy);\r\n   if (s1*s2&gt;0) return false;\r\n   return true;\r\n}\r\n<\/pre>\n<p>Dans l&rsquo;ordre on commence par un premier test qui v\u00e9rifie si les Bounding Box de la AABB et du Cercle ne sont pas en contact, auquel cas inutile d&rsquo;aller plus loin, il n&rsquo;y a pas de collision.<\/p>\n<p>Puis on v\u00e9rifie si un des 4 coins de la AABB est en contact avec le cercle, si c&rsquo;est le cas il y a collision.<\/p>\n<p>On v\u00e9rifie ensuite si le centre du cercle est en contact avec la AABB, si c&rsquo;est le cas il y a collision.<\/p>\n<p>Nous utilisons bien sur pour cela les m\u00e9thodes d\u00e9j\u00e0 vues pr\u00e9c\u00e9demment \u00e0 savoir : <\/p>\n<pre class=\"brush: jscript; title: ; notranslate\" title=\"\">\r\nfunction collisionBoxBox(A,B){\r\n\tif (A.y+A.height &lt; B.y || A.y &gt; B.y+B.height || A.x &gt; B.x+B.width || A.x+A.width &lt; B.x) return false;\r\n\treturn true;\r\n}\r\n \r\nfunction collisionCerclePoint(X,Y,C){\r\n\tvar cX = C.x+C.rayon;\r\n\tvar cY = C.y+C.rayon;\r\n\tvar distance = (X-cX)*(X-cX) + (Y-cY)*(Y-cY);\r\n   \tif (distance&lt;C.rayon*C.rayon) return true;\r\n\treturn false;\r\n}\r\n \r\nfunction collisionPointAABB(X, Y,B){\r\n\tif (X&gt;=B.x &amp;&amp; X&lt;B.x+B.width &amp;&amp; Y&gt;=B.y &amp;&amp; Y&lt;B.y+B.height) return true;\r\n\treturn false;\r\n}\r\n<\/pre>\n<p>Si aucun de ces tests n&rsquo;a stopp\u00e9 la d\u00e9tection il va falloir v\u00e9rifier un peu plus finement si il y a contact, pour cela on va une nouvelle fois utiliser un produit scalaire, comme nous l&rsquo;avons vus dans la collision entre un cercle et un segment, afin de d\u00e9terminer si le point projet\u00e9 sur un segment de la AABB se trouve \u00e0 l&rsquo;int\u00e9rieur de ce segment. A partir de l\u00e0 vous pouvez d\u00e9terminer pr\u00e9cis\u00e9ment le point d&rsquo;impact et g\u00e9rer par exemple les rebonds comme nous l&rsquo;avons vus avec la collision de cercle sur segment.\n<\/p><\/div>\n<div class=\"lsep\"><\/div>\n<h2 class=\"bloctitle\">A retenir<\/h2>\n<div class=\"blocorange\">\n<p>Nous allons nous arr\u00eater l\u00e0 pour le moment, il reste quelques cas de collisions qui n&rsquo;ont pas \u00e9t\u00e9 abord\u00e9s, comme la collision entre un cercle et une courbe ou la collision au pixel pr\u00e8s, j&rsquo;\u00e9crirai les formules si je trouve un peu de temps suppl\u00e9mentaire.<\/p>\n<p>Je n&rsquo;ai pas parl\u00e9 d&rsquo;optimisation dans cette fiche, bien sur vous pouvez sortir toute la panoplie habituelle pour optimiser \u00e0 mort les formules, mais vous pouvez aussi vous int\u00e9resser au partitionnement de l&rsquo;espace. C&rsquo;est particuli\u00e8rement utile dans le cas de grands ensemble, comme par exemple un vaste niveau complet d&rsquo;un jeu comme Doom, compos\u00e9 de tr\u00e8s nombreux segments. Cette technique peut prendre plusieurs formes et sert essentiellement \u00e0 compartimenter des espaces en sous sections afin de limiter la d\u00e9tection de collision \u00e0 de petite zones. Vous avez aussi la possibilit\u00e9 de grouper vos objets dans des ensembles plus vastes et tester la collision avec le groupe avant d&rsquo;affiner sur les objets qui composent le groupe, bref il existe encore tout un monde d&rsquo;optimisations au del\u00e0 des simples formules de collisions que nous avons abord\u00e9s.<\/p>\n<p>J&rsquo;esp\u00e8re que cette petite fiche r\u00e9capitulative vous sera utile.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p><i class=\"fa fa-clock-o\"><\/i> 06h00<br \/>\n<i class=\"fa fa-user\"><\/i> D\u00e9butant<br \/>\n<i class=\"fa fa-book\"><\/i> Fiche technique<br \/>\n<i class=\"fa fa-cog\"><\/i> Tous langages<br \/>\n<i class=\"fa fa-graduation-cap\"><\/i> Ma\u00eetriser les collisions 2D les plus courantes<br \/>\n<i class=\"fa fa-suitcase\"><\/i> Notions de math\u00e9matiques et de programmation <\/p>\n","protected":false},"author":1,"featured_media":167,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"aside","meta":[],"categories":[4],"tags":[29,22,10,21],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v16.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.cmarzin.fr\/site\/2015\/11\/14\/collisions\/\" \/>\n<meta property=\"og:locale\" content=\"fr_FR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Collisions - Cmarzin\" \/>\n<meta property=\"og:description\" content=\"06h00  D\u00e9butant  Fiche technique  Tous langages  Ma\u00eetriser les collisions 2D les plus courantes  Notions de math\u00e9matiques et de programmation\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.cmarzin.fr\/site\/2015\/11\/14\/collisions\/\" \/>\n<meta property=\"og:site_name\" content=\"Cmarzin\" \/>\n<meta property=\"article:published_time\" content=\"2015-11-14T02:57:21+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2016-01-07T23:14:03+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"300\" \/>\n\t<meta property=\"og:image:height\" content=\"169\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Dur\u00e9e de lecture est.\">\n\t<meta name=\"twitter:data1\" content=\"28 minutes\">\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.cmarzin.fr\/site\/#website\",\"url\":\"https:\/\/www.cmarzin.fr\/site\/\",\"name\":\"Cmarzin\",\"description\":\"Formation et d\\u00e9veloppement Web et Multimedias\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":\"https:\/\/www.cmarzin.fr\/site\/?s={search_term_string}\",\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"fr-FR\"},{\"@type\":\"ImageObject\",\"@id\":\"https:\/\/www.cmarzin.fr\/site\/2015\/11\/14\/collisions\/#primaryimage\",\"inLanguage\":\"fr-FR\",\"url\":\"https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions.jpg\",\"contentUrl\":\"https:\/\/www.cmarzin.fr\/site\/wp-content\/uploads\/collisions.jpg\",\"width\":300,\"height\":169},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.cmarzin.fr\/site\/2015\/11\/14\/collisions\/#webpage\",\"url\":\"https:\/\/www.cmarzin.fr\/site\/2015\/11\/14\/collisions\/\",\"name\":\"Collisions - Cmarzin\",\"isPartOf\":{\"@id\":\"https:\/\/www.cmarzin.fr\/site\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/www.cmarzin.fr\/site\/2015\/11\/14\/collisions\/#primaryimage\"},\"datePublished\":\"2015-11-14T02:57:21+00:00\",\"dateModified\":\"2016-01-07T23:14:03+00:00\",\"author\":{\"@id\":\"https:\/\/www.cmarzin.fr\/site\/#\/schema\/person\/7c0008d57d9793c6cac9bea19c9dc1ba\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.cmarzin.fr\/site\/2015\/11\/14\/collisions\/#breadcrumb\"},\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.cmarzin.fr\/site\/2015\/11\/14\/collisions\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.cmarzin.fr\/site\/2015\/11\/14\/collisions\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"item\":{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.cmarzin.fr\/site\/\",\"url\":\"https:\/\/www.cmarzin.fr\/site\/\",\"name\":\"Accueil\"}},{\"@type\":\"ListItem\",\"position\":2,\"item\":{\"@id\":\"https:\/\/www.cmarzin.fr\/site\/2015\/11\/14\/collisions\/#webpage\"}}]},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.cmarzin.fr\/site\/#\/schema\/person\/7c0008d57d9793c6cac9bea19c9dc1ba\",\"name\":\"cmarzin@noos.fr\",\"image\":{\"@type\":\"ImageObject\",\"@id\":\"https:\/\/www.cmarzin.fr\/site\/#personlogo\",\"inLanguage\":\"fr-FR\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/2719b7011bb8e1850a08c47f07a022ed?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/2719b7011bb8e1850a08c47f07a022ed?s=96&d=mm&r=g\",\"caption\":\"cmarzin@noos.fr\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","_links":{"self":[{"href":"https:\/\/www.cmarzin.fr\/site\/wp-json\/wp\/v2\/posts\/185"}],"collection":[{"href":"https:\/\/www.cmarzin.fr\/site\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.cmarzin.fr\/site\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.cmarzin.fr\/site\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.cmarzin.fr\/site\/wp-json\/wp\/v2\/comments?post=185"}],"version-history":[{"count":45,"href":"https:\/\/www.cmarzin.fr\/site\/wp-json\/wp\/v2\/posts\/185\/revisions"}],"predecessor-version":[{"id":865,"href":"https:\/\/www.cmarzin.fr\/site\/wp-json\/wp\/v2\/posts\/185\/revisions\/865"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.cmarzin.fr\/site\/wp-json\/wp\/v2\/media\/167"}],"wp:attachment":[{"href":"https:\/\/www.cmarzin.fr\/site\/wp-json\/wp\/v2\/media?parent=185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.cmarzin.fr\/site\/wp-json\/wp\/v2\/categories?post=185"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.cmarzin.fr\/site\/wp-json\/wp\/v2\/tags?post=185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}