MazeLesson-554x368.png

Wall Follower Algorithm

8-10 yrs old

11-13 yrs old

Computer Science

The goal of this lesson is to implement a simple wall follower algorithm using code connection. The implementation is then tested with the agent.

avatar Submitted By: Philip Golden

February 16, 2018

Skills

  • Creativity
  • Critical Thinking

External References

Wall Follower World (*.mcworld)

This is a modification of the 'Blocks of Grass' world with a simple maze added

Example Solution using Makecode (Code Connection)

This code can be used to implement the original algorithm. The additional teleport command is used to bring the agent to the start of the maze.

Learning Objectives

  • Understanding Algorithms: A key goal is that the students understand an algorithm as a sequence of steps of solve a problem. They will take steps to evaluate the algorithm, and debug any unexpected results. Progressions involve coming up with new algorithms with novel features
  • Logical thinking: Both the core exercise and progressions involve analysis and prediction
  • Creativity: Although the initial phase of the lesson involves implementing a known algorithm, the final progression promotes highly creative and lateral thinking

Guiding Ideas

Why does the wall follower algorithm work?

Does it matter which way the agent is facing at the start?

Could the agent follow the left hand wall instead?

Can you think of a maze for which the wall follower would not work? What could you do in this case?

How else could the agent be programmed to get to the exit of the maze?

Student Activities

1) Each student starts in their own world, and opens code connection (MakeCode is used for the example solution)

2) Students read the instructions on the boards beside the spawning point and implement the algorithm described using code connection (it is easiest to do this outside the maze so you can see the instructions)

3) Once the algorithm is in place, try it out and debug and issues. Remember that debugging is one of the most important skills in computing! Do not worry at all if the first attempt is not successful

4) Once the algorithm is working, try starting the agent at the beginning, and quickly spawning a villager at the same point. See who can exit the maze first. Is the villager using an algorithm? Try with different mobs (cows, sheep etc.).

5) Progression 1: Can you implement a similar algorithm where the agent follows the wall on the left instead?

6) Progression 2: How else could the agent be programmed to get to the exit? Possible solutions include teleporting directly to the exit, moving up 3 and simply walking over the maze, using a 'clear' function to destroy the maze and simply walk to the exit. Are these valid solutions to the problem (discuss)?

Performance Expectations

Students should understand that an algorithm is a series of steps that is used to solve a problem. They should have some confidence to implement an algorithm in code, and then evaluate and debug it. Students who complete the first progression should achieve a deeper understanding of the above by creating their own algorithm. The final progression is intended to encourage lateral thinking, and ideally can engage students who may not have been among the first to finish their code. Some of the questions are intentionally open, and can hopefully inspire interesting discussions.

Practical point: in order to program the agent, students will need to have worldbuilder ability (/ability @a worldbuilder true) and operator status (/op @a). Unfortunately this means that they can accidentally destroy the instructions board quite easily, so it is probably a good idea to have it visible in the classroom if possible!

Skills

  • Creativity
  • Critical Thinking

External References

Wall Follower World (*.mcworld)

This is a modification of the 'Blocks of Grass' world with a simple maze added

Example Solution using Makecode (Code Connection)

This code can be used to implement the original algorithm. The additional teleport command is used to bring the agent to the start of the maze.