Dr. Johannes Mayer Abteilung Angewandte Informationsverarbeitung 29. November 2005
Axel Blumenstock Blatt 6
Christian Ehrhardt






Allgemeine Informatik III / Systemnahe Software I (WS 2005/2006)


Abgabetermin: 6. Dezember 2005

Wo, bitte, geht's denn hier zum Quark? (10 Punkte)

Li Del, der findige Lebensmittel-Einzelhändler, steckt wie viele seiner Kollegen derzeit in einer massiven Absatzkrise. Er glaubt, je länger die Kunden in seinem Laden sind, desto mehr werden sie kaufen. Darum hat er die Regale ein bisschen umgestellt.

Sie hingegen stehen vor der Aufgabe, für Ihren Stollen noch schnell einen Quark zu besorgen. Glücklicherweise hat Ihnen Ihr Nachbar bereits einen Plan des Ladens angefertigt, der Ihnen erlaubt, die Route schon vorab durchzuspielen.

Der Plan liegt Ihnen als Textdatei vor, die wie folgt aussehen könnte:

  21 11
  XXXXXXXXXXXXXXXXXXXXX
  X     X           X X
  X XXX X XXXXXXXXX X X
  X X X X     X   Xo  X
  X X X XXXXX X XXXXX X
  X X  *    X X     X X
  X XXXXX XXXXXXXXX X X
  X     X X         X X
  X XXX XXX X XXXXXXX X
  X   X     X         X
  XXXXXXXXXXXXXXXXXXXXX

In der ersten Zeile stehen, durch Whitespace getrennt, die Breite w und Höhe h des Ladens in Rastereinheiten. w und h sind positive, ungerade Ganzzahlen kleiner als 100. Dann folgen h Zeilen mit je w Zeichen. In diesem Raster steht ein 'X' für ein Regal und ein Leerzeichen für freie, begehbare Fläche. Ferner symbolisiert genau ein '*' Ihren Einstiegspunkt (das Ende der Rolltreppe) und genau ein 'o' das gewünschte Päckchen Quark. Die Außenwände sind komplett geschlossen.

1. Schreiben Sie eine Funktion, die einen Ladenplan im beschriebenen Format aus einer Datei einliest, deren Namen an der Kommandozeile (also als Programmparameter) angegeben werden kann. Fehlt der Parameter oder bezeichnet keine lesbare Datei, soll das Programm einen entsprechenden Hinweis geben. Sie finden dazu ein Beispielprogramm im ftp-Verzeichnis zu diesem Blatt.

   Der Plan soll in einem zweidimensionalen Array fester Größe gehalten werden, wobei zwei weitere Variablen den tatsächlich genutzten Teil angeben. Verwenden Sie (außer ggf. Konstanten) keine globalen Variablen, sondern übergeben Sie sämtliche Informationen als Funktionsparameter bzw. Rückgabewerte.

2. Erstellen Sie eine weitere Funktion, die Ihnen den Plan auf dem Bildschirm ausgibt. Zweckmäßigerweise löschen Sie vorher den Bildschirm und beginnen mit der Ausgabe an einer definierten Stelle. Dabei werden Ihnen Escape-Sequenzen nützlich sein - auch dazu finden Sie ein Beispielprogramm. Verbessern Sie die Lesbarkeit durch Einsatz von Farben. Geben Sie dabei Ihrem kreativen Potential Raum.

3. Schließlich schreiben Sie eine Funktion, die dem Array (unter Zuhilfenahme einer weiteren Funktion) zunächst Ihre Position ('*') bzw. die des Quarks ('o') entnimmt. Dann soll sie dem Benutzer per Tastendruck erlauben, im Labyrinth zu navigieren. (Zum Einlesen von Tastendrücken ohne ENTER und ohne Ausgabe beachten Sie ein weiteres Beispielprogramm.) Als Tasten können Sie die vi-Kommandos h/j/k/l anbieten, oder - wenn Sie Escape-Sequenzen interpretieren - auch die Pfeiltasten. Sehen Sie mindestens ein weiteres Kommando zum vorzeitigen Beenden des Programms vor.

   Zur Aktualisierung der Anzeige nutzen Sie wiederum Escape-Sequenzen. Beachten Sie, dass das Labyrinth dabei nicht jedes Mal aufs Neue ausgegeben werden muss. Ist der Quark erreicht, soll das Programm gratulieren.

4. (Zusatzaufgabe, 5 Punkte) Neben der Möglichkeit, einen Plan aus einer Datei zu lesen, soll das Programm sich nun auch selbst ein Labyrinth erzeugen können. Gehen Sie dazu folgendermaßen vor:
   • Füllen Sie den zu nutzenden Teil des Arrays (Größe von der Kommandozeile; diese ist zu limitieren und auf ungerade Werte zu korrigieren) komplett mit 'X'.
   • In jedes Feld, das Sie nun betreten, schreiben Sie ein Leerzeichen. Beginnen Sie an einer zufällig ausgewählten Stelle mit ungeraden Koordinaten.
   • Wählen Sie zufällig eine der vier möglichen Richtungen als erste, probieren dann aber reihum alle durch. Gehen Sie jeweils zwei Array-Zellen in die aktuelle Richtung, wobei Sie nur dann einen ,,Wanddurchbruch`` (erste Zelle mit Leerzeichen überschreiben) machen dürfen, wenn Sie dadurch nicht aus dem Array fallen und die zweite Zelle (wieder mit ungeraden Koordinaten) dahinter noch unbesucht ist ('X'). Diese zweite Zelle betreten Sie durch einen rekursiven Funktionsaufruf, testen von dort also wiederum alle vier möglichen Richtungen. Verlassen Sie eine Funktionsinstanz erst, wenn Sie keinen Schritt mehr gehen können.
   • Start- und Ziel werden zufällig in je ein freies Feld gesetzt.

Viel Erfolg!