Computer Science · 12th Grade

Active learning ideas

Pathfinding in Grids: Introduction to A*

Active learning works well for A* because pathfinding is a spatial and visual concept. Students need to see the trade-off between exploration and efficiency firsthand to grasp why heuristics matter. Paper grids and simulations make the abstract concrete, turning calculations into visible choices.

• Common Core State Standards
• CSTA: 3B-AP-12
• CCSS.ELA-LITERACY.RST.11-12.3

• 25–35 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Simulation Game
• 35 min · Pairs

Problem Solving: Paper Grid Pathfinding

Give student pairs a 6x6 grid on paper with obstacles marked. Students manually trace an A* search by calculating f, g, and h scores for each candidate cell on sticky notes. After finding the optimal path, they compare how many cells they evaluated versus a BFS approach on the same grid.

How do pathfinding algorithms navigate complex environments?

Facilitation Tip

During Paper Grid Pathfinding, walk the room to catch students who assign g(n) values incorrectly by miscounting steps or ignoring obstacles.

What to look for

Present students with a 5x5 grid, a start point, an end point, and a few obstacles. Ask them to manually calculate the g(n), h(n) (using Manhattan distance), and f(n) for the first three nodes A* would explore. Have them write down their calculations and the order of exploration.

• Apply
• Analyze
• Evaluate
• Create
• Social Awareness
• Decision-Making

Activity 02

• Think-Pair-Share
• 25 min · Pairs

Think-Pair-Share: Heuristic Trade-Off Analysis

Present three heuristics for grid pathfinding: h(n) = 0 which reduces to Dijkstra's, Manhattan distance, and Euclidean distance. Pairs trace how each heuristic changes which nodes get explored on a small grid with diagonal versus cardinal-only moves. Groups share how heuristic choice affects both the path found and the number of cells examined.

Explain the role of heuristics in guiding a pathfinding algorithm.

Facilitation Tip

In Heuristic Trade-Off Analysis, assign pairs with opposite heuristic views so they must defend their choices using their calculations.

What to look for

Pose the question: 'Imagine you are designing a navigation app for a city with many one-way streets and traffic lights. How would you choose an admissible heuristic for A*? What challenges might arise if your heuristic is not admissible?'

• Understand
• Apply
• Analyze
• Self-Awareness
• Relationship Skills

Activity 03

• Simulation Game
• 30 min · Whole Class

Simulation Game: The A* Priority Race

Set up a physical grid with desks representing nodes. Student volunteers hold cards with their f scores and represent the open set. The class must always select the volunteer with the lowest f score to expand next. As expansions proceed, students observe the algorithm narrowing its focus toward the goal.

Design a simple grid-based pathfinding problem and outline a strategy to solve it.

Facilitation Tip

For The A* Priority Race, set a visible timer to emphasize how the priority queue changes exploration order in real time.

What to look for

Provide students with a scenario where a heuristic function is proposed for a grid. Ask them to determine if the heuristic is admissible and to justify their answer with a brief explanation, referencing the definition of an admissible heuristic.

• Apply
• Analyze
• Evaluate
• Create
• Social Awareness
• Decision-Making

Activity 04

• Gallery Walk
• 25 min · Small Groups

Gallery Walk: Admissible vs. Inadmissible Heuristics

Post examples of pathfinding scenarios where different heuristics are used, including at least one inadmissible heuristic that overestimates. Students annotate which heuristics are admissible, which produce optimal paths, and which yield only fast-but-suboptimal results. Class discussion connects admissibility to guaranteed optimality.

How do pathfinding algorithms navigate complex environments?

Facilitation Tip

During Admissible vs. Inadmissible Heuristics, ask groups to post their grids with clear labels so misconceptions are visible to all during the walk.

What to look for

Present students with a 5x5 grid, a start point, an end point, and a few obstacles. Ask them to manually calculate the g(n), h(n) (using Manhattan distance), and f(n) for the first three nodes A* would explore. Have them write down their calculations and the order of exploration.

• Understand
• Apply
• Analyze
• Create
• Relationship Skills
• Social Awareness

A few notes on teaching this unit

Teach A* by starting with a simple grid and labeling g(n), h(n), and f(n) for every node at each step. Use color-coding to show which nodes are in the open set, closed set, and the final path. Avoid rushing to the algorithm’s definition before students see why heuristics reduce exploration. Research shows that students grasp informed search better when they first experience uninformed search’s inefficiency, so consider having them run BFS on the same grid before introducing A*.

By the end of these activities, students should explain how g(n), h(n), and f(n) guide A*’s decisions and compare its efficiency to uninformed searches. They should also justify heuristic choices and identify when a heuristic is or isn’t admissible.

---

Watch Out for These Misconceptions

• During Paper Grid Pathfinding, watch for students who assume the path with the fewest steps is always optimal, even when edge weights vary.

  During Paper Grid Pathfinding, point to a grid with varying edge costs and ask students to recalculate g(n) using the given weights. Have them compare total costs of different paths to show that minimizing steps isn’t always the same as minimizing cost.

• During Heuristic Trade-Off Analysis, watch for students who think a more informative heuristic is always better, without considering admissibility.

  During Heuristic Trade-Off Analysis, provide an inadmissible heuristic example (e.g., Euclidean distance on a grid with diagonal movement costs). Ask pairs to run the heuristic on their grids and observe how A* misses the optimal path, then discuss why admissibility matters.

• During The A* Priority Race, watch for students who confuse A* with BFS because both use a queue or priority structure.

  During The A* Priority Race, pause the simulation and ask students to compare the order in which nodes are explored when h(n) is set to zero versus when it uses a heuristic. Have them note how Dijkstra’s behavior emerges when the heuristic is removed.

---

Methods used in this brief

• Simulation Game
• Think-Pair-Share
• Gallery Walk