Attraper 1 fromage avec de la boue

Durée2h30 + préparation

Objectifs de la séance

Dans cette séance, nous augmentons légèrement la difficulté en introduisant de la boue dans le labyrinthe. Si deux cases adjacentes dans le labyrinthe sont séparées par de la boue, il faut plus d’un tour pour passer de l’une à l’autre, ce qui ralentit le personnage.

L’algorithme BFS vu lors de la séance précédente avait la propriété de trouver le chemin le plus court dans un graphe non pondéré, mais il ne garantit rien dans un graphe pondéré. Nous introduisons donc l’algorithme de Dijkstra, qui permet de trouver le chemin le plus court dans un tel graphe. Pour l’implémenter, nous devons introduire une nouvelle structure de données appelée le tas min (min-heap).

Les notions ci-dessus sont couvertes par quelques articles que vous devez étudier avant le cours. Dans l’activité pratique, vous devrez programmer l’algorithme de Dijkstra, afin que votre personnage puisse se déplacer d’une case à une autre dans un labyrinthe avec de la boue.

Important

Le contenu de cette séance sera évalué. Consultez les détails en bas de cette page.

Avant le cours

Pré-requis

Pour pouvoir commencer à travailler sur l’activité, vous devez remplir les conditions suivantes :

Articles à étudier

Pour pouvoir commencer à travailler efficacement sur l’activité pratique de cette séance, vous devez étudier les articles suivants avant d’arriver en classe :

  • Dans cet article, vous apprendrez ce qu'est un tas min (min-heap), une structure de données avec des propriétés particulières.

    15 min de lecture

Pendant le cours

Quiz Wooclap

Comme pour les autres cours en classes inversées, nous commencerons la séance par un petit quiz Wooclap pour vérifier votre compréhension des notions, et discuter de vos interrogations. Le lien sera fourni par les enseignant(e)s dans votre classe.

Attribuer les rôles

La séance 3 est évaluée. Vous ne serez pas tous évalués sur les mêmes aspects, comme mentionné sur la page principale du projet. Avant de commencer l’activité pratique, discutez avec votre groupe pour décider qui sera responsable de quelle partie du livrable :

  • Qualité du code.
  • Documentation.
  • Tests unitaires.

Activité pratique

  • Cette activité étend la précédente en proposant d'implémenter de nouveaux algorithmes de parcours de graphe, qui permettent de trouver des chemins dans un graphe pondéré.

    2h30

Après le cours

Terminer l’activité pratique

Cette séance est évaluée. Vous devez rendre un livrable décrit ci-dessous avant le début de la séance 4. Ce livrable devra contenir vos productions pour cette séance, répondant aux consignes données dans l’activité pratique.

Information

Si vous avez été plus loin que le minimum requis, n’hésitez pas à inclure ces éléments supplémentaires dans votre rendu, qui seront pris en compte dans l’évaluation.

Toutefois, veuillez ne pas fournir de code ou de documentation hors sujet par rapport à cette séance, ni votre environnement virtuel ou des fichiers temporaires.

La modalité d’évaluation est décrite sur la page principale du projet. Avant la prochaine séance, vous devez donc :

  • Revoir le contenu des articles ci-dessus.

  • Compléter les parties non optionnelles de l’activité pratique.

  • Vérifier que votre enseignant(e) est bien membre de votre dépôt GitLab avec le rôle Maintainer, comme demandé lors de la séance 1. Sans cela, nous ne pourrons pas récupérer votre travail, et votre livrable ne pourra pas être évalué.

  • Vérifier que votre dépôt est organisé comme suit (c’est l’organisation de votre pyrat_workspace) :

    pyrat_workspace
|
|_ games
|  |_ # Placez vos scripts de jeu ici
|
|_ players
|  |_ # Placez vos joueurs ici
|
|_ tests
|  |_ # Placez vos tests unitaires ici
|
|_ utils
|  |_ # Placez vos codes supplémentaires ici (si nécessaire)
|
|_ data
|  |_ # Placez vos données ici (si nécessaire)
|
|_ ... # Tout autre répertoire que vous jugez pertinent à ajouter
|
|_ pyproject.toml # Le fichier qui déclare les bibliothèques dont votre code a besoin
|
|_ uv.lock        # Le fichier qui fixe les versions exactes de ces bibliothèques
|
|_ README.md
    Important

    Les fichiers pyproject.toml et uv.lock doivent être versionnés : sans eux, nous ne pourrons pas recréer l’environnement dans lequel votre code fonctionne. À l’inverse, le dossier .venv et les dossiers __pycache__ ne doivent jamais apparaître sur GitLab : le .gitignore fourni par PyRat s’en charge, ne le supprimez pas.

    Le fichier README.md, à la racine de votre dépôt, doit être formaté en Markdown, avec le contenu suivant (remplacez les parties entre chevrons par les informations appropriées) :

    ​
    # Étudiants

- Responsable des codes : <votre nom ici>
- Responsable de la documentation : <votre nom ici>
- Responsable des tests unitaires : <votre nom ici>

# Joueurs

*Quels sont les joueurs implémentés dans le répertoire `players` ?*
*Précisez quels choix vous avez faits, et pourquoi.*
*Si vous avez choisi de créer des fonctions, lesquelles et pourquoi ?*
*Quelle est la complexité de ces fonctions ?*
*Avez-vous utilisé la programmation défensive ? Si oui, où et comment ?*

<détaillez ça ici>

# Jeux

*Que font les scripts que vous avez fournis ?*
*Avez-vous modifié certains paramètres du jeu ? Si oui, lesquels et pourquoi ?*

<détaillez ça ici>

# Tests unitaires

*Quels tests unitaires avez-vous réalisés ?*
*Testez-vous certains cas d'erreur ?*
*Y a-t-il des tests manquants que vous auriez aimé réaliser ?*

<détaillez ça ici>

# Utilitaires

*Avez-vous fourni quelque chose dans le répertoire `utils` ?*
*Quels sont ces fichiers ? À quoi servent-ils ?*

<détaillez ça ici>

# Documentation

*Quelque chose à dire concernant la documentation ?*

<détaillez ça ici>

# Autres

*Avez-vous fait des analyses intéressantes ?*
*Votre code a-t-il des dépendances particulières que nous devrions installer ?*
*Autre chose à ajouter ?*

<détaillez ça ici>

  • Pousser votre travail sur GitLab avec git push, puis relever l’identifiant du commit qui correspond à votre livrable. Cet identifiant (ou hash) est la suite de caractères qui désigne de façon unique une version de votre dépôt. Vous l’obtenez avec la commande git log -1 depuis votre workspace, ou dans le menu Code > Commits de votre projet GitLab.

  • L’étudiant(e) responsable du code doit déposer sur Moodle, avant le début de la séance 4 :

    • l’URL de clonage de votre dépôt GitLab ;
    • l’identifiant du commit à évaluer.
    Important

    C’est exactement cette version de votre dépôt que nous évaluerons : les commits suivants ne seront pas pris en compte. Vérifiez donc que le commit annoncé est bien poussé sur GitLab (il doit être visible depuis la page du projet), et qu’il contient bien tout le travail que vous voulez nous montrer.

Important

En plus de la qualité du code, de la documentation et des tests unitaires, nous évaluerons également votre capacité à produire un livrable. En d’autres termes, faites attention aux éléments importants suivants :

  • Votre code doit fonctionner directement, c’est-à-dire qu’exécuter un script dans les répertoires games ou tests doit lancer une partie ou effectuer des tests sans aucune intervention de notre part. Pour cela, suivez les instructions suivantes (ce sont les mêmes que nous suivrons pour vous évaluer) :

    1. Créez un dossier livrable_1 vide sur votre ordinateur, ailleurs que dans votre workspace habituel.

    2. Depuis ce dossier, clonez votre dépôt et placez-vous sur la version annoncée sur Moodle :

      git clone <url de clonage du projet GitLab>
cd pyrat_workspace
git checkout <identifiant du commit>

    3. Dans un terminal, placez-vous dans le dossier pyrat_workspace ainsi obtenu, et lancez la commande uv sync. Cette commande recrée l’environnement virtuel, y installe PyRat ainsi que les bibliothèques déclarées dans votre pyproject.toml, et installe votre workspace lui-même, ce qui rend vos programmes importables entre eux. C’est votre pyproject.toml, qui est versionné, qui rend cette étape automatique : veillez donc à bien le pousser sur le dépôt.

    4. Si votre code a besoin d’autres bibliothèques, elles doivent avoir été ajoutées à votre projet avec uv add (elles apparaissent alors dans pyproject.toml) et être mentionnées dans votre README.md. Nous n’installerons rien à la main.

    5. Ouvrez ce dossier pyrat_workspace dans VSCode, et assurez vous que VSCode utilise l’environnement virtuel .venv de ce dossier.

    6. Lancez vos scripts de jeu et de test (par exemple uv run games/visualize_dijkstra.py et uv run tests/test_dijkstra.py depuis le dossier pyrat_workspace), et vérifiez que tout fonctionne correctement.

  • Nous évaluerons votre capacité à produire un livrable conforme aux directives données. Considérez que nous sommes un client à qui vous envoyez un logiciel que vous deviez produire. L’organisation de votre dépôt et le contenu du fichier README.md doivent correspondre à nos exigences listées ci-dessus.

Préparer la prochaine séance

  • Consulter la section « Avant le cours » de la prochaine séance, et vérifier que vous avez bien tout fait pour la préparer.
  • La prochaine séance commencera par un quiz afin de vérifier que vous avez compris les articles.