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/#