How a computer finds the shortest path

Watch three pathfinding methods race across maps you can change.

By Amit Patel, Red Blob GamesFree to visitA Starvard Treasure

When a character in a game walks around a wall to reach you, an algorithm planned that route. Amit Patel's page shows three ways to find a path, side by side, on maps you can change yourself.

Move a wall and watch each method spread out, search and settle on its answer. It is clear enough for a beginner and still pleasing for anyone who already writes code.

Introduction to the A* Algorithmredblobgames.comWatch three pathfinding methods race across maps you can change.Visit Introduction to the A* Algorithm ↗

Try this first

Draw a wall across the map and run all three methods at once. Breadth-first floods everywhere, Dijkstra works harder, and A* aims politely at the goal. Each step is explained in plain words beside the demo.

Good to know

Part of Red Blob Games' pathfinding guides by Amit Patel, a beloved free corner of the programming web. No licence line is posted, so we link rather than copy.

Keep exploring

Geometry in bold colourByrne's Euclid Probability you can play withSeeing Theory

← All Starvard Treasures

Treasures are wonderful free things made by other people. Starvard gathers them with admiration; the credit is all theirs.