Explication de l'algorithme

Son objectif

Dans un graphe, on peut utiliser l'algorithme du BFS (Breadth-First Search / Algorithme de Parcours en Largeur) pour construire un arbre couvrant tout le graphe en ayant pour chaque sommet le chemin le plus direct vers le sommet de départ.

Son principe

On choisi le sommet de départ vers lequel "pointerons" tous les autres. On prend ensuite chaque voisin et on les visite, puis les voisins des voisins, et ainsi de suite en avançant par "couche" en notant à chaque fois quel voisin nous a mené à qui. Ensuite, pour chaque sommet du graphe, il suffit de suivre les voisins dans le sens inverse pour obtenir le chemin le plus court vers le sommet de départ.

Explication du principe de l'algorithme en image

Notre utilisation

Pourquoi utiliser cet algorithme ?

Nous avons utilisé le BFS pour calculer, depuis n'importe quelle position sur les chemins de notre plateau de jeu, le trajet le plus court pour atteindre l'arrivée. Cela est utilisé par les attaquants possédant la capacité MoveToEndAbility (actuellement tous).

L'implémentation

Il est assez simple de faire "tourner" cet algorithme à la main mais la mise en place dans le code est légèrement plus délicate. Cela utilise un concept de "file" ("Queue" en anglais).

Pseudo-code

La logique derrière cet algorithme correspond, en pseudo code, à :

Procédure calculerBFS(graphe : Graphe, départ : Sommet)
    Construire une file f
    Marquer départ
    Enfiler départ dans f

    TantQue f n'est pas vide Faire
        Défiler dans f et appeler le sommet obtenu s
        TantQue s a un voisin non marqué dans graphe Faire
            Appeler t le voisin obtenu
            Marquer t
            Enfiler t
            Enregistrer que t vient de s
        Fin TantQue
    Fin TantQue
Fin Procédure

Java

Notre implémentation en Java utilise une List<Cell> plutôt qu'une Queue<Cell> car cela nous a paru plus simple et totalement équivalant en terme de résultat final. Nous avons une classe Cell qui matérialise un sommet de graphe ayant un état (marqué ou non) et pouvant mémoriser son suivant (dans l'ordre de lecture, donc son prédécesseur dans l'ordre de construction). Cette méthode fait parti d'un objet Graphe qui possède un départ fixe et chaque sommet connait son graphe, ce qui leur permet de donner la liste de leurs voisins.

L'algorithme :

public void bfs() {
    // On réinitialise le graphe au cas où des opérations aient déjà été effectuées.
    // Cela équivaut à réinitialiser le marquage de tous les sommets et de supprimer leur "suivant"
    this.reset();
    // On construit notre file avec une liste dans laquelle on ajoutera toujours à la fin et on récupèrera au début
    List<Cell> queue = new ArrayList<Cell>();
    Cell c, d;
    this.start.setMarked(true);
    queue.add(this.start); // Enfiler

    while (! queue.isEmpty()) {
        c = queue.remove(0); // Défiler
        while ((d = c.getUnmarkedNeighbor()) != null) {
            d.setMarked(true);
            d.setNext(c);
            queue.add(d); // Enfiler
        }
    }
}

La subtilité réside dans le fait de récupérer les voisins non marqués tant qu'il y en a. Nous avons donc opté pour une méthode getUnmarkedNeighbor() dans la classe Cell qui permet d'obtenir un voisin non marqué (de manière arbitraire), ou null si il n'y en a pas. Voici la méthode :

public Cell getUnmarkedNeighbor() {
    Cell c;
    for (Dir d : Dir.list(this.paths)) // On récupère les directions dans lesquelles la cellule a un chemin
        if ((c = this.graph.getCellAt(d.n(this.loc))) != null && ! c.isMarked()) // On récupère et vérifie le voisin
            return c;
    return null;
}