Dokumentation zu Nexus
Einleitung:
Ich habe versucht, einen möglichst flexibel erweiterbaren Hamster zu
programmieren. Deshalb arbeitet er mit sehr vielen kleinen
abstrakten Methoden und Klassen.
Strategie:
Mein Hamster hat grob gesagt folgende Instruktionen:
Grundstrategien:
- Gehe zu Interessanten
Feldern und nimm dort alles Korn.
- interessant:
- es lohnt sich von dort Korn zu holen
- das Feld ist unbekannt und es würde sich lohnen von dort
Korn zu holen
-
Unterbreche das Kornsammeln nur um dies nach Hause zu bringen
-
Hören erst auf, wenn du kein interessantes Feld mehr findest.
Erweiterungen
Strategien, die erst auf dem erweiterten Labyrinth nötig wurden.
- Wenn du keinen Weg nach Hause findest, (weil du blind eine
Klippe runtergesprungen bist), dann erkunde die
Umgebung so lange bist du einen Weg gefunden hast.
- Falls dein Heimweg auf Grund von Klippen kürzer sein sollte,
als dein Hinweg, dann werfe das Korn von der Klippe und
versuche erst einmal noch Korn zu sammeln, das auf ein einer
Ebene mit dir liegt.
-
Zusammenfassen von für sich alleine uninteressanten Feldern am
Ende zu eine Route. (bringt leider nichts - ich denke aber, es
könnte vorkommen, dass es gebraucht wird)
Im großen und ganzen macht er nicht mehr. Die meiste Zeit habe
ich aber damit verbracht so nach und nach diese abstrakten
Probleme so aufzuteilen, dass sie Lösbar wurden.
Datenstrukturen:
- 2D Array mit fester Größe:
Da die Maximalgröße
des Labyrinthes feststand, werden die einzelnen Felder in einem Festen
zwei dimensionalen Array gespeichert. FieldMap kapselt diesen
und ermöglicht der Zugriff darauf über Positionen.
Da jedes Feld die Wege zu seinen Nachbarn kennt, kann man die
FieldMap auch als Graphen interpretieren und entsprechende
Algorithmen darauf anwenden.
-
In einer Liste: wird der Relative Weg abgespeichert,
den ein Hamster zuerst sucht, und dann abläuft.
Alogorithmen:
-
Breadth-First
Search
(vgl. Goodrich & Tamassia: Data Structures and
Algotithms in Java)
Dies ist wahrscheinlich DER Algorithmus in meinem
Hamster. D.h. ich habe ihn einmal abstrakt definiert. Und die
Anwendung kommt erst mit seinen Erben. Manchmal wäre es
vielleicht effizienter gewesen (ich meine sogar O(irgendwas)
effizienter) wenn ich für mache Probleme ihn lieber verändert
als vererbt hätte, aber die Probleme wurden anders gelöst
bzw. sind mir als Geschwindigkeitsproblem (noch) nicht
aufgefallen.
-
Rekursive Methoden, wie es sich angeboten hat. z.B. wie in Path
Style
Läßt natürlich zu wünschen übrig, um so näher der Abgabetermin
rückt. (Ich bin doch erst 2.Semester ;o)) Einige Sachen könnte
man noch zusammenfassen und verallgemeiner. Ich aber hoffe der
Code ist noch halbwegs les- und nachvollziehbar. Bei der Anzahl der
Klassen weiß ich nicht, ob ich mich nun entschuldigen muss,
dafür, dass es so viel sind, oder immer noch zu wenige ;o).
Jens Lincke
Last modified: Thu Apr 25 20:09:40 CEST 2002