Discussion :

[NiklosKoda]

Tout d'abord bonjour à tous.

Je programme actuellement un jeu de billard en pascal (Pascal Objet pour être exact, sous Lazarus) mais mon problème n'est pas spécifique à Pascal mais est plutôt d'ordre algorithmique.

Le problème que je rencontre se trouve au niveau de la détection des collisions entre boules et de leur gestion.
Je m'explique : lorsque l'utilisateur joue un coup, un composant appelé "Timer" est activé et se charge d'appeler une fonction toutes les X microsecondes.

C'est cette fonction qui se charge de calculer les nouvelles positions des boules, les nouvelles vitesses et également des collisions.
Pour cela elle dispose d'objets décrivant les boules par les coordonnées de leur centre et du vecteur vitesse de ce dernier dans un repère global lié au tapis.
Les boules sont ensuite dessinées sur le tapis, ce sont de simples cercles, comme sur une vue de haut du billard.

Du fait que les positions soient actualisées toutes les X microsecondes, le mouvement de la boule n'est pas "véritablement continu" : à l'œil nu le mouvement semble parfait, étant donné le faible décalage de pixel à chaque rafraichissement et la fréquence des rafraichissements, mais au niveau de l'ordinateur, la boule prend des positions successives, comme ceci :


Le problème est alors le suivant : lors de déplacements impliquant plusieurs boules, ils arrivent que celles ci se recouvrent, comme ceci :


Et cela pose problème pour gérer correctement la collision (je précise au passage que j'ai toutes les équations nécessaires pour le calcul des nouvelles vitesses, là n'est pas le problème). Voilà ce qui se passe précisément :

• Premier calcul : Les positions des boules sont actualisées et ces dernières sont détectées comme étant en collision.
  Les vitesses sont alors recalculées avec les équations qui vont bien et le billard est redessiné.
  
• Second calcul : X microsecondes plus tard la fonction de gestion des boules est appelée une seconde fois et met à jour les positions des boules en tenant compte cette fois ci des vitesses modifiées après choc. Puis, elle recommence le même travail que précedemment, à savoir la détection de collisions. Là est tout le problème : si les vitesses des boules sont assez faibles, il se peut qu'elles soient toujours en recouvrement malgré la mise a jour des positions, ainsi la fonction détècte une collision qui n'a pas lieu d'être, et assigne des vitesses qui sont fausses

Voici un schéma qui résume le tout :



Je cherche donc un moyen de fixer tout cela...
Pour le moment j'ai pensé à déclarer un flag pour chaque paire de boule pouvant entrer en collision, mettre à 1 ce flag lorsqu'il y a collision et le remettre à 0 lorsque les boules ne sont plus en recouvrement (que je peux détecter facilement). Il suffirait ensuite de ne prendre en compte la collision de ces deux boules (celles correspondant au flag) uniquement si le flag est à 0. Qu'en pensez vous, je ne suis qu'à moitié satisfait...

Si quelqu'un avait la gentillesse de m'aider je lui en serais grandement reconnaissant.
Merci d'avance.
++
NiklosKoda.


PS : j'ai oublié de préciser la manière dont je détecte les collisions : pour le moment c'est la manière la plus basique, sans algorithme complexe particulier. Je parcours simplement tous les couples de boules possibles, en évitant les redondances, et je teste si la distance entre les centres des deux boules est inférieure ou égale à la somme des deux rayons.

[pseudocode]

Bonsoir,

Premièrement, félicitation pour la mise en page du post: texte, paragraphe, images...

Deuxièmement, concernant ton problème de recouvrement, il faut trouver la valeur exacte du temps "T" pour lequel les boules sont tangentes. C'est assez facile dans ton cas puisque les déplacements sont linéaires. A partir de là, tu es dans le cas que tu as appelé "collision idéale". Cool.

Si plusieurs boules se recouvrent, tu as 2 options:

- gérer chaque collision indépendamment les unes des autres. Pour chaque collision détectée, tu calcules le temps "T" exact de la collision pour te retrouver dans le cas idéal. Attention, si les collisions sont trop proches les unes des autres, tu risques a nouveau de te retrouver avec des recouvrements (cas d'une boule qui en tape 2 autres en meme temps).

- calculer tous les temps exacts des collisions et prendre le plus petit. Tu t'occupes alors seulement de la première collision idéale, puis tu repars dans ta boucle de simulation, en repartant du temps T de cette collision.


Voila, ce sont les bases pour la conception d'un moteur physique. Pour plus de détails, il y a un tutoriel de Gregory Corgie disponible sur notre site: http://gregorycorgie.developpez.com/tutoriels/physic

[Sepia]

Salut,

Je me joins à pseudocode pour te féliciter : ton post est d'une limpidité quasi magique

Pour ton problème, j'ai vu plusieurs points.

1er point:
tu es obnubilé par ton timer = "comment faire pour que l'on ait une bonne représentation toutes les x secondes ?" mais ton pb n'est pas lié directement au temps (même s'il en dépend). En fait, le découpage temporel fixe te pose un problème ==> garde-le lorsque tu en as besoin et vire-le sinon. Je m'explique. En représentation (topologique) le déplacement de tes billes peut être visualisé toutes les secondes (si pas de collision) mais lorsqu'une collision se produit, cet événement devient prioritaire comme si ton échelle de temps n'était plus bonne ==> passe à une représentation de type "marqueur temporel" dans lequel il y a des événements soit réguliers (toutes les secondes) soit les collisions soit rien (pourquoi tu voudrais dessiner alors que tes boules sont au repos. je parle bien sûr sur l'approche du problème pas sur la facilité de l'implémentation). Si ton système est au repos, tu le dessines pas (heu en fait, il faut le dessiner une fois c'est quand même plus sympa de voir les boules dans un jeu de billard, je reconnais ).

2ième point
on peut utiliser une analogie marrante : les mécanismes de détection de... collision dans les réseaux Ethernet (CSMA/CD). En fait si tu utilises cette approche que l'on peut résumer comme suit "on regarde (= détecte) pendant un certain temps avant de supposer qu'il ne va y avoir une collision".

Dans ton cas je vais me limiter à 2 boules (parce que 1° tu ne nous a pas dit s'il s'agissait de billard français, américain ou de snooker... 2° parce qu'il faut bien qu'il te reste des choses à faire 3° tu ne nous a pas dit si ton billard est rectangulaire ). Les cas sont les suivants:

• Tes 2 boules ne sont pas en collision et sont loin (ie elles ne peuvent pas entrer en collision vu leurs vitesses, leurs taille et leurs directions) avant le prochain calcul : typiquement les 2 boules sont au repos et ne se touchent pas ==> elles se déplacent de façon indépendante
• Tes boules vont entrer en collision avant la prochaine échéance de timer (collision avec recouvrement potentiel) ==> calcule ton heure d'impact (ce qui te semble facile) et relance ton timer à partir de cette position temporelle et tu as résolu tous tes problèmes (puisque tu avais déjà tout le reste).

En fait, c'est la seule approche que j'ai vu pour résoudre un cas complexe : la collision multiple durant le même intervalle. En effet, comment tu calcules que les boules ont eu un impact puis un deuxième avec changement de direction dans un même intervalle. Bien sûr, les puristes pourraient dire que ce cas est théorique (en plus je n'avais que 2 boules donc en mécanique, après une collision, et si on n'a pas d'effet tunnel, les 2 boules ne risquent pas de se toucher de si tôt) et là on voit encore les limites des outils, ici les maths et les . En effet, ton pb est une simulation d'un jeu de billard donc une table avec des bords et donc des coins ==> si tes 2 boules sont dans un coin et que tu frappes la boule la plus au centre directement vers l'autre en faisant un carreau presque parfait, la boule initiale transférer presque toute son énergie à la seconde et ne va plus beaucoup bouger, la seconde boule proche du coin va frapper le coin et va rebondir (très vite) puisque proche du coin et peut revenir frapper la boule initiale avec une vitesse et surtout une direction qui n'a pas de relation directe avec celle de la collision initiale entre les 2 boules ==> les erreurs que tu as mis en évidence avec le schéma "second calcul". Il faut donc que tes collisions soient proches de la réalité et pas de ta simulation si tu veux les représenter correctement ==> à chaque collision (donc collision parfaite), on reinitialise le timer et c'est OK.

Tiens-nous au courant
@+

[NiklosKoda]

Merci grandement à vous deux pour vos réponses !
Couplées à celle d'un autre forum, je pense qu'elles me permettront de résoudre le problème =)

J'ai voulu attendre le week-end pour répondre afin d'avoir le temps de bosser et d'avoir un peu de matière à poster, mais malheureusement je n'ai pas pu m'en occuper. :/
J'essayerai de vous tenir au courant, de toute façon c'est un projet scolaire donc j'ai un délai à respecter.

Pseudocode, merci beaucoup pour ton lien, ça m'a l'air d'être tout à fait ce que je recherche. Je vais donc essayer de recaler les boules au moment exact de la collision pour faire mes calculs. Après, comme le dit Sepia, il faudra traiter le cas complexe des collisions multiples, mais chaque chose en son temps ^^

Sinon Sepia, pour le Timer : il n'est pas tout le temps activé. Comme tu le dis pas besoin de rafraichir l'affichage si rien ne se passe. Donc lorsque toutes les boules ont des vitesses (quasi) nulles, je passe d'un affichage "périodique" à une affichage "événementiel" et la fonction du Timer n'est plus appelée.

Encore une fois merci à vous deux.
Cordialement.
NiklosKoda