The Shortest Way

Out of the Maze

A character in a game has to get from one place to another. So it looks for the best route.

Almost every game needs this. Characters walk through mazes. They get around obstacles. And they take the shortest way to the goal.

Two ways to find the way

1. 1

   Breadth-first search (BFS)

   Breadth-first search goes step by step. It spreads out from the start evenly in all directions. So it always finds the way with the fewest steps.

2. 2

   A* (A-Star)

   A* is cleverer: for every square it guesses how far the goal still is. It checks squares near the goal first.

3. 3

   Not just in games

   Your satnav uses these methods too. Robots plan their moves with them. Even search engines on the internet use them.

4. 4

   In Video Games

   In a game, enemies chase you with it. Other characters walk around obstacles. And units in strategy games find their way across the map.

In a moment you find your own way through a maze. Then you see how the AI finds it.