Dies ist eine alte Version des Dokuments!
1. Pfadfinder-Algorithmen
Betrachte die Aufgabe zum Programmierwettbewerb Hidden-Gems: https://hiddengems.gymnasiumsteglitz.de/
Bei „Stages“ siehst du den einfachsten Testlevel und die Informationen, die man erhält.
Aufgabe
- Überlege dir, welchen Algorithmus man bei der Testumgebung verwenden könnte? Wie steuert man den Bot zu den Edelsteinen?
- Was ändert sich, wenn man sich in einer Umgebung mit Wänden bewegt? Wie wird die Umgebung, die Position des Bots und der Edelsteine repräsentiert?
- Überlege dir einen möglichen Algorithmus, der auch bei Wänden funktionieren könnte. Schreibe den exakten Ablauf deines Algorithmus schriftlich hin.
- Recherchiere nach bekannten Pfadfinder-Algorithmen. Was ist die Manhatten-Distanz? (BFS, DFS, Dijkstra, A*)(Bsp: Englisches Video mit Visualisierung)
- Eine gute visuelle Darstellung von verschiedenen Algorithmen findet sich z.B. hier: https://clementmihailescu.github.io/Pathfinding-Visualizer/#
- Erklärung zur Breitensuche: Breitensuche in Khan-Academy
- Erklärung des Dijkstras-Algorithmus Dijkstra Computerphile
- Wie funktioniert die Breitensuche?
- Was ist eine Queue und wie verwendet man sie, wenn man die Breitensuche implementiert? (Siehe Link von Khan-Academy)