Pathfinder
Tap Go to run a search. Tap streets to add or clear buildings, drag the car or pin to move them, and drag along roads to draw a route. Desktop: 1, 2, 3 pick BFS, DFS or A*, Enter runs.
What is Pathfinder?
Pathfinder is a free game about how computers find routes, the same idea behind sat-navs and the characters in video games. You watch three real search algorithms flood a night-time city with light as they look for the way from a car to a map pin. Breadth-first search ripples out evenly and always finds a shortest route, depth-first search dives down one road at a time, and A* aims for the goal using a guess of the distance left. Then you predict which search checks the fewest squares, draw your own route as the sat-nav, and place roadblocks to send DFS the long way round.
How to play Pathfinder
Controls: Tap Go to run a search. Tap streets to add or clear buildings, drag the car or pin to move them, and drag along roads to draw a route. Desktop: 1, 2, 3 pick BFS, DFS or A*, Enter runs.
- 1Press Go and watch the search light up the streets. Every glowing square is one the computer checked.
- 2Tap a street to add a building or tap a building to clear it, then search again to see what changes.
- 3In the predict levels, guess which of BFS, DFS and A* will check the fewest squares, then watch all three run on the same map.
- 4In the sat-nav levels, drag from the car along the roads to the pin. Match the shortest route to score top points.
- 5In the roadblock level, place up to two roadblocks so depth-first search has to check as many squares as possible.
- 6Try City challenge for random maps once you know how each search behaves.
Pathfinder tips and strategy
- BFS always finds a shortest route on a grid like this, but it pays for that by checking squares in every direction, even ones pointing away from the pin.
- A* ranks squares by steps taken plus blocks left to go. When there is a clear path toward the pin it barely strays from it, which is why it usually checks the fewest squares.
- DFS follows a fixed rule: up first, then right, down and left. Block the road it wants and you can send it on a long detour.
- Checking the fewest squares is not the same as finding the shortest route. DFS sometimes gets lucky and checks very few, but its route can still be far longer.
Pathfinder FAQ
What is the difference between BFS and DFS?
Breadth-first search (BFS) checks every place one step away, then two steps, then three, like ripples, so on a map where every step costs the same the first route it finds is a shortest one. Depth-first search (DFS) follows one path as far as it can and only backs up at dead ends, so it finds a route but not necessarily a short one.
What is the A* search algorithm?
A* (said A-star) is a pathfinding algorithm that ranks each square by the steps taken so far plus an estimate of the distance still to go. As long as that estimate never overestimates, A* still finds a shortest route, and it usually checks far fewer squares than BFS because it heads toward the goal first.
How does a sat-nav find the fastest route?
It treats the roads as a network of junctions and runs a search algorithm over it, usually a relative of A* or Dijkstra's algorithm, with each road weighted by distance or expected travel time. Real systems add extra tricks such as precomputed shortcuts so they can answer in a fraction of a second on maps with millions of roads.
Why do games use A* for their characters?
Because it is quick and reliable. A game has to move many characters at once, and A* finds a shortest path while exploring only a small part of the map, which keeps the game running smoothly. The same idea works on grids, tile maps and navigation meshes.
