Table des matières

TD 8 : Cartographie martienne (fin)

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. Pour le moment, nous n’indiquons aucune information pertinente.

Menu editMenu = new Menu("Edit");
MenuItem connectivityItem = new MenuItem("Check connectivity");
editMenu.getItems().add(connectivityItem);

connectivityItem.setOnAction(e -> {
    Alert alert = new Alert(Alert.AlertType.INFORMATION);
    alert.setHeaderText(null);
    alert.setContentText("We should indicate whether the map is fully connected or not!");
    alert.showAndWait();
});

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

4) Ajoutez une méthode public Graph<Position> getGraph() dans la classe Grid. Cette méthode devra construire et renvoyer un graphe représentant la carte actuelle. Dans cette méthode, créez dans un premier temps un graphe contenant un nœud pour chaque case accessible. Parcourez ensuite tous les nœuds du graphe. Pour chacun d’entre eux, rechercher les nœuds existants correspondants à des cases adjacentes.
Ajoutez des arrêtes avec ces

5) Ajouter la méthode public boolean isConnected() ci-dessous dans la classe Graph pour déterminer si le graphe est connexe. Cette méthode initialise une table d’association entre un nœud et un booléen pour savoir si un nœud a déjà été visité. Il suffit ensuite de choisir un nœud quelconque du graphe et de faire un parcours en profondeur dfs à partir de cette source. À la fin, s’il reste un nœud du graphe non visité, le graphe n’est pas connexe.

public boolean isConnected() {
    Hashtable<T, Boolean> visited = new Hashtable<>();
    nodes.forEach(node -> visited.put(node.getData(), false));
    if (nodes.stream().findFirst().isPresent()) {
        Node<T> source = nodes.stream().findFirst().get();
        dfs(source, visited);
    }
    return ! visited.containsValue(false);
}

Indications

Le parcours d’un graphe en profondeur se réalise en partant d’un sommet arbitraire v à visiter, et en parcourant d’abord un de ses voisins u et tous ses descendants (c’est-à-dire tous les sommets accessibles à partir de u) avant de traiter le voisin suivant de v. Cet algorithme se code très facilement en récursif.

Calcul du plus court chemin

1) Nous devons ajouter quelques menus dans notre éditeur pour pouvoir sélectionner deux nœuds 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) Ajoutez 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) Ajoutez 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 nœuds du graphe, vous pouvez implémenter l’algorithme A* dans la classe Graph. Affichez le chemin sur la console.

6) Dessinez un cercle de couleur sur chaque case composant le plus court chemin.