Forum Liberty Basic France

Le 26/04/2020 à 07h21

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
[EDIT] Archive : trad à compléter + maj le tuto PDF [/EDIT]

Bonjour,


Ci-après, un tutoriel sur les fonctions de collisions en JustBasic.

La version originale est en anglais.

Vous pouvez la retrouver ici : http://jbfilesarchive.com/phpBB3/viewtopic.php?t=1504

- Tout le texte écrit en << bleu >> , représente la traduction de ce tuto.
(J'ai tout d'abord utilisé un traducteur en ligne, puis effectué quelques reformulations ici et là, avec parfois une certaine liberté, afin d'avoir une lecture plus fluide et compréhensible...
Merci de me signaler toutes erreurs éventuelles) ;)


Légende :
- [...] : portion de texte (minime) non traduite.
- NDT : signifie "Note du traducteur"
- Les zones cachés contiennent les textes originaux (je les ai conservé afin que vous puissiez vous y référer si besoin).



Bonne lecture.

@+joan74



Edité par joan74 Le 01/06/2020 à 17h38
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 26/04/2020 à 07h43

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95

*** [JB] Tutoriel sur la Détection de Collisions Avancées ***


- par Andy AMAYA -



<< Cela m'a pris beaucoup plus de temps que prévu, mais voici enfin un tutoriel qui présente pas moins de 12 façons différentes de détecter différents types de collisions !

Une fois que vous aurez compris l’utilisation des techniques de collision, vous devriez être capable de programmer les différents types de jeux suivants :
> JDR Graphique (simple joueur uniquement, pas les MMORPG)
> "Duck Hunt" (NDT : célèbre jeu sortit sur console en 1985)
> Jeux de Tir
> Objet caché
> Image Miroir
> Gestion d'entreprise ferroviaire.
> Jeux de Course
> Et bien plus encore ...!

Le fichier ZIP contient :
> Le tutoriel, à la fois au format RTF et au format PDF.
> Des programmes exemples illustrant l’utilisation des fonctions de collisions (dont un petit jeu avec des triangles et deux jeux de puzzle).
> Un éditeur de polygone
> La solution au "flaxen's dilemma" (mentionné plus loin dans ce tutoriel). >>

<<< Télécharger les fichiers >>>



Caché:
It's taken a lot longer than I had anticipated, but here's a tutorial that presents no less than 12 different ways to detect different types of collisions!

Once you understand using the collision techniques, you should be able to program the following types of games:

Graphical RPG (single player only not MMORPG)
Duck Hunt game
Shooting Gallery
Hidden Object
Mirror Picture
Railroad Tycoon
Road Race
And many more!

Attached is a .zip file that has:
> The tutorial in both Word .doc format and HTML
> The source code for all of the collision functions.
> Simple example code to see how everything works
> The solution to "flaxen's dilemma" (discussed in tutorial)
> A simple triangle game that starts out easy and later becomes frantic
> A puzzle game (see Point In Polygon Function.bas)





Edité par joan74 Le 01/06/2020 à 16h07
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 26/04/2020 à 07h47

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Objectif et Sommaire

<< L’objectif de ce tutoriel est de présenter différentes techniques de tests de collisions. De discuter de leurs applications possibles, et de fournir des exemples d'utilisation. Les exemples sont entièrement commentés et ce tutoriel explique la logique employée dans les routines les plus courantes. L'utilisation de fonctions et de Subs a été privilégié afin de vous permettre de facilement les copier/coller dans vos propres programmes [...].

Ce tutoriel est a destination des programmeurs ayant déjà une bonne connaissance de JB et qui sont familiarisé avec le système de collision des sprites. J'espère que les nouveaux programmeurs tireront également profit des exemples fournis.

Voici la liste des fonctions présentés dans ce tutoriel :

Détection des collisions de base
- Point dans un Rectangle
- Point dans un Cercle
- Point dans une Ellipse
- Point dans un Triangle
- Rectangle avec Rectangle
- Cercle avec Cercle
- Cercle avec une Ligne

Détection de Collision Avancée
- Point dans un Polygone
- Polygone avec Polygone

Autres (Fonctions postérieures au tutoriel initial)
- Ellipse avec Rectangle
- Cercle avec Rectangle
- Cercle avec Triangle

Beaucoup d'entres-vous doivent-être déjà familiarisés avec les fonctions de base. Je les ai tous de même incluses dans ce tutoriel afin d'être aussi complet que possible. Je ne vais pas passer du temps à expliquer le fonctionnement de ces dernières, mais je ferai quelques commentaires sur la façon dont elles peuvent être utilisées.

Ceci dit, faisons maintenant connaissances avec ces fonctions. >>


Caché:
* * * JB Advanced Collision Checking Tutorial * * *

The objective of this tutorial is to introduce different types of collision checking techniques available, to discuss their possible applications, and to provide working examples. The examples are fully commented and this tutorial explains the logic employed in the more involved routines. Functions and SUBs are used almost exclusively to allow you to copy and paste the collision detecting code into your own programs for further exploration.

The intended audience of this tutorial is a programmer who has a working knowledge of JB and is familiar with the JB sprite collision system. It is hoped that new programmers will also derive benefit from the working examples provided.

Here is a list of the collision detection functions provided in this tutorial:

Basic Collision Detection
- Point In Rectangle
- Point In Circle
- Point In Ellipse
- Point In Triangle
- Rectangle To Rectangle Collision
- Circle To Circle Collision
- Circle To Line Collision

Advanced Collision Detection
- Point In Polygon
- Polygon To Polygon Collision

Many will be familiar with the basic detection functions. I have included them all to be as thorough as possible in the discussion of collision techniques available to you the programmer. I don’t intend to spend too much time explaining how these familiar functions work, but will comment on how they can be used.

Having said that, let’s “dive in” and familiarize our selves with these collision functions.




Edité par joan74 Le 01/06/2020 à 16h12
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 26/04/2020 à 07h48

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Fonction Point dans un Rectangle

<< C’est la plus simple et la plus courante des fonctions de collision. Je suis sûr que la plupart d’entre vous a déjà utilisé quelque chose de similaire. Je sais qu'il m'est souvent arrivé d'effectuer les tests de collision directement dans le code, et j’ai constaté que je répétais constamment les mêmes lignes avec seulement des valeurs différentes.... Si l'on remplace ces tests par une fonction, elle devient alors aussi commode qu'une fonction intégrée, telle que COS, INT, SQR, etc. Et, en stockant les informations relatives au rectangle dans un tableau, il devient alors possible de scanner, étudier, traiter et manipuler autant de rectangles que l'on souhaite.

C'est exactement ce que j’ai fais pour l’exemple relatif à cette fonction.

Un très bon usage de cette fonction vient immédiatement à l’esprit. Que faire si vous avez un grand nombre de zones de forme irrégulière à l’écran qui doivent être tester à chaque fois que la souris se déplace ? [...]. La solution consiste à diviser l’écran en quadrants, qui seront à leur tour subdivisés en quadrants, et ainsi de suite... permettant ainsi des tests de collisions sans ralentissement notable dans votre programme.

C'est pourquoi cette fonction devrait-être la plus utilisée de toutes car elle vous permet de décomposer des collisions complexes ou nombreuses en de plus petites, plus facile à gérer. Elle est également l’une des plus rapides à évaluer. Et lorsqu'il s'agit de graphismes, plus c'est rapide mieux c'est !

Une autre utilisation évidente est de permettre la création de vos propres boutons graphique pour les interfaces utilisateurs, au lieu d’utiliser les contrôles 'BUTTONS' de base.

Vous pouvez également utiliser « Point In Rectangle » comme base pour un système d’inventaire graphique, ou un module de sélection d’armes graphique dans un JDR 'point-n-click'.

Remarque : toutes les fonctions "Point Dans ..." peuvent-être utilisé pour les boutons mais la fonction "Point Dans Polygone" (que nous verrons plus loin dans ce tutoriel) peut accueillir des formes de boutons particulièrement intéressantes. En effet, un polygone pouvant prendre les formes les plus diverses et variées, « Point Dans Polygone » s'avère alors être la fonction idéale pour certaines utilisations : sélection graphique précises de boutons, d’objets, de personnages, de régions sur une Mappemonde, etc.

Code VB :
Function pnr(px, py, x, y, w, h)
'=================================================================
' Fonction de collision : "Point Dans Rectangle"
'=================================================================
' Cette fonction permet de vérifier si le point (px, py) se trouve à l'intérieur du rectangle spécifié.
' Si le point EST à l'intérieur du rectangle, la fonction renvoie la valeur 1.
' Si la fonction N'EST PAS à l'intérieur du rectangle, la fonction renvoie 0 (zéro).
'=================================================================
' px = la coordonnée X du point à vérifier
' py = la coordonnée Y du point à vérifier
' x = coordonnée X du sommet supérieur gauche du rectangle
' y = coordonnée Y du sommet supérieur gauche du rectangle
' w =  largeur du rectangle
' h = hauteur du rectangle
'=================================================================

    pnr = ((px>=x) And (px<=(x+w-1)) And (py>=y) And (py<=(y+h-1)))
 
End Function


Comme vous pouvez le constater, cette fonction ne se compose que d'une seule ligne de code, et elle a été optimisée afin d'obtenir un maximum de vitesse et d'efficacité.

Le fichier "Point Dans Rectangle - Exemple.Bas” propose un exemple d'utilisation de cette fonction. >>


Caché:
Point In Rectangle Function

This is the simplest and most familiar of the collision detection functions. I’m sure most of you have used something similar to this code. I know that I’ve performed the check directly in code, but have found that I often had to repeat the same lines of code only with different values. When used as a function it becomes as useful as any other intrinsic function (e.g. COS, INT, SQR, etc…;). I can iterate through as many different rectangles as I could possibly wish by storing the rectangle information in an array. Which is exactly what I’ve done in the working example for this function.

A very good use of this function immediately comes to mind. What if you have a large number of irregularly shaped areas on screen to check each time the mouse moves? You would quickly bring any collision detection system to a crawl if you checked all of the graphic entities for each mouse movement. The trick is to divide the screen into quadrants, which are in turn sub-divided into quadrants, and so forth until you can detect collisions without any noticeable slowdown in your program.

This collision function will be the most used of all the collision functions because it allows you to break down complex or numerous collisions into manageable pieces of code. It’s also one of the fastest to evaluate, because when it come to graphics, faster is always better.

Another obvious use would be to create your own GUI (Graphical User Interface) buttons instead of using BMP buttons.

(Note: all of the “Point In … shape“ functions are great for interestingly shaped buttons however the “Point In Polygon” function can accommodate especially interesting button shapes.)

You can also use “Point In Rectangle” as the basis for a graphical inventory system, or a graphical weapons selection module in a point-n-click RPG.

Code VB :
Function pnr(px, py, x, y, w, h)
'=================================================================
'   Function "Point In Rectangle"
'=================================================================
' This function checks to see if the point (px, py) is within the specified rectangle.
' If the point IS inside the rectangle a value of 1 is returned.
' If the point IS NOT inside the rectangle a value of 0 (zero) is returned.
'=================================================================
' px = the X coord of the point in question
' py = the Y coord of the point in question
' x = upper  left X coord of rectangle
' y = upper  left Y coord of rectangle
' w =  width of rectangle
' h = height of rectangle
'=================================================================

    pnr = ((px>=x) And (px<=(x+w-1)) And (py>=y) And (py<=(y+h-1)))
 
End Function


As you can see it’s only one line of code that does the job and has been optimized for maximum speed and efficiency.

See “Point In Rectangle.Bas” for an example on how to implement this function.




Edité par joan74 Le 01/06/2020 à 17h11
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 26/04/2020 à 07h50

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Fonction Point dans un Cercle

<< Cette fonction détecte si un point se trouve à l’intérieur du rayon d’un cercle donné.

Code VB :
Function pnc(px, py, cx, cy, cr)
'=================================================================
' Fonction de collision : "Point Dans Cercle"
'=================================================================
' Cette fonction permet de vérifier si le point (px, py) se trouve à l'intérieur du cercle spécifié.
' Si le point EST à l'intérieur du cercle, la fonction renvoie la valeur 1.
' Si la fonction N'EST PAS à l'intérieur du cercle, la fonction renvoie 0 (zéro).
'=================================================================
' px = la coordonnée X du point à vérifier
' py = la coordonnée Y du point à vérifier
' cx = coordonnée X du centre du cercle
' cy = coordonnée Y du centre du cercle
' cr = rayon du cercle
'=================================================================

    'Ce format est plus rapide et peut être 'aligné' pour un maximum de vitesse
    pnc = (  ((px-cx)*(px-cx) + (py-cy)*(py-cy)) <= cr*cr  )
 
'=================================================================

    'Ce format est plus lisible ... mais légèrement plus lent
    'dx2 = (px-cx)*(px-cx)
    'dy2 = (py-cy)*(py-cy)
    'r2 = cr * cr

    'pnc = ( dx2 + dy2 < r2)

End Function


Le code de détection a été optimisé pour une vitesse et une efficacité maximales.

Le fichier "Point Dans Cercle - Exemple.Bas” propose un exemple d'utilisation de cette fonction. >>


Caché:
Point In Circle Function

This function detects when a point is inside the radius of a given circle.

Code VB :
Function pnc(px, py, cx, cy, cr)
'=================================================================
'   Function "Point In Circle"
'=================================================================
' This function checks to see if the point (px, py) is inside the specified circle.
' If the point IS inside the circle a value of 1 is returned.
' If the point IS NOT inside the circle a value of 0 (zero) is returned.
'=================================================================
' px = the X coord of the point in question
' py = the Y coord of the point in question
' cx = center of circle X coordinate
' cy = center of circle Y coordinate
' cr = circle radius
'=================================================================

    'This format is fastest and can be 'inlined' for maximum speed
    pnc = (  ((px-cx)*(px-cx) + (py-cy)*(py-cy)) <= cr*cr  )
 
'=================================================================

    'This format is more readable ... but slightly slower
    'dx2 = (px-cx)*(px-cx)
    'dy2 = (py-cy)*(py-cy)
    'r2 = cr * cr

    'pnc = ( dx2 + dy2 < r2)

End Function


The detection code has been optimized for maximum speed and efficiency.

Run the code “Point In Circle Function.Bas” to get an idea of how to use this function.




Edité par joan74 Le 23/05/2020 à 10h23
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 26/04/2020 à 07h51

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Fonction Point dans une Ellipse

<< Cette fonction détecte si un point se trouve à l’intérieur d'une ellipse.

Code VB :
Function pne(px, py, ex, ey, ew, eh)
'=================================================================
' Fonction de collision : "Point Dans Ellipse"
'=================================================================
' Cette fonction permet de vérifier si le point (px, py) se trouve à l'intérieur de l'ellipse spécifié.
' Si le point EST à l'intérieur de l'ellipse, la fonction renvoie la valeur 1.
' Si la fonction N'EST PAS à l'intérieur de l'ellipse, la fonction renvoie 0 (zéro).
'=================================================================
' px = la coordonnée X du point à vérifier
' py = la coordonnée Y du point à vérifier
' ex = coordonnée X du centre de l'ellipse
' ey = coordonnée Y du centre de l'ellipse
' ew = largeur de l'ellipse
' eh = hauteur de l'ellipse
'=================================================================

    'Ce format est plus rapide et peut être 'aligné' pour un maximum de vitesse
    pne = ((px-ex)*(px-ex)/((ew/2)*(ew/2))+(py-ey)*(py-ey)/((eh/2)*(eh/2))<1)
 
 '=================================================================

    'Ce format est plus lisible ... mais légèrement plus lent
    'dx = (px - ex) * (px - ex)
    'dy = (py - ey) * (py - ey)
    'ew2 = (ew/2)*(ew/2)
    'eh2 = (eh/2)*(eh/2)

    'pne = (dx/ew2 + dy/eh2 <= 1)

End Function


Le code de détection a été optimisé pour une vitesse et une efficacité maximales.

Le fichier "Point Dans Ellipse - Exemple.Bas" propose un exemple d'utilisation de cette fonction. >>


Caché:
Point In Ellipse Function

This function detects when a point is inside of an ellipse.

Code VB :
Function pne(px, py, ex, ey, ew, eh)
'=================================================================
'   Function "Point In Ellipse"
'=================================================================
' This function checks to see if the point (px, py) is inside the specified ellipse.
' If the point IS inside the ellipse a value of 1 is returned.
' If the point IS NOT inside the ellipse a value of 0 (zero) is returned.
'=================================================================
' px = the X coordinate of the point in question
' py = the Y coordinate of the point in question
' ex = ellipse center X coordinate
' ey = ellipse center Y coordinate
' ew = ellipse width
' eh = ellipse height
'=================================================================

    'This format is fastest and can be 'inlined' for maximum speed
    pne = ((px-ex)*(px-ex)/((ew/2)*(ew/2))+(py-ey)*(py-ey)/((eh/2)*(eh/2))<1)
 
 '=================================================================

    'This format is more readable ... but slightly slower
    'dx = (px - ex) * (px - ex)
    'dy = (py - ey) * (py - ey)
    'ew2 = (ew/2)*(ew/2)
    'eh2 = (eh/2)*(eh/2)

    'pne = (dx/ew2 + dy/eh2 <= 1)

End Function


The detection code has been optimized for maximum speed and efficiency.

Run the code “Point In Ellipse Function.Bas” to get an idea of how to use this function.




Edité par joan74 Le 23/05/2020 à 10h23
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 26/04/2020 à 07h51

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Fonction Point dans un Triangle

<< Cela détecte si un point est à l’intérieur d’un triangle.

Code VB :
Function pnt(px,py, x1,y1, x2,y2, x3,y3)
'================================================================='  
' Fonction de collision : "Point Dans Triangle"
'=================================================================
' Cette fonction permet de vérifier si le point (px, py) se trouve à l'intérieur du triangle spécifié.
' Si le point EST à l'intérieur du triangle, la fonction renvoie la valeur 1.
' Si la fonction N'EST PAS à l'intérieur du triangle, la fonction renvoie 0 (zéro).
'=================================================================
' px = la coordonnée X du point à vérifier
' py = la coordonnée Y du point à vérifier
' x1, y1 = coordonnées du premier sommet du triangle
' x2, y2 = coordonnées du second sommet du triangle
' x3, y3 = coordonnées du troisième sommet du triangle
'=================================================================

    b0 =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
    b1 = ((x2 - px) * (y3 - py) - (x3 - px) * (y2 - py)) / b0
    If b1 <= 0 Then pnt = 0 : Exit Function
    b2 = ((x3 - px) * (y1 - py) - (x1 - px) * (y3 - py)) / b0
    If b2 <= 0 Then pnt = 0 : Exit Function
    b3 = ((x1 - px) * (y2 - py) - (x2 - px) * (y1 - py)) / b0
    If b3 <= 0 Then pnt = 0 : Exit Function
    pnt = 1
 
End Function


Le code de détection a été optimisé pour une vitesse et une efficacité maximales.

Le fichier 'Point Dans Triangle - Exemple.Bas' propose un exemple d'utilisation de cette fonction.
Le fichier ‘Point Dans Triangle – Jeu’ propose un autre exemple d'utilisation de cette fonction. >>


Caché:
Point In Triangle Function

This detects when a point is inside of a triangle.

Code VB :
Function pnt(px,py, x1,y1, x2,y2, x3,y3)
'================================================================='   
'  Function "Point In Triangle"
'=================================================================
' This function checks to see if the point (px,py) is within the specified triangle.
' If the point IS inside the triangle a value of 1 is returned.
' If the point IS NOT inside the triangle a value of 0 (zero) is returned.
'=================================================================
' px = the X coord of the point in question
' py = the Y coord of the point in question
' x1, y1 =  first triangle vertex
' x2, y2 = second triangle vertex
' x3, y3 =  third triangle vertex
'=================================================================

    b0 =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
    b1 = ((x2 - px) * (y3 - py) - (x3 - px) * (y2 - py)) / b0
    If b1 <= 0 Then pnt = 0 : Exit Function
    b2 = ((x3 - px) * (y1 - py) - (x1 - px) * (y3 - py)) / b0
    If b2 <= 0 Then pnt = 0 : Exit Function
    b3 = ((x1 - px) * (y2 - py) - (x2 - px) * (y1 - py)) / b0
    If b3 <= 0 Then pnt = 0 : Exit Function
    pnt = 1
 
End Function


The detection code has been optimized for maximum speed and efficiency.

Run the code “Point In Triangle Function.Bas” to get an idea of how to use this function.




Edité par joan74 Le 23/05/2020 à 10h22
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 26/04/2020 à 07h54

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Fonction de Collision Rectangle avec Rectangle

<< Cette fonction vérifie si deux rectangles sont en collision. Il s’agit du même type de détection que JB utilise pour les collisions de sprites. Vous pouvez utiliser la fonction « Rectangle Avec Rectangle » avec des images, des boîtes ou tout autre élément rectangulaire qui n’a pas besoin de transparence.

Oh, et c’est bien pratique également pour les interfaces "glisser-déposer".

Code VB :
Function r2r(ax, ay, aw, ah, bx, by, bw, bh)
'=================================================================
' Fonction de collision : « Rectangle Avec Rectangle »
'=================================================================
' Cette fonction permet de vérifier si deux rectangles sont en collision.
' Si les rectangles SONT en collision, la fonction renvoie une valeur différente de zéro. 
' Si les rectangles NE SONT PAS en collision, la fonction renvoie 0 (zéro).
''=================================================================
' ax = coordonnée X du sommet supérieur gauche du rectangle "a"
' ay = coordonnée Y du sommet supérieur gauche du rectangle "a"
' aw = largeur du rectangle "a"
' ah = hauteur du rectangle "a"
' bx = coordonnée X du sommet supérieur gauche du rectangle "b"
' by = coordonnée Y du sommet supérieur gauche du rectangle "b"
' bw = largeur du rectangle "b"
' bh = hauteur du rectangle "b"

'NOTE: les coordonnées de valeurs négatives renverront des résultats non valides.

'=================================================================

    'Ce format est plus rapide et peut être 'aligné' pour un maximum de vitesse
    r2r =(((((bx+bw-1)-ax) Xor (bx-(ax+aw-1)))  And _
           ((by-(ay+ah-1)) Xor ((by+bh-1)-ay))) And 2147483648)
 
'=================================================================

    'Ce format est plus lisible ... mais légèrement plus lent

    'ax2 = ax + aw - 1
    'ay2 = ay + ah - 1
    'bx2 = bx + bw - 1
    'by2 = by + by - 1

    'a = (bx2 - ax) Xor (bx - ax2)
    'b = (by - ay2) Xor (by2 - ay)
    'c = 2147483648                    'c = &H80000000

    'r2r = (a And b) And c

End Function


Le code de détection a été optimisé pour une vitesse et une efficacité maximales.

Le fichier 'Rectangle Avec Rectangle - Exemple.Bas' propose un exemple d'utilisation de cette fonction. >>


Caché:
Rectangle To Rectangle Collision Function

This function checks to see if two rectangles have collided. This is the same collision detection that the JB sprite system uses to detect when sprites have collided. You can use this “Rectangle To Rectangle” collision detection using pictures, boxes, or anything else that is rectangular and doesn’t need transparency.

Oh, and it’s also good for “drag and drop” interfaces.

Code VB :
Function r2r(ax, ay, aw, ah, bx, by, bw, bh)
'=================================================================
'   Rectangle To Rectangle Collision Function
'=================================================================
' This function checks to see if two rectangles have collided.
' If the rectangles HAVE COLLIDED a non-zero value is returned.
' If the rectangles HAVE NOT COLLIDED a value of 0 (zero) is returned.
''=================================================================
' ax = upper  left X coordinate of rectangle "a"
' ay = upper  left Y coordinate of rectangle "a"
' aw =  width of rectangle "a"
' ah = height of rectangle "a"
' bx = upper  left X coordinate of rectangle "b"
' by = upper  left Y coordinate of rectangle "b"
' bw =  width of rectangle "b"
' bh = height of rectangle "b"

'NOTE: negative coordinate values will return non-valid results.

'=================================================================

    'This format is fastest and can be 'inlined' for maximum speed
    r2r =(((((bx+bw-1)-ax) Xor (bx-(ax+aw-1)))  And _
           ((by-(ay+ah-1)) Xor ((by+bh-1)-ay))) And 2147483648)
 
'=================================================================

    'This format is more readable... but slightly slower

    'ax2 = ax + aw - 1
    'ay2 = ay + ah - 1
    'bx2 = bx + bw - 1
    'by2 = by + by - 1

    'a = (bx2 - ax) Xor (bx - ax2)
    'b = (by - ay2) Xor (by2 - ay)
    'c = 2147483648                    'c = &H80000000

    'r2r = (a And b) And c

End Function


The detection code has been optimized for maximum speed and efficiency.

Run the code “Rectangle To Rectangle Function.Bas” to get an idea of how to use this function.




Edité par joan74 Le 23/05/2020 à 09h51
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 26/04/2020 à 08h01

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Fonction de Collision Cercle avec Cercle

<< Cette fonction détermine si deux cercles sont en collision.

Code VB :
Function c2c(ax, ay, ar, bx, by, br)
'=================================================================
' Fonction de collision : « Cercle Avec Cercle »
'=================================================================
' Cette fonction permet de vérifier si deux cercles sont en collision.
' Si les cercles SONT en collision, la fonction renvoie la valeur 1.
' Si les cercles NE SONT PAS en collision, la fonction renvoie 0 (zéro).
'=================================================================
' ax = coordonnée X du centre du cercle "a"
' ay = coordonnée Y du centre du cercle "a"
' ar = rayon du cercle "a"
' bx = coordonnée X du centre du cercle "b"
' by = coordonnée Y du centre du cercle "b"
' br = rayon du cercle "b"
'=================================================================

    c2c = (((ar + br) * (ar + br)) > ((ax - bx) * (ax - bx) + (ay - by) * (ay - by)))
 
End Function


Le code de détection a été optimisé pour une vitesse et une efficacité maximales.

Le fichier 'Cercle Avec Cercle - Exemple.Bas' propose un exemple d'utilisation de cette fonction. >>


Caché:
Circle To Circle Collision Function

This function determines when two circles have collided.

Code VB :
Function c2c(ax, ay, ar, bx, by, br)
'=================================================================
'   Circle To Circle Collision Function
'=================================================================
' This function checks to see if the two circles have collided.
' If the circles HAVE COLLIDED a value of 1 is returned.
' If the circles HAVE NOT COLLIDED a value of 0 (zero) is returned.
'=================================================================
' ax = center X coordinate of circle "a"
' ay = center Y coordinate of circle "a"
' ar = radius of circle "a"
' bx = center X coordinate of circle "b"
' by = center Y coordinate of circle "b"
' br = radius of circle "b"
'=================================================================

    c2c = (((ar + br) * (ar + br)) > ((ax - bx) * (ax - bx) + (ay - by) * (ay - by)))
 
End Function


The detection code has been optimized for maximum speed and efficiency.

Run the code “Point In Triangle Function.bas” to get an idea of how to use this function.




Edité par joan74 Le 23/05/2020 à 09h52
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 26/04/2020 à 08h05

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Fonction de Collision Cercle avec Ligne

<< Cette fonction détermine si un cercle et un segment de ligne sont en collision. Quelques utilisations possibles viennent immédiatement à l’esprit, comme un jeu de billard, un jeu de golf miniature, ou un jeu de flipper.

Code VB :
Function c2L(x1, y1, x2, y2, cx, cy, cr)
'=================================================================
' Fonction de collision : « Cercle avec Ligne »
'=================================================================
' Cette fonction vérifie si un cercle est en collision avec une ligne
' c2L renvoie 1 si le cercle est en collision avec la ligne
' c2L renvoie à 0 (zéro) si aucune collision n'a lieu
'=================================================================
' x1, y1, x2, y2 sont deux coordonnées de la ligne à vérifier
' cx, cy sont les coordonnées du centre du cercle
' cr est le rayon du cercle
'=================================================================

    d = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)
    If d <> 0 Then d = ((cx - x1) * (x2 - x1) + (cy - y1) * (y2 - y1)) / d
 
    'Ajustement des valeurs limites du segment 
    '("Clip To the line segments legal bounds")
    If d < 0.0 Then d = 0
    If d > 1.0 Then d = 1
    dx = cx - ( (x2 - x1) * d + x1)
    dy = cy - ( (y2 - y1) * d + y1)
    c2L = (dx * dx + dy * dy <= cr * cr)
 
End Function


Le code de détection a été optimisé pour une vitesse et une efficacité maximales.

Le fichier 'Circle Avec Ligne - Exemple.Bas' propose un exemple d'utilisation de cette fonction. >>


Caché:
Circle To Line Collision

This function determines when a circle and a line segment collide. A few possible uses come immediately to mind, such as a bumper pool game, miniature golf game, or a pinball game.

Code VB :
Function c2L(x1, y1, x2, y2, cx, cy, cr)
'=================================================================
' Circle To Line Function
'=================================================================
' This function checks if a circle has collided with a line
' c2L returns a 1 if the circle has collided with the line
' c2L returns a 0 (zero) if no collision has occurred
'=================================================================
' x1, y1, x2, y2 are the two coordinates defining the line to check
' cx, cy are the coordinates of the center of the circle
' cr is the radius of the circle
'=================================================================

    d = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)
    If d <> 0 Then d = ((cx - x1) * (x2 - x1) + (cy - y1) * (y2 - y1)) / d
 
    'Clip To the line segments legal bounds
    If d < 0.0 Then d = 0
    If d > 1.0 Then d = 1
    dx = cx - ( (x2 - x1) * d + x1)
    dy = cy - ( (y2 - y1) * d + y1)
    c2L = (dx * dx + dy * dy <= cr * cr)
 
End Function


The detection code has been optimized for maximum speed and efficiency.

Run the code “Circle To Line Function.Bas” to get an idea of how to use this function.




Edité par joan74 Le 23/05/2020 à 10h20
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 26/04/2020 à 08h27

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
<< Les sept fonctions de base que nous venons de voir étaient très simples, mais il ne faut pas les sous-estimer pour autant, dans les circonstances appropriées, ce sont les routines les plus efficaces existantes.

Il y aura toujours une certaine limite à ne pas dépasser pour ce qui est de la complexité de nos codes (due aux ressources matériels : CPU, mémoire,...). Les deux prochaines fonctions présentées ci-après, bien que complexes conservent cependant suffisamment de rapidité. >>


Caché:
The seven basic collision detection functions are very simple but do not underestimate their usefulness, under the proper circumstances they are the most efficient routines available.

It’s always going to be a trade off between ease of use (complexity) and resources (CPU or memory or both), yet the next two collision routines while not quite as simple are still fairly fast.




Edité par joan74 Le 21/05/2020 à 08h49
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 26/04/2020 à 08h28

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Fonction Point dans un Polygone
& Fonction Polygone Avec un Polygone


<< La fonction ‘Point Dans Polygone’ détecte si un point se trouve à l’intérieur du polygone spécifié par l’utilisateur.

Comme il n'y a pas de limite au nombre maximal de côtés pour un polygone, cela offre beaucoup de liberté dans leur conception, que se soit au niveau de leur forme ou de leur taille.

Jusqu’à maintenant, nous n’avons eu à traiter que des cas à 4 points maxi, comme dans « Point dans un Rectangle ». Cette nouvelle fonction permettra de traiter un nombre de points, allant d'un minimum de 3 points et à un maximum de 500 points ! Il s'avère évident que nous devrons trouver une procédure logique pour traiter toute la gamme des possibilités.

Ce qui signifie que nous aurons besoin de stocker et de pouvoir accéder à chaque paire de coordonnées définissant le polygone. Aussi, nous allons naturellement utiliser un tableau pour stocker ces informations. Une autre implication est que nous aurons besoin d'avoir ces coordonnées stockées sous forme de DATA ou alors les lire à partir d’un fichier disque afin de pouvoir renseigner le tableau. Ne vous inquiétez pas, tout a été pris en compte, mais nous vous détaillerons la façon dont tout est mis en place afin que vous puissiez utiliser au mieux cette fonction dans vos propres programmes.

Tout d’abord, nous devons définir ce qu’est un polygone et ce qu’il n’est pas. Voici notre définition d’un polygone :

Un polygone peut-être considéré comme un ensemble d'au moins trois points non colinéaires (NDT: colinéaire=aligné).

Autrement dit, rien n'interdit d'avoir des points colinéaires dans un polygone, mais il faut obligatoirement qu'au moins trois d'entres-eux ne sont pas colinéaires.

C’est clairement un cas où une image vaut mille mots. Comme illustré dans la figure 1 ci-dessous, vous pouvez créer une variété infinie de formes qui répondent aux exigences de la définition du polygone indiquée ci-dessus.



figure 1

La seule chose que vous devez garder en tête est que plus votre polygone aura de points, plus il faudra de temps à votre ordinateur pour afficher et/ou tester ce polygone.

Si vous avez juste besoin d'afficher ou de tester un polygone avec un grand nombre de sommets (le point où deux côtés se rejoignent), vous ne devriez pas constater un ralentissement significatif. Cependant, si vous avec plusieurs polygones avec un grand nombre de sommets ou des centaines de polygones avec peu de sommets à afficher en même temps, vous noterez un ralentissement significatif pendant la vérification de collisions

Maintenant que nous avons la définition d’un polygone, nous allons voir comment utiliser un tableau pour stocker les paires de coordonnées X-Y qui le définisse.

Commençons par définir les informations nécessaires pour décrire un polygone.

1) Le nombre de sommets existants, qui nous permettra par la suite de manipuler le polygone, au travers de boucles FOR..NEXT.

2) Les coordonnées X et Y du coin supérieur gauche du cadre délimitant le polygone (en jaune dans la figure 2 ci-dessous), de la même façon que nous le faisons pour les sprites, afin de pouvoir le localiser n’importe où à l’écran.

3) Le coin supérieur gauche du cadre délimitant le polygone, sa largeur et sa hauteur nous permettent de vérifier rapidement les événements de collision, même si les sprites ne sont pas utilisé.

4) La liste des coordonnées X-Y des sommets du polygone.


Dans tous les codes exemples, j’utilise un tableau nommé « poly() ». Nous utiliserons également ce même terme, pour les commentaires à l'intérieur des codes.

Pour aider à comprendre la logique utilisée pour remplir le tableau poly(), je vous renvoie à la figure 2, qui montre toutes les informations requises pour définir un polygone. Dans cet exemple, notre polygone est un triangle, ceci afin de présenter les choses le plus simplement possible.



figure 2

1) Le nombre de sommets définissant le polygone = 3
2) Les décalages X,Y = 0,0
(ici par défaut, ces valeurs peuvent être différente selon la position de votre polygone dans votre programme. Modifiez selon vos besoins)
3) La largeur du cadre délimitant le polygone est de : 11 – 0 + 1 = 12 (pixels 0 à 11 inclus)
La hauteur du cadre délimitant le polygone est de : 10 – 0 + 1 = 11 (pixels 0 à 10 inclus)
4) La liste des paires de coordonnées est : 6,0 11,10 0,10 (3 paires de coordonnées = 3 sommets)
(NDT: dans la V.O. il y a une petite erreur, c'est écrit 0,0 mais c'est 6,0 pour ce premier sommet.)

Note: tous les coins supérieurs gauche des cadres délimitant les polygones sont situés à 0,0 lorsqu’ils sont initialement définis afin que nous puissions les placer plus tard n’importe où sur l’écran, tout comme nous le faisons avec les sprites dans JB. Veuillez garder cela à l’esprit lorsque vous installez un polygone dans votre propre programme.

Si vous choisissez de ne pas le faire, vous devrez coder vous-même l’emplacement de votre polygone.

La première dimension du tableau contiendra le numéro « index » du polygone. Cela vous permettra d’accéder à n’importe quel polygone par numéro d’index.

Comme JB ne permet que des tableaux à deux dimensions, nous allons présenter les informations concernant les polygones comme suit :
Numéro d'index = 1 ‘puisque c'est le premier polygone défini...
poly(1, 0) = 3 ‘nombre de sommets
poly(1, 1) = 0 ‘décalage en X. Le décalage réel en X dépendra de votre programme
poly(1, 2) = 0 ‘décalage en Y. Le décalage réel en Y dépendra de votre programme
poly(1, 3) = 12 ‘Le cadre délimitant le polygone est large de 12 pixels
poly(1, 4) = 11 ‘Le cadre délimitant le polygone est haut de 11 pixels
poly(1, 5) = 6 ‘La coordonnée X pour le 1er sommet
poly(1, 6) = 0 ‘La coordonnée Y pour le 1er sommet
poly(1, 7) = 11 ‘La coordonnée X pour le 2nd sommet
poly(1, 8) = 10 ‘La coordonnée Y pour le 2nd sommet
poly(1, 9) = 0 ‘La coordonnée X pour le 3e sommet
poly(1, 10) = 10 ‘La coordonnée Y pour le 3e sommet

Note - l’espace total requis pour stocker un polygone est déterminé par la formule suivante :

Nombre de sommets * 2 + 4 = élément le plus élevé requis pour la seconde dimension

Pour l'exemple du polygone de la figure 2,
il faudrait donc dimensionner le tableau poly() comme cecI :
DIM poly(1,10)’ (1 polygone, 3 sommets * 2 + 4 = 10).


Avec 20 polygones, dont le plus grand ayant 28 sommets, il vous faut dimensionner le tableau poly() comme ceci :
DIM poly(20, 60) (20 polygones, 28 sommets * 2 + 4 = 60).


Ci-après, un code JB qui permettrait de charger les données du polygone dans le tableau poly(), selon l’exemple du triangle ci-dessus :
Code VB :
Dim poly(1,10)
numPolys = 1
 
'[…]

    Restore [polygonData]
 
    For i = 1 To numPolys
        Read numVerts, locX, locY, wide, high
        poly(i,0) = numVerts
        poly(i,1) = locX
        poly(i,2) = locY
        poly(i,3) = wide
        poly(i,4) = high
        For j = 5 To numVerts*2 + 3 Step 2
            Read x, y
            poly(i, j)   = x
            poly(i,j+1) = y
        Next j
    Next I
 
'[…]

[polygonData]
Data 3          ‘nombre de sommets
Data 0, 0      ‘posX, posY     ‘à utiliser comme vous le feriez avec Spritexy
Data 12        ‘largeur du cadre délimitant le polygone
Data 11        ‘hauteur du cadre délimitant le polygone
Data 6,0,  11,10,  0,10      ‘Les 3 paires de coordonnées des sommets


Tout ce qu’il y a à faire c'est de placer les sommets dans le tableau poly(). Évidemment, vous ne voudriez pas avoir à entrer tous les sommets du polygone manuellement, car cela serait extrêmement fastidieux et source d''erreur. J’ai donc écrit un petit « Editeur de Polygone » (voir « Polygon Editor.bas »).

Cela résume la façon dont nous allons stocker les informations du polygone dans le tableau poly(). Maintenant, nous sommes prêts pour la fonction « Point dans un Polygone ».


Code VB :
Function pnp(idx, x, y)
'===============================================================
' Fonction de collision :  "Point Dans Polygone"
'===============================================================
' Cette fonction permet de vérifier si un point (x, y) se trouve à l'intérieur du polygone définie par 'idx'.
' Si le point EST à l'intérieur du polygone, la fonction renvoie la valeur 1.
' Si la fonction N'EST PAS à l'intérieur du polygone, la fonction renvoie 0 (zéro).
'===============================================================
' idx – est l'index des coordonnées du polygone
' x, y sont les coordonnées du point qui doit être testé [...]
'===============================================================
    'lastX is the last X-coordinate of the polygon
    lastX = poly(idx, 0) * 2 + 3    'lastY would be poly(idx,0) * 2 + 4
    'X-offset  of polygon indicated by 'idx'
       oX = poly(idx,1)
    'Y-offset  of polygon indicated by 'idx'
       oY = poly(idx,2)
 
    'on passe en revue tous les points du polygone
    For i = 5 To lastX Step 2
        If i=lastX Then j=5 Else j=(i+2)
        v1 = (poly(idx,i+1) + oY)<=y
        v2 = y < (poly(idx,j+1)+oY)
        v3 = (poly(idx, j+1)+oY)<=y
        v4 = y < (poly(idx,i+1)+oY)
        v5 = (((poly(idx,j)+oX))-(poly(idx,i)+oX))*(y-(poly(idx,i+1)+oY))
        v6 = ((poly(idx,j+1)+oY))-(poly(idx,i + 1)+oY)
        If v6 = 0.0 then v6 = 0.00001    'empêche la division par zéro
        v7 = poly(idx, i) + oX
        If (((v1 And v2))Or(v3 And v4))And(x<v5/v6+v7)) Then pnp=1-pnp
    Next i
End Function


Pour voir un exemple d’utilisation de la fonction « Point dans un Polygone » exécutez « Point Dans Polygone - Jeu 1 » ou « Point Dans Polygone - Jeu 2 ».

Je vais faire ici, une petite digression pour vous montrer deux routines complémentaires que nous pourrions choisir d'utiliser ou pas, mais qu'il est tout de même intéressant d'avoir dans sa 'boîte à outils' [...].

Une de ces routines est un SUB pour dessiner des polygones à l’écran. Il peut être utilisé comme un programme autonome ou comme outil pour déboguer visuellement un programme qui utilise la détection de collision de polygones.


Code VB :
Sub drawPoly  h$, index
'===============================================================
'  Fonction : “Dessiner Un Polygone”
'===============================================================
' Cette fonction dessine le polygone mentionné en ‘index’
'===============================================================
' h$ représente l'handle de votre fenêtre graphique
' index – indique quel doit être le polygone qui sera dessiné à l'écran
'===============================================================

          lastX  = poly(index,0) * 2 + 3     ‘lastY would be poly(index, 0) * 2 + 4
          oX = poly(index, 1)           ‘offset X value allows place anywhere on screen
          oY = poly(index, 2)          ‘offset Y value allows place anywhere on screen
          #h$ “Place “;poly(index, 5)+oX;” “;poly(index, 6)+oY
 
          For i = 7 To  lastX Step 2
                   #h$ “Goto “;poly(index, i)+oX;” “;poly(index, i + 1)+oY
          Next I
 
          #h$ “Goto “;poly(index,5)+oX;” “;poly(index, 6)+oY
 
End Sub


Une autre routine utile serait un SUB pour déplacer un polygone vers un nouvel emplacement à l’écran, de la même manière que la commande JB « Spritexy » positionne les sprites.

Code VB :
Sub movePoly index, x, y
'===============================================================
'  Fonction : “Déplacer un Polygone”
'===============================================================
' Cette fonction permet de définir de nouvelles coordonnées d'affichage d'un polygone sur l'écran
'===============================================================
' index – indique quel doit-être le polygone à déplacer
' x, y sont les nouvelles coordonnées d'affichage
'===============================================================

          poly(index, 1) = x
          poly(index, 2) = y
 
End Sub


Bien, laissons cela de côté et revenons à nos "moutons" !

Maintenant que nous avons compris que « Point Dans Polygone » fonctionne en utilisant un tableau poly() pour stocker les coordonnées des sommets, nous allons étendre son utilité en parcourant les coordonnées d’un petit polygone et en utilisant le « Point Dans Polygone » (ci-dessus nommé PNP) pour voir s’il se trouve à l’intérieur d’un autre polygone (plus grand). Le résultat est que nous aurons une fonction de collision « Polygone Avec Polygone » (ci-après nommée P2P).

Le principal inconvénient de la fonction P2P est que si nous dépassons un certain nombre de tests par "frame" [...], cela aura pour conséquence de générer un ralentissement, pouvant être 'léger' ou plus important. Ce seuil dépendra de la vitesse de votre processeur et de votre sous-système graphique. Nous vous suggérons de travailler avec un nombre raisonnable de sommets et/ou de comparaisons pour vous assurer qu’une grande partie de votre public cible est capable d’utiliser ce type de test de collision [...].

Une autre stratégie consiste à utiliser au préalable la fonction « Rectangle Avec Rectangle » pour voir si les cadres délimitants les deux polygones sont en collision. C’est une fonction très rapide qui permet également de réduire la zone de test. S’il y a collision, vous pouvez alors effectuer un test plus précis en utilisant la fonction P2P plus lourde en calculs. L’utilisation consécutive de ces deux fonctions vous donnera la meilleure performance possible.


Code VB :
Function p2p(index1, index2)
'===============================================================
' Fonction de collision : “Polygone Avec Polygone”
'===============================================================
' Cette fonction vérifie si un polygone1 est en collision avec polygone2
' Typiquement, il s'agit de tester chacun des sommets du polygone ayant le moins de sommets avec un autre ayant un nombre de sommets équivalent ou plus important.
' Si les polygones sont en collision, la fonction renvoie la valeur 1.
' Si les polygones ne sont pas en collision, la fonction renvoie 0 (zéro).
'      ***** Note: Cette fonction nécessite également la fonction 'Point Dans Polygone' *****
'===============================================================
' index1 – désigne le premier polygone 
' index2 – désigne le second polygone 
'===============================================================

          numVerts = poly(index1, 0)        'nombre de sommets du polygone (index1)
          oX = poly(index1, 1)                  'current X-coordinate offset of polygon (index1)
          oY = poly(index1, 2)                  'current Y-coordinate offset of polygon (index1)

          For i = 5 To numVerts * 2 + 3 Step 2
              p2p = pnp(poly(index1, i) + oX, poly(index1, i+1) + oY, index2)
              If p2p = 1 Then Exit For    'si un sommet est à l'intérieur du polygone (index2) alors sortir de la boucle 'For…Next' 
          Next i
 
End Function


Si ce tutoriel a vu le jour, c’est suite à une question posée sur le forum Justbasic Anglophone (NDT : la page web auquel il est fait référence n’existe plus...). Voici une version paraphrasée de la question : « Comment puis-je permettre au sprite de mon personnage de traverser un pont sans qu'il ne pénètre dans la rivière ? ». Je fais référence à cette question en tant que “flaxen’s dilemma”. (voir figure 3 ci-dessous)


figure 3

C’est un cas parfait pour utiliser certaines des techniques de collision que nous avons étudiées : « Rectangle Avec Rectangle » (R2R), « Point Dans Polygone » (PNP) et « Polygone Avec Polygone » (P2P). Nous devons juste faire quelques préparatifs avant de commencer à coder notre solution au “flaxen’s dilemma”.

Tout d’abord, à l'aide de « Polygon Editor », nous allons tracer un polygone qui représentera le sprite du personnage et représenter les deux zones de rivière avec deux autres polygones qui feront office de "frontières". Le polygone du personnage ne devra pas traverser ces polygones "frontières".



Après avoir tracé les polygones et appuyé sur le bouton « Save Data » pour chacun des polygones, nous devons dimensionner le tableau poly() et allouer suffisamment de mémoire pour stocker les trois polygones.

Ensuite, nous aurons besoin de lire les données pour charger les sommets du polygone dans le tableau poly().

Enfin, effectuons un copiez/collez des fonctions nécessaires à la finalisation de cette tâche.


Pour conclure ce tutoriel, voici trois conseils, qui résument l’utilisation des fonctions de collisions dans vos programmes :

1) Faites tous vos calculs en dehors de la boucle de rendu graphique dans la mesure du possible.
2) Minimisez le nombre de collisions que vous vérifiez pendant chaque 'frame'.
3) S’il y a de trop de collisions à vérifier au cours des 'frames', essayez de mettre en œuvre une stratégie type "diviser pour régner", afin que le nombre de tests à effectuer, soit au minimum possible. >>


-------------------------
Caché:
Point In Polygon Function
& Polygon In Polygon Function


This function detects when a point is on the inside of a user-defined polygon. Since the number of sides of the polygon can be huge, you have a great deal of freedom in creating polygons of just about any shape and size.

Up until now, the most we’ve had to deal with is four points as in “Point In Rectangle”. This next function can process a minimum of three points and a practical maximum of 500 points! It’s obvious that we’ll need to come up with a logical procedure for dealing with the entire range of possibilities.

This means that we’ll need to store and access every single pair of coordinates that define the polygon, so naturally we’ll have to resort to using an array to store all those coordinates. Another implication is that we’ll need to either store those coordinates in data statements or read them in from a disk file to fill all the elements of the array. Don’t worry it’s all been taken care of, but we’ll need to discuss how it’s all laid out so you can use this function in your own programs.

First things first, we must define what a polygon is and is not. Here’s our definition of a polygon:

A polygon is a collection of any three or more non-collinear points.

Which means you can have points that are collinear as long as at least three of the points that define the polygon are not collinear.

This is definitely a case where a picture is worth at least a thousand words. As illustrated in the figure 1 below, you can create an infinite variety of shapes that meet the requirements of the polygon definition stated above.



figure 1

The one thing that you’ll want to keep in mind is that the more points required to define the polygon, the more time it will take your computer to display and/or check the polygon. If you only need to display or check one polygon with a large number of vertices (i.e. the point where two sides converge), you shouldn’t notice a significant slow down. However, if you have several polygons with a high number of vertices or hundreds of polygons with a low number of vertices displayed at the same time, you will notice a significant slow down when checking for collisions.

Now that we have the definition for a polygon, we’ll need to consider how to utilize an array to store the X-Y coordinate pairs defining a polygon.

Let’s start by defining the information required to describe the polygon.

1) The number of vertices used to define the polygon. This will allow us to use For…Next loops to iterate through the vertices defining the polygon.

2) The amount of offset in the X and Y directions for the upper-left bounding box corner of the polygon, so that we can locate the polygon anywhere on the screen the same as we do with sprites.

3) The bounding box’s upper-left corner and the width and height of the bounding box which will allow us to quickly check for collision events even when sprites are not used.

4) The list of X-Y coordinate pairs locating the vertices of the polygon.

In all of the example code I use an array named “poly()”. In describing the details of the polygon storage we’ll use the same array name.

To help understand the logic used to populate the poly() array, I refer you to figure 2, which shows all of the required information to define a polygon. In this case the polygon is a triangle to keep things simple.



figure 2

1) The number of vertices defining the polygon = 3
2) The X & Y offsets default to 0,0 (you will locate the polygon in your program as necessary)
3) The bounding box width is 11 – 0 + 1 = 12 (pixels 0 – 11 inclusive)
The bounding box height is 10 – 0 + 1 = 11 (pixels 0 – 10 inclusive)
4) The list of coordinate pairs are: 0,0 11,10 0,10 (3 pairs of coordinates = 3 vertices)

Note: all polygon bounding box upper-left corners are located at 0,0 when they are initially defined so that we can later place them anywhere on screen just as we do with sprites in JB. Please keep this in mind when laying out a polygon in your own program.

If you choose not to do so, you will have to hard code the location of your polygon yourself.

The first array dimension will hold the “index” number of the polygon. This will allow you to access any polygon by index number.

Since JB only allows two-dimensional arrays, we will lay out the polygon information as follows:

Index number = 1 ‘since it’s the first polygon defined
poly(1, 0) = 3 ‘number of vertices
poly(1, 1) = 0 ‘X offset The actual X offset will be determined in your program
poly(1, 2) = 0 ‘Y offset The actual Y offset will be determined in your program
poly(1, 3) = 12 ‘The bounding box is 12 pixels wide
poly(1, 4) = 11 ‘The bounding box is 11 pixels tall
poly(1, 5) = 6 ‘The X coordinate for vertex 1
poly(1, 6) = 0 ‘The Y coordinate for vertex 1
poly(1, 7) = 11 ‘The X coordinate for vertex 2
poly(1, 8) = 10 ‘The Y coordinate for vertex 2
poly(1, 9) = 0 ‘The X coordinate for vertex 3
poly(1, 10) = 10 ‘The Y coordinate for vertex 3

Note - the total array space required to store a polygon is determined by the following formula:

Number of vertices * 2 + 4 = highest array element required in second dimension

So we would need to DIM the poly() array as …‘DIM poly(1,10)’ (1 polygon, 3 vertices * 2 + 4 = 10) for the example polygon shown in figure 2.

With 20 polygons, and the largest of the 20 polygons having 28 vertices you would need to DIM the poly() array as …’DIM poly(20, 60) (20 polygons, 28 vertices * 2 + 4 = 60).

Here’s the code snippet that loads the polygon data from the example above into the poly() array.


Dim poly(1,10)
numPolys = 1

...

Restore [polygonData]

For i = 1 To numPolys
Read numVerts, locX, locY, wide, high
poly(i,0) = numVerts
poly(i,1) = locX
poly(i,2) = locY
poly(i,3) = wide
poly(i,4) = high
For j = 5 To numVerts*2 + 3 Step 2
Read x, y
poly(i, j) = x
poly(i,j+1) = y
Next j
Next I


[polygonData]
Data 3 ‘number of vertices
Data 0, 0 ‘locX, locY ‘use just like you would SpriteXY
Data 12 ‘bounding box width
Data 11 ‘bounding box height
Data 6,0, 11,10, 0,10 ‘the 3 vertex coordinate pairs


That’s all there is to placing the vertices in the poly() array. Obviously you wouldn’t want to have to enter all of the polygon vertices by hand as that would become extremely tedious and prone to error. So I’ve written a very simple “Polygon Editor” (see “Polygon Editor.bas”;).

That sums up the way we’re going to store the polygon information in the poly() array. At long last we’re ready to implement the “Point In Polygon” function.


Code VB :
Function pnp(idx, x, y)
'===============================================================
'  Function “Point In Polygon”
'===============================================================
' This function checks to see if a point is inside the polygon indicated by ‘idx’.
' If the point IS inside the polygon a value of 1 is returned.
' If the point IS NOT inside the polygon a value of 0 (zero) is returned.
'===============================================================
' idx – is the index of the polygon coordinates to check
' x, y are the coordinates being checked (in or out of polygon)
'===============================================================
    'lastX is the last X coordinate defining current polygon
    lastX = poly(idx, 0) * 2 + 3     'lastY = poly(idx, 0) * 2 + 4
    'assign X-offset to 'oX
    oX = poly(idx,1)
    'assign X-offset to 'oY
    oY = poly(idx,2)
    'loop through all of the points defining current polygon

    For i = 5 To lastX Step 2
        If i = lastX Then j = 5 Else j = (i+2)
        v1 = (poly(idx, i + 1) + oY) <= y
        v2 = y < (poly(idx, j + 1) + oY)
        v3 = (poly(idx, j + 1) + oY) <= y
        v4 = y < (poly(idx, i + 1) + oY)
        v5 = (( (poly(idx,j   ) + oX)) - (poly(idx, i)+oX)) * (y - (poly(idx, i + 1) + oY))
        v6 = ((poly(idx,j + 1) + oY)) - (poly(idx, i + 1)+oY)
        If v6 = 0.0 then v6 = 0.0001
        v7 = poly(idx, i) + oX
        If (((v1 And v2)) Or (v3 And v4)) And (x < v5 / v6 + v7)) Then pnp = 1 - pnp
    Next i
 
End Function


For a working example of the “Point In Polygon” function run “Point In Polygon.bas”

I’m going to digress slightly by showing you two supporting routines that we may or may not use, but nice to have in our toolbox just the same.

One of those routines is a SUB to draw the polygon on screen. This could be used as a stand-alone graphic routine or as tool to visually debug a program that uses polygons in collision detection.


Code VB :
Sub drawPoly  h$, index
'===============================================================
'  Function “Draw A Polygon”
'===============================================================
' This function draws the polygon indicated by ‘index’
'===============================================================
' h$ is the string representing the graphics handle used in your program
' index – indicates which polygon will be drawn on screen
'===============================================================

          lastX  = poly(index,0) * 2 + 3     ‘lastY would be poly(index, 0) * 2 + 4
          oX = poly(index, 1)           ‘offset X value allows place anywhere on screen
          oY = poly(index, 2)          ‘offset Y value allows place anywhere on screen
          #h$ “Place “;poly(index, 5)+oX;” “;poly(index, 6)+oY
 
          For i = 7 To  lastX Step 2
                   #h$ “Goto “;poly(index, i)+oX;” “;poly(index, i + 1)+oY
          Next I
 
          #h$ “Goto “;poly(index,5)+oX;” “;poly(index, 6)+oY
 
End Sub


Another useful routine would be a SUB for moving a polygon to a new location on screen in much the same way the JB “SpriteXY” command locates sprites.

Code VB :
Sub movePoly index, x, y
'===============================================================
'  Function “Move A Polygon”
'===============================================================
' This function changes the location of where a polygon will be drawn or used on screen.
'===============================================================
' index – indicates which of the polygons move
' x, y are the new coordinates where the polygon will be moved
'===============================================================

          poly(index, 1) = x
          poly(index, 2) = y
 
End Sub


Ok, with that out of the way, let’s get back on track.

Now that it’s understood how the “Point In Polygon” function works using the poly() array to store the vertex coordinates, we’re going to extend it’s usefulness by cycling through the coordinates of a small polygon and use the “Point In Polygon” (hereafter referred to as PNP) function to see if it is inside of another (larger) polygon. The result is that we’ll have a “Polygon To Polygon” (hereafter referred to as P2P) collision detection function.

The main drawback to the P2P function is that if we exceed a certain number of comparisons per frame of graphics display, we will encounter a slight to significant slow down. What that threshold is will depend on the speed of your CPU and graphics subsystem. It is suggested that you work with a conservative number of vertices and/or comparisons to ensure that a large portion of your intended audience is able to use this type of collision detection code with out noticeable or significant slow down. Another strategy is to use the “Rectangle To Rectangle” collision function to see if the bounding boxes of the two polygons have collided. It’s a very fast function reducing the area of the screen you’ll need to check. If there is a collision, you can then check for a collision using the more computationally intensive P2P function. Utilizing both strategies in tandem will give you the best performance.


Code VB :
Function p2p(index1, index2)
'===============================================================
'  Function “Polygon To Polygon” collision
'===============================================================
' This function checks to see if polygon1 has collided with polygon2.
' Typical usage is to check a polygon with a small number of vertices against a
' polygon with the same or larger number of vertices.
' If the polygons have collided a value of 1 is returned.
' If the polygons have not collided a value of 0 (zero) is returned.
'      ***** Note: This function is dependent upon Point In Polygon Function *****
'===============================================================
' index1 – indicates the first polygon to use for collision checking
' index2 – indicates the second polygon to use for collision checking '===============================================================

          numVerts = poly(index1, 0)        'number of vertices in polygon (index1)
          oX = poly(index1, 1)                  'current X-coordinate offset of polygon (index1)
          oY = poly(index1, 2)                  'current Y-coordinate offset of polygon (index1)

          For i = 5 To numVerts * 2 + 3 Step 2
              p2p = pnp(poly(index1, i) + oX, poly(index1, i+1) + oY, index2)
              If p2p = 1 Then Exit For    'If a vertex is inside polygon (index2) then exit from For…Next loop
          Next i
 
End Function


The whole reason this tutorial came into being is because of a question asked on the JustBASIC forum (URL – http://justbasic.conforums.com/index.cgi?board=code&action=display&num=1240653153 ). Here’s a paraphrased version of the question: “How do I allow my character sprite to cross a bridge spanning a meandering river and still keep my character sprite from entering the river?” I refer to this question as “flaxen’s dilemma”. (see figure 3 below)


figure 3

This is a perfect situation to utilize some of the collision techniques we’ve studied; “Rectangle To Rectangle” (R2R), “Point In Polygon” (PNP), and “Polygon To Polygon” (P2P). We just need to make a few preparations before we start coding the solution to “flaxen’s dilemma”.

First of all, using the “Polygon Editor”, we’ll trace the character sprite with a polygon that keeps the character sprite from entering the river, and trace both the left and the right sides of the river with polygon boundaries that the character sprite polygon will not cross.

After tracing the polygons and pressing the “Save Data” for each of the polygon’s, we need to DIM the poly() array and allot enough memory to store all three polygons.

Then we’ll need to read the data statements to load the polygon vertices into the poly() array.

Lastly, let’s copy and paste the functions necessary to complete the task.

Well, that wraps up this collision tutorial. Here are three tips that summarize the use of these collision functions in your own programs.

1) Do all of your calculations outside of the graphics rendering loop whenever possible.
2) Minimize the number of collisions you check during each frame of graphics.
3) If there are many collisions to check during each frame of graphics, try to implement a divide and conquer strategy to keep the number of collision checks to a minimum.




Edité par joan74 Le 01/06/2020 à 18h13
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 28/04/2020 à 14h13

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Fonction de collision Ellipse avec Rectangle

Code VB :
Function e2r(boxX, boxY, boxW, boxH, cx, cy, ew, eh)
'=====================================================================
' Fonction de collision : “Ellipse Avec Rectangle”
' Cette fonction vérifie si une ellipse est en collision avec un rectangle
'=====================================================================
' boxX, boxY sont les coords du coin supérieur-gauche du rectangle
' boxW, boxH sont la Largeur et la Hauteur du rectangle
'
' cx, cy sont les coordonnées du centre de l’ellipse
' ew est la largeur de l’ellipse /along the X-Axis
' eh est la hauteur de l’ellipse /along the Y-Axis
'=====================================================================
' e2r renvoie 1 si l’ellipse est en collision avec le rectangle
' e2r renvoie 0 (zéro) si aucune collision n’est détectée
'=====================================================================
    rx = ew/2 : ry = eh/2
    chkX = cx : chkY = cy
    If chkX < boxX Then chkX = boxX
    If chkX > (boxX+boxW) Then chkX = boxX + boxW
    If chkY < boxY Then chkY = boxY
    If chkY > (boxY+boxH) Then chkY = boxY + boxH
    e2r = ((chkX-cx)*(chkX-cx)/(rx*rx)+(chkY-cy)*(chkY-cy)/(ry*ry)<1)
End Function


Caché:
NDT : aucun commentaire dans le fichier original.




Edité par joan74 Le 23/05/2020 à 10h25
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 28/04/2020 à 14h14

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Fonction de collision Cercle avec Rectangle

Code VB :
Function c2r(boxX, boxY, boxW, boxH, cx, cy, cr)
'=====================================================================
' Fonction de collision : « Cercle Avec Rectangle »
' Cette fonction vérifie si un cercle est en collision avec un rectangle
'=====================================================================
' boxX, boxY sont les coords du coin supérieur-gauche du rectangle
' boxW, boxH sont la Largeur et la Hauteur du rectangle
' cx, cy sont les coordonnées du centre du cercle
' cr est le rayon du cercle
'=====================================================================
' c2r renvoie 1 si le cercle est en collision avec le rectangle
' c2r renvoie 0 (zéro) si aucune collision n’est détectée
'=====================================================================
    chkX = cx
    chkY = cy
    If chkX < boxX Then chkX = boxX
    If chkX > (boxX+boxW) Then chkX = boxX + boxW
    If chkY < boxY Then chkY = boxY
    If chkY > (boxY+boxH) Then chkY = boxY + boxH
    c2r = ((chkX-cx)*(chkX-cx)+(chkY-cy)*(chkY-cy)) < cr * cr
End Function


Caché:
NDT : aucun commentaire dans le fichier original.




Edité par joan74 Le 23/05/2020 à 10h25
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 28/04/2020 à 14h14

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Fonction de collision Cercle avec Triangle

[NDT] Cette fonction vérifie si un cercle est en collision avec un triangle.

Je me suis permis d'ajouter un test supplémentaire à la fonction cnt() par rapport à la V.O.,
pour les cas où, le cercle se trouverait complètement à l'intérieur du triangle (sans qu'il ne touche aucun des cotés).[/NDT]

Code VB :
Function c2t(x1, y1, x2, y2, x3, y3, cx, cy, cr)
'=====================================================================
' Fonction de collision : « Cercle Avec Triangle »
' Cette fonction vérifie si un cercle est en collision avec un triangle
'=====================================================================
' x1, y1, x2, y2, x3, y3 sont les paires de coordonnées du triangle
' cx, cy sont les coordonnées du centre du cercle
' cr est le rayon du cercle 
'=====================================================================
' c2t renvoie 1 si le cercle est en collision avec le triangle
' c2t renvoie 0 (zéro) si aucune collision n’est détectée
'=====================================================================
'    *** Note: Cette fonction nécessite également la fonction c2L() "Cercle Avec Ligne" ***
'    *** Note: Cette fonction nécessite également la fonction pnt() "Point Dans Triangle" ***
'=====================================================================
    c2t = 0
    if pnt(cx,cy,x1,y1,x2,y2,x3,y3) Then c2t=1 : Exit Function
    If c2L(x1,y1,x2,y2,cx,cy,cr) Then c2t=1 : Exit Function
    If c2L(x2,y2,x3,y3,cx,cy,cr) Then c2t=1 : Exit Function
    If c2L(x3,y3,x1,y1,cx,cy,cr) Then c2t=1 : Exit Function
End Function


Caché:
NDT : aucun commentaire dans le fichier original.




Edité par joan74 Le 23/05/2020 à 10h26
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 06/05/2020 à 17h53

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Sa y est, j'ai tout traduit !
Si quelqu'un pouvait relire ma prose et faire un retour (erreur de compréhension, fautes, etc)

p.s. c'est la premiere fois que je traduis quelque chose...



Edité par joan74 Le 06/05/2020 à 18h47
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 06/05/2020 à 18h44

Administrateur

Groupe: Administrateur

Inscrit le: 04/03/2012
Messages: 2200
joan74:
Slt,

Sa y est, j'ai tout traduit !
Si quelqu'un pouvait relire ma prose et faire un retour (erreur de compréhension, fautes, etc)

p.s. c'est la premiere fois que je traduis quelque chose...


Pour l'orthographe c'est Parfait et pour la traduction c'est assez clair.
19/20 (il manque 1 point d'humour :party )
____________________
Roro

   
Le 06/05/2020 à 19h58

Modérateur

Groupe: Modérateur

Inscrit le: 09/02/2015
Messages: 601
Pour la relecture, je vais m'y coller moi aussi, dans les jours qui viennent. J'ai vu deux-trois petites choses qui pourraient être remaniées, mais c'est au niveau du détail, car globalement c'est bon.

Peut-être faudrait-il aussi traduire les commentaires dans les programmes, ce serait plus parlant parce qu'on les a sous les yeux dans l'éditeur JB/LB, et ce serait plus simple que la traduction de paragraphes plus ou moins abscons.

Merci du boulot, en tout cas.
____________________
Just BASIC v2.0 :
  • utilisation courante avec GNU/Linux Mageia6 + Wine (Pas trouvé d'incohérences ou de bug de compilation à ce jour)
  • utilisation occasionnelle ou vérification/débugage difficile avec Windows XP sur un petit eeepc

   
Le 07/05/2020 à 09h18

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
Roland:
il manque 1 point d'humour :party

... pas beaucoup d'humour, mais j'y ai mis beaucoup d'amour :love :love :love !

@Christophe
Au départ j'ai voulu rester le plus fidèle possible au texte original, d'où la lourdeur de certain passage...
Mais au final j'ai reformulé au max que j'ai pu pour que celà soit plus clair...
j'attend ton retour avec impatience

...pour les trad des commentaires/codes je prends note ;)
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   
Le 23/05/2020 à 11h25

Libertynaute

Groupe: Membre

Inscrit le: 17/12/2010
Messages: 95
je pense que c'est bon maintenant ...

J'ai traduit les commentaires des codes, rajouté/modifié des images, fais une énieme relecture et à nouveau reformulé certains passages (encore^^)
Remplacer l'archive original par une VF (avec fichiers réorganisés également).

Maintenant je passe à autre chose^^
mais si vous trouvez des erreurs ou avez des suggestions n'hésitez pas. Je repasserai à l'occasion

@++



Edité par joan74 Le 23/05/2020 à 12h08
____________________
"L'urgent c'est fait ! L'impossible est en cours... pour les miracles, merci de prévoir un délai supplémentaire !"

   

 |  |

1 Utilisateur en ligne : 0 Administrateur, 0 Modérateur, 0 Membre et 1 Visiteur
Utilisateur en ligne : Aucun membre connecté
Répondre
Vous n'êtes pas autorisé à écrire dans cette catégorie