Maze Algorithms

Maze Algorithms

11-13 yrs old

14-18 yrs old

Art and Design

Computer Science

Technology

This lesson was designed by Victor Rajewski, Footscray High School. It extends on the beginner Wall Follower Algorithm lesson to code maze solutions.

avatar Submitted By: Victorian Minecraft Innovators

April 27, 2021

Skills

  • Creativity
  • Critical Thinking

External References

Wall Follower Algorithm

Wall Follower Algorithm lesson by Philip Golden is to create simple wall follower algorithm using code which is then tested with the agent.

Learning Objectives

  • Students build mazes and program the Agent to solve them. Mazes and code are developed in increasing levels of sophistication.
  • • Become familiar with algorithms as a sequence of steps
  • • Break down a problem into a sequence of steps
  • • Introduction to loops for repeating instructions
  • • Introduction to branching (if/else)

Guiding Ideas

How do we follow, describe and represent a sequence of steps and decisions (algorithms) needed to solve simple problems?

Student Activities

Phase 1: Rectangular Room

  • This activity can be firstly done ‘unplugged’ with the teacher (or another student) as the agent, and students ‘programming’ them to walk around the room.
  • Build a room with 4 walls and an entry way.
  • Write a program to get the agent to walk around the outside of the room, and out the door. This will initially be a straight sequence (e.g. forward x3, left, forward x4, etc)
  • Modify your code to make the agent appear at a random place in the room, then be able to exit the room (this can use loops, but doesn’t need them)

Phase 2: Maze

  • Students create new flat world, then build a maze/labyrinth.
  • Optional - at the end of your maze, add a pressure plate which triggers fireworks or other event to show that the maze has been solved.
  • Write code to solve your maze
  • Optional - swap maze worlds with another student, write code to solve their maze

Phase 3: General Maze solving

  • Discuss and research how to solve a general maze. This can be done ‘unplugged’ like in Phase 1, using an irregular room (e.g. with a table jutting out from one of the walls)
  • Develop (either individually or as a class; depending on class abilities) an algorithm for doing this (i.e. following a wall). Will need to consider certain conditions (e.g. if wall left, if wall right, if wall ahead, if no walls, etc).
  • Create code for your agent to do this algorithm.
  • Test your code on your maze, then swap mazes with a few other students

    Further investigation:

  • Does it make a difference if the maze requires you to start/end in the centre?
  • Does your maze solving code solve all possible mazes?
  • Are there more efficient ways to solve the maze? Are there other tricks we could use (e.g. leave a trail to note where we’ve already been)

Performance Expectations

Students can:
•    Break down a problem into a sequence of steps
•    Use algorithms as a sequence of steps
•    Use loops for repeating instructions
•    Use branching (if/else)

Victorian Curriculum

These lessons provide opportunity for humanities/literature cross-curricular links, by providing a narrative for the maze challenges, questioning why humans like mazes and puzzles, linking to young adult literature e.g. Maze Runner.

Digital Technologies
•    Specification, algorithms and development
•    Creating digital solutions

Skills

  • Creativity
  • Critical Thinking

External References

Wall Follower Algorithm

Wall Follower Algorithm lesson by Philip Golden is to create simple wall follower algorithm using code which is then tested with the agent.