Spark & Anvil Privacy

Ages 15–18 · Grades 9–12 · Computer Science

BehaviorForge

When an NPC finds its way across a level, it is not "thinking" — it is running a search algorithm. Here you pit breadth-first search, Dijkstra and A* against the same grid. All three reach the goal on an optimal path, but a good heuristic lets A* aim at the goal and finalize far fewer cells. Predict the winner, then run all three and read the numbers. This is classical AI — not machine learning.

Loading the search lab…

Where this idea comes from

Dijkstra and A*

In 1956 Edsger Dijkstra, a young programmer in Amsterdam, worked out how to find the shortest route between two cities in about twenty minutes, sitting on a café terrace with his fiancée, without pencil or paper; he published it in 1959. In 1968 Peter Hart, Nils Nilsson and Bertram Raphael at the Stanford Research Institute added a guess of the distance left, and called the result A*. They needed it for Shakey, a wheeled robot that had to plan its own way between rooms.

One thing to hold: A map of a few rooms with doorways, and a ruler to guess how far the goal still is.

Why it matters: A* finds the same cheapest route as Dijkstra, but its guess must never overestimate the distance left: then it can aim at the goal and look at far fewer places. Game characters and map apps still find their way with versions of these two searches.

What we don’t know: The café story comes from Dijkstra himself, told in an interview fifty years later; no notes from that day survive.

Dates:

  1. 1956 Dijkstra works out the shortest-route search on a café terrace.
  2. 1959 He publishes it in two pages.
  3. 1968 Hart, Nilsson and Raphael publish A*, built for the robot Shakey.

Sources: E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik 1 (1959) · P. E. Hart, N. J. Nilsson & B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics SSC-4(2), 1968 · T. J. Misa & P. L. Frana, “An interview with Edsger W. Dijkstra”, Communications of the ACM 53(8), 2010 · N. J. Nilsson, The Quest for Artificial Intelligence (Cambridge University Press, 2010), ch. 12 (Shakey)

A case · you decide

Marisol's guard that got lost

Marisol, 16 — building a stealth game where the guard keeps walking into walls on the way to the player

The idea in play: a search algorithm is chosen for what it guarantees and what it costs — BFS, Dijkstra and A* all find a shortest path, but a good heuristic lets A* look at far fewer cells.

Marisol's guard moves by picking whichever neighbouring tile is closest to the player in a straight line. In open rooms it looks smart. The moment a wall sits in between, the guard presses its face into the bricks and stays there.

Greedy straight-line chasing has no memory of where it has been and no idea a wall blocks the shortcut. It is fast, and it can get stuck.

A pathfinder looks ahead before moving. The question is which one: BFS treats every step the same, Dijkstra handles steps that cost different amounts (mud, stairs), and A* adds a guess of the distance left so it searches toward the goal.

Every floor tile costs the same to cross. Which fix gets the guard around the wall reliably?

Marisol adds mud tiles that cost three times as much to cross, and the map grows to 200 by 200. The guard now stutters. What should she use?

Open the pathfinding lab →

What next? Pick a door

Chosen from what this app is about. What you open is remembered on this device only.