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 :

Voici un petit quiz d’auto-évaluation pour vérifier votre compréhension des articles :

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 enseignants dans votre classe.

Attribuer les rôles

La séance actuelle sera évaluée, et 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.

Comme décrit en bas de cette page, vous devrez télécharger une archive, qui inclut un fichier README.md. Dans ce fichier, vous devrez indiquer qui est responsable de quoi.

Activité pratique

Le reste de la séance sera consacré à une activité pratique visant à programmer les algorithmes étudiés dans les articles ci-dessus. Cliquez sur le lien ci-dessous :

Après le cours

Terminez l’activité pratique

Cette séance est évaluée. 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.

  • Créer une archive nommée etudiant1_etudiant2_etudiant3.zip, où etudiant1, etudiant2 et etudiant3 sont les noms de famille des membres de votre groupe. Cette archive doit être structurée comme suit :

    etudiant1_etudiant2_etudiant3.zip
|
|_ 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
|
|_ README.md

    Le README.md doit être un fichier texte formaté en Markdown. Téléchargez ce fichier pour l’utiliser comme base, et remplissez-le là où c’est demandé (remplacez tout ce qui est entre <...>).

  • L’étudiant responsable du code doit uploader cette archive sur Moodle avant le début de la séance 4.

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, 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 sur votre ordinateur, contenant un sous-dossier workspace.
    2. Placez dans workspace le contenu de votre archive (les dossiers players, games, etc.).
    3. Créez un environnement virtuel dans livrable et suivez les instructions d’installation des dépendances que vous avez écrites dans votre README.md.
    4. Dans un terminal, activez l’environnement virtuel que vous venez de créer, et lancez la commande python3 -c "import pyrat; pyrat.init_workspace('path/to/your/workspace')" (en adaptant avec le bon chemin et le bon exécutable python3).
    5. Ouvrez votre dossier livrable dans VSCode, et assurez vous que VSCode utilise l’environnement virtuel que vous venez de créer.
    6. Lancez vos scripts de jeu et de test, 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. Le nom de l’archive, l’organisation de son contenu et le contenu du fichier README.md doivent correspondre à nos exigences listées ci-dessus.

Préparer la prochaine séance

  • Consultez la section “Avant le cours” de la prochaine séance, et assurez-vous de faire tout ce qui est requis pour la préparer.
  • La prochaine séance commencera par un quiz évalué pour vérifier que vous avez compris les articles.