Apprendre


Vous êtes
nouveau sur
Oniromancie?

Visite guidée
du site


Découvrir
RPG Maker

RM 95
RM 2000/2003
RM XP
RM VX/VX Ace
RM MV

Apprendre
RPG Maker

Guides
Tutoriels
Making-of

Dans le
Forum

Section Entraide

Tutos: Ren'Py - Combiner les (...) / Tutos: Réaliser un pathfinder sur (...) / News: Cérémonie des Alex d'or 2020 / Jeux: Beetle Ninja / Jeux: Le Miroir de Philéas / Chat

Bienvenue
visiteur !




publicité RPG Maker!

Statistiques

Liste des
membres


Contact

Mentions légales

77 connectés actuellement

10806049 visiteurs
depuis l'ouverture

1093 visiteurs
aujourd'hui



Barre de séparation

Partenaires

Indiexpo

Akademiya RPG Maker

Hellsoft

Planète Glutko

Le Temple de Valor

Alex d'Or

Lunae - le bazar d'Emz0

New RPG Maker

Tous nos partenaires

Devenir
partenaire



Quelques tests géométriques simples
Ecrit par Tassle le 06/10/2020

Quelques tests géométriques simples







Dans ce tuto je vais vous montrer comment tester certaines propriétés géométriques simples en 2D, du style « Est-ce que tel point est à une distance inférieure à d de tel droite ? » ou « Est-ce que tel point est à l’intérieur de tel triangle ? ». Je vais essayer d'illustrer chaque test avec un exemple d’application possible pour un jeu vidéo, mais il se peut que le test vous soit utile dans un tout autre contexte. Ce tuto donne des outils plutôt que des produits finis.
Tous les tests sont basés sur l’addition, la soustraction, la multiplication et la comparaison de nombres entiers uniquement (tant que les objets manipulés ont des coordonnées entières). Ils peuvent donc être utilisés dans beaucoup de logiciels différents, sont précis et relativement peu coûteux en termes de ressources de l’ordinateur.

NOTE :
Dans tout ce qui suit, je vais partir du principe que les axes du système de coordonnées sont tels que l’axe des y pointe d’un quart de tours plus loin que l’axe des y dans le sens anti-horaire (sens inverse des aiguilles d’une montre). Par exemple si l’axe des x pointe vers la droite, l’axe des y pointe vers le haut. Si l’axe des x pointe vers le haut, l’axe des y pointe vers la gauche. Et ainsi de suite.

image
Illustrations de quelques systèmes de coordonnées valables et un qui ne l’est pas.



Si le système de coordonnées dans votre logiciel est dans « le mauvais sens », pas de panique. La seule différence se situe au test 2 de ce tuto, où je préciserai ce qu'il faut changer.

NOTATIONS :
• J’utilise le point central ⋅ pour dénoter la multiplication.
• Pour un point dans le plan P, je note ses coordonnées xP et yP (c’est pas beau mais faire beaucoup mieux sur un forum pas adapté à ce genre de choses). J’ecrirai aussi P = (xP,yP).
• Si P et Q sont deux points différents, je note (P,Q) la droite qui passe par P et Q et je note [P,Q] le segment de droite qui va de P à Q.


image


SOMMAIRE

• TEST 1 : Tester la distance entre deux points
• TEST 2 : Tester l’orientation de trois points
• TEST 3 : Tester si deux segments s’intersectent
• TEST 4 : Tester la distance d’un point à une droite
• TEST 5 : Tester la distance d’un point à un segment
• TEST 6 : Tester si un point est dans un polygone convexe
• TEST 7 : Tester l’appartenance à un polygone général


image


TEST 1 : Tester la distance entre deux points

image



Bon, celui là est facile et la plupart d’entre vous savent probablement déjà comment faire. Disons que j’ai deux points P et Q de coordonnées respective (xP,yP) et (xQ,yQ).
Leur distance est : sqrt((xP-xQ)² + (yP-yQ)²), où sqrt désigne la fonction « racine carrée » (« square root » en anglais). Donc pour tester si les deux points sont à distance moins de d, il suffit de regarder si
sqrt((xP-xQ)² + (yP-yQ)²) < d ?
Sauf que je vous avais promis d’utiliser que des nombres entiers et les operations arithmétiques de base. Donc on va passer le tout au carré pour nous débarasser de cette méchante racine, ce qui donne le test :
(xP-xQ)² + (yP-yQ)² < d² ?

Application :
Les application sont innombrables, et je suis sûr que vous pouvez en trouver plein par vous-même. Pour donner un exemple, ça peut servir à tester si un ennemi est assez proche du héros pour le détecter et commencer à l’attaquer.


image


TEST 2 : Tester l’orientation de trois points

image



Ce test là est moins connu mais étonnamment utile. On a trois points P,Q et R et on veut savoir si le chemin qui va de P à Q puis de Q à R forme un virage à gauche ou à droite.

Pour ce faire, il suffit de tester le signe de :
Orientation(P,Q,R) = (xQ-xR)⋅(yR-yQ)-(yQ-yR)⋅(xR-xQ).

Si le système de coordonnées est « dans le mauvais sens » (voir l'intro du tuto) il faut multiplier par -1 et la formule devient :
Orientation(P,Q,R) = (yQ-yR)⋅(xR-xQ)-(xQ-xR)⋅(yR-yQ).


• Si Orientation(P,Q,R) = 0 alors les trois points P,Q et R sont alignés (donc soit la trajectoire P→Q→R va tout droit soit elle fait un demi tour complet arrivé à Q)

• Si Orientation(P,Q,R) > 0 alors la trajectoire P→Q→R forme un virage à gauche.

• Si Orientation(P,Q,R) < 0 alors la trajectoire P→Q→R forme un virage à droite.


Application :
Ça peut par exemple servir pour déterminer le message d’un copilote dans un jeu de course (« Attention, virage à gauche imminent ») ou pour savoir si un personnage a franchi une certaine ligne (Si P→Q→R forme un virage à gauche alors R se trouve à gauche de la droite orientée passant par P puis R. Si P→Q→R forme un virage à droite alors R se trouve de l’autre côté de cette droite).
On va également utiliser ce test comme une étape dans certains des tests suivants.


image


TEST 3 : Tester si deux segments s’intersectent

image




Disons qu’on a deux segments, le premier est [A,B] qui va du point A au point B et le second est [P,Q] (oui PQ caca c’est rigoulo) qui va du point P au point Q. On veut savoir si les deux s’intersectent.

Remarquez que si les deux segments s’intersectent, alors P et Q sont sur différents côtés de la droite passant par A et B. De même, A et B sont de côtés différents de la droite passant par P et Q. Inversement si ces deux conditions sont réunies, alors les deux segments s’intersectent.

Donc il suffit de tester ces orientations pour voir si les segments s’intersectent ! (voir le point 2 du tuto)

Bon j’ai passé sous silence le cas particulier où les deux segments sont alignés sur la même droite et tous les tests d’orientation vont donner 0. Ce cas est traité dans la première partie de la procédure qui suit.

Si Orientation(A,B,P) = 0 et Orientation(A,B,P) = 0 alors les deux segments sont alignés.
Dans ce cas les deux segments s'intersectent si et seulement si maximum(xA,xB) >= minimum(xP,xQ) et minimum(xA,xB) <= maximum(xP,xQ) et maximum(yA,yB) >= minimum(yP,yQ) et minimum(yA,yB) <= maximum(yP,yQ).

Si les segments ne sont pas alignés, alors ils s'intersectent si et seulement si Orientation(A,B,P)⋅Orientation(A,B,P) <= 0 et Orientation(P,Q,A)⋅Orientation(P,Q,B) <= 0.

Application :
Ce test est surtout utile pour des tests de collisions entre objets, qui peuvent être représentés par un segment ou par plusieurs (par exemple un rectangle composé de quatre segments).


image


TEST 4 : Tester la distance d’un point à une droite

image



On a une droite D = (P,Q) qui passe par les points P et Q ainsi qu’un troisième point R. On veut savoir si la distance de R à D est inférieure à d.

Pour cela il suffit de tester si :
((xQ-xP) ⋅(yR-yP) - (yQ-yP)⋅(xR-xP))² < d²⋅((xQ-xP)²+(yQ-yP)²)

Application :
Ça peut servir à tester si un objet est trop près d’un mur par exemple, pour savoir si il peut continuer sa trajectoire ou si il faut le faire rebondir contre celui-ci. On peut aussi imaginer que la droite représente le rempart d’un château et que le point R représente le héros. S'il s’approche trop près du rempart, il se fait repérer/canarder/saluer.


image


TEST 5 : Tester la distance d’un point à un segment

image



On a un segment S = [P,Q] qui va du point P au point Q ainsi qu’un troisième point R. On veut savoir si la distance de R à S est inférieure à d. C’est en quelque sorte un raffinement du test précédent, sauf qu’il faut également gérer le cas où la projection orthogonale de R sur la droite (P,Q) n’est pas sur le segment S (le cas de droite sur l’illustration précédente).

Pour ce faire on peut définir les points P’ = (xP – yQ + yP, yP + xQ – xP) et Q’ = (xQ – yQ + yP, yQ + xQ – xP).

Si Orientation(P,P’,R)⋅Orientation(Q,Q’,R) ≥ 0 alors on est dans le cas de droite sur la figure précédente. Pour savoir si la distance de R à [P,Q] est inférieure à d, il suffit de tester si la distance de R à P est inférieure à d ou si la distance de R à Q est inférieure à d (voir le test 1 de ce tuto). Je précise qu’il faut bien effectuer les deux tests (pour P et pour Q) et qu’il suffit que l’un des deux soit à distance inférieure à d pour que la distance de R à [P,Q] soit inférieure à d.

Si Orientation(P,P’,R)⋅Orientation(Q,Q’,R) < 0 alors on est dans le cas de gauche sur la figure précédente. Dans ce cas il suffit de tester si la distance entre R et la droite passant par P et Q est inférieure à d (voir le test 4 de ce tuto).

Application :
Globalement les applications sont similaire au test précédent, dans le cas où l’objet considéré (un mur par exemple) n’est pas de longueur infinie.


image


TEST 6 : Tester si un point est dans un polygone convexe

image




On a un polygone convexe défini par une suite de points P_1, P_2, …, P_(n-1) et P_n qui sont listés dans l'ordre obtenu en faisant le tour du polygone dans le sens anti-horaire. Parce que ça simplifiera les choses plus loin, on va aussi donner le nom P_0 au point P_n (c'est cohérent avec le fait qu'un polygone se « referme sur lui même », c'est à dire que si on fait le tour on commence et on finit au même point).

Convexe signifie qu’il n’y a pas d’angles « vers l’intérieur », pas de creux en quelque sorte (voir l’illustration du test suivant pour un polygone qui n’est pas convexe).

On a aussi un autre point Q et on veut tester si Q est à l’intérieur du polygone.

Pour ce faire, il suffit de tester si P_0→P_1→Q forme un virage à gauche et P_1→P_2→Q forme un virage à gauche et P_2→P_3→Q forme un virage à gauche, et ainsi de suite jusqu'à P_(n-1)→P_n→Q (voir le point 2 de ce tuto pour tester le sens d'un virage).

Si tous ces virages sont à gauche, Q est dans le polygone. Il suffit qu’un seul de ces virages soit vers la droite pour être sûr que Q n’est pas dans le polygone.

Quand un virage est plat (les points sont alignés) c’est à vous de décider si vous voulez le considérer comme un virage à gauche ou à droite, selon si vous voulez inclure les points sur le bord du polygone comme étant dans le polygone ou pas.

Application :
Tester si un personnage est dans une certaine zone. La zone en question peut même se déplacer si vous voulez. Un exemple que je trouve sympa est un triangle formé par trois ennemis, et on veut tester si le héros se trouve dans ce triangle (auquel cas il est considéré comme entouré d’ennemis et obtient un boost d’adrénaline ou un truc du genre).

Remarques :
Quand le polygone convexe en question est très grand (c'est à dire défini par beaucoup de points) il est possible d’accélérer beaucoup cet algorithme en utilisant ce qu’on appelle une recherche par dichotomie. Mais c’est un peu trop long à expliquer pour ce tuto.

Néanmoins, un moyen simple de souvent accélérer le test quand le polygone en question ne bouge pas est de commencer par tester si le point Q est au moins dans un « rectangle limite », qui contient le polygone.
On commence par calculer une fois pour toute xMin qui est le minimum de xP_1, xP_2,... xP_n, et aussi xMax qui est le maximum de xP_1, xP_2,... xP_n, et de même pour yMin et yMax. Quand je dis « une fois pour toute » je veux dire qu'il n'est pas nécessaire de recalculer ces valeurs à chaque test qu'on fait vu qu'elles vont rester les mêmes.
Puis, avant de tester si Q est dans le polygone, on commence par tester si xMin ≤ xQ ≤ xMax et yMin ≤ yQ ≤ yMax. Si ce n'est pas le cas, on sait d'avance que Q n'est pas dans le polygone et ce n'est pas la peine d'effectuer le test complet.


image


TEST 7 : Tester l’appartenance à un polygone général

image



Cette question est similaire à la précédente mais dans le cas où le polygone n’est pas forcément convexe. Le test est basé sur l'idée que si on commence au point Q et qu'on avance dans une direction (disons vers la droite), on va passer par dessus le bord du polygone un certain nombre de fois. Si ce nombre est impair, Q est à l’intérieur du polygone. Si ce nombre est pair, Q est à l’extérieur du polygone.
En exploitant cette idée on peut arriver au test suivant :

On commence par définir w = 0.
Pour chaque i compris entre 0 et n-1 on fait ce qui suit (notez l'utilisation des inégalités strictes et larges, c'est pas fait au hasard et c'est important) :
SI yP_i < yQ ≤ yP_(i+1) ou bien yP_i ≥ yQ > yP_(i+1) alors :
 SI (Orientation(P_i,P_(i+1),Q) > 0 et yP_(i+1) > yP_i) ou bien (Orientation(P_i,P_(i+1),Q) < 0 et yP_(i+1) < yP_i) alors :
  w = 1-w
 Fin SI
Fin SI


À la fin de cette procédure, w représente le résultat du test (si w = 1 alors Q est dans le polygone et si w = 0 alors Q n'est pas dans le polygone).

Si Q est exactement sur le bord du polygone alors la valeur de w dépend de la nature du bord en question, mais en pratique osef un peu si le test se trompe dans ce cas (à l’œil nu ça change rien si le bord fait partie de l'intérieur ou pas).

Remarques :
La même remarque sur le « rectangle limite » que dans le test précédent est valable ici.



image


Si vous avez des questions sur ces tests ou même sur comment tester d'autres propriétés géométriques qui n’apparaissent pas dans ce tuto n'hésitez pas à m'envoyer un MP (je risque de ne pas le voir si vous laissez seulement un commentaire ici). Je partagerai les réponses éventuelles dans les commentaires ci-dessous. La géométrie algorithmique étant mon domaine de prédilection, je serais ravi de pouvoir me rendre utile sur ça [img]smileys/sourire.gif" alt="Sourit"

Ciao !


Nemau - posté le 06/10/2020 à 22:14:23 (39510 messages postés) - admin -

❤ 0

Hé hé! Tu vas te perdre dans Oniromancie. Hi hi! Bien fait!!

image

=>[]

Proposez vos news !TrombinoscopePolaris 03Planète Glutko • Doom Doom Doom Doom! I want you in my tomb!


Tassle - posté le 06/10/2020 à 23:00:03 (4739 messages postés)

❤ 1

Disciple de Pythagolf

Oui je m’ennuie un peu en attendant la reprise des études :F
Mais je me suis restreint aux trucs pour lesquels je voyais immédiatement des applications possibles aux jeux vidéo (et encore, j'en ai laissé tombé certains), sinon j'ai bien pire en stock :p

En vrai tout ce qui est dans ce tuto peut s'avérer utile et peut être compris avec un peu de patience. Si un jour t'as besoin d'une de ces fonctionnalités tu arriveras sans doute à t'en sortir (en tout cas moi je fonctionne comme ça, je suis 1000 fois plus patient et appliqué quand j'apprends avec un but en tête).

~~


gif - posté le 07/10/2020 à 11:51:49 (4421 messages postés) - staff -

❤ 0

Très pratique, merci Tassle :) !

Twitter | Cochouchou à la coupe du monde ! | le concours hebdomadaire du meilleur screen !


Gari - posté le 07/10/2020 à 14:20:27 (2494 messages postés) - staff -

❤ 0

J'ai l'impression que le level des tutos augmente. Bientôt il faudra bac+8 pour espérer pouvoir faire un jeu :F

En vrai c'est cool, ce sont des trucs qui manquent (même si là pour qu'un visiteur trouve ça avec l'outil de recherche et ses termes à lui, va falloir s'accrocher).
Si ça te dérange pas, je vais juste modifier un peu la mise en page pour qu'on puisse lire les titres.


Tassle - posté le 07/10/2020 à 14:57:39 (4739 messages postés)

❤ 0

Disciple de Pythagolf

Oui pas de souci pour la mise en page, celle de ton tuto qui vient de sortir est effectivement bien plus lisible.

Pour faciliter la recherche il pourrait être utile de pouvoir ajouter des mots-clefs (ou "tags") aux articles.

~~

Suite à de nombreux abus, le post en invités a été désactivé. Veuillez vous inscrire si vous souhaitez participer à la conversation.

Haut de page

Merci de ne pas reproduire le contenu de ce site sans autorisation.
Contacter l'équipe - Mentions légales

Plan du site

Communauté: Accueil | Forum | Chat | Commentaires | News | Flash-news | Screen de la semaine | Sorties | Tests | Gaming-Live | Interviews | Galerie | OST | Blogs | Articles perso | Recherche
Apprendre: Visite guidée | RPG Maker 95 | RPG Maker 2003 | RPG Maker XP | RPG Maker VX | RPG Maker MV | Tutoriels | Guides | Making-of
Télécharger: Programmes | Scripts | Packs de ressources | Midis | Eléments séparés | Sprites
Jeux: Au hasard | Notre sélection | Sélection des membres | Jeux complets | Tous les jeux | Le cimetière | RPG Maker 95 | RPG Maker 2000 | RPG Maker 2003 | RPG Maker XP | RPG Maker VX | RPG Maker VX Ace | RPG Maker MV | Autres | Proposer
Ressources RPG Maker 2000/2003: Chipsets | Charsets | Panoramas | Backdrops | Facesets | Battle anims | Battle charsets | Monstres | Systems | Templates
Ressources RPG Maker XP: Tilesets | Autotiles | Characters | Battlers | Window skins | Icônes | Transitions | Fogs | Templates
Ressources RPG Maker VX: Tilesets | Charsets | Facesets | Systèmes
Ressources RPG Maker MV: Tilesets | Characters | Faces | Systèmes | Title | Battlebacks | Animations | SV/Ennemis
Archives: Palmarès | L'Annuaire | Livre d'or | Le Wiki | Divers