Planet und Karte
Pfade und Knoten
Versorgungsstationen beziehungsweise Kommunikationspunkte oder kurz Knoten/Kreuzungen, sind 50 mm x 50 mm große, an den Himmelsrichtungen ausgerichtete Quadrate. Sie liegen auf einem unsichtbaren 50 cm x 50 cm Raster; allerdings nur dort, wo sie über Pfade erreichbar sind. Es gibt sie in zwei Farben, rot und blau, wobei im Raster orthogonal zueinander liegende benachbarte Kreuzungen nie dieselbe Farbe besitzen. Eine Verbindung zwischen zwei Kreuzungen wird Pfad genannt. Pfade sind 12,5 mm breit, schwarz und verlaufen auf den letzten 50 mm senkrecht zur Kreuzung.
Wir versuchen, die Maße möglichst genau einzuhalten.
Die Pfade und Kreuzungen werden per Hand geklebt, daher können minimale Abweichungen (leider) auftreten.
Farbkalibrierung
Um euch die Arbeit zu erleichtern und nicht immer Werte anpassen zu müssen, empfehlen wir euch, zu Beginn ein kleiner Algorithmus zur Farbkalibrierung zu implementieren. In jedem Fall zu integrieren sind Wertebereiche für Rot und Blau, Schwarz und Weiss können als Momentaufnahme (bspw. zur Grauwertberechung) abgespeichert werden.
Um die Werte nicht vor jeder Fahrt neu aufnehmen zu müssen, können sie beispielsweise in einer Config-Datei abgespeichert und bei Programmstart geladen werden.
Hindernisse
Auf manchen Pfaden können sich Hindernisse befinden. Im Normalfall sind dies Meteoriten, die erstaunlicherweise wie überdimensionale Flaschen aussehen. Die Galaxie, in der das Mutterschiff unterwegs ist, wurde anscheinend von einem besonderen Flaschen-Schauer heimgesucht.
Zum Glück können die Meteoriten aufgrund von verborgenen Goldadern allerdings nur auf den Gitter-Linien einschlagen. Zusätzlich sorgt auch noch das Chakra der unterirdischen Strömungen dafür, dass es vor Meteoriten immer eine gerade Strecke gibt. Diese Meteoriten sind ca. 30 cm hoch und ähneln bis zu einer Höhe von mindestens 15 cm einem Zylinder mit 8 cm Durchmesser. Ab 15 cm Höhe können diese Meteoriten witterungsbedingt nach oben spitz zulaufen.
Ausgiebige Analysen haben gezeigt, dass sich innerhalb der Meteoriten wohl eine hohe Konzentration an Dihydrogenmonoxid (DHMO) befindet.
Kontakt mit dieser Substanz kann zu permanenten Schäden an der Elektronik des Roboters führen.
Folglich kann der Roboter diese Hindernisse zwar erkennen, darf sie jedoch aufgrund des hohen Sicherheitsrisikos nicht sprengen (Erkundungsroboter sind teuer).
Also setzt stattdessen nur eine kurze Warnung für andere Roboter in der Umgebung ab, dreht um und kehrt zum ursprünglichen Knoten zurück.
Dort macht er eine kurze Meldung an das Mutterschiff über den blockierten Pfad und fordert schweres Gerät zur Räumung in den nächsten Tagen an.
Dann ignoriert er fortan diesen Weg und setzt die Erkundung fort.
Die Warnung an andere Roboter kann zum Beispiel eine markante Tonfolge oder andere deutlich wahrnehmbare Aktion sein.
Das Hindernis soll nicht selbstständig durch den Roboter geräumt werden!
Im All kann es immer wieder zu Meteoritenschauern kommen. Dadurch passiert es unter Umständen, dass bereits befahrene Strecken plötzlich nicht mehr passierbar sind.
Kürzester Weg
Es gilt: Ist der Roboter am Ziel angekommen oder sind alle Knoten entdeckt, beendet er seine Erkundung (nach Bestätigung durch das Mutterschiff).
Zur Berechnung des kürzesten Weges (shortest path) können verschiedene Ansätze genutzt werden.
Neben dem bekannten Dijkstra-Algorithmus können zur Wegfindung auch andere Algorithmen wie Floyd-Warshall oder Bellman-Ford genutzt werden.
Bitte beachtet bei der Implementierung die Rechenkapazitäten des EV3-Brick und den Zeitfaktor!
Intelligentes Erkunden
Zur effizienten Erkundung des Planeten sollten unnötige Fahrten vermieden werden. Aufgrund dessen soll der Roboter bei der Erkundung versuchen, die Kosten der zurückgelegten Strecke so gering wie möglich zu halten. Das bedeutet, dass für die Erkundung die Anzahl der Wegstücke (Hops) oder der Zeitpunkt des Hinzufügens (Stichwort: Queue) keine bestimmenden Kriterien sind. Auch kann der Roboter die Distanz zwischen zwei Knoten nicht abschätzen (Stichwort: Heuristik). Falls Pfade mehrfach befahren werden müssen, sollte die Wichtung der zurückszulegenden Strecke das einzige bestimmende Kriterium sein.
Um den nächsten zu befahrenen Pfad zu bestimmen existieren unterschiedliche Ansätze. Algorithmen wie Tiefensuche, Backtracking (basiert auf der Tiefensuche) oder Breitensuche haben jeweils Vor- und Nachteile, in Abhängigkeit davon, wie und mit welchen Bedingungen sie implementiert werden. Da nicht jeder Algorithmus effizient ist, sollte der Zeitfaktor auch berücksichtigt werden. Vor allem bei größeren Planeten werden einige sehr ineffizient.
Auch kann man sich darüber Gedanken machen, wie oft Knoten gescannt werden sollen. Je nach Erkundungsstrategie werden Knoten mehrfach besucht, wobei ein nochmaliges Scannen dabei nicht notwendig ist.
Beispiele
Beispiele für Planeten findet ihr HIER.
