Path Search vs. Heuristics (Key Stage 3 / GCSE)

1. Lesson Objective

Describe how search algorithms navigate mazes, contrasting blind search with heuristic-guided search (A*).

2. Workshop Overview

Students build custom mazes on the A* Pathfinding Cabinet, step through the algorithm cell-by-cell, and calculate f, g, and h scores.

3. Scheduled Lesson Steps

1. 1

   Concept Intro

   Draw a grid maze on the blackboard. Explain how a robot can find the exit. Introduce the formula: f = g + h.

2. 2

   Interactive Lab

   Launch the A* Pathfinding Cabinet. Set up a simple obstacle. Have students click 'Step' to watch the search expand.

3. 3

   Calculation

   Pause the stepping and ask students to calculate the 'h' cost (straight-line distance, ignoring walls) and 'g' cost (steps from start) for a specific node.

4. 4

   Discussion

   How did A* help Shakey the Robot in 1968 navigate rooms? Compare this to GPS navigation apps today.