Table des matières

TD 6 : Cartographie martienne (suite)

Gestion des fichiers

Nous allons faire évoluer notre classe gridRepoString pour qu’elle puisse être utilisée pour lire et écrire dans un fichier. L’objectif est que cette classe implémente une deuxième interface GridRepoIO définie ci-dessous.

public interface GridRepoIO {
    Grid load(Reader in) throws IOException;
    void export(Grid grid, Writer ou) throws IOException;
}

1) Modifiez la déclaration de la variable gridRepoString dans la classe EditorView pour que son type soit le suivant :

GridRepoString gridRepoString = new GridRepoString();

2) Ajoutez les méthodes nécessaires dans la classe gridRepoString. Faites en sorte de factoriser les traitements entre les différentes méthodes load et export.

3) Ajoutez les lignes suivantes dans la classe EditorView. Ajoutez les déclarations nécessaires et faites en sorte que le menu soit mis à jour. Testez votre application.

// Load from file
loadItemF.setOnAction(e -> {
    File file = fileChooser.showOpenDialog(stage);
    if (file != null) {
        // Chargement depuis un fichier (sans compression)
    }
});

// Export to file
exportItemF.setOnAction(e -> {
    File file = fileChooser.showSaveDialog(stage);
    if (file != null) {
        // Sauvegarde dans un fichier (sans compression)
    }
});

Création d’une carte vierge

Nous allons ajouter la possibilité de créer une carte vierge d’une certaine taille. Ajoutez les lignes suivantes dans la classe EditorView.

MenuItem newItem = new MenuItem("New map");

// New map
newItem.setOnAction(e -> {
    Form form = new Form(stage, "Size of the map : width x height");
    String[] parts = form.getText().replaceAll("\\s+","").split("x");
    if (parts.length != 2)
        return;
    try {
        int x = Integer.parseInt(parts[0]);
        int y = Integer.parseInt(parts[1]);
        this.grid = gridRepoString.create(x, y);
        updateGrid(grid);
    } catch (NumberFormatException numberFormatException) {
        return;
    }
});

1) Ajoutez la ligne newItem, new SeparatorMenuItem(), dans fileMenu.getItems().addAll(`

2) Implémentez la méthode public Grid create(int width, int height) { } dans la classe GridRepoString et testez votre code. Cette méthode doit créer une nouvelle carte et la remplir avec Entity.GROUND.

3) Pour rendre la manipulation des cartes plus faciles, ajoutez les lignes suivantes dans la méthode createTile de la classe GridView.

ColorAdjust colorAdjust = new ColorAdjust();
colorAdjust.setBrightness(-0.2);
tile.setOnMouseEntered(e -> {
    if (e.isShiftDown()) {
        update(tile, i, j);
    }
    tile.setEffect(colorAdjust);
});
tile.setOnMouseExited(e -> {
    tile.setEffect(null);
});

Vérifions la carte

Maintenant que nous pouvons éditer des cartes complexes, il faut faire attention que toutes les cases soient bien atteignables par notre robot, sinon il ne pourra pas explorer toute la surface martienne.

1) Nous supposerons qu’une case est accessible si le robot peut rouler dessus. Il s’agit de toutes les cases à l’exception des rochers (ROCK et BIGROCK). Ajoutez une méthode ` public boolean isAccessible() dans la classe Entity`.

2) Avant de commencer, nous devons ajouter un nouveau menu à notre application. Ajoutez les lignes suivantes dans la classe EditorView et faites en sorte d’afficher le nouveau menu.

Menu editMenu = new Menu("Edit");
MenuItem connectivityItem = new MenuItem("Check connectivity");
editMenu.getItems().addAll(connectivityItem, marksItem);

connectivityItem.setOnAction(e -> {
    Alert alert = new Alert(Alert.AlertType.INFORMATION);
    alert.setHeaderText(null);
    alert.setContentText("Map may be fully connected ???");
    alert.showAndWait();
});

2) Toutes les cases de la carte sont atteignables s’il existe un chemin entre tous les couples de cases accessibles de la carte. Pour répondre à cette question, il suffit de construire un graphe représentant les cases accessibles et dont les arrêtes sont les chemins entre deux cases. Déterminer si toutes les cases sont atteignables revient à déterminer si le graphe sous-jacent est connexe. Créez une classe paramétrée Node et Graph comme ci-dessous :

public class Node<T> {
    private final T data;
    private final List<Node<T>> neighbours;

    public Node(T data) { /* A compléter */ }
    public T getData() { /* A compléter */ }
    public void addEdge(Node to) { /* A compléter */ }
    public List<Node<T>> getNeighbours() { /* A compléter */ }
}


public class Graph<T> {
    private final Set<Node<T>> nodes;

    public Graph() {  /* A compléter */ }
    public void addNode(T data) {  /* A compléter */ } 
    public Node<T> getNode(T data) {  /* A compléter */ }
    public Set<Node<T>> getNodes() { /* A compléter */ }
}

3) Ajoutez une méthode public Graph<Position> getGraph(Grid grid) dans la classe GridRepoString. Cette méthode devra construire et renvoyer un graphe représentant la carte actuelle.

4) Ajouter une méthode public boolean isConnected() dans la classe Graph pour déterminer si le graphe est connexe. Vous pouvez définir une association entre un noeud et un booléen (par exemple avec une table de hachage) pour savoir si un noeud a déjà été visité. Il suffit ensuite de faire un parcours en profondeur du graphe. S’il reste un noeud du graphe non visité, le graphe n’est pas connexe.

Calcul du plus court chemin

1) Nous devons ajouter quelques menus dans notre éditeur pour pouvoir sélectionner deux noeuds et faire un calcul de plus court de chemin. Ajoutez les lignes suivantes dans la classe EditorView.

MenuItem marksItem = new MenuItem("Clear marks");
editMenu.getItems().add(marksItem);  
marksItem.setOnAction(e -> gridView.getMarker().clear());

2) Ajoutez la classe Marker dans le package view.

3) Ajoutex le champ private final Marker marker; dans la classe GridView et ajoutez la ligne this.marker = new Marker(this); dans le constructeur de la classe.

4) Ajoutex les lignes suivantes dans la méthode createTile de la classe GridView.

tile.setOnContextMenuRequested(e -> {
    ContextMenu contextMenu = new ContextMenu();
    MenuItem itemMark = new MenuItem("Set mark");
    MenuItem itemPath = new MenuItem("Path finding");
    itemPath.setDisable(!marker.exists());
    // Put marker
    itemMark.setOnAction(event -> {
        marker.create(new Position(i, j));
    });
    // Path finding
    itemPath.setOnAction(event -> {
        System.out.println("Path finding " + marker.getPosition() + " -> " + new Position(i,j));
        // This needs to be updated!
        // Create the graph and run A* to find the shortest path
    });
    contextMenu.getItems().addAll(itemMark, itemPath);
    contextMenu.show(tile, e.getScreenX(), e.getScreenY());
});

5) Pour calculer le chemin le plus court entre deux neouds du graphe, vous pouvez implémenter l’algorithme A* dans la classe Graph.