Pathfinding lab · Grades 6–12

Rescue Grid: The A* Mission

Guide the rover to the beacon, then race five search strategies on the same map to see which one finds the cheapest route — and how much work each one does.

Navigate across the Martian surface to reach the rescue beacon while avoiding craters and slow sand zones.

Can you find the cheapest route?

Predict a route, then Run search. The rover moves up, down, left, or right. Each tile entered costs: Open ground 1 Sand 3 Craters Blocked

Choose a map
Paint
How to edit the map

Choose a tool, then tap or drag across tiles. Keyboard: focus the map, use the arrow keys to choose a tile, then press Enter to paint. Pause the search before editing.

Mission map 12 × 8Ready to explore

Build your grid, then run the mission.

0 / 0
  • Rover (Start)
  • Beacon (Goal)
  • Debris (Blocked)
  • Sand (Cost 3)
  • Waiting to check · ring
  • Checked · dot
  • Final route
  • Checking now · crosshair

Algorithm race: same map, five strategies

Every run races all five strategies on your current map. Shorter bars mean less work. Only some strategies promise the cheapest route. Choose a name to watch that strategy explore.

Strategy Cells checked Route cost Cheapest?
A* · grid steps———
A* · straight line———
Dijkstra———
Greedy best-first———
Breadth-first (BFS)———

Try it. Change it. Explain it.

1 · Find a detour

Run First contact and write down the route cost. Paint one crater on the route, then run again. Which way did the rover go? Why did the cost change?

2 · Steps or cost?

Load Sand shortcut. Look at the race: BFS finds the route with the fewest steps, but is it the cheapest? Count the cost of each route by hand to explain the difference. Then erase the sand. Does BFS catch up?

3 · Fast or right?

Greedy usually checks the fewest cells. Build a map where Greedy's route costs more than A*'s. (Hint: put a wall with a gap on the far side.) What does A* do that Greedy doesn't?

Ready for a bigger challenge?

Open the Controls panel. In Fuel Critical mode, set a cost budget below your route cost, then raise it until a route appears. In Dynamic Obstacles mode, watch the map change and the search start again. How could reusing earlier work help a real robot?

The Mario theme adds gravity and jumps, so its movement rules and estimates differ from the rover grid. Compare its results with Dijkstra before assuming a route is cheapest.

Explain your result: “I changed ___. With ___, the route cost changed from ___ to ___ and it checked ___ cells. I think this happened because ___.”

Go deeper

What Is Pathfinding?

What Is Pathfinding?

Pathfinding is the problem of finding a route between two points through a space that has obstacles, costs, or rules attached to it. That space might be a grid on a screen, a road network, a warehouse floor, or the inside of a computer chip — the algorithm doesn't care what the "space" represents, only how it's connected.

In Software

Every time a map app reroutes you around traffic, a game character walks toward you around a wall, or a delivery app schedules stops on a route, pathfinding is running underneath. It's also inside tools you wouldn't expect: network routers use pathfinding-style algorithms to decide how a data packet hops from server to server, and chip designers use it to route the microscopic wires connecting a processor's components without letting any two cross.

In Hardware

A warehouse robot planning a route between shelves, a robot vacuum mapping a room, a drone weaving between obstacles, and a factory arm avoiding a collision are all solving a pathfinding problem — but now a wrong answer costs real time, real hardware, or a real collision instead of a wasted frame. Hardware pathfinding also usually has to run continuously as the world changes, not just once at the start.

Example: a robot vacuum doesn't want the shortest path — it wants a path that covers every open patch of floor. That's a coverage problem: the same map, but a very different question.

An original iRobot Roomba robot vacuum on a floor
A different goal on the same mapA robot vacuum needs to cover the whole room, not just reach one spot. Same grid, different question. Larry D. Moore · CC BY 4.0 · Wikimedia Commons
NASA's Curiosity rover self-portrait on the Martian surface at the Big Sky drilling site
A real rover on real terrainNASA's Curiosity rover plans safe routes across Martian rock and sand — the same rover-and-terrain idea behind this lab's Mars theme. NASA/JPL-Caltech/MSSS · public domain · Wikimedia Commons

Biomimicry: Borrowing From Nature

Some of the best pathfinding ideas were discovered by biologists, not computer scientists. Ants leave pheromone trails that evaporate over time, so shorter round-trips get reinforced faster than long ones — a decentralized way for a whole colony to converge on an efficient path, now used in ant colony optimization for shipping and network routing. Slime mold, given oat flakes arranged like a map's cities, grows a network of tubes that closely mirrors real-world rail systems, because it prunes inefficient connections as it grows. Flocking birds and schooling fish navigate collision-free as a group using only simple local rules, which is the same idea behind "boid" simulations that give game crowds and swarms of robots believable, coordinated movement without any one member planning the whole route.

Close-up photo of ants tending brood in a colony
No single ant plans the routeAn ant colony finds efficient paths through the shared, decentralized behavior of many individual ants, not a leader plotting a course. Insects Unlocked, UT Austin · CC0 (public domain dedication) · Wikimedia Commons
Yellow slime mold spreading in branching tubes across a surface
A network with no brainSlime mold keeps the tubes that carry food well and lets weak ones shrink. In a 2010 experiment, its network looked a lot like the Tokyo rail system. frankenstoen · CC BY 2.5 · Wikimedia Commons
A huge flock of starlings forming a swirling cloud shape in the evening sky
Thousands of birds, no collisionsEach starling only watches its nearest neighbors. Simple local rules add up to a group that moves as one. Walter Baxter · CC BY-SA 2.0 · Wikimedia Commons
Why Pathfinding?

Why Pathfinding?

Pathfinding shows up any time something needs to move — or spread — intelligently through a space. It's one of the most common sources of real complexity in a student game project, and it's rarely just one question.

Five Different Questions

"Pathfinding" is really a family of related problems, and picking the right one saves a lot of wasted effort:

  • ConnectivityAre these two locations connected at all?
  • ReachabilityWhat are all the locations connected to this one?
  • Any pathFind some path between two locations — it doesn't need to be good.
  • Fewest stepsFind the path between two locations with the fewest steps.
  • Lowest costFind the path between two locations with the lowest total cost, when steps aren't all equal.

Case Study: Hedge Mazes

A hedge maze is a graph you can walk through. The old “keep one hand on the wall” trick is really a depth-first search. It always gets you out of a maze whose walls all connect, but it can take a very long route.

Aerial view of the large hedge maze at Longleat, England
A graph made of hedgesEvery junction is a node and every corridor is an edge. Can you spot which corridors are dead ends? Rurik · public domain · Wikimedia Commons

Case Study: Pac-Man

Ghosts chasing Pac-Man, creepers in Minecraft, or units routing between cities in a strategy game all need one or more pathfinding algorithms just to move believably. This is usually baked into the "minimum viable product" for any game with intelligent enemies — it isn't an optional extra.

Case Study: Floodfill

Not every use of pathfinding looks like a maze. In a bubble-shooter game, popping a bubble destroys every same-colored bubble connected to it — and separately checks whether any bubbles are still connected to the ceiling. Both checks are pathfinding in disguise. The same idea is the paint-bucket tool in an image editor: "fill everything connected to this pixel" is a reachability search, usually called floodfill.

Example: in Minecraft, water poured on flat ground spreads to every open neighbor block, then their neighbors, until it runs out of reach. That's floodfill you can watch.

Graphs: The Map Behind the Maze

Graphs: The Map Behind the Maze

Every pathfinding algorithm searches a graph — a set of nodes (locations) connected by edges (connections between them). How you build that graph from your actual problem determines which algorithm fits.

Directed vs. Undirected

An edge is undirected when it works both ways — like a hallway you can walk down in either direction. It's directed when it only works one way, like a one-way street.

Weighted vs. Unweighted

A graph is unweighted when every edge costs the same to cross. It's weighted when some edges cost more than others — a longer street, a slower terrain, a pricier flight.

Same Idea, Different Graphs

  • Train routes between citiesUndirected + weighted — trains run both ways, but routes differ in length.
  • Pac-Man's mazeUndirected + unweighted — any two open cells without a wall between them cost the same one step.
  • Bubble-shooter connectionsUndirected + unweighted — same-colored neighboring bubbles are simply connected or not.
  • City streetsDirected + weighted — one-way streets exist, and block lengths vary.

This rover grid allows movement both ways between neighbors. The cost depends on the tile you enter: 1 for open ground or 3 for sand.

The Algorithm Family: DFS → BFS → Dijkstra → Greedy → A*

The Algorithm Family: DFS → BFS → Dijkstra → Greedy → A*

A* is the last step in a short chain of increasingly smart search strategies. Each one solves the previous one's biggest limitation.

Depth First Search (DFS)

Picks a direction and commits, backtracking only when it hits a dead end — the same idea as recursive backtracking. Great for solving a maze, finding any path, or floodfill. Doesn't care whether the path it finds is short.

Breadth First Search (BFS)

Visits the start node's neighbors, then their neighbors, then theirs — radiating outward one full ring at a time. Whichever ring reaches the goal first has, by construction, the fewest steps. Guarantees the shortest path only when every edge costs the same — an unweighted graph.

Dijkstra's Algorithm

BFS's fix for weighted graphs. Instead of expanding ring by ring, it always expands whichever unvisited node currently has the cheapest known distance from the start. It will happily revise a node's best-known cost if a cheaper route turns up later, which means it guarantees the lowest-cost path. However, because Dijkstra ignores the goal's coordinates, it expands outward in every direction equally, which results in evaluating many unnecessary nodes behind the starting point.

Greedy Best-First Search

The opposite extreme: it ignores the cost paid so far and always expands whichever cell looks closest to the goal. On an open map it races straight there, checking very few cells. But because it has no memory of accumulated movement cost, a wall or a patch of sand leads it down expensive dead-ends. Consequently, Greedy Best-First cannot guarantee the shortest path because it never reconsiders previous choices.

A* Algorithm

A powerful upgrade to Dijkstra: it adds an admissible heuristic \(h(n)\) — an estimate of remaining distance — in order to prioritize cells heading toward the target. That formula is f(n) = g(n) + h(n): cost so far plus estimated cost remaining. Because \(h(n)\) never overestimates the actual distance, A* is mathematically guaranteed to find the optimal path while exploring far fewer nodes than Dijkstra. Therefore, it combines Dijkstra's mathematical rigor with Greedy's targeted direction.

Worked Example: Scoring Two Cells

The rover starts at the top-left corner and the goal is 6 columns right and 4 rows down. After a few moves, A* has two cells waiting:

  • Cell A (2 moves on open ground)g = 1 + 1 = 2, h = 10 − 2 = 8 left (Manhattan) → f = 10
  • Cell B (4 moves, the last onto sand)g = 1 + 1 + 1 + 3 = 6, h = 10 − 4 = 6 left → f = 12

Greedy only looks at h, so it picks B (6 is less than 8). Dijkstra only looks at g, so it picks A (2 is less than 6). A* adds them and also picks A, because \(f = 10\) is less than \(f = 12\). The sand cost more than the ground B gained toward the goal. Therefore, A* avoids the sand trap, which means it guarantees the lowest total path cost. Because the Manhattan distance never overestimates the actual steps on a grid, the heuristic is admissible, which explains why A* never misses a truly cheaper shortcut in order to reach the beacon.

Try it: Paint a strip of sand across the rover’s path in the lab above. Watch how the f-scores decide when crossing the sand is worth it and when going around wins.

Building Up: Try Them in Order

If you're implementing any of this yourself, don't start with A*. Build Dijkstra first — it only needs loops and a couple of data structures to track distances and parents — and confirm it finds correct lowest-cost paths. Then add a heuristic to turn it into A*. Trying to write A* from scratch first means debugging two ideas — shortest-path search and heuristic guidance — at once.

The Evolution of Pathfinding: Games and Real Life

The Evolution of Pathfinding: Games and Real Life

Pathfinding has gotten steadily smarter as hardware got faster and the problems it needed to solve got harder.

Where A* Came From

A* was invented in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at SRI. They built it for Shakey, the first mobile robot that could reason about its own actions. Shakey needed to plan routes around boxes in a room. The algorithm it inspired now runs in games, phones, and cars. Dijkstra's algorithm, the base A* builds on, came from Edsger Dijkstra in 1956. He said he worked it out in about twenty minutes at a café, without pencil or paper.

Shakey the robot, a tall wheeled robot with a camera and range finder, with labeled parts
The robot A* was built forShakey (SRI, 1966–1972) used A* to plan paths around obstacles in its room. Its heuristic was straight-line distance. SRI International · CC BY-SA 3.0 · Wikimedia Commons
Portrait of computer scientist Edsger W. Dijkstra
Edsger DijkstraDijkstra invented the shortest-path algorithm in 1956 to show off a new computer. He used it to find routes between 64 Dutch cities. Hamilton Richards · CC BY-SA 3.0 · Wikimedia Commons

Video Games: From Grids to Navmeshes

Pac-Man's ghosts (1980) used simple, almost hard-coded chase rules on a small maze grid — there wasn't enough processing power for much else. By the 1990s and 2000s, real-time strategy games like StarCraft and Age of Empires needed dozens of units pathfinding across large maps simultaneously without freezing the game, which pushed developers toward more efficient search and shared, precomputed route data. Modern 3D games mostly don't search a grid at all — they search a navigation mesh, a set of connected walkable polygons draped over the 3D level, which is far faster to search than checking every tiny tile.

Real Life: From Paper Maps to Live Rerouting

Early car navigation and mainframe route planning (1960s–1980s) could only compute a static shortest path on a fixed map, computed once, well ahead of time. Consumer GPS navigation in the 1990s–2000s brought this to a dashboard, but still assumed the road network didn't change mid-trip. Today's map apps continuously re-run pathfinding using live traffic data, treating slow roads as temporarily higher-cost edges — the same g(n)/h(n) idea in this lab, just rerun every few seconds on a vastly bigger graph.

Artist's illustration of a GPS Block II-F satellite in Earth orbit
Live position data from orbitGPS satellites give every device on the ground the position data that turns a static map into a live-rerouting one. NASA · public domain · Wikimedia Commons
Stanford's self-driving car Stanley, winner of the 2005 DARPA Grand Challenge
Planning a route with no driverStanley, Stanford's autonomous car, won the 2005 DARPA Grand Challenge by planning and replanning its own desert route in real time. DARPA · public domain · Wikimedia Commons
The Future of AI Pathfinding

The Future of AI Pathfinding

Classic algorithms like A* guarantee a correct answer, but they still search a known map with a hand-designed heuristic. The active research now is about what happens when the map is huge, unknown, shared by many agents, or changing faster than a search can keep up with.

Learned Heuristics

Instead of a programmer designing h(n) by hand — Manhattan distance, Euclidean distance, or zero — machine learning models can be trained on millions of past searches to predict a much better estimate of remaining cost, letting A*-style search check far fewer nodes on huge, complex maps like real city road networks.

Reinforcement Learning

Rather than searching a graph at all, an agent can learn a movement policy directly by trial and error in a simulated environment — useful when the "cost" of a path is hard to define in advance, like a robot arm avoiding a fragile object or a legged robot crossing rubble. Train one yourself in the Robot Reinforcement Learning lab.

Multi-Agent Coordination

Warehouses like Amazon's run hundreds of robots on the same floor at once, where the hard problem is finding paths for all of them at once that don't collide or deadlock each other, which needs its own family of algorithms on top of A*.

Where A* sits in a real robot: the grid it searches usually comes from an occupancy grid map built by SLAM. A* draws the global route, then a local planner such as the Dynamic Window Approach follows it and dodges things that move. For robot arms and drones, sampling planners like RRT replace the grid entirely. Race them in the Motion Planning Lab.

The core idea from this lab — balance what you already know against your best guess of what's ahead — keeps showing up at every layer of this progress, from a single rover on a grid to a fleet of self-driving cars.

Glossary

Glossary

Key words for talking about how a search thinks. Use them in your explanation sentence.

Pathfinding
Finding a route between two points through a space with obstacles, costs, or rules.
Graph
A set of nodes (places) joined by edges (connections). Every map a search uses is a graph.
Node
One location in a graph, like a single grid cell, a city, or a maze junction.
Edge
A connection between two nodes. It can be one-way (directed) or two-way (undirected).
Weight / cost
How expensive it is to cross an edge or enter a tile. In the rover lab, open ground costs 1 and sand costs 3.
Neighbor
A node you can reach in one move. On the rover grid, that means up, down, left, or right.
Heuristic
A quick, educated guess. In A*, it estimates the cost left to reach the goal.
g(n)
The real cost paid so far to get from the start to node n.
h(n)
The heuristic estimate of the cost from node n to the goal.
f(n)
g(n) + h(n): the total estimated cost of a route through node n. A* expands the lowest f first.
Admissible
A heuristic that never overestimates the true remaining cost. It lets A* guarantee the cheapest path.
Manhattan distance
Horizontal steps plus vertical steps, like walking city blocks. Fits grids with no diagonal moves.
Euclidean distance
Straight-line (“as the crow flies”) distance between two points.
Open set (frontier)
Cells found but not checked yet. The waiting cells in the lab.
Closed set
Cells already checked. The search won't expand them again.
Priority queue
A to-do list that always gives back the lowest-scored item first. Dijkstra and A* both use one.
Optimal path
The cheapest possible route. BFS finds the fewest steps. Dijkstra and A* find the lowest total cost.
Floodfill
Filling every cell connected to a starting cell, like a paint-bucket tool.
Backtracking
Going back to the last choice point after hitting a dead end, then trying another way. DFS works this way.
Navigation mesh (navmesh)
Connected walkable polygons laid over a 3D game level. Characters search it in place of a fine grid.
Replanning
Running the search again when the map changes, like a map app rerouting around traffic.

Explore the ideas behind this lab: Red Blob Games’ illustrated guide to A*.