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.

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.

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.

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:

• modifier la direction de deux billes au moment d’une collision;
• afficher la configuration actuelle du billard;
• arrêter la simulation.

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.

À chaque étape de la simulation:

• on considère l’instant de la prochaine collision ;
• on déplace les billes en mouvement pour les mettre dans la configuration de l’instant où la collision intervient ;
• on change les vitesses des billes concernées par l’évènement ;
• on met à jour la file des évènements prévus en prévoyant les collisions des billes dont la trajectoire vient de changer ;
• certains évènements deviennent caducs et sont ignorés.

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ènements de eventQueue par ordre chronologique et à positionner les billes correctement avant chaque évènement, 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 sont ignorés.

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

Déposer Billiard.java

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écédemment.

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écédemment.

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

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.

Déposer Billiard.java

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.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.

2

Déposer WallCollisionEvent.java

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 */ }
}

Déposer BallCollisionEvent.java

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é.

4.1 Conservation de l’énergie cinétique (facile)

Les méthodes Ball.collideBall() et Ball.collideWall() devraient conserver l’énergie cinétique, mais il est bon de le vérifier soi-même.

4.2 Réversibilité (facile)

La fichier de configuration initiale init/joule-expansion.txt permet de simuler une détente de Joule–Gay-Lussac, qui est un phénomène irréversible. Toutefois, les équations de la mécanique sont réversibles, il suffit de renverser les vitesses.

4.3 Une file d’évènements moins encombrée (difficile)

De tous les évènements introduits par un appel à la méthode Billiard.predictCollisions, au plus un sera réalisé et tous les autres encombrent la file des évènements. On propose un nouvel évènement BallEventQueueEvent qui contient une file d’évènements concernant une même bille. Elle est utilisée dans la classe FasterBilliard.

4.4 Fusion nucléaire (difficile)

Proposition de solution : TD7.solutions.zip

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