Pathfinding Using the Lee Algorithm

Overview

---

Goals

Students will create a simple implementation of the Lee algorithm for grid-based pathfinding using a simulated robot.

Learning Objectives

The main objective is to introduce the idea of pathfinding and its importance, as well as to demonstrate a simple algorithm that can be used for pathfinding. After creating their own implementation of the algorithm, the students will also understand its limitations (inefficiency and high resource consumption) and will be able see why optimization and the use of heuristics and better algorithms are important in practical applications.

Context

Pathfinding, i.e. navigating an object around obstacles toward a goal, is a crucial concept in many fields ranging from robotics to game development. This exercise will combine these two applications by inviting students to program a simple pathfinding algorithm in a game-like simulated environment involving a virtual robot who has to find its way to a goal on a two-dimensional grid containing obstacles. Similar to sorting, there are many algorithms that can be used for pathfinding, some of which are a better fit for certain tasks. Unlike sorting, the end result in pathfinding is not always the same: some algorithms may produce sub-optimal solutions (e.g. more steps needed to reach the goal), but consume fewer resources. It is thus important to understand such trade-offs when choosing to use a particular algorithm. To solve this specific problem, students will use the Lee algorithm (also known as the wave algorithm): a simple maze routing solution that always produces the optimal result, but consumes a considerable amount of resources in doing so. After creating their implementation, students will be able to discuss the advantages and shortcomings of the Lee algorithm, which will help them understand the trade-offs that must be considered in practical implementations of pathfinding.