Teaching

LI 230 - Eléments de programmation par objets avec Java

Site de l'ue

Ressources pour les TDs/TMEs

Sokoban

TME SOLO?

TME 7

TME 6 - Modélisation d'un labyrinthe et sa résolution

Dans cette version simple, une case de labyrinthe peut être vide ou occupée par un mur. On utilisera la classe Couple pour représenter une position (x,y), et également une classe File pour gérer les listes de Cases. Voici les spécifications des classes :

  • Classe Couple :
    • variables d'insancte : les entiers x et y
    • constructeurs : un vide et un à deux paramètres
    • Méthodes :
      • getX, getY : accesseurs;
      • méthodes Couple getDroit(), getGauche(), getHaut(), getBas() : renvoie les coordonnées du voisin de droite, gauche, haut, bas;
      • randCouple(int x, int y) : renvoie une position aléatoire comprise entre 0 et x, 0 et y;
  • Classe Labyrinthe :
    • variables d'instance : tab, un tableau de Case, ncol et nrow nombre de colonnes et de lignes;
    • 3 constructeurs : un vide, un qui prend un paramètre et construit un labyrinthe carré de la taille du paramètre et un qui prend deux paramètres, nombre de colonnes et nombre de ligne;
    • Méthodes :
      • randomWall(double ths) : initialise aléatoirement le labyrinthe en plaçant un mur sur une case si un nombre tiré aléatoirement est plus petit que ths
      • get(int x, int y), get(Couple c) : renvoie la case à la position (x,y) ou c
      • copy() : construit une copie du labyrinthe
      • toString() : renvoie une description du labyrinthe
  • Classes Case, CaseMur : quelle est l'hierarchie ? au moins une méthode getPos pour renvoyer la position de la case, une méthode estLibre() renvoyant un booléen, et une variable distance pour stocker des informations.
  • Classe File et Element : on veut modéliser une liste doublement chainée pour faire une file (pile : last in first out, file : first in first out). Chaque élément de la liste est composé d'un objet Element, comportant les variables : next, prev de classe Element et case de classe Case, et les méthodes setNext, getNext, setPrev, getPrev, getCase. La classe File aura au moins les méthodes push, pop, merge (assembler deux listes), size et isEmpty.
  • Coder ces classes-là.
  • Ajouter à la classe Labyrinthe une méthode getVoisins() qui renvoie les 4 voisins de la case dans une file.
  • Ajouter la méthode solveLab(Case c) qui permet d'enregistrer dans la variable distance de chaque case la distance de cette case par rapport à la case passée en paramètre selon l'algo suivant
    1. file contient la case initiale, avec comme distance 0, et la distance de toutes les autres cases est initialisée à -1.
    2. Tant que file n'est pas vide
      1. la case c est dépilée de la file
      2. pour chaque voisin de c, si distance == -1 ou si la distance > (distance de c +1), alors la distance du voisin est fixée à (distance de c+1) et le voisin est placé dans la file; sinon on ne fait rien.

Home

Research?

Teaching

(2014-2015)

Licence

Master

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki