Catch a single piece of cheese... with mud

Duration2h30 + preparation

Presentation & objectives

In this session, we slightly increase the difficulty by introducing mud inside the maze. Two adjacent locations in the maze that are separated with mud require more than one unit of time to reach, and therefore cause the character to slow down. While the BFS algorithm seen in the previous session had the property to find the shortest path in an unweighted graph, this is not the case anymore. Therefore, we introduce Dijkstra’s algorithm, that can find the shortest path in a weighted graph. To implement it, we need to introduce a new data structure called the min-heap.

The notions above are covered by a few articles that you have to study before the class. In the practical activity, you will have to program Dijkstra’s algorithm, so that your character can move from a location to another in a maze with mud.

Important

The content of this session will be evaluated. Check the details at the end of this page.

Before the class

Technical requirements

To be able to start working on the activity, you should meet the following requirements:

Prior knowledge acquisition

To be able to start the practical activity efficiently, we introduced some needed concepts at the end of the previous session. Here are the slides used in class:

These slides only cover the main elements of the course, and many more details are given in the associated articles. Thus, you should study the following articles at home after before the session:

You can verify your understanding of these articles here:

During the class

Quiz

At the very beginning of the session, we start with an evaluated Wooclap quiz to check your understanding of the articles you had to study. The link will be given by the teacher at the beginning of the class. Make sure to be there on time!

Attribute roles

The current session will be evaluated, and you will not all be evaluated on the same aspects, as mentioned on the project main page. Before starting the practical activity, discuss with your group to decide who will be in charge of:

  • The code quality.
  • The documentation.
  • The unit tests.

As described at the end of this page, you will have to upload an archive, that includes a README.md file. In this file, you will have to indicate who is responsible of what.

Practical activity

The class is dedicated to a practical activity. Once you are done with all the things above, click on the link below to start:

After the class

Complete the current session

This session is evaluated. The modality of evaluation is described on the project main page. Before the next session, you should thus:

  • Review the contents of the articles above.

  • Complete the non-optional parts of the practical activity.

  • Create an archive named student1_student2_student3.zip, where student1, student2 and student3 are the family names of the members of your group. This archive should be structured as follows:

    student1_student2_student3.zip
|
|_ games
|  |_ # Put your game scripts here
|
|_ players
|  |_ # Put your players here
|
|_ tests
|  |_ # Put your unit tests here
|
|_ utils
|  |_ # Put your additional codes here (if any)
|
|_ data
|  |_ # Put your other files here (if any)
|
|_ README.md

    The README.md should be a text file formatted in Markdown. Download this file to use as a basis, and fill it where asked (replace everything in <...>).

  • The student responsible of the code should upload this archive on Moodle before the start of session 4.

Important

In addition to the quality of the code, the documentation and the unit tests, we will also evaluate your ability to produce a deliverable. In other words, pay attention to the following important elements:

  • We are going to unzip your archive, and use it as a workspace in Visual Studio Code. Your code should work directly, i.e., running a script in the games or tests directories should create a game or perform tests without any intervention on our side. You should ensure that by testing this in a new Visual Studio Code workspace before uploading your code on Moodle.

  • We will evaluate your ability to produce a deliverable according to given directives. Consider that we are a client to which you send a piece of software you had to produce. The name of the archive, the organization of its contents, and the content of the README.md file should match our requirements listed above.

Prepare the next session

  • Check the “Before the class” section of the next session, and make sure you do everything required to prepare it.
  • The next session will start with an evaluated quiz to check that you have understood the articles.