Activité pratique

Consignes globales

L’objectif de cette activité est d’écrire des programmes pour guider votre rat à travers le labyrinthe grâce à des algorithmes de parcours. Nous allons tout d’abord nous placer dans un cas simple :

• Un seul joueur.
• Un seul morceau de fromage à attraper.
• Pas de boue dans le labyrinthe.

Nous écrirons deux algorithmes de parcours, le parcours en profondeur (DFS) et le parcours en largeur (BFS). Nous verrons ensuite que ces deux approches partagent pas mal d’éléments en commun, ce qui nous permettra de mieux structurer nos programmes.

Contenu de l’activité

Parcours en profondeur (DFS)

Préparation

Tout d’abord, nous allons créer un joueur et un script pour visualiser son comportement.

• players/dfs.py — Inspirez-vous de ce que vous avez fait en séance 1 pour créer un joueur DFS héritant de Player, et ayant :

  • Un constructeur __init__(...).
  • Une méthode preprocessing(...).
  • Une méthode turn(...).

• games/visualize_dfs.py — Créez un fichier qui lancera une partie avec un joueur DFS, dans un labyrinthe respectant les critères listés plus haut (un seul fromage, pas de boue). Vous pouvez éventuellement définir une random_seed (pour toujours travailler avec le même labyrinthe) et une trace_length (pour suivre la trajectoire de votre joueur). Inspirez-vous des autres fichiers du sous-dossier games que vous avez rencontrés lors de la séance précédente.

La méthode traversal(...)

Implémentation

Comme vous avez pu l’étudier dans vos cours de programmation et d’algorithmique, la clé pour écrire un bon programme est de bien décomposer les tâches à effectuer en fonctions. Pour cela, au lieu d’effectuer directement le parcours dans une des méthodes du joueur, on vous demande d’écrire une méthode traversal(...) qui effectuera le parcours en profondeur, et renverra les distances depuis la source jusqu’à chaque sommet exploré, ainsi que la table de routage correspondante.

La distance à un sommet est la somme des poids des arêtes le long du chemin trouvé par le parcours (qui n’est pas forcément le plus court). Le poids de l’arête entre deux sommets voisins u et v s’obtient avec graph.get_weight(u, v). Il n’y a pas de boue dans les parties de cette séance : tous les poids valent alors 1, et la distance est simplement le nombre de déplacements. Cependant, les tests fournis plus bas utilisent des labyrinthes avec de la boue, et cette notion nous servira en séance 3 : utilisez donc bien graph.get_weight(...) pour calculer les distances.

Notez que cette méthode prend en paramètre un objet de type Graph (et non un Maze, comme reçu par preprocessing(...) ou turn(...)). En effet, ce parcours est générique, et pourrait s’appliquer à d’autres types de graphes que des labyrinthes. De plus, la classe Maze hérite de Graph : vous pouvez donc fournir un objet de type Maze à traversal(...) sans aucun problème.

def traversal ( self,
                graph:  Graph,
                source: int
              ) ->      tuple[dict[int, int], dict[int, int | None]]:

    """
    This method performs a DFS traversal of a graph.
    It returns the explored vertices with associated distances.
    The distance to a vertex is the sum of the weights of the edges along the path found (given by ``graph.get_weight(...)``).
    It also returns the routing table, that is, the parent of each vertex in the traversal.

    Args:
        graph:  The graph to traverse.
        source: The source vertex of the traversal (we type it as int here because we will only manipulate mazes, but Graph uses Hashable as a more generic type).

    Returns:
        A tuple containing:
        - The distances from the source to each explored vertex.
        - The routing table, that is, the parent of each vertex in the traversal (None for the source).
    """

    # Your code here

Tests

Avez-vous bien pensé à vérifier que votre méthode traversal(...) fonctionne ? On peut souvent faire des erreurs en écrivant du code, que ça soit un détail de raisonnement oublié, un cas un peu inhabituel pas géré, ou juste une erreur de syntaxe. Par défaut, une bonne approche est de partir du principe que tout code non testé est faux.

Vous avez vu en séance 2 de programmation comment exécuter des tests unitaires, et en séance 3 comment en concevoir. Pour le moment, nous allons vous fournir un fichier de tests pour vérifier votre implémentation de traversal(...) dans la classe DFS.

• tests/test_dfs.py.

Ce fichier présuppose que vous avez bien suivi les instructions jusqu’à présent, c’est-à-dire que votre joueur s’appelle bien DFS dans un fichier players/dfs.py, que traversal(...) a bien le prototype de la méthode donnée plus haut, etc.

Parcourons un peu ce fichier ensemble. Tout d’abord, il contient un peu de documentation, et quelques imports nécessaires. Puis, il introduit une classe DFS_Tests qui hérite de unittest.TestCase, la classe de base pour les tests unitaires dans Python. Cette classe contient un certain nombre d’éléments :

• Une méthode setUpClass(...). Cette méthode est exécutée une unique fois, avant tous les autres tests de la classe. Elle permet notamment d’initialiser des éléments qui seront utilisés par tous les tests. Ici, nous nous en servons pour créer quelques labyrinthes fixés à l’avance, ainsi qu’une centaine de labyrinthes générés aléatoirement, sur lesquels nous exécuterons nos tests. Notez que cette méthode est une méthode de classe (et non d’instance) comme l’indiquent le décorateur @classmethod et le premier paramètre cls (par opposition à self pour les méthodes d’instance). Cela signifie que les attributs de classe qui y sont créés (ici cls.tree_maze, cls.cycle_maze, cls.disconnected_maze, et cls.random_mazes) seront partagés par toutes les méthodes de test de la classe DFS_Tests, et ne seront pas recréés pour chaque test.

  @classmethod
  def setUpClass (cls) -> None:
  
      """
      This method is called once, before all test methods.
      Here, we use it to create the mazes, so that they are shared by all tests instead of being created again in each test.
      """
  
      cls.tree_maze = ...
      cls.cycle_maze = ...
      cls.disconnected_maze = ...
      cls.random_mazes = ...

• Ensuite, une méthode setUp(...), exécutée avant chaque test, qui instancie le joueur dont on veut tester les méthodes. Contrairement à setUpClass(...) qui est une méthode de classe, setUp(...) est une méthode d’instance (indiqué par le premier paramètre self). Cela signifie que self.player sera différent pour chaque test.

  def setUp (self) -> None:
  
      """
      This method is called before each test method.
      Here, we use it to instantiate a DFS player.
      """
  
      # Instantiate a DFS player to test its methods
      self.player = DFS()

• La suite du fichier contient un certain nombre de tests pour la méthode traversal(...). Certains tests vérifient des propriétés sur les labyrinthes fixés (on s’attend à obtenir une sortie particulière) ; d’autres portent sur des labyrinthes tirés aléatoirement, et évaluent des propriétés générales (des invariants) des solutions trouvées. Pour vous aider à vous y retrouver, nous avons choisi de nommer chaque test de manière assez explicite, en suivant le modèle test___<tested method>___<test case>___<tested property>. On précise également pour chaque test s’il correspond à un cas normal, limite (corner case) ou d’erreur. Par exemple, le test suivant (un cas normal) évalue, sur un ensemble de labyrinthes générés aléatoirement, si les types des sorties de la méthode traversal(...) sont corrects :

  def test___dfs_traversal___random_mazes___output_types (self) -> None:
  
      """
      Category: normal use.
      This method tests the ``traversal(...)`` method on random mazes.
      It checks that outputs are of the expected types.
      """
  
      # Distances should be a dictionary with integer keys and values
      # The routing table should be a dictionary with integer keys and integer or None values
      for maze in self.random_mazes:
          start_vertex = maze.get_vertices()[0]
          distances, routing_table = self.player.traversal(maze, start_vertex)
          self.assertIsInstance(distances, dict, "Distances should be a dictionary")
          self.assertTrue(all(isinstance(k, int) and isinstance(v, int) for k, v in distances.items()), "Distances should have integer keys and values")
          self.assertIsInstance(routing_table, dict, "The routing table should be a dictionary")
          self.assertTrue(all(isinstance(k, int) and isinstance(v, (type(None), int)) for k, v in routing_table.items()), "The routing table should have integer keys, and integer or None values")

• Enfin, nous fournissons d’ores et déjà des tests pour une méthode find_route(...) que nous allons développer dans la partie suivante. Jusque-là, vous avez défini les méthodes avant les tests. Nous allons passer à une approche dite test-driven, où les tests précèdent l’implémentation des méthodes.

Utiliser la table de routage

Implémentation

Maintenant que vous avez un algorithme de parcours qui marche (et testé !), écrivons une méthode qui exploite la table de routage pour renvoyer la série de cases à suivre pour atteindre une case donnée.

def find_route ( self,
                 routing_table: dict[int, int | None],
                 source:        int,
                 target:        int
               ) ->             list[int]:

    """
    This method finds the route from a source vertex to a target vertex using a routing table.

    Args:
        routing_table: The routing table, that is, the parent of each vertex in the traversal (None for the source).
        source:        The source vertex.
        target:        The target vertex.

    Returns:
        The route from the source to the target as a list of vertices.
    """

    # Your code here

Pensez à régulièrement exécuter vos tests pour vérifier que votre code est correct.

Assembler tout ça

Implémentation

Maintenant, il ne reste plus qu’à assembler les morceaux !

• __init__(...) — Mettez à jour votre constructeur afin de déclarer un attribut self.actions = None. Vous pourriez directement l’initialiser avec une liste vide [], mais il est préférable de l’initialiser dans preprocessing(...) pour permettre de faire un reset(...) de la partie sans avoir des valeurs restantes de la partie précédente dans les attributs du joueur.

• preprocessing(...) — Pendant la phase de prétraitement, utilisez les méthodes introduites précédemment (traversal(...) et find_route(...)) pour calculer les actions à effectuer depuis votre position initiale jusqu’à la position du seul morceau de fromage. Ensuite, stockez ces actions dans l’attribut self.actions.

  Information

  Quelques fonctions de PyRat qui vous seront utiles :

  • Vous pouvez obtenir votre position courante avec my_location = game_state.player_locations[self.get_name()].
  • S’il n’y a qu’un morceau de fromage dans le labyrinthe, sa position est donnée par game_state.cheese[0].
  • Pour obtenir des actions à partir d’un chemin, la classe Maze fournit une méthode locations_to_actions(...).

• turn(...) — À chaque tour, vous devez retourner une action provenant de self.actions. Il suffit d’extraire la prochaine action à effectuer depuis cet attribut et de la renvoyer.

À quoi ça ressemble ?

À présent, utilisez votre script visualize_dfs.py pour observer votre joueur.

Vous devriez obtenir un rat qui se comporte comme suit :

Parcours en largeur (BFS)

Comme vous avez pu le voir dans l’article sur les parcours, le DFS trouve un chemin qui n’est pas forcément le plus court. Nous allons maintenant utiliser un autre algorithme, appelé parcours en largeur (Breadth-First Search, BFS). Cet algorithme a la propriété de renvoyer le chemin le plus court dans un graphe non pondéré.

• Créez un fichier pour lancer une partie, nommé visualize_bfs.py, dans le sous-dossier games de votre workspace PyRat.

• Créez un fichier joueur nommé bfs.py dans le sous-dossier players. Pour ce dernier, vous pouvez partir d’une copie de votre fichier dfs.py, car il n’y aura pas beaucoup de différences !

• Adaptez les fonctions pour que votre rat effectue un parcours en largeur pour déterminer le chemin le plus court. N’oubliez pas de modifier la documentation, pour qu’elle décrive bien votre nouveau joueur.

• N’oubliez pas non plus de tester vos fonctions ! Voici les tests que vous pouvez utiliser pour vous assurer que votre code fonctionne : tests/test_bfs.py.

  Information

  Remarquez à quel point les tests sont similaires à ceux du DFS. Lesquels diffèrent ? Pourquoi ?

Vous devriez obtenir un rat qui se comporte comme suit :

Comparer aux programmes aléatoires

Maintenant que vous avez deux nouveaux joueurs, il serait intéressant de les comparer avec les joueurs aléatoires que vous avez développés lors de la séance précédente.

Factoriser les codes

Similarités et différences entre DFS et BFS

Comme vous l’avez peut-être remarqué, les codes de BFS et DFS sont extrêmement similaires. En fait, c’est la structure de données utilisée qui détermine l’ordre dans lequel les sommets sont explorés. En effet, avec une file (FIFO), le parcours effectue une recherche en largeur. Avec une pile (LIFO), le parcours effectue une recherche en profondeur.

Ainsi, de manière générale, un parcours peut être vu comme un algorithme global qui, à un moment donné, doit :

• Créer une structure de données.
• Ajouter un élément à la structure de données.
• Extraire un élément de la structure de données.
• Savoir si la structure de données est vide, pour arrêter le parcours.

Par ailleurs, la notion de parcours n’a pas vraiment sa place dans un joueur. Un parcours est un algorithme sur un graphe : il ne sait rien des fromages ou des tours de jeu, et pourrait servir dans bien d’autres contextes (dans d’autres joueurs, pour analyser un labyrinthe, etc.). Le rôle d’un joueur est de décider quoi faire à chaque tour. Il peut s’appuyer sur un parcours pour ça, mais il n’a pas besoin de savoir comment ce parcours fonctionne.

Il est donc plus pertinent de définir une classe de parcours à part, qui regroupe tout ce qui est commun aux parcours, et de la spécialiser selon la stratégie d’exploration souhaitée. Le paradigme de la programmation orientée objet (POO) rend cela pratique grâce à l’héritage. L’idée est de créer une classe de base qui factorise le code commun, et des sous-classes qui spécialisent les particularités. Le joueur, de son côté, n’a plus qu’à créer le parcours qui l’intéresse et à s’en servir.

Dans la suite de cette activité, nous allons mettre en place cette réorganisation ensemble. Schématiquement, elle correspond au diagramme suivant (si vous avez effectué la factorisation demandée en fin de séance 1, le diagramme pourra être un peu différent pour vous) :

Le diagramme ci-dessus est ce que l’on appelle un diagramme de classes UML. Voici comment le lire :

• On a cinq classes : Player, fournie par la bibliothèque PyRat (en orange), et TraversalPlayer, Traversal, BFSTraversal et DFSTraversal, qui font partie de votre workspace (en vert). Les cadres indiquent où se trouve chaque classe : players et utils/traversal sont des sous-dossiers de votre workspace.

• Chaque boîte est une classe, avec trois compartiments : son nom, ses attributs, et ses méthodes.

• Traversal, écrit en italique et marqué «abstract», est une classe abstraite, ce qui signifie qu’on ne peut pas l’instancier (cela n’aurait pas de sens de le faire, car elle ne définit aucune stratégie de parcours). Elle sert uniquement à abstraire la notion de parcours d’un graphe et regroupe les aspects communs à tous les algorithmes. En Python, une classe abstraite est une classe qui hérite de abc.ABC (Abstract Base Class).

• La classe Traversal possède deux attributs : routing_table et distances. Ces attributs doivent être déclarés dans le constructeur de Traversal. La valeur de routing_table et distances est définie par la méthode traversal(...), et on peut la lire avec les méthodes get_routing_table(...) et get_distances(...). Le + devant chaque attribut et méthode indique qu’il est public, c’est-à-dire qu’on peut l’utiliser depuis l’extérieur de la classe (par exemple bfs.find_route(...)). À l’inverse, le - indique qu’il est privé, c’est-à-dire réservé à la classe elle-même (par exemple, seul TraversalPlayer manipule sa liste actions). Le # indique qu’il est protégé, c’est-à-dire réservé à la classe et à ses classes enfants.

• La classe Traversal possède huit méthodes : get_distances(...), get_routing_table(...), traversal(...), find_route(...), initialize_structure(...), add_to_structure(...), get_from_structure(...) et is_structure_empty(...). Les quatre dernières sont en italique, ce qui signifie qu’elles sont abstraites, c’est-à-dire qu’elles ne font rien et doivent être implémentées dans les classes enfants. On les déclare quand même dans la classe Traversal car cela permet de fixer leur signature, c’est-à-dire le nombre et le type de leurs arguments, et leur type de retour. En Python, on déclare une méthode abstraite en utilisant le décorateur @abc.abstractmethod juste avant la déclaration de la méthode.

• Une ligne terminée par un triangle creux est un héritage : les classes BFSTraversal et DFSTraversal héritent de Traversal. Elles héritent donc des attributs et méthodes définis dans Traversal, et peuvent utiliser ceux qui sont publics ou protégés. Contrairement à Traversal, elles sont instanciables.

• Ces deux classes redéfinissent les méthodes abstraites de Traversal pour les rendre utilisables. Chacune range comme elle le souhaite la structure de données qui stocke les sommets à explorer, dans son propre attribut : une file queue pour BFSTraversal, et une pile stack pour DFSTraversal. Traversal n’a pas besoin de connaître cette structure : elle la manipule uniquement au travers de ces méthodes.

• De la même manière, TraversalPlayer hérite de Player, comme tous les joueurs que vous avez écrits jusqu’ici.

• La ligne avec un losange creux est une agrégation : TraversalPlayer utilise un objet Traversal, qu’il reçoit à sa création et range dans son attribut traversal_algorithm, par exemple TraversalPlayer(BFSTraversal()). Le 1 indique qu’il en utilise exactement un. Contrairement à une composition (losange plein), le joueur ne crée pas lui-même l’objet qu’il utilise : c’est le code qui crée le joueur qui choisit le parcours. Le joueur fonctionne ainsi avec n’importe quelle sous-classe de Traversal, y compris celles que vous écrirez plus tard, sans avoir à être modifié. Si aucun parcours n’est donné, il crée un BFSTraversal. Attention : chaque joueur doit recevoir son propre objet, car un parcours garde les résultats de son dernier appel.

• Dans cette nouvelle organisation, routing_table et distances sont des attributs de Traversal, et non plus des variables de retour de la méthode traversal(...). L’objectif de ce changement est d’encapsuler la manière dont le résultat du parcours est stocké et manipulé, et de fournir à l’utilisateur de la classe Traversal une interface plus logique. Par exemple, on avait préalablement ce code, qui donnait à l’utilisateur la responsabilité de passer la table de routage comme argument de la fonction find_route(...) :

  distances, routing_table = self.traversal(maze, my_location)
  path = self.find_route(routing_table, my_location, game_state.cheese[0])

  On peut à présent cacher cette étape intermédiaire, de sorte que l’utilisateur n’ait qu’à faire :

  self.traversal_algorithm.traversal(maze, my_location)
  path = self.traversal_algorithm.find_route(game_state.cheese[0])

Implémentation

Construisons maintenant cette réorganisation ensemble ! Nous vous fournissons les fichiers correspondant aux classes du diagramme, et vous n’aurez qu’à compléter la classe Traversal.

• Tout d’abord, créez un nouveau sous-dossier utils (c’est un nom standard en programmation pour désigner une boîte à outils), et dans celui-ci, un sous-dossier traversal. Le dossier utils accueillera au fil des séances d’autres sous-dossiers (utils/tsp, utils/greedy…), un par thème : regrouper les fichiers par thème permet de s’y retrouver quand leur nombre augmente.

• Créez les fichiers suivants dans votre workspace PyRat, en copiant-collant le code de l’onglet correspondant ci-dessous :

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is provided during session 2 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session2/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import abc

# PyRat imports
from pyrat import Graph

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class Traversal (abc.ABC):

    """
    This is an abstract class that defines the interface for graph traversal algorithms.
    It is meant to be inherited by specific traversal algorithm implementations, such as breadth-first search (BFS) or depth-first search (DFS).
    
    Each subclass chooses the data structure that stores the vertices to visit, and keeps it as it wishes.
    The traversal only manipulates it through four abstract methods that must be implemented in the subclasses:
        * ``initialize_structure``: Initializes the data structure needed for the traversal.
        * ``add_to_structure``: Adds an element to the data structure.
        * ``get_from_structure``: Extracts an element from the data structure.
        * ``is_structure_empty``: Indicates whether the data structure is empty.
    The choice of data structure (e.g., queue, stack) will determine the behavior of the traversal algorithm.
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        *(This class is abstract and meant to be subclassed, not instantiated directly).*

        Initializes a new instance of the class.

        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """
        
        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # Calling traversal will set these attributes
        self.routing_table = None
        self.distances = None

    ##################################################################################
    #                                     METHODS                                    #
    ##################################################################################

    def get_distances (self) -> dict[int, int]:

        """
        This method returns the distances computed by the last traversal.

        Returns:
            The distance from the source to each vertex explored, as a dictionary.
        """

        # Return the distances found
        return self.distances

    ##################################################################################

    def get_routing_table (self) -> dict[int, int | None]:

        """
        This method returns the routing table computed by the last traversal.

        Returns:
            The parent of each vertex explored, as a dictionary (None for the source).
        """

        # Return the routing table found
        return self.routing_table

    ##################################################################################

    def traversal ( self,
                    graph:  Graph,
                    source: int
                  ) ->      None:

        """
        This method performs a traversal of the given graph from the given source vertex.
        It computes the distances from the source to all other vertices, as well as a routing table that can be used to reconstruct paths.
        The distance to a vertex is the sum of the weights of the edges along the path found (given by ``graph.get_weight(...)``).
        The results are stored in the ``distances`` and ``routing_table`` attributes.
        
        Args:
            graph:  The graph to traverse.
            source: The source vertex of the traversal (we type it as int here because we will only manipulate mazes, but Graph uses Hashable as a more generic type).
        """

        # Initialization
        self.distances = {}
        self.routing_table = {}

        # Complete the method here
        # Use methods `self.initialize_structure()`, `self.add_to_structure(...)`, `self.get_from_structure()` and `self.is_structure_empty()` to manage the data structure, which each subclass stores as it wishes

    ##################################################################################

    def find_route ( self,
                     target: int
                   ) ->      list[int]:

        """
        This method finds the route from the source vertex to a target vertex using a routing table.

        Args:
            target: The target vertex.

        Returns:
            The route from the source to the target as a list of vertices.

        Raises:
            RuntimeError: If no traversal has been performed yet.
            ValueError: If the target was not reached by the last traversal (e.g., it is in another component of the graph).
        """

        # A route can only be found from the results of a traversal
        if self.routing_table is None:
            raise RuntimeError(f"Cannot find a route to {target!r}: no traversal has been performed yet")

        # The target must have been reached by the traversal
        if target not in self.routing_table:
            raise ValueError(f"Cannot find a route to {target!r}: it was not reached by the last traversal")

        # Your code here
        # Use the `self.routing_table` attribute to find the route from the source (vertex with parent None) to the target

    ##################################################################################

    @abc.abstractmethod
    def initialize_structure (self) -> None:

        """
        *(This method is abstract and must be implemented in the subclasses).*

        It initializes the data structure needed for the traversal.

        Raises:
            NotImplementedError: If called through ``super()``, as a subclass that does not redefine this method cannot be instantiated.
        """

        # This method must be implemented in the child classes
        # By default we raise an error
        raise NotImplementedError(f"{type(self).__name__} must redefine method 'initialize_structure' of Traversal")

    ##################################################################################

    @abc.abstractmethod
    def add_to_structure ( self,
                           element: object
                         ) ->       None:

        """
        *(This method is abstract and must be implemented in the subclasses).*

        It adds an element to the data structure.

        Args:
            element: The element to add, as a tuple (distance, vertex, parent).

        Raises:
            NotImplementedError: If called through ``super()``, as a subclass that does not redefine this method cannot be instantiated.
        """

        # This method must be implemented in the child classes
        # By default we raise an error
        raise NotImplementedError(f"{type(self).__name__} must redefine method 'add_to_structure' of Traversal")

    ##################################################################################

    @abc.abstractmethod
    def get_from_structure (self) -> object:

        """
        *(This method is abstract and must be implemented in the subclasses).*

        It extracts an element from the data structure.

        Returns:
            The extracted element, as a tuple (distance, vertex, parent).

        Raises:
            NotImplementedError: If called through ``super()``, as a subclass that does not redefine this method cannot be instantiated.
        """

        # This method must be implemented in the child classes
        # By default we raise an error
        raise NotImplementedError(f"{type(self).__name__} must redefine method 'get_from_structure' of Traversal")

    ##################################################################################

    @abc.abstractmethod
    def is_structure_empty (self) -> bool:

        """
        *(This method is abstract and must be implemented in the subclasses).*

        It indicates whether the data structure contains no more elements to extract.

        Returns:
            True if the data structure is empty, False otherwise.

        Raises:
            NotImplementedError: If called through ``super()``, as a subclass that does not redefine this method cannot be instantiated.
        """

        # This method must be implemented in the child classes
        # By default we raise an error
        raise NotImplementedError(f"{type(self).__name__} must redefine method 'is_structure_empty' of Traversal")

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is provided during session 2 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session2/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# PyRat imports
from utils.traversal.traversal import Traversal

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class BFSTraversal (Traversal):

    """
    This class implements a breadth-first search (BFS) traversal algorithm by defining the abstract methods from the parent class.
    We use a FIFO queue to indicate the order in which vertices should be explored.
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        *(This class inherits from* ``Traversal`` *).*

        It implements a breadth-first search (BFS) traversal algorithm by defining the abstract methods from the parent class.
        We use a FIFO queue to indicate the order in which vertices should be explored.

        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """
        
        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # FIFO queue of the elements to visit, as a list, created by initialize_structure
        self.queue = None

    ##################################################################################
    #                                     METHODS                                    #
    ##################################################################################

    def initialize_structure (self) -> None:

        """
        *(This method redefines the method of the parent class with the same name).*

        It initializes the data structure needed for the traversal, and stores it in the ``queue`` attribute.
        Here, we use a list to implement a FIFO queue.
        """

        # We start with an empty list
        self.queue = []

    ##################################################################################

    def add_to_structure ( self,
                           element: object
                         ) ->       None:

        """
        *(This method redefines the method of the parent class with the same name).*

        It adds an element to the data structure stored in the ``queue`` attribute.
        Here, we append the element to the end of the list to implement a FIFO queue.

        Args:
            element: The element to add, as a tuple (distance, vertex, parent).
        """

        # We append the element to the end of the list
        self.queue.append(element)

    ##################################################################################

    def get_from_structure (self) -> object:

        """
        *(This method redefines the method of the parent class with the same name).*

        It extracts an element from the data structure stored in the ``queue`` attribute.
        Here, we remove and return the first element of the list to implement a FIFO queue.

        Returns:
            The extracted element, as a tuple (distance, vertex, parent).
        """

        # We remove and return the first element of the list
        return self.queue.pop(0)

    ##################################################################################

    def is_structure_empty (self) -> bool:

        """
        *(This method redefines the method of the parent class with the same name).*

        It indicates whether the data structure stored in the ``queue`` attribute contains no more elements to extract.
        Here, the FIFO queue is empty when the list has no element.

        Returns:
            True if the data structure is empty, False otherwise.
        """

        # The queue is empty when the list has no element
        return len(self.queue) == 0

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is provided during session 2 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session2/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# PyRat imports
from utils.traversal.traversal import Traversal

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class DFSTraversal (Traversal):

    """
    This class implements a depth-first search (DFS) traversal algorithm by defining the abstract methods from the parent class.
    We use a LIFO stack to indicate the order in which vertices should be explored.
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        *(This class inherits from* ``Traversal`` *).*

        It implements a depth-first search (DFS) traversal algorithm by defining the abstract methods from the parent class.
        We use a LIFO stack to indicate the order in which vertices should be explored.

        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """
        
        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # LIFO stack of the elements to visit, as a list, created by initialize_structure
        self.stack = None

    ##################################################################################
    #                                     METHODS                                    #
    ##################################################################################

    def initialize_structure (self) -> None:

        """
        *(This method redefines the method of the parent class with the same name).*

        It initializes the data structure needed for the traversal, and stores it in the ``stack`` attribute.
        Here, we use a list to implement a LIFO stack.
        """

        # We start with an empty list
        self.stack = []

    ##################################################################################

    def add_to_structure ( self,
                           element: object
                         ) ->       None:

        """
        *(This method redefines the method of the parent class with the same name).*

        It adds an element to the data structure stored in the ``stack`` attribute.
        Here, we append the element to the end of the list to implement a LIFO stack.

        Args:
            element: The element to add, as a tuple (distance, vertex, parent).
        """

        # We append the element to the end of the list
        self.stack.append(element)

    ##################################################################################

    def get_from_structure (self) -> object:

        """
        *(This method redefines the method of the parent class with the same name).*

        It extracts an element from the data structure stored in the ``stack`` attribute.
        Here, we remove and return the last element of the list to implement a LIFO stack.

        Returns:
            The extracted element, as a tuple (distance, vertex, parent).
        """

        # We remove and return the last element of the list
        return self.stack.pop()

    ##################################################################################

    def is_structure_empty (self) -> bool:

        """
        *(This method redefines the method of the parent class with the same name).*

        It indicates whether the data structure stored in the ``stack`` attribute contains no more elements to extract.
        Here, the LIFO stack is empty when the list has no element.

        Returns:
            True if the data structure is empty, False otherwise.
        """

        # The stack is empty when the list has no element
        return len(self.stack) == 0

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is provided during session 2 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session2/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# PyRat imports
from pyrat import Player, Maze, GameState, Action
from utils.traversal.traversal import Traversal
from utils.traversal.bfs_traversal import BFSTraversal

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class TraversalPlayer (Player):

    """
    *(This class inherits from* ``Player`` *).*

    This player controls a PyRat character that explores the maze using a graph traversal algorithm.
    The traversal algorithm is given at creation, as an object of a subclass of ``Traversal`` (e.g., ``BFSTraversal()``).
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   traversal_algorithm: Traversal | None = None,
                   *args:               object,
                   **kwargs:            object
                 ) ->                   None:

        """
        Initializes a new instance of the class.
        Here, the constructor is only used to initialize the player.
        It transmits the arguments to the parent constructor, which is responsible for initializing the name and the skin of the player.

        Args:
            traversal_algorithm: The traversal algorithm to use, as an object of a subclass of ``Traversal`` (default is a new ``BFSTraversal``).
                                 Each player needs its own object, as it stores the results of the last traversal.
            args:                Arguments to pass to the parent constructor.
            kwargs:              Keyword arguments to pass to the parent constructor.
        """

        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # We create an attribute to store the actions to perform
        self.actions = None

        # We store the chosen traversal algorithm, or create the default one
        self.traversal_algorithm = traversal_algorithm if traversal_algorithm is not None else BFSTraversal()

    ##################################################################################
    #                                  PYRAT METHODS                                 #
    ##################################################################################

    def preprocessing ( self,
                        maze:       Maze,
                        game_state: GameState,
                      ) ->          None:
        
        """
        *(This method redefines the method of the parent class with the same name).*

        This method is called once at the beginning of the game.
        Here, we use the traversal algorithm to compute a path that reaches the piece of cheese from the initial position of the player.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        """

        # We perform a traversal of the maze graph from the initial position of the player
        my_location = game_state.player_locations[self.get_name()]
        self.traversal_algorithm.traversal(maze, my_location)

        # Find the series of locations/actions to go from the player location to the first piece of cheese
        path = self.traversal_algorithm.find_route(game_state.cheese[0])
        self.actions = maze.locations_to_actions(path)

    ##################################################################################

    def turn ( self,
               maze:       Maze,
               game_state: GameState,
             ) ->          Action:

        """
        *(This method redefines the method of the parent class with the same name).*

        It is called at each turn of the game.
        It returns an action to perform among the possible actions, defined in the ``Action`` enumeration.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        
        Returns:
            One of the possible actions.
        """

        # At each turn, we perform the next action in the list of actions
        return self.actions.pop(0)

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is provided during session 2 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session2/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import pprint

# PyRat imports
from pyrat import Game
from players.traversal_player import TraversalPlayer
from utils.traversal.bfs_traversal import BFSTraversal

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Instantiate a game with a few arguments
    game_config = {"mud_percentage": 0.0,
                   "maze_width": 13,
                   "maze_height": 10,
                   "nb_cheese": 1,
                   "random_seed": 2,
                   "trace_length": 1000}

    # Instantiate a game with specified arguments
    game = Game(**game_config)

    # Instantiate the player
    player = TraversalPlayer(BFSTraversal(), name="Factorized BFS")
    game.add_player(player)

    # Start the game
    stats = game.start()
    pprint.pprint(stats)

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is provided during session 2 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session2/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import pprint

# PyRat imports
from pyrat import Game
from players.traversal_player import TraversalPlayer
from utils.traversal.dfs_traversal import DFSTraversal

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Instantiate a game with a few arguments
    game_config = {"mud_percentage": 0.0,
                   "maze_width": 13,
                   "maze_height": 10,
                   "nb_cheese": 1,
                   "random_seed": 2,
                   "trace_length": 1000}

    # Instantiate a game with specified arguments
    game = Game(**game_config)

    # Instantiate the player
    player = TraversalPlayer(DFSTraversal(), name="Factorized DFS")
    game.add_player(player)

    # Start the game
    stats = game.start()
    pprint.pprint(stats)

##########################################################################################
##########################################################################################

Les fichiers bfs_traversal.py et dfs_traversal.py sont déjà fonctionnels. Regardez-les pour comprendre leurs différences.

Une fois terminé, lancez les scripts visualize_factorized_bfs.py et visualize_factorized_dfs.py (par exemple avec uv run games/visualize_factorized_bfs.py) pour exécuter des parties avec le nouveau joueur.

Tests

Les fichiers tests/test_bfs.py et tests/test_dfs.py testent les joueurs BFS et DFS, et ne s’appliquent pas directement aux classes BFSTraversal et DFSTraversal. En effet, l’interface a changé : traversal(...) ne renvoie plus les distances et la table de routage, mais les stocke dans les attributs distances et routing_table (que l’on lit avec get_distances(...) et get_routing_table(...)), et find_route(...) ne prend plus que la cible en argument.

Pour aller plus loin

Arrêter l’algorithme de parcours plus tôt

Pour calculer les informations nécessaires pour se déplacer vers le morceau de fromage, il suffit uniquement de savoir où se trouve ce fromage. Cependant, le BFS et le DFS sont des algorithmes qui explorent le graphe jusqu’à ce que tous les sommets soient visités.

Dans notre cas, tous les calculs effectués après avoir trouvé ce morceau de fromage sont inutiles, car vous n’allez pas utiliser ces résultats. Une amélioration possible consiste donc à modifier l’algorithme de parcours pour qu’il s’arrête dès que toutes les informations nécessaires sont disponibles.

Pour aller encore plus loin

Un parcours en profondeur récursif

Comme le parcours en profondeur utilise une pile, et que les fonctions récursives exploitent la pile d’appels de fonctions pour calculer un résultat, il est assez facile de programmer un DFS récursivement.

L’algorithme IDDFS

Une autre piste que vous pouvez explorer est de programmer un algorithme appelé IDDFS. Cet algorithme combine des aspects des algorithmes BFS et DFS : comme le BFS, il trouve un chemin avec le nombre minimal de déplacements, et comme le DFS, il n’a besoin que d’une mémoire proportionnelle à la profondeur explorée, bien moins que le BFS.

L’algorithme de Seidel

Alors que le BFS fournit le plus court chemin d’un sommet vers tous les autres, l’algorithme de Seidel permet d’obtenir les plus courts chemins entre tous les sommets dans un graphe non pondéré.