Teaching - 2i013

Enseignants


2i013 - Groupe 5 : Course de voiture

TME 4

Radar, Stratégie Radar et simulateur de référence

Le but de cette séance est une mise à niveau générale du groupe. Tout le monde doit avoir bouclé l'ensemble du TME 3 à la fin de la séance:

TME 3

Bilan avancement

Tous les éléments de bases (voiture, circuit et factories) doivent être opérationnels au début du TME. Cette séance doit permettre à tous les groupes de soumettre leurs courses premières courses sur le serveur. Vous devez donc avoir développé les éléments suivants (cf TME 3):

  • Radar (interface)
  • RadarClassique (implémentation)
  • StrategyRadar
  • Simulation (pour jouer une course)
  • Gestion des sauvegardes de liste de commandes

Dijkstra

Pour ceux qui avancent bien, voici tout de même la suite!

Rappel:

Définition de l'infini en JAVA:

 Double.POSITIVE_INFINITY

Commencer par les outils de base

Rappel: dans l'algorithme de Dijkstra, nous avons besoin de trouver la case (non encore traitée) qui se trouve le plus près du but.

  1. il existe des outils automatiques en java pour trier des listes, extraire des minima ou des maxima...
  2. nous devons trouver le minimum dans une liste de coordonnées (i,j)
  3. la liste n'est pas directement triable, l'information utile pour le tri dépend d'un autre tableau: la distance à l'arrivée
  4. la solution consiste à construire un Comparator connaissant la ressource externe et capable de dire quel couple (i,j) est inférieur ou supérieur à quel autre couple.

Outil de comparaison de deux cases repérées par leur coordonnées stockées dans des Vecteurs:

 public class ComparatorDijk implements Comparator<Vecteur> {
        private double[][] dist;

        public ComparatorDijk(double[][] dist) {        this.dist = dist;       }
        public int compare( Vecteur o1,  Vecteur o2) {
                if(dist[(int) o1.getX()][(int) o1.getY()]>dist[(int) o2.getX()][(int) o2.getY()])
                        return 1;
                else if (dist[(int) o1.getX()][(int) o1.getY()]==dist[(int) o2.getX()][(int) o2.getY()])
                        return 0;
                return -1;
        }
 }

Une fois que vous disposez de cet outil, vous pouvez instancier:

  • soit une PriorityBlockingQueue (cf javadoc)
  • soit une ArrayList, en utilisant ensuite la méthode static Collections.sort (cf javadoc)

Diviser l'algorithme en sous parties pour un codage plus simple

Constructeur

  • contient la création et l'initialisation du tableau de distance
  • initialisation de l'ArrayList ou du tas Q

Algorithme

  • Tant qu'il reste des points dans Q
    • Extraire le point le plus proche de l'arrivée
    • Trouver les voisins & MAJ -> dans une autre méthode

Trouver les voisins & MAJ

  • Autour du point (i,j)
  • Boucle: pour di allant de -1 à 1 et dj allant de -1 à 1
    • Eliminer les indices inintéressants (continue)
    • Eliminer les mauvais voisins
    • Calculer la nouvelle distance et comparer avec la distance existante

Attention: dans le cas où vous utilisez un tas, si vous modifiez la distance d'un point à l'arrivée, toute la structure du tas devient bancale. Pour éviter les problèmes, on sort le point du tas et on le réinsert après avoir mis à jour la matrice dits.

  • cas 1: voisin à l'infini
    • 1) mettre à jour sa distance, 2) ajouter dans Q (NB: la distance doit être mise à jour avant l'ajout
  • cas 2: voisin déjà dans Q mais proposition d'un meilleur score
    • 1) retrait de Q, 2) mettre à jour sa distance, 3) ajouter dans Q (le point ira à la bonne place grace à la nouvelle valeur de distance

Vérification du bon fonctionnement

Construire une image représentant les distances à l'arrivée afin de valider votre implémentation de l'algorithme. Tester également dijkstra sur plusieurs circuits de tailles différentes pour vérifier la robustesse de l'implémentation.

Pour construire une couleur représentative de la distance à l'arrivée (et ainsi vérifier le bon fonctionnement de votre classe), il existe deux approche:

Solution 1: on fait un dégradé sur une couleur (le rouge dans l'exemple ci-dessous) qui se réinitialise tout les 256 coups. La dessin final sera rayé, le coté noir des bandes est proche de l'arrivée, le coté rouge plus loin

 // couleur du pixel (i,j)
 new Color((int) track.getDist(i, j)%255, 0 , 0)

Solution 2: on normalise la couleur par rapport à la distance maximum (dMax). Le terrain est alors coloré avec un seul dégradé: noir sur la ligne d'arrivée, rouge vif sur les points les plus éloignés

 // couleur du pixel (i,j)
 // il faut avoir trouvé dMax au préalable
 new Color((int) track.getDist(i, j)*255/dMax, 0 , 0)

Pour que la coloration soit plus parlante, il est utile de ne colorier que les pixels sur lesquels il est possible de rouler (ne pas colorier l'herbe ou les obstacles)

Construction du radar et de la stratégie Dijkstra

Construire un nouveau radar implémentant l'interface précédemment définie: la même stratégie devrait pouvoir utiliser un radar classique ou dijkstra.

NB il suffit de faire en sorte que le meilleur faisceau renvoie le score le plus haut.