Der kürzeste Weg

Raus aus dem Labyrinth

Eine Figur im Spiel muss von einem Punkt zum anderen kommen. Dafür sucht sie sich den besten Weg.

Fast jedes Spiel braucht das. Figuren laufen durch Labyrinthe. Sie weichen Hindernissen aus. Und sie nehmen den kürzesten Weg zum Ziel.

Zwei Wege, den Weg zu finden

1. 1

   Breitensuche (BFS)

   Die Breitensuche geht Schritt für Schritt vor. Sie breitet sich vom Start gleichmäßig in alle Richtungen aus. So findet sie immer den Weg mit den wenigsten Schritten.

2. 2

   A* (A-Stern)

   A* ist schlauer: Es schätzt bei jedem Feld, wie weit das Ziel noch weg ist. Felder nah am Ziel prüft es zuerst.

3. 3

   Nicht nur im Spiel

   Diese Verfahren stecken auch im Navi. Roboter planen damit ihre Bewegungen. Und sogar Suchmaschinen im Internet nutzen sie.

4. 4

   In Videospielen

   Im Spiel jagen dich Gegner damit. Andere Figuren laufen um Hindernisse herum. Und Einheiten in Strategiespielen finden ihren Weg über die Karte.

Gleich suchst du selbst einen Weg durch ein Labyrinth. Danach siehst du, wie die KI ihn findet.