Computer Science · 12th Grade · Complex Algorithms and Optimization · Weeks 1-9

Pathfinding in Grids: Introduction to A*

Students explore pathfinding in grid-based environments, conceptually understanding how algorithms like A* find optimal paths by balancing cost and heuristic estimates.

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

About This Topic

A* (pronounced A-star) is the most widely used pathfinding algorithm in production applications, powering navigation in GPS systems, video game AI, and robotics. Unlike BFS, which explores nodes purely by distance from the source, A* uses a heuristic function to estimate the remaining distance to the goal and prioritizes nodes that appear most promising. This allows A* to find optimal paths far more efficiently than BFS in large search spaces by focusing exploration rather than spreading it uniformly.

At the 12th-grade level, students approach A* conceptually, focusing on the intuition behind informed search: the f(n) = g(n) + h(n) scoring function, where g(n) is the known cost from the start and h(n) is the estimated cost to the goal. Students explore how different heuristics, such as Manhattan distance for grid movement and Euclidean distance for free movement, affect which paths the algorithm explores first. The key constraint is admissibility: the heuristic must never overestimate the true remaining cost.

Active learning is productive here because A*'s decision-making process is spatial and visual. Working through grid-based examples manually helps students build intuition for why heuristic choice matters before the formal analysis.

Key Questions

1. How do pathfinding algorithms navigate complex environments?
2. Explain the role of heuristics in guiding a pathfinding algorithm.
3. Design a simple grid-based pathfinding problem and outline a strategy to solve it.

Learning Objectives

• Compare the efficiency of A* search to Breadth-First Search (BFS) on a given grid using cost and heuristic values.
• Analyze the impact of different heuristic functions (Manhattan, Euclidean) on the pathfinding process in a grid-based scenario.
• Design a simple grid-based pathfinding problem and articulate the steps an A* algorithm would take to solve it.
• Evaluate the admissibility of a given heuristic function for a specific grid pathfinding problem.

Before You Start

Graph Traversal Algorithms (e.g., Breadth-First Search)

Why: Students need a foundational understanding of how algorithms explore nodes in a graph or grid to grasp the improvements A* offers.

Basic Coordinate Systems and Distance Calculations

Why: Understanding how to calculate distances (like Manhattan or Euclidean) between points on a grid is essential for implementing heuristic functions.

Key Vocabulary

Pathfinding	The process of finding a sequence of steps or movements from a starting point to a destination, often in a constrained environment like a grid.
Heuristic Function (h(n))	An educated guess or estimation of the cost from a current node to the goal node, used to guide search algorithms like A*.
Cost Function (g(n))	The actual cost incurred to reach a current node from the starting node in a search algorithm.
Evaluation Function (f(n))	The sum of the cost function and the heuristic function (f(n) = g(n) + h(n)), used by A* to prioritize which node to explore next.
Admissible Heuristic	A heuristic function that never overestimates the actual cost to reach the goal, ensuring that A* finds the optimal path.

Watch Out for These Misconceptions

Common Misconception

A* always finds the path with the fewest steps.

What to Teach Instead

A* finds the path that minimizes total cost according to the g(n) cost function, which may represent distance, time, fuel, or any user-defined metric. If all edges have equal weight, minimizing cost and minimizing steps are the same thing, but A* is designed for weighted graphs where different paths have different costs. Changing edge weights changes which path A* considers optimal.

Common Misconception

A more informative heuristic always makes A* faster without any downside.

What to Teach Instead

A more informed heuristic reduces the nodes A* explores, but an inadmissible heuristic (one that overestimates remaining cost) can cause A* to miss the true optimal path. The trade-off between heuristic accuracy and admissibility is a genuine engineering concern. A heuristic that is close to perfect but occasionally overestimates can produce faster but suboptimal results.

Common Misconception

A* is just BFS with a priority queue.

What to Teach Instead

A* uses a priority queue like Dijkstra's algorithm, not BFS. The key difference from Dijkstra's is the heuristic h(n) that biases exploration toward the goal. Without the heuristic (h(n) = 0 for all nodes), A* reduces to Dijkstra's algorithm, which explores in all directions based on known cost alone. The heuristic is what makes A* an informed rather than uninformed search.

Active Learning Ideas

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.

35 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.

25 min·Pairs

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.

30 min·Whole Class

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.

25 min·Small Groups

Real-World Connections

• Video game developers use A* pathfinding to control non-player characters (NPCs), enabling them to navigate complex game maps, avoid obstacles, and move towards objectives realistically.
• Robotics engineers employ A* and similar algorithms for autonomous navigation, allowing robots to plan efficient routes in warehouses or hazardous environments while avoiding collisions.

Assessment Ideas

Quick Check

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.

Discussion Prompt

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?'

Exit Ticket

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.

Frequently Asked Questions

How is A* different from Dijkstra's algorithm?

Dijkstra's algorithm finds the shortest path from a source to all other nodes, expanding in order of known cost g(n) from the source. A* adds a heuristic estimate h(n) of the remaining cost to the goal, prioritizing nodes that appear closest to the destination. A* is more efficient when you need a path to a specific goal because it focuses exploration rather than computing distances to all nodes.

What makes a heuristic admissible in A*?

An admissible heuristic never overestimates the true remaining cost to the goal. This guarantees A* will find the optimal path because it never prematurely rules out the actual shortest route. Manhattan distance (sum of horizontal and vertical distances) is admissible for grid movement restricted to cardinal directions. Euclidean distance (straight-line distance) is admissible for movement that allows any direction.

What real-world applications use A* pathfinding?

A* is used in GPS navigation to find optimal driving routes, in video game AI to move characters around obstacles, in robotics for motion planning in known environments, and in network routing to find efficient data paths. Any application that needs the least-cost path to a specific goal in a graph where distance estimates are available can benefit from A* over simpler alternatives like BFS or Dijkstra's.

How does working through paper grid examples help students learn A*?

A* requires tracking multiple values (f, g, and h scores) for each candidate cell simultaneously, which is cognitively demanding from code alone. When students write these values on sticky notes placed on a paper grid, they can see the algorithm's priority decisions laid out spatially. Comparing the number of cells evaluated by A* versus BFS on the same grid makes the heuristic's efficiency benefit concrete and measurable.