Billard et files de priorité

INF411 · TD7

 Login :  Mot de passe :

Exprimez-vous

1 Introduction

Ce sujet aborde le problème de la simulation de billes de billard. On étudie ici un modèle simplifié : billes dures, chocs élastiques (sans perte d’énergie), pas de friction avec le tapis. Entre deux chocs, les billes ont donc un mouvement rectiligne uniforme. Mais il faut détecter et traiter les chocs.

Une approche classique (et quasiment universelle) consiste à discrétiser le temps. Mais les contraintes discontinues (deux billes ne peuvent s’interpénétrer) sont difficiles à implémenter dans une telle approche.

Ici, les trajectoires des billes sont très simples. On peut donc précalculer les collisions à venir, les traiter par ordre de temporalité et mettre à jour, à chaque collision, la liste des collisions à venir. L’utilisation d’une file de priorité permet d’implémenter efficacement cette approche.

Pour commencer:

1.1 Les billes

class Ball {
    double x, y;   // position
    double vx, vy; // vitesse
    double radius; // rayon
    double mass;   // masse
    
    void forward(double t) {
        x += vx * t;
        y += vy * t;
    }
    
    void collideBall(Ball other) {
        // compliqué
    }
    
    void collideWall(Direction dir) {
        if (dir == Direction.Horizontal)
            vy = -vy;
        else
            vx = -vx;
    } 

    double nextBallCollision(Ball other)
    double nextWallCollision(Direction dir)
    
    int nbCollisions()
}

Une bille est représentée par une instance de la class Ball. Diverses méthodes permettent de manipuler la vitesse et la position d’une bille, ainsi que de prévoir les collisions.

void forward(double t)
Met à jour la position de la bille, en supposant un mouvement rectiligne uniforme pendant un temps t.
Effet de forward
void collideBall(Ball other)
Met à jour les vitesses de this et other de manière à refléter une collision entre les deux. Laisse les positions inchangées. Incrémente le compteur de collisions de this et other.
Effet de collideBall
void collideWall(Direction dir)
L’argument dir peut être Direction.Horizontal ou Direction.Vertical. Met à jour la vitesse de this de manière à refléter une collision sur une bande, horizontale ou verticale, selon la valeur de dir. Incrémente le compteur de collisions de this.
Effet de collideWall
double nextBallCollision(Ball other)
Renvoie l’instant de la prochaine collision entre this et other, en supposant des mouvements rectilignes uniformes. Le résultat est relatif à l’instant présent. Une valeur négative est renvoyée si aucune collision n’adviendra.
double nextWallCollision(Direction dir)
Renvoie l’instant de la prochaine collision entre this et l’une des deux bandes dont la direction est dir. Spécification similaire à nextBallCollision.
int nbCollisions()
Renvoie le nombre de collisions subies par this depuis sa création.

On ne touchera pas à cette classe (mais vous pouvez jeter un œil au code).

1.2 Le billard

class Billiard {
    Vector<Ball> balls;
    double currentTime;
    PriorityQueue<Event> eventQueue;
}

NB: “Billard” en français, “billiard” en anglais.

Un billard est représenté par un tableau redimensionnable balls contenant les billes, un champ currentTime contenant l’instant présent et une file de priorité eventQueue contenant les évènements prévus.

// Exemple d'itération
for(Ball b : balls) {
    faitQuelqueChose(b);
}

Rappelons que la syntaxe for(E x : collection) permet d’itérer sur une collection d’objets.

La classe GraphicalBilliard utilise ce que vous écrirez dans Billiard pour lancer des animations rien moins que spectaculaires, avec des configurations initiales variées et amusantes.

1.3 Les évènements

class Event implements Comparable<Event> {
    final double time;
    final Billiard billiard;
    
    public int compareTo(Event e);
    
    boolean isValid();
    void process();
}

Un évènement est une opération que l’on prévoit d’effectuer à un moment précis dans le futur. Voici quelques exemples:

Du point de vue de l’implémentation, les évènements sont les instances de la classe Event. Ils ont un champ time qui représente l’instant auquel se produira l’évènement et un champ billiard qui pointe vers le billard concerné par l’évènement.

Il se peut qu’un évènement prévu soit caduc au moment où il doit se réaliser. Par exemple, si l’on prévoit une collision entre deux billes A et B au temps t mais que A a changé de trajectoire (à cause d’une autre) collision avant le temps t, l’évènement correspondant est caduc.

int compareTo(Event e)
Méthode utilisée pour trier les évènements par ordre d’apparition.
boolean isValid()
Renvoie false si et seulement si l’évènement this est caduc.
void process()
Applique l’effet de l’évènement.

1.4 Un exemple

Regardons sur un exemple ce qu’on cherche à simuler. On part d’une configuration initiale à trois billes. On prévoit des collisions (colonne de droite). Il y a des doublons (par exemple jaune-orange et orange-jaune), mais peu importe.

Position initiale

À chaque étape de la simulation:

Collision n° 1
Collision n° 2
Collision n° 3
Collision n° 4

2 Programmation du billard

2.1 La boucle d’évènements

// Extrait de l'interface de PriorityQueue
class PriorityQueue<E> {
    boolean add(E e);  // ajoute un élément à la file
    E poll(); // retire et renvoie le plus petit élément
}

Le rôle d’eventLoop consiste à traiter les évèvements de eventQueue par ordre chronologique et à positionner les billes correctement avant chaque évèvement, en supposant un mouvement rectiligne uniforme.

Si l’évènement à traiter e n’est pas caduc, on déplace les billes pour les mettre dans la configuration du temps e.time (utiliser forward), on met à jour currentTime, puis on exécute l’évènement (avec e.process()). Les évènements caducs n’ont aucun effet.

class Billiard {
    ...
    void eventLoop() { /* TODO */ }
}

Écrire la méthode eventLoop. Tester avec TestEventLoop.

Déposer Billiard.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Vous pouvez déjà essayer GraphicalBilliard, mais les collisions ne sont pas encore prises en compte. Cette classe utilise votre boucle d’évènements pour afficher à intervalles réguliers la configuration du billard.

2.2 Prédiction des collisions

La méthode predictCollisions(Ball b) de la classe Billiard ajoute à la file des évènements eventQueue toutes les collisions (bille-bille ou bille-bande) susceptibles de concerner la bille b.

On peut prévoir l’heure d’une collision éventuelle entre une bille b et une autre bille c avec currentTime + b.nextBallCollision(c). On crée l’évènement correspondant avec new BallCollisionEvent(this, time, b, c), où time est le moment calculé précedemment.

On peut prévoir l’heure d’une collision éventuelle entre une bille b et une bande de direction dir avec currentTime + b.nextWallCollision(dir). On crée l’évènement correspondant avec new WallCollisionEvent(this, time, b, dir), où time est le moment calculé précedemment.

class Billiard {
    ...
    void predictCollisions(Ball b) { /* TODO */ }
    void initialize() { /* TODO */ }
    void run () {
        initialize();
        evenLoop();
    }
}

Écrire la méthode predictCollisions.

La méthode initialize ajoute à la file des évènements toutes les collisions susceptibles d’arriver. Elle est appelée au début de la simulation.

Écrire la méthode initialize. Tester avec TestPredictCollisions.

Déposer Billiard.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

La simulation est lancée en appelant initialize et eventLoop. Mais les collisions ne sont toujours pas calculées correctement : il manque encore le code dans BallCollisionEvent et WallCollisionEvent.

3 Programmation des évènements

class MyNewEvent extends Event {
    @Override boolean isValid() { ... }
    @Override void process() { ... }
}

La boucle des évènements ne fait que déplacer les billes selon un mouvement rectiligne uniforme. Tout le reste est géré par les évènements.

Les évènements ont des natures différentes : un évènement qui déclenche une actualisation de l’image à l’écran n’est pas de la même nature qu’un évènement qui traite une collision entre deux billes. En particulier, les méthode isValid et process ne peuvent pas être les mêmes pour tous les évènements.

Pour programmer un nouveau type d’évènement MyNewEvent, on déclare une classe qui hérite de la classe Event. Puis on implémente les méthodes isValid et process propres au type d’évènement. Le mot-clé @Override indique qu’on remplace le comportement par défaut de Event (qui ne fait rien d’intéressant).

Partout où l’on peut mettre une instance de Event, on peut aussi mettre une instance de MyNewEvent. Cela permet à la file des évènements de contenir des évènements de nature différentes.

3.1 Collision avec une bande

class WallCollisionEvent extends Event {
    // Les champs suivants sont hérités de Event:
    // Billiard billiard;
    // final double time;
    
    Direction direction;
    Ball ball;
    int nbCollisions;
    
    WallCollisionEvent(Billiard billiard,
            double time, Ball ball,
            Direction direction) {
        super(billiard, time);
        this.ball = ball;
        this.direction = direction;
        this.nbCollisions = ball.nbCollisions();
    }
    
    @Override
    boolean isValid() { /* TODO */ }
    
    @Override
    void process() { /* TODO */ }
}

WallCollisionEvent est la classe d’évènements qui traite les collisions d’une bille avec une bande. Pour programmer process, on s’appuiera sur la méthode collideWall de la classe Ball.

Le constructeur de WallCollisionEvent prend comme arguments billiard, time (l’instant de l’évènement), ball (la bille concernée par l’évènement) et direction (l’orientation de la bande concernée). Il passe les arguments billiard et time au constructeur de la classe parent grâce au mot-clé super.

Pour savoir si l’évènement est caduc, il faut savoir si la bille ball a subi une collision depuis la création de l’évènement. La méthode ball.nbCollisions() permet de connaître le nombre total de collision subies par une bille. On enregistre sa valeur dans le constructeur, c’est-à-dire à la création de l’évènement.

Écrire les méthodes isValid et process de la classe WallCollisionEvent. On n’oubliera pas mettre à jour la file des évènements.

Tester avec TestWallCollisionEvent.

Déposer WallCollisionEvent.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

On peut lancer GraphicalBilliard.main, les billes ne sortent plus de l’écran!

3.2 Collision entre deux billes


class BallCollisionEvent extends Event {
    // TODO
    
    BallCollisionEvent(Billiard billard, 
            double time, Ball a, Ball b) {
        super(billiard, time);
        // TODO
    }
        
    @Override
    boolean isValid() { /* TODO */ }
    
    @Override
    void process() { /* TODO */ }
}

De manière analogue, compléter le constructeur et écrire les méthodes isValid et process de la classe BallCollisionEvent.

Tester avec TestBallCollisionEvent.

Déposer BallCollisionEvent.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

GraphicalBilliard est maintenant fonctionnel ! Changez de conditions initiales en décommentant telle ou telle ligne dans GraphicalBilliard.main. Voir le constructeur Billiard(String path) pour la définition du format de fichier accepté.

 


Référence: Algorithms, R. Sedgewick et K. Wayne, 4th edition, Addison Wesley