Attraper 1 fromage avec de la boue

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.

Avant le cours

Pré-requis

• Assurez-vous d’avoir un algorithme BFS qui fonctionne (cf. séance 2).

Articles à étudier

• Algorithme de Dijkstra

  Dans cet article, vous apprendrez à naviguer dans un graphe pondéré.

  20 min de lecture

• Tas min

  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

• Quiz d’auto-évaluation

  Ces quiz sont là pour vous permettre de vérifier que vous avez compris les articles à étudier.

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 tou(te)s évalué(e)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

• Activité pratique

  Cette activité prolonge la précédente : vous allez programmer un nouvel algorithme de parcours, l'algorithme de Dijkstra, qui permet de trouver des plus courts chemins dans un graphe pondéré.

  2h30

Après le cours

Terminer l’activité pratique

• Si besoin, révisez les articles de cette séance.
• Terminez les parties obligatoires de l’activité pratique.
• Préparez le livrable mentionné ci-dessous.

Évaluation

Ce qui est évalué

Cette séance clôt la première partie du projet, qui vise à attraper un unique morceau de fromage dans le labyrinthe. Avant le début de la séance 4, vous devrez rendre un livrable contenant les codes que vous aurez produits jusque-là pour répondre à cet objectif (séance 3 incluse).

La modalité d’évaluation est décrite sur la page principale du projet. Une grille d’évaluation est également donnée plus bas sur cette page.

Comment rendre le livrable

Ces codes seront à rendre de la manière suivante :

• Renseignez le fichier README.md de votre projet avec le contenu suivant (remplacez les éléments entre chevrons <...> (chevrons inclus) par ce qui est demandé). Vous pouvez intégrer des images ou schémas si nécessaire, par exemple si vous avez fait des analyses de vos programmes. Référez-vous à la documentation du langage Markdown si nécessaire.

  Important

  SVP allez droit au but, un fichier README.md n’est pas un rapport de projet, c’est un document court qui permet à son lecteur de comprendre rapidement le contenu du dépôt.

  # Étudiant(e)s
  
  - Responsable de la qualité du code : <votre nom ici>
  - Responsable de la documentation : <votre nom ici>
  - Responsable des tests unitaires : <votre nom ici>
  
  # Players
  
  *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 annexes, 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>
  
  # Games
  
  *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
  
  *Quels tests unitaires avez-vous réalisés ?*
  *Comment les avez-vous réalisés ?*
  *Quels aspects du code avez-vous testés ?*
  *Lesquels pourraient manquer ?*
  
  <détaillez ça ici>
  
  # Qualité du code
  
  *Comment avez-vous organisé vos fichiers ?*
  *Comment avez-vous documenté votre code ?*
  *Comment avez-vous géré les erreurs ?*
  
  <détaillez ça ici>
  
  # Améliorations optionnelles
  
  *Quelles parties optionnelles des séances avez-vous faites ?*
  *Avez-vous fait des analyses intéressantes de vos programmes ?*
  *D'autres choses à ajouter ?*
  
  <détaillez ça ici>
  
  # IA Générative
  
  *Quelle a été votre utilisation de l'IA générative ?*
  *Pour quelles parties du travail l'avez-vous utilisée ?*
  *Dans quels buts ?*
  *Quels modèles avez-vous utilisés ?*
  
  <détaillez ça ici>

• Vérifiez bien que vous avez envoyé tous vos codes et le README.md sur le dépôt GitLab de votre équipe.

  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. Mentionnez-le dans le README.md.

• Assurez-vous 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.

• L’étudiant(e) en charge de la qualité du code doit se connecter sur Moodle, et fournir :

  • l’URL HTTPS de clonage de votre dépôt GitLab :
  • l’identifiant du commit à évaluer :

Comment nous allons l’évaluer

Afin de vous évaluer, nous allons procéder comme suit :

• Tout d’abord, nous allons cloner votre dépôt GitLab, au commit indiqué :

  git clone <url_de_votre_depot_git>
  cd <nom_du_depot>
  git checkout <identifiant_du_commit>

• Ensuite, nous allons recréer un environnement adapté au projet, en nous basant sur le pyproject.toml que vous avez fourni, et en nous assurant que les dépendances sont correctement installées :

  uv sync

• Enfin, nous allons ouvrir le dossier de votre projet dans VS Code, lire votre fichier README.md, et exécuter vos scripts et tests.

Remarques très importantes

• Veuillez ne pas fournir de code ou de documentation hors sujet (mention de fonctions inexistantes, etc.)

• Attention à ce que vous mettez sur votre dépôt GitLab : n’y mettez que ce qui est nécessaire. Vous ne devez pas y mettre votre environnement virtuel ou des fichiers temporaires.

• 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 et vos tests doivent fonctionner (reproduisez la manière dont nous allons l’évaluer pour vérifier que tout va bien).
  • Assurez-vous que le livrable est complet et correspond à ce qui est demandé.

• On vous demande de renseigner votre usage de l’IA dans le fichier README.md. SVP soyez honnêtes et précis (modèles utilisés, méthode, etc.). Le but est de comprendre comment vous avez travaillé et de nous adapter aux besoins futurs.

• Toutefois, si l’IA est autorisée pour vous aider dans votre projet, vous restez responsables de votre livrable, qui doit correspondre à ce qui est demandé. En conséquence, un projet présentant un trop grand nombre d’incohérences, d’éléments hallucinés, ou ne correspondant pas à ce qui est demandé sera sanctionné par une note de 0/20.

Grille d’évaluation

Comme indiqué sur la page principale du projet, l’évaluation comporte une partie commune et une partie différenciée. Pour fournir une note pour ces différentes parties, nous allons utiliser la grille suivante :

Préparer la prochaine séance

• Consultez la section « Avant le cours » de la prochaine séance, et vérifiez 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.