Planet und Karte

Pfade und Knoten

Versorgungsstationen beziehungsweise Kommunikationspunkte oder kurz Knoten/Kreuzungen, sind 50mm x 50mm große, an den Himmelsrichtungen ausgerichtete Quadrate. Sie liegen auf einem unsichtbaren 50cm x 50cm Raster; allerdings nur dort, wo sie über Pfade erreichbar sind. Es gibt sie in zwei Farben, rot und blau, wobei im Raster orthogonal zu einander liegende benachbarte Kreuzungen nie dieselbe Farbe besitzen. Eine Verbindung zwischen zwei Kreuzungen wird Pfad genannt. Pfade sind 15mm breit, schwarz und verlaufen auf den letzten 50mm senkrecht zur Kreuzung.

Planet Kepler-0815
Figure 1. Planet Kepler-0815
Kommunikationspunkt
Figure 2. Kommunikationspunkte/Kreuzungen

Wir versuchen, die Maße möglichst genau einzuhalten.
Die Pfade und Kreuzungen werden per Hand geklebt, daher können minimale Abweichungen (leider) auftreten.

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 besonders schweren 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. 30cm hoch und ähneln bis zu einer Höhe von mindestens 15cm einem Zylinder mit 8cm Durchmesser. Ab 15cm 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 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!

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 Djikstra-Algorithmus können zur Wegfindung auch andere Algorithmen wie Floyd-Warshall oder Bellman-Ford genutzt werden.

Intelligentes Erkunden

Um den Planeten effizient zu erkunden können unterschiedliche Ansätze genutzt werden, um noch unbekannte Knoten oder Pfade aufzudecken.
Intelligentes Erkunden bedeutet: Unnötige Fahrten zu vermeiden. Wenn Pfade mehrfach befahren werden müssen, sollten kurze Pfade oder solche mit geringerer Gewichtung bevorzugt werden.

Inspirationen für intelligentes erkunden:
Tiefensuche und Breitensuche beispielsweise haben jeweils Vor- und Nachteile in Abhängigkeit davon, wie und mit welchen Bedingungen sie implementiert werden.
Eine weitere Erkundungsstrategie wäre das Backtracking (basiert auf der Tiefensuche).

Auch kann man sich darüber Gedanken machen, wie oft man Knoten scannt.
Je nach Erkundungsstrategie werden Knoten mehrfach besucht, wobei ein nochmaliges Scannen nicht unbedingt notwendig ist.

Einige Erkundungsstrategien werden bei größeren Planeten sehr ineffizient. Bei der Wahl sollte daher auch der Zeitfaktor beachtet werden.