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

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

• Apportez votre propre ordinateur.
• Assurez-vous d’avoir une connexion réseau fonctionnelle.

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 :

• Algorithme de Dijkstra.
• Tas min.

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

• Quiz d’auto-évaluation.

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 :

• Activité pratique.

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, avec le contenu suivant (remplacez les parties entre chevrons par les informations appropriées) :

  ​

  README.md

  # Étudiants
  
  - Responsable des codes : <votre nom ici>
  - Responsable de la documentation : <votre nom ici>
  - Responsable des tests unitaires : <votre nom ici>
  
  - Lien du dépôt GitHub/GitLab : <lien 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
  
  *À quoi servent les scripts dans le répertoire `games` ?*
  *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>

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

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.