Hallo liebe Community,
anstatt mich dem Wahnsinn des Karnevals hinzugeben, habe ich die Zeit genutzt um mir einen neuen Programmier-Contest auszudenken!
Der Titel des neuen Contests lautet "Rutschige Angelegenheit", es handelt sich um einen Geschwindigkeits-Contest (eure Programme müssen möglichst schnell sein), und er läuft bis einschließlich zum 03.03.2013.
Das Spiel
Diesmal geht es um ein einfaches Spiel, das ich "Sokoslide" nenne.
Ein Sokoslide-Level sieht wie folgt aus:
Jedes Level besteht aus
16x16 Feldern.
Ein Feld kann folgendes sein:
- Leer bzw. Eisfläche
- Mauer
- Spielfigur (roter/grüner/blauer Kreis)
- Zielfeld (rotes/grünes/blaues Quadrat)
Wichtige Eigenschaften eines Levels:
- Der innere Rand eines Levels besteht immer vollständig aus Mauern, so wie im Beispiel oben.
- In jedem Level gibt es
exakt 3 Spielfiguren (eine in jeder Farbe) und
exakt 3 Zielfelder (eins in jeder Farbe).
- Auch wenn das im Beispiel-Level der Fall ist, ist
nicht garantiert, dass sich die Spielfiguren und die Zielfelder direkt neben einer Mauer befinden.
- Der betretbare Bereich jedes Levels ist eine zusammenhängende Fläche. Es kann also nicht passieren, dass zwei Spielfiguren durch Mauern komplett getrennt sind.
Das Ziel des Spiels ist es, alle drei Spielfiguren auf ihre farblich passenden Zielfelder zu bewegen.
Eine Spielfigur kann sich aber nicht beliebig bewegen, sondern nur in eine Richtung (links, rechts, oben, unten)
angestoßen werden. Da alles auf einer Eisfläche stattfindet, "rutscht" sie so lange weiter, bis sie entweder gegen eine Mauer oder gegen eine andere Spielfigur stößt (daher der Name des Contests). Sie bleibt insbesondere auch nicht automatisch stehen, wenn sie ein Zielfeld erreicht hat.
Schauen wir uns einmal eine Lösung für das oben gezeigte Level an (anklicken zum Vergrößern):
Wie man sieht, benötigt diese Lösung
14 Züge.
Tatsächlich ist dies auch eine kürzeste Lösung, d.h. mit weniger als 14 Zügen kann man das Level nicht bewältigen.
Die Aufgabe
Vielleicht könnt ihr euch jetzt bereits denken, was eure Aufgabe ist ...
Ihr sollt eine Funktion programmieren, die für ein gegebenes Sokoslide-Level berechnet, wie viele Züge mindestens für die Lösung benötigt werden.
Übergibt man der Funktion also das Level aus unserem Beispiel, dann müsste sie korrekterweise mit 14 antworten.
Folgender Code zeigt die Definition der Funktion sowie des Typs
Level, der einfach nur ein 16x16-
char-Array ist.
Im Code seht ihr auch bereits, wie die verschiedenen Spielfelder im Array dargestellt werden, nämlich mit den Zeichen
. # r g b R G B:
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// 16x16-Spielfeld.
// Jedes Feld ist entweder:
// - leer '.'
// - Mauer '#'
// - Block 'r', 'g', 'b'
// - Zielfeld 'R', 'G', 'B'
typedef char Level[16][16];
// Die zu programmierende Funktion:
// Gegeben ist ein garantiert in höchstens 255 Zügen lösbares Level.
// Gesucht, als Rückgabewert, ist die Anzahl der Züge der optimalen Lösung (Mindestanzahl).
int numMovesToSolve(const Level& level)
{
// Hier kommt dein Code!
// Berechne die zur Lösung benötigte Anzahl von Zügen und gib sie zurück.
return 0;
}
|
Das Beispiel-Level von vorhin sieht "kodiert" wie folgt aus:
|
|
Quellcode
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
################
#.......R......#
#..............#
#..####.....####
#..####.....####
#..####..b..####
#..####..#.....#
#..####..#.....#
#........#.....#
#..####..#..g..#
#..####..####..#
#..##.r.......B#
#..##..........#
#......G.....###
#............###
################
|
Worauf ihr euch verlassen dürft
Um die Sache nicht unnötig kompliziert zu machen, dürft ihr euch auf folgende Dinge verlassen:
- Es gibt keine ungültigen Levels bzw. Eingaben.
- Jedes übergebene Level ist lösbar, und zwar mit mindestens 3 und höchstens 255 Zügen.
- Die Eigenschaften der Levels, die weiter oben aufgelistet wurden, werden immer eingehalten.
Das Programmier-Paket
Ich habe ein kleines Test-Framework geschrieben, mit dem ihr eure Lösung testen könnt. Es enthält eine Datei
levels.txt, in der bereits 5 Beispiel-Levels zusammen mit ihren korrekten Lösungen enthalten sind. Das Framework lädt diese, ruft eure Funktion auf und testet sie auf Korrektheit. Außerdem misst es die Geschwindigkeit eurer Lösung.
Im Zip-Paket findet ihr einen
CodeLite-Workspace und eine Solution für Visual C++ 2010.
Das Paket könnt ihr hier herunterladen:
zum Download
Was ist erlaubt/verboten?
Zunächst gelten die
normalen Regeln. Das Wichtigste hier noch einmal:
- Programmiersprache: C++!
- Kein Inline-Assembler erlaubt, auch keine Intrinsics.
- Eure Funktion darf keine statischen Variablen benutzen oder sich auf sonstige Weise Dinge für einen nachfolgenden Aufruf "merken". Das gilt auch für Speicherreservierungen.
- Keine Nicht-Standard-Libraries benutzen!
- Kein OpenMP/Multithreading.
Wie wird ausgewertet / Worauf kommt es an?
Ich werde jede eingereichte Lösung mit einer Reihe von Sokoslide-Levels testen (nicht nur die, die im Paket enthalten sind!).
Oberstes Kriterium ist die Korrektheit. Liefert eine Funktion eine falsche Antwort, führt dies zur Disqualifikation.
Alle korrekten Lösungen werden nun auf Geschwindigkeit getestet. Um die Benutzer von GCC bzw. Visual C++ nicht zu benachteiligen, werde ich versuchen jede Lösung mit beiden Compilern zu kompilieren und dann jeweils das bessere Ergebnis benutzen. Wenn eine Lösung nur mit einem Compiler kompiliert werden kann, ist das nicht weiter schlimm, aber ihr verliert diesen Vorteil.
Wie genau die Lösungen untereinander verglichen werden, kann ich jetzt noch nicht sagen. Es wird aber ähnlich ablaufen wie in früheren Contests dieser Art.
Ich werde Visual C++ 2012 sowie die bei der neuesten CodeLite-Version mitgelieferte MinGW-Version zum Kompilieren benutzen, und zwar mit den Standardeinstellungen für den Release-Mode (beim GCC bedeutet das -O2). Bei Visual C++ wird die Größe des Stacks der von MinGW angepasst (2 MB), um eine bessere Vergleichbarkeit zu gewährleisten. Ich benutze die 32-Bit-Versionen der Compiler.
Was gibt es zu gewinnen?
Dem Gewinner des Contests winkt ein besonderer Rang im Forum (siehe z.B. Helmut!), unendlicher Ruhm und Ehre, sowie ein kleiner Sachpreis (ich weiß jedoch noch nicht, was es sein wird).
Was muss ich tun, um mitzumachen?
Lade dir das Programmier-Paket herunter, tüftle eine Lösung aus und teste sie auf Herz und Nieren. Sende deinen Code dann an
contest@spieleprogrammierer.de, und zwar bis zum 03.03.2013 (23:59:59 Uhr). Es ist kein Problem, mehrfach eine Lösung einzureichen (ich benutze dann die zuletzt eingereichte Version). Gib in der E-Mail auch bitte deinen Benutzernamen im Forum an. Alle Lösungen werden später veröffentlicht.
Bei Fragen/Problemen schreibt bitte in diesen Thread.
Viel Erfolg! 
Aber für den Contest akzeptabel. 
Schöne Aufgabe 
Szene »
Global Game Jam 2013 Leizpig - Videoreviews der Ergebnisse
(29.01.2013, 23:05)
19.04.2024, 09:32
Zum Seitenanfang
