5909
Comment:
|
6469
|
Deletions are marked like this. | Additions are marked like this. |
Line 1: | Line 1: |
#acl Axel Lehmann:read,write All:read | #acl All:read |
Line 3: | Line 3: |
= Projekt zur Vorlesung '''Programmieren in C++''' im Sommersemester 2014 = | = Projekt zur Vorlesung '''Programmieren in C++''' im Sommersemester 2016 = {{{ #!html <span style="font-weight:bold; color: #ff0000; font-size:150%">Bis Vorlesung 12 sind noch kleinere Änderungen möglich!</span> }}} |
Line 7: | Line 12: |
'''Projekt 1: !PooSweeper (das Spiel)''' | '''Projekt 1: Sokoban (das Spiel)''' |
Line 9: | Line 14: |
'''Projekt 2: !PooSweeper (der Löser)''' | '''Projekt 2: Sokoban (der Löser)''' |
Line 13: | Line 18: |
''Alternative Namen für das Spiel von Projekt 1 und 2:'' !AlienSweeper (Aliens ausweichen, sonst wird man entführt), !LoveSweeper (Single bleiben, damit man in Ruhe arbeiten kann), !BorgSweeper (Borgs ausweichen, sonst wird man assimiliert), !MacSweeper (Fast Food ausweichen, sonst Übergewicht und Herzinfarkt), ... | |
Line 15: | Line 19: |
Im Folgendenden eine detailliertere Beschreibung der drei Projekte | Im Folgenden eine detailliertere Beschreibung der drei Projekte |
Line 17: | Line 21: |
== Projekt 1: PooSweeper (das Spiel) == | == Projekt 1: Sokoban (das Spiel) == |
Line 19: | Line 23: |
'''Kurzbeschreibung:''' Das Spiel !PooSweeper soll mit Konsolengrafik realisiert werden. | '''Kurzbeschreibung:''' Das Spiel Sokoban soll mit Konsolengrafik realisiert werden. |
Line 21: | Line 25: |
'''Hintergrund:''' Eine voll-funktionale Online-Version des Spiels findet sich zum Beispiel hier: http://minesweeperonline.com . (Mit Minen, aber das wollen wir hier nicht.) | '''Hintergrund:''' Eine voll-funktionale Online-Version des Spiels findet sich zum Beispiel hier: http://sokobanonline.com . |
Line 25: | Line 29: |
* Ein Zustand des Spiels soll mit einer Klasse ''!PooSweeperState'' realisiert werden, die eine Unterklasse der auf dem Wiki verlinkten abstrakten Klasse ''!PooSweeperStateBase'' ist. | * Einlesen einer Instanz aus einer Datei in dem [[http://www.sokobano.de/wiki/index.php?title=Level_format|hier beschriebenen Format]]. Es reicht, wenn das einfache Dateiformat (in dem explizit jedes Zeichen dargestellt wird) unterstützt wird. |
Line 27: | Line 31: |
* Konsolengrafik (möglichst ansprechend und übersichtlich) | * Konsolengrafik: dabei sollte jedes Objekt (Box, Spieler, Teil der Mauer) in einer eigenen Farbe gezeichnet werden, mit einer über Kommandozeilenparameter einstellbaren Anzahl Zeichen pro Objekt in x und y Richtung (und einer vernünftigen Defaulteinstellung). |
Line 29: | Line 33: |
* Bedienung über die Maus (linke Maustaste = Zelle aufdecken, rechte Maustaste = als Poo markieren) | * Bedienung über die Tastatur mit den Pfeiltasten. |
Line 31: | Line 35: |
* Dimension des Spielfeldes (Anzahl Reihen und Spalten) und Anzahl der Poos frei wählbar. Entweder über Kommandozeilenargumente, oder im Programm selber. | * Undo Funktion, wobei die Anzahl Züge die man höchstens hintereinander rückgängig machen kann ein Argument in der Kommandozeile sein sollte (Default: 5). |
Line 33: | Line 37: |
* Auf http://minesweeperonline.com ist das erste Aufdecken immer garantiert kein Poo. In anderen Versionen kann auch mit dem ersten Aufdecken das Spiel schon zu Ende sein. Sie können sich aussuchen, welche Variante Sie implementieren. | * Alle Funktionalität, die mit Ein- bzw. Ausgabe zu tun hat, sollte sauber getrennt von den anderen Teilen in eigenen Methoden stehen und diese Methoden brauchen nicht getestet zu werden. Für alle anderen Methoden soll es selbstverständlich wie gehabt einen Unit Test geben. |
Line 35: | Line 39: |
* Wie beim Originalspiel soll, falls eine Zelle aufgedeckt wird, die keine Poos in der Nachbarschaft hat, alle Zellen in der Nachbarschaft automatisch mit aufgedeckt werden. Und so weiter wenn da auch wieder eine Zelle dabei ist, die keine Poos in der Nachbarschaft hat. Siehe http://minesweeperonline.com und Vorführung in der Vorlesung. |
* Es soll selbstverständlich auf alles geachtet werden, was Sie in der Vorlesung gelernt haben: gutes Klassendesign, Trennung in .h und .cpp Dateien, const correctness, richtige Verwendung von public und private, valgrind soll ohne Fehler durchlaufen, TODO: was noch. |
Line 41: | Line 43: |
* Bei gleichzeitigem Klick mit linker und rechter Maustaste: übrige Felder in der Nachbarschaft aufdecken, falls schon die volle Anzahl von Poos markiert. Sonst Felder nur kurz andeuten solange beide Maustasten gedrückt. Siehe http://minesweeperonline.com und Vorführung in der Vorlesung. | * Erkennen und Einlesen des RLE-kodierten Dateiformates (nicht viel mehr Arbeit). |
Line 43: | Line 45: |
* Auf Knopfdruck läuft eine Schafherde über die Wiese und kackt sie voll (= zusätzliche Poos in Zellen, die noch nicht aufgedeckt sind -> dann müssen sich auch die betroffenene Zahlenangaben ändern) | * Einlesen mehrerer Instanzen + ein Menu im Programm, in dem man die Instanz auswählen kann + Möglichkeiten, die Instanzen der Reihe nach durchzuspielen. |
Line 45: | Line 47: |
* Besondere grafische Effekte | * Minimale Anzahl der Züge pro Instant merken. |
Line 47: | Line 49: |
* High Score | * Was immer Ihnen noch (Sinnvolles und Sinnloses) einfällt. |
Line 49: | Line 51: |
== Projekt 2: PooSweeper (automatischer Löser) == | == Projekt 2: Sokoban (automatischer Löser) == |
Line 51: | Line 53: |
'''Kurzbeschreibung:''' Ein Programm, dass ein beliebiges gegebenes !PooSweeper Spiel von Anfang bis Ende automatisch durchspielt. Die Strategie sollte dabei so gut sein, dass sie unter bestimmten Bedinungen (siehe Anforderungen unten) mindestens die Hälfte aller Spiele erfolgreich löst. | '''Kurzbeschreibung:''' Ein Programm, das versucht eine gegebene Instanz zu lösen und dabei einfache Deadlocks erkennt. Die im SVN unter public/projekt angegebenen Instanzen sollten dabei alle korrekt gelöst werden. |
Line 53: | Line 55: |
'''Hintergund:''' Einfach ein paar Mal Minesweeper spielen und sich allgemeine Lösungsstrategien überlegen. Es gibt dazu auch viel Material auf dem Netz, von sehr einfach bis sehr tief. | '''Hintergund:''' Eine Darstellung der typischen Deadlocks findet sich unter http://www.sokobano.de/wiki/index.php?title=Deadlocks . Eine Darstellung von einfachen und komplexen Lösungsstrategien findet sich unter http://www.sokobano.de/wiki/index.php?title=Solver . |
Line 55: | Line 57: |
'''Anforderungen (Minimum):''' Folgende Anforderungen müssen für volle Punktzahl mindestens erfüllt sein | '''Anforderungen (Minimum):''' Folgende Anforderungen müssen mindestens erfüllt sein, um die volle Punktzahl erreichen zu können. |
Line 57: | Line 59: |
* Ein Zustand des Spiels soll mit einer Klasse ''!PooSweeperState'' realisiert werden, die eine Unterklasse der auf dem Wiki verlinkten abstrakten Klasse ''!PooSweeperStateBase'' ist. | * Eine Methode, die zumindest [[http://www.sokobano.de/wiki/index.php?title=Deadlocks#Dead_square_deadlocks|dead square deadlocks]] und [[http://www.sokobano.de/wiki/index.php?title=Deadlocks#Freeze_deadlocks|freeze deadlocks]] erkennt. |
Line 59: | Line 61: |
* Die Schritte des Lösers und der jeweilige Zustand des Spiels sollen visualisiert werden. Sie können dazu auf die auf dem Wiki bereitgestelle ''libpoo'' Bibliothek zurückgreifen (malt den aktuellen Zustand auf die Konsole). | * Ein Brute-Force Löser, der alle Möglichkeiten durchspielt, bis man einen Deadlock, eine vorherige Konfiguration oder die Lösung erreicht. Wenn es eine Lösung gibt, reicht es, irgendeine solche Lösung zurückzugeben (siehe optional für die kürzeste Lösung). Die Lösung soll im [[http://www.sokobano.de/wiki/index.php?title=Level_format#Solution|udlr Format]] zurückgegeben werden. |
Line 61: | Line 63: |
* Es sollen mindestens fünf prinzipiell verschiedene Strategien für den nächsten Zug implementiert sein. Beispiele für solche Strategien wurden in Vorlesung 11 vorgestellt. | * Falls es eine Lösung gibt, soll diese visualisiert werden. Sie können dazu auf die auf dem Wiki bereit gestellte ''libsokoban'' Bibliothek zurückgreifen. Diese stellt eine Funktion ''sokoban::visualize(std::string filename, std::string moves)'' zur Verfügung, die für eine gegebene Instanz und eine gegeben Zugfolge den Zustand der Instanz nach diesen Zügen malt. |
Line 63: | Line 65: |
* Für den Beginner Level (9 x 9, 10 Poos) sollen im Durchschnitt mindestens 80% aller Spiele gewonnen werden. Für den Intermediate Level (16 x 16, 40 Poos) mindestens 50%. Und für den Expert Level (16 x 30, 99 Poos) mindestens 10%. Dabei werden nur Spiele gezählt, bei denen nicht schon der erste Zug fehlschlägt. Benutzen Sie dazu die über die libpoo bereitgestelle Funktion !PooSweeperBenchmark::evaluate, siehe Code im SVN unter public/code/projekt . | * Die Bibliothek ''libsokoban'' stellt außerdem eine Funktion ''sokoban::evaluate(std::vector<std::string> movesPerInstance)'' zur Verfügung. Diese soll bei Kommandozeilenoption ''--evaluate'' mit Ihren (berechneten, nicht von Hand codierten) Lösungen für die auf dem Wiki gegebenen Instanzen aufgerufen werden. So können wir bei der Korrektur leicht schauen, welche Instanzen Ihr Löser erfolgreich lösen konnte. |
Line 65: | Line 67: |
* Alle Funktionalität, die mit Ein- bzw. Ausgabe zu tun hat, sollte sauber getrennt von den anderen Teilen in eigenen Methoden stehen und diese Methoden brauchen nicht getestet zu werden. Für alle anderen Methoden soll es selbstverständlich wie gehabt einen Unit Test geben. | * Dieselben Anforderungen an Unit Tests und allgemeine Eigenschaften des Codes wie für Projekt 1. |
Line 69: | Line 71: |
* Alle möglichen fortgeschritteneren Strategien. | * Ausgeben der kürzesten Lösung (falls es mehrere gibt, die wählen, bei der möglichst wenige Züge eine Kiste verschieben). |
Line 71: | Line 73: |
* Ansprechendere Grafik als in der gegebenen ''libpoo''. | * Erkennung auch von komplexeren Deadlocks. * Implementierung von fortgeschritteneren Strategien. * Ansprechendere Grafik als in der gegebenen ''libsokoban''. |
Line 83: | Line 89: |
* Sind diese Voraussetzungen erfüllt, bitte bis Donnerstag, den 24. Juli 2014, eine kurze Mail an Ihre*n Tutor*in (mit Cc an Axel Lehmann und an Hannah Bast) mit einer kurzen Beschreibung Ihres Projektes (ein Absatz) und einer kurzen Begründung, dass es an Umfang und Komplexität mit Projekt 1 oder 2 oben vergleichbar ist (ein Absatz). | * Das Projekt sollten von Umfang und Komplexität her den beiden Projekten oben vergleichbar sein. * Sie sollten in der Lage sein, das Projekt selbsttätig durchzuführen. (Bei allgemeinen Programmierfragen können Sie trotzdem gerne auf das Forum zurückgreifen.) * Sind diese Voraussetzungen erfüllt, bitte bis Donnerstag, den 7. Juli 2016, eine kurze Mail an Ihre*n Tutor*in (mit Cc an Axel Lehmann und an Hannah Bast) mit einer kurzen Beschreibung Ihres Projektes (ein Absatz) und einer kurzen Begründung, dass es an Umfang und Komplexität mit Projekt 1 oder 2 oben vergleichbar ist (ein Absatz). Wir werden diese Fälle dann am Freitag, den 8. Juli 2016 von 15 - 16 Uhr besprechen und Ihnen dann gleich Bescheid geben, ob wir einverstanden sind. |
Projekt zur Vorlesung '''Programmieren in C++''' im Sommersemester 2016
Bis Vorlesung 12 sind noch kleinere Änderungen möglich!
Es gibt drei Projekte zur Auswahl:
Projekt 1: Sokoban (das Spiel)
Projekt 2: Sokoban (der Löser)
Projekt 3: Ein Projekt eigener Wahl (nur für Fortgeschrittene)
Im Folgenden eine detailliertere Beschreibung der drei Projekte
Projekt 1: Sokoban (das Spiel)
Kurzbeschreibung: Das Spiel Sokoban soll mit Konsolengrafik realisiert werden.
Hintergrund: Eine voll-funktionale Online-Version des Spiels findet sich zum Beispiel hier: http://sokobanonline.com .
Anforderungen (Minimum): Folgende Anforderungen müssen für volle Punktzahl mindestens erfüllt sein
Einlesen einer Instanz aus einer Datei in dem hier beschriebenen Format. Es reicht, wenn das einfache Dateiformat (in dem explizit jedes Zeichen dargestellt wird) unterstützt wird.
- Konsolengrafik: dabei sollte jedes Objekt (Box, Spieler, Teil der Mauer) in einer eigenen Farbe gezeichnet werden, mit einer über Kommandozeilenparameter einstellbaren Anzahl Zeichen pro Objekt in x und y Richtung (und einer vernünftigen Defaulteinstellung).
- Bedienung über die Tastatur mit den Pfeiltasten.
- Undo Funktion, wobei die Anzahl Züge die man höchstens hintereinander rückgängig machen kann ein Argument in der Kommandozeile sein sollte (Default: 5).
- Alle Funktionalität, die mit Ein- bzw. Ausgabe zu tun hat, sollte sauber getrennt von den anderen Teilen in eigenen Methoden stehen und diese Methoden brauchen nicht getestet zu werden. Für alle anderen Methoden soll es selbstverständlich wie gehabt einen Unit Test geben.
- Es soll selbstverständlich auf alles geachtet werden, was Sie in der Vorlesung gelernt haben: gutes Klassendesign, Trennung in .h und .cpp Dateien, const correctness, richtige Verwendung von public und private, valgrind soll ohne Fehler durchlaufen, TODO: was noch.
Anforderungen (optional): Hier ein paar Ideen für optionale Erweiterungen:
- Erkennen und Einlesen des RLE-kodierten Dateiformates (nicht viel mehr Arbeit).
- Einlesen mehrerer Instanzen + ein Menu im Programm, in dem man die Instanz auswählen kann + Möglichkeiten, die Instanzen der Reihe nach durchzuspielen.
- Minimale Anzahl der Züge pro Instant merken.
- Was immer Ihnen noch (Sinnvolles und Sinnloses) einfällt.
Projekt 2: Sokoban (automatischer Löser)
Kurzbeschreibung: Ein Programm, das versucht eine gegebene Instanz zu lösen und dabei einfache Deadlocks erkennt. Die im SVN unter public/projekt angegebenen Instanzen sollten dabei alle korrekt gelöst werden.
Hintergund: Eine Darstellung der typischen Deadlocks findet sich unter http://www.sokobano.de/wiki/index.php?title=Deadlocks . Eine Darstellung von einfachen und komplexen Lösungsstrategien findet sich unter http://www.sokobano.de/wiki/index.php?title=Solver .
Anforderungen (Minimum): Folgende Anforderungen müssen mindestens erfüllt sein, um die volle Punktzahl erreichen zu können.
Eine Methode, die zumindest dead square deadlocks und freeze deadlocks erkennt.
Ein Brute-Force Löser, der alle Möglichkeiten durchspielt, bis man einen Deadlock, eine vorherige Konfiguration oder die Lösung erreicht. Wenn es eine Lösung gibt, reicht es, irgendeine solche Lösung zurückzugeben (siehe optional für die kürzeste Lösung). Die Lösung soll im udlr Format zurückgegeben werden.
Falls es eine Lösung gibt, soll diese visualisiert werden. Sie können dazu auf die auf dem Wiki bereit gestellte libsokoban Bibliothek zurückgreifen. Diese stellt eine Funktion sokoban::visualize(std::string filename, std::string moves) zur Verfügung, die für eine gegebene Instanz und eine gegeben Zugfolge den Zustand der Instanz nach diesen Zügen malt.
Die Bibliothek libsokoban stellt außerdem eine Funktion sokoban::evaluate(std::vector<std::string> movesPerInstance) zur Verfügung. Diese soll bei Kommandozeilenoption --evaluate mit Ihren (berechneten, nicht von Hand codierten) Lösungen für die auf dem Wiki gegebenen Instanzen aufgerufen werden. So können wir bei der Korrektur leicht schauen, welche Instanzen Ihr Löser erfolgreich lösen konnte.
- Dieselben Anforderungen an Unit Tests und allgemeine Eigenschaften des Codes wie für Projekt 1.
Anforderungen (optional): Hier ein paar Ideen für optionale Erweiterungen:
- Ausgeben der kürzesten Lösung (falls es mehrere gibt, die wählen, bei der möglichst wenige Züge eine Kiste verschieben).
- Erkennung auch von komplexeren Deadlocks.
- Implementierung von fortgeschritteneren Strategien.
Ansprechendere Grafik als in der gegebenen libsokoban.
Projekt 3: ein Projekt eigener Wahl
Kurzbeschreibung: Ein Projekt eigener Wahl, das den beiden vorherigen von Umfang und Komplexität vergleichbar ist.
Hintergrund: Ihnen überlassen.
Anforderungen (Minimum):
- Ein Projekt eigener Wahl ist nur für diejeniger Kursteilnehmer*innen gedacht, die in den bisherigen Übungsblättern fast volle Punktzahl erreicht haben und die das bisher vermittelte Wissen relativ problemlos voll durchdrungen haben.
- Das Projekt sollten von Umfang und Komplexität her den beiden Projekten oben vergleichbar sein.
- Sie sollten in der Lage sein, das Projekt selbsttätig durchzuführen. (Bei allgemeinen Programmierfragen können Sie trotzdem gerne auf das Forum zurückgreifen.)
- Sind diese Voraussetzungen erfüllt, bitte bis Donnerstag, den 7. Juli 2016, eine kurze Mail an Ihre*n Tutor*in (mit Cc an Axel Lehmann und an Hannah Bast) mit einer kurzen Beschreibung Ihres Projektes (ein Absatz) und einer kurzen Begründung, dass es an Umfang und Komplexität mit Projekt 1 oder 2 oben vergleichbar ist (ein Absatz). Wir werden diese Fälle dann am Freitag, den 8. Juli 2016 von 15 - 16 Uhr besprechen und Ihnen dann gleich Bescheid geben, ob wir einverstanden sind.