Lehrzeit

Schule & Informatik

Kategorie: Klasse 11 (Seite 1 von 6)

Tiefensuche mit Processing

Basierend auf meinem letzten Beitrag habe ich jetzt noch die Tiefensuche mit Hilfe einer Adjazenzmatrix implementiert. Besuchte Knoten werden mit Gelb markiert und der aufspannenden Baum besteht aus gelben Kanten.

Die Knoten 1 und 7 wurden nicht besucht, was man an dem fehlenden gelben Punkt sieht. Ob ein Graph zusammenhängend ist, lässt sich daher mit der Tiefesuche feststellen.

Zum besseren Verständnis habe ich noch das in meinem Fall benötigte besucht[]:boolean – Feld ausgeben lassen, sowie den zu jedem Knoten gehörigen Vorgänger-Knoten, den ich in einem Feld vorgaenger[]:int speichere.

Die darüberstehenden Zahlen gibt die Durchlaufreihenfolge der Knoten wieder.

Den bisherigen Stand biete ich hier wieder zum Download an: ProcessingTiefensuche

Im nächsten Schritt möchte ich natürlich den schrittweisen Durchlauf animiert darstellen. Aber dazu muss ich die rekursive Implementierung des Algorithmus aufbrechen, damit bei jedem Durchlauf der draw()-Methode nur 1 Schritt gemacht wird.

Graphen und Processing

Angeregt durch die Videos von Daniel Shiffman möchte ich dieses Jahr das Implementieren der Graphenalgorithmen in der elften Jahrgangsstufe auf Basis von processing mit wie immer Java machen.

Hierzu habe ich jetzt in BlueJ ein Grundprojekt programmier, dass den Schüler als Vorlage zum Weitermachen dienen soll. Folgende Features habe ich dabei umgesetzt:

  1. Graphen werden per Zufall erzeugt.
    Hierzu werden 20 Knoten zufällig im Fenster erzeugt, Die Kanten werden ebenfalls zufällig erzeugt. Um nicht nur vollständige Graphen zu bekommen, habe ich zu folgender Implementierung gegriffen:

    for(int i=0; i < maxKnoten; i=i+1) {
        for(int j=0; j < maxKnoten; j=j+1) {
            if(i==j) { //Diagonale mit Nullen belegen
                adjazenzmatrix[i][j] = 0;
            } else {
                int zufallsGewicht = (int)random(1,60);
                 //Die 3 oder das == durch != ersetzen
                if (zufallsGewicht%3==0)
                    adjazenzmatrix[i][j] = zufallsGewicht;
                else
                    adjazenzmatrix[i][j] = 0;
            }
        }
    }
    

    Dadurch erhalte ich alle möglichen Graphen mit einer unterschiedlichen Anzahl an Kanten. Auch mal nicht zusammenhängende Graphen.

  2. Ist der Graph mal erzeugt können die Knoten mit der Maus noch verschoben werden. Hierzu muss der Graph aber im Verschiebmodus sein. Dieser ist standardmäßig aktiviert und kann durch Drücken der Taste ‚m‘ verändert werden.
  3. Durch Drücken der Taste ‚i‘ werden die Knotennamen eingeblendet. Die Kantengewichte werden durch Drücken der Taste ‚e‘ ausgegeben.
    Die erstmalige Anzeige der Knotennamen dauert am Anfang etwas. Warum weiß ich nicht.
  4. Durch Drücken der Taste ‚a‘ wird ein Algorithmus gestartet, wobei im Moment noch keiner implementiert ist.
  5. Durch Drücken der Taste ’s‘ und mit einem Mausklick wird ein möglicher Startknoten grün markiert oder entmarkiert.
  6. Durch Drücken der Taste ‚t‘ und mit einem Mausklick wird ein möglicher Zielknoten rot markiert oder entmarkiert.
  7. Durch Drücken der Taste ‚h‘ kann auch während der Benutzung des Programms die Hilfe angezeigt werden. Auch das dauert am Anfang etwas.

Hier noch die zip-Datei zum Runterladen und weiterentwickeln:  ProcessingAdjazenzMatrix.

Programmieraufgabe 93

Vor ein paar Tagen war die freie App der Woche bei iTunes das Spiel „Lifeline: Das Experiment„. Hierbei geht es irgendwie darum, einem in der Arktis Gestrandeten zu helfen. Er weiß nicht mehr wer ist oder warum er dort ist. Das Ganze ist als reines Textadventure angelegt, da die einzige Kommunikation mit der Figur Adams über einen Kommunikator läuft. Das Spiel verläuft mehr oder weniger im Echtzeitmodus. Wenn er also beispielsweise schreibt, dass er Holz suchen geht, hört man auch mal drei Stunden nichts. Das macht die Sache ganz angenehm, aber auch manchmal langweilig, da man ewig warten muss bis es weiter geht.

Praktisch finde ich dagegen die Steuerung. Man muss keinen Text eingegeben, sondern bekommt nur zwei Antwortalternativen von denen man eine anklickt. Auf einen Parser wie bei den Spielen von Infocom, die wohl einen der besten entwickelt haben, wird dabei verzichtet. Das macht das Spiel auch praktisch für unterwegs auf dem Handy. Man ist allerdings auch nicht wirklich frei in den Spielzügen. Dass es dennoch genügend Spielsituationen gibt, kann man mit seinen Schülern in 11/2 beim Thema Binärbäume ja mal überlegen.

Jetzt aber zur Aufgabe, die sich wunderbar in der 10. Klasse, wenn man Verzweigungen eingeführt hat, schon mal umsetzen kann. Sicher nicht die beste Möglichkeit, aber EINE Möglichkeit.

Aufgabe

Erstelle ein Textadventure bei dem eine Spielfigur mit dem eigentlichen Spieler schriftlich kommuniziert.

Der Spieler kann dabei immer nur zwischen den Alternativantworten A und B wählen. Die Spielfigur erzählt was sie macht oder sieht und fragt dann immer weiter, wie es weitergehen soll.

Das Ganze kann man natürlich auch mit Arrays später nochmal machen. Denn Binärbäume lassen sich auch in einem Array speichern, wie man bei wikipedia u.a. nachlesen kann.

Wer noch einen drauflegen will, der packt die Aufgabe dann doch in die 11. Klasse. Hier lässt sich dann noch wunderbar über das Zurücknehmen der Züge nachdenken. Denn wenn einem die Spielfigur weg stirbt, kann man zu einem beliebigen Punkt zurückgehen und seine Entscheidung ändern. Das Merken der Züge passiert dann entweder in einem Stack, der wieder abgebaut wird oder das Spiel wurde tatsächlich als Binärbaum aufgebaut und der Spieler, in dem Fall ich, kann einfach die Vorgängerknoten in dem Baum Richtung Wurzel zurückgehen.

Eine andere Variante wäre noch die Implementierung mit Hilfe eines Zustandsautomaten in der 10. Klasse. Das Alphabet besteht aus den Buchstaben A und B (s.o.). Je nach aktuellem Spielzustand wird abhängig vom ausgewählten Zustand einer von zwei möglichen Nachfolgezuständen ausgewählt. Durch den Übergang wird ein anderer Text der Spielfigur angezeigt.

Alles in allem also eine wirklich schöne Aufgabe, egal, ob sie nun umgesetzt wird oder ob man nur mal darüber redet.

Ach ja, was man nicht vergessen darf, ist die Problematik der Geschichte. Hier kann man eventuell auf (Kurz)geschichte versuchen auszuweichen. Oder man schreibt selbst welche. Letzteres würde ich irgendwie versuchen auf die gesamte Klasse zu verteilen.

Die Schüler sind dann quasi die Zustände oder Knoten. Ein Schüler wird zur Wurzel erklärt und schreibt die Einleitung (5 Sätze oder so). Am Ende schreibt er zwei Antwortalternativen auf. Die zwei Nachfolgezustände (zwei andere Schüler), schreiben dann wieder ca. 5 Sätze dazu und geben wieder zwei Antwortalternative an. Bei rund 30 Schülern kommt man so auf knapp 5 Entscheidungen des Spielers. Noch nicht so viel, aber wenn man die Figur frühzeitig Sterben lässt, fallen ganze Zweige der Baumstruktur weg und man kann die Entscheidungstiefe vergrößern. Im Idealfall hat dann jeder Schüler was zu schreiben und für die nächste Runde muss dann die Hälfte aller Antwortalternativen direkt zum Tod der Spielfigur führen. Man erzeugt einen nicht vollständigen Baum mit genau so viel Verzweigungen pro Ebene, wie Schüler in der Klasse.

So kann man als Lehrer die Blätter am Ende eines Zyklus immer einsammeln, ich als Lehrer entscheide, welche Antwort zum Tod führt und markiere die Alternative dementsprechend und kontrolliere, dass es wirklich genau so viel Antworten wie Schüler übrigbleiben. Danach verteile ich die Texte wieder an die Schüler. Jede Geschichte ist damit ein Pfad von der Wurzel bis zu einem Blatt.

Das ließe sich im übrigen auch digital machen, in dem die Texte an einer zentralen Stelle, wegen mir auch mebis, verwaltet werden. Schöner wäre jetzt eine Software, aber da kenne ich keine. Vielleicht kann man so etwas im Rahmen eines P-Seminars ja mal programmieren.

Insofern kann man aus dieser Aufgabe gleich noch zwei weitere erzeugen:

Aufgabe 1

Schreibe mit deiner Klasse eine Geschichte als Basis für ein solches Spiel

Aufgabe 2

Entwickle eine Software zum Erzeugen solcher Geschichten.

Ältere Beiträge

© 2018 Lehrzeit

Theme von Anders NorénHoch ↑