CONTEST: Mapgenerierung

Alle Jahre wieder kommt das Contestkind auf die Erde nieder und sagt euch, daß ihr gefälligst was programmieren sollt. Jetzt ist alle Jahre wieder, also haben wir einen aufregenden Contest für euch vorbereitet, der euch die Socken ausziehen wird, garantiert*.

Bei diesem Contest (und ja, wir wollen die Dinger in Zukunft wieder etwas häufiger machen) geht es um verlassene Verliese und verführerisch verfallene... Fallen. Also, um Dungeons, wie man sie aus Rollenspielen (ob Computer- oder Pen and Paper-) kennt. Ordentliche Dungeons wachsen nicht auf Bäumen und da kommt ihr ins Spiel: Ihr sollt die unglaublichen mathematischen Fähigkeiten eurer Heimrechner benutzen, um ebensolche Dungeons zu generieren.

Nebenbei müssen es keine Dungeons sein, aber es muß eine Art Plan (oder Sammlung von Plänen) rauskommen, der etwas in der Art darstellt. Wenn euer Programm also eine Raumstation oder eine Stadt modelliert, die den Anforderungen entspricht – good to be you.

Die Regeln hier einmal ganz trocken:

Alle Einsendungen müssen folgende Voraussetzungen erfüllen:
1. Das Programm muß mindestens einen Parameter entgegennehmen und verarbeiten: Wie viele Räume die Karte mindestens haben soll (mögliche Korridore nicht mitgezählt).
2. Anhand der gegebenen Parameter muß eine Karte generiert werden, in der mindestens die gewünschten Räume vorhanden sind. Bei gleichem Input sollte das Programm unterschiedlichen Output erzeugen.
2.1. Falls der Seed der Zufallsfunktion als Parameter umgesetzt wird, darf in diesem Fall natürlich deterministisch gearbeitet werden. Der Defaultwert sollte aber "zufällig" sein.
3. Die erzeugte Karte muß mindestens einen Eingang und ein "Ziel" haben (wie auch immer das geartet sein mag).
4. Es darf keinen Raum geben, der nicht irgendwie mit dem Eingang verbunden ist.
5. Die erzeugte Karte muß mindestens in einem grafischen Format ausgegeben werden (ASCII art, PNG, SVG, HTML+CSS...).
6. Das Programm muß im Quelltext abgegeben werden. Binaries sind als Zugabe erlaubt, nicht aber als alleinige Abgabe. Wir wollen hier voneinander lernen.

Des Weiteren ist erwünscht:
7. Die Karte sollte halbwegs kompakt sein. Niemand mag kilometerlange Gänge zwischen kleinen Räumen.
8. Achtet darauf, daß die meisten User nur Programme bewerten, die sie auch ausführen können. Kompatibilität ist ein wichtiger Faktor, wenn ihr Punkte kriegen wollt.
9. Ebenso achtet auf lesbaren Quelltext. Wie schon in Punkt 6 gesagt: Wir wollen hier voneinander lernen.
10. Beispieloutput bei der Abgabe ist erwünscht, aber nicht Pflicht.

Weitere Leistungen des Programms sind vollkommen optional und euch freigestellt


Bewertet wird per Abstimmung unter den Usern des Forums. Die genauen Modalitäten werden zum Abstimmungstermin bekannt gegeben.
Abgabe ist bis zum 09.03.2009 23:59:59 16.03.2009 00:00:00; die Abstimmung erfolgt zwischen dem 10. 16.03.2009 und dem 16. 22.03.2009.
Der Preis ist das tolle Gefühl, gewonnen zu haben. Oh, und eine tolle Signatur. Und es gehen Gerüchte von einem tollen Sonderrang um. Aber das tolle Gefühl ist der wichtige Teil.



Viel Spaß.


* Es wird keine Garantie für irgendwelche Qualitäten des Contests übernommen.

Wäre mal ein grund, sich mit grafik-anlegung und mit abstrakten planvorgaben zu beschäftigen.
Vielleicht ist mir ja langweilig.
(Und man hat ja bekanntlich recht hohe Chancen, hier zu gewinnen, wenn man überhaupt etwas einreicht :D)

Gute Contestidee.
Man könnte das ganze ja gleich auch mit einem Tutorial verbinden, falls jemand lust darauf hat.
Ich habe nämlich schon öfter zum Thema Mapgenerierung gegoogelt, aber nichts vernünftiges gefunden.
Das Tutorial müsste imo nicht mal für eine bestimmte Sprache geschrieben sein, sondern könnte generell die Struktur des Skripts für die Mapgenerierung beschreiben. Die Umsetzung in der gewünschten Sprache könnte dann ja jeder selbst übernehmen.

Zitat:

---

Zitat von rgb

Gute Contestidee.
Man könnte das ganze ja gleich auch mit einem Tutorial verbinden, falls jemand lust darauf hat.
Ich habe nämlich schon öfter zum Thema Mapgenerierung gegoogelt, aber nichts vernünftiges gefunden.
Das Tutorial müsste imo nicht mal für eine bestimmte Sprache geschrieben sein, sondern könnte generell die Struktur des Skripts für die Mapgenerierung beschreiben. Die Umsetzung in der gewünschten Sprache könnte dann ja jeder selbst übernehmen.

---

Jep, spätestens hinterher wird sicher irgendwer die Erkenntnisse aus dem Contest zusammenfassen.

Freut mich übrigens, dass die Idee gut ankommt. Wir haben ne ganze Weile gegrübelt, bis wir ein interessantes Thema und dazu noch eine Aufgabe mit halbwegs angemessenem Schwierigkeitsgrad hatten.

Ich finde die Idee auch interessant. Hat etwas Herausforderndes bezüglich dem Zufallsalgorithmus, aber auch nicht zu technisch oder trocken.
Leider habe ich lange nichts mehr mit einer Programmiersprache gemacht und müsste mich erst einarbeiten, bevor da was kommen könnte. Einen algorithmus hab ich aber schon ausgearbeitet, der auch funktionieren sollte... :)

Es lebt. :eek:

Hm, richtig gute Dungeons sind handgemacht. Ich wage zu bezweifeln, dass ein Programm einen richtig schönen, epischen Dungeon generieren kann. Was sollte bei der Bewertung denn wichtiger sein? Der Code oder die Ästhetik des Dungeons? Damit ein Programm einen "echten" Dungeon erstellt (mit fiesen, verwirrenden Gängen, kleinen Metzelräumen und einer großen Endgegner-Halle), sind mehr als reine Zufalls-Algorithmen nötig.

freundliche Grüße, Rolus

Zitat:

---

Zitat von Rolus

Damit ein Programm einen "echten" Dungeon erstellt (mit fiesen, verwirrenden Gängen, kleinen Metzelräumen und einer großen Endgegner-Halle), sind mehr als reine Zufalls-Algorithmen nötig.

---

Das ist doch auch keine Bedingung, dass der Algorithmus rein aus Zufallszahlen besteht, man kann da ja ein paar Abhängigkeiten und Rahmenbedingungen schaffen.

Zitat:

---

Zitat von Rolus

Hm, richtig gute Dungeons sind handgemacht. Ich wage zu bezweifeln, dass ein Programm einen richtig schönen, epischen Dungeon generieren kann. Was sollte bei der Bewertung denn wichtiger sein? Der Code oder die Ästhetik des Dungeons?

---

Wüsste ich auch gerne.

Ich würde wenn, dann was schreiben, das für PnP Rollenspiele geeignet ist, und sich dann nur auf die halbwegs logische ANlegung von Räumen auf einem Platz beschränkt. Sprich, Büroräume, Burgverliese und ähnliches, was auch immer irgendwie Funktionell gebaut wird.
Da braucht man keine fiesen Gänge, keine Monster etc.

Zitat:

---

Zitat von Rolus

Es lebt. :eek:

Hm, richtig gute Dungeons sind handgemacht. Ich wage zu bezweifeln, dass ein Programm einen richtig schönen, epischen Dungeon generieren kann. Was sollte bei der Bewertung denn wichtiger sein? Der Code oder die Ästhetik des Dungeons? Damit ein Programm einen "echten" Dungeon erstellt (mit fiesen, verwirrenden Gängen, kleinen Metzelräumen und einer großen Endgegner-Halle), sind mehr als reine Zufalls-Algorithmen nötig.

freundliche Grüße, Rolus

---

Bewertet wird einerseits der Code und andererseits der Gesamteindruck (Qualität des Outputs, Bedienbarkeit, Zusatzfeatures, ...) des abgelieferten Programms. Worauf dann am meisten Wert gelegt wird, hängt von jedem selbst ab. Es wird keine Jury geben, die nach festen Kriterien Punkte vergibt, sondern ihr müsst wie schon bei einigen vergangenen Contests um die Gunst der Userschaft kämpfen.

Außerdem hat niemand verlangt, dass die Dungeons rein zufällig bestimmt werden. Es geht lediglich darum, dass ihr auf Basis mindestens einer Zufallszahl und einer Usereingabe einen Dungeon generiert. Ob ihr dafür vorher von Hand Einzelteile erstellt, die ihr dann zusammen klebt oder ob ihr euch was Anderes einfallen lasst, bleibt ganz allein euch überlassen. Solche Sachen haben wir ganz bewusst offen gelassen. Genau so, wie es euch überlassen bleibt, ob ihr einen "klassischen" Dungeon in Form einer Höhle, eine Stadt, ein Raumschiff, einen Bürokomplex oder sonst was baut.

Verstehe ich es richtig, dass man
a) Eine (3D) Welt kreieren soll, durch die man auch laufen kann.
und
b) Eine 2D Karte dieser Welt erstellen soll. ( Wie man es aus zahlreichen spielen kennt, eine Map, die sich dann in irgendeiner Ecke versteckt oder sich auf M öffnet.)
?

Interessant, interessant.
Wenn ich Zeit und Lust finde, bin ich auf jeden Fall dabei. Aber versprechen kann ich nichts... Die chronische Unlust ist bei mir nicht nur 'ne Ausrede... ._."

Auf jedenfall eine gute Idee, macht sicher Spaß. D:

Zitat:

---

Zitat von makkurona

Verstehe ich es richtig, dass man
a) Eine (3D) Welt kreieren soll, durch die man auch laufen kann.
und
b) Eine 2D Karte dieser Welt erstellen soll. ( Wie man es aus zahlreichen spielen kennt, eine Map, die sich dann in irgendeiner Ecke versteckt oder sich auf M öffnet.)
?

Interessant, interessant.
Wenn ich Zeit und Lust finde, bin ich auf jeden Fall dabei. Aber versprechen kann ich nichts... Die chronische Unlust ist bei mir nicht nur 'ne Ausrede... ._."

Auf jedenfall eine gute Idee, macht sicher Spaß. D:

---

Nur eine 2D Darstellung ist gefordert und selbst da reicht ein Grundrissplan. Das Ergebnis muss auch in keiner Form interaktiv sein. Wenn du zusätzlich mehr machen willst, nur zu. Das dürfte deine Chancen erhöhen.

Sehr interessanter Contest. Ich kann aber leider nicht sagen ob ich mitmachen kann wegen Studium, Beruf, Führerschein und Freundin. o.o Bin schon auf die Ergebnisse anderer gespannt. Postet Zwischenstände wenn ihr was habt!

Zitat:

---

Zitat von Rolus

Es lebt. :eek:

Hm, richtig gute Dungeons sind handgemacht. Ich wage zu bezweifeln, dass ein Programm einen richtig schönen, epischen Dungeon generieren kann.

---

Generierte Dungeons können durchaus stimmig oder zumindest eine gute Ausgangsbasis für händische Nachbearbeitung sein.

Hier mal 2 Beispielscreens von dem was ich bisher habe.
http://img217.imageshack.us/img217/4065/mapgen01.th.pnghttp://img502.imageshack.us/img502/6032/mapgen02.th.png

Der rote Fleck wird ein Eingang, der blaue Fleck ein Ausgang und grüne Flecken Raumeingänge. Räume selbst fehlen noch.
Generiert werden die Maps mit folgendem Lindenmayer-System :
Start: FX
F -> F++F----F++[++++FG]-F[---F]
G -> [+F]
Iterationen: 4
Winkel: 17°

Jedes G das letztendlich überbleibt wird zu einem Raumeingang. Die Berechnung des L-Systems bricht ab, sobald die gewünschte Raumanzahl +1 (für den Ausgang) erreicht wurde. Aufgrund der Beschränkung auf 4 Iterationen(mehr und eine sehr hohe Raumanzahl > 50 ergeben beim derzeitigen System oft Unsinn) ist auch die maximale Raumanzahl limitiert. Der Zufallsfaktor bei der Generierung ist die Startposition des L-Systems nach 4 Iterationen die zwischen 0 und der Hälfte des Systems liegt.

Interessant, eine kleine Tileset - Engine in Java.
Das hier ist, was ich bis jetzt habe: http://drakes.dr.ohost.de/dungeon_genotype/
Ich habe mich zuerst um das Frontend gekümmert, es wird noch kein Dungeon generiert. Ausserdem habe ich hierfür extra eine Art winziges PHP-Prototype erstellt, XHTML wird per PHP-Objekte erstellt.

Ist mal wieder ohost.de, also Werbung wegklicken, sonst klappt das Javascript nicht richtig. (Dazu werden Cookies benötigt)
(Hoffentlich werde ich wegen der Figur nicht angeklagt *g*)

Wahnsinn, wieviel Mühe ihr euch alle mit der Grafikausgabe gebt... ich fürchte, meine wird sich auf was beschränken, was aussieht, wie eine Paintkritzelei.

Also ich finds schonmal Klasse dass man da im Browser durch die Karte marschieren kann ohne so heftige zusätze wie Flash zu verwenden. Alles über Javascript?

Ja, es ist alles Javascript(also das Herumlaufen, das generieren wird dann PHP sein), genauer gesagt Prototype + script.aculo.us. Verwende ich zurzeit meistens, wobei ich vielleicht auch mal The Dojo Toolkit anschauen sollte. :)

Zitat:

---

Zitat von Drakes

Ist mal wieder ohost.de, also Werbung wegklicken, sonst klappt das Javascript nicht richtig. (Dazu werden Cookies benötigt)
(Hoffentlich werde ich wegen der Figur nicht angeklagt *g*)

---

Zeigt unter Firefox 3.0.7 (OS X) nicht immer was an; manchmal kommt nur eine schwarze Fläche. Genauer gesagt: Immer dann, wenn vorher die Werbung angezeigt wurde.


Was mein Ding angeht: Bisher habe ich einen halben Algorithmus fertig (implementiert in PHP) und die Ausgabe ist eine Tabelle, deren Zellen ich per CSS einfärbe. Das ist häßlich, ging aber schnell zu coden. Die endgültige Ausgabe wird wohl per gd in ein Bild gehen, um die Seite zu verschlanken.

Mein erster Algorithmus ist sehr primitiv, kann aber mißbraucht werden, um nette Höhlen zu generieren. Nur haben die dann keine Räume mehr, aber das ist eh ein Nebenprodukt. Weitere sind in Planung.

Zitat:

---

Zitat von Jesus_666

Zeigt unter Firefox 3.0.7 (OS X) nicht immer was an; manchmal kommt nur eine schwarze Fläche. Genauer gesagt: Immer dann, wenn vorher die Werbung angezeigt wurde.

---

Same here (Opera 9.63)

Ich bin im Übrigen bis jetzt noch nicht über ein paar Ideen rausgekommen, aber ich denke, das wird noch.

Edit:
Ich hab grad mal angefangen, einzelne Räume zu generieren, die ich später verbinde. Hier ist einer davon:
http://www.wecallit42.de/temp/test.svg

Edit 2:
Noch einer, mit einem leicht veränderten Algorithmus:
http://www.wecallit42.de/temp/test2.svg

Hab leider keine Zeit mehr zum Weitermachen.

Das Programm gibts unter
http://gebackene-ente.at/nudelsalat/...pGenerator.zip
In dem Zip ist sowohl der Sourcecode als auch ein ausführbares Jar. Unter Linux(Ubuntu) hat es mir nur beim Starten des Programmes mit der Shell das Chipset angezeigt. ("./MapGenerator.jar" in der Shell ausführen)

Unter OS X Leopard krieg ichs auch nicht zum Laufen:

Code:

---

mac42white-2:Desktop dfyx$ java -jar MapGenerator.jar
Exception in thread "main" java.lang.UnsupportedClassVersionError: Bad version number in .class file
        at java.lang.ClassLoader.defineClass1(Native Method)
        at java.lang.ClassLoader.defineClass(ClassLoader.java:675)
        at java.security.SecureClassLoader.defineClass(SecureClassLoader.java:124)
        at java.net.URLClassLoader.defineClass(URLClassLoader.java:260)
        at java.net.URLClassLoader.access$100(URLClassLoader.java:56)
        at java.net.URLClassLoader$1.run(URLClassLoader.java:195)
        at java.security.AccessController.doPrivileged(Native Method)
        at java.net.URLClassLoader.findClass(URLClassLoader.java:188)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:316)
        at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:280)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:251)
        at java.lang.ClassLoader.loadClassInternal(ClassLoader.java:374)

---

Ich vermute mal, dass du irgendwas Java 1.6 spezifisches verwendest, was unter OS X noch nicht zur Verfügung steht.

Zitat:

---

Zitat von DFYX

Ich vermute mal, dass du irgendwas Java 1.6 spezifisches verwendest, was unter OS X noch nicht zur Verfügung steht.

---

Muss er gar nicht: wenn ich mich nicht irre kommt der Fehler einfach, wenn die Runtime die Version des Compilers, mit dem die .class-Files erstellt wurden, nicht unterstützt. Also solange man javac 1.6 zum Kompilieren verwendet, wird (afaik) nichtmal ein stinknormales Hello-World-Programm unter OS X rennen.
Kompiliere einfach selber von Source, dann kann es zumindest gehen – wenn er nicht zusätzlich noch J6-Spezifisches verwendet hat.

@ Markus: Ahja, das sieht schon mal sehr nett aus. :D Also, es ist zwar dringend anzuraten, den Output auf /dev/null zu leiten, weil sonst die Performance unter alle erträglichen Maße sinkt, aber sonst ist's schon ein guter Anfang. ^^'
Aber schade, dass du nicht weitermachen kannst, hat doch noch einige Bugs. Z.B. überschneiden sich Räume manchmal mit Gängen, sodass man sie bei der Textur-Darstellung manchmal gar nicht erkennt. Naja, aber das wirst du ja eh selber wissen.

Zum Thema: Hört sich interessant an. Wie es der Zufall so will, habe ich genau eine Woche Urlaub. Mal sehen, wenn mir langweilig ist werde ich mich bestimmt an diesen Contest erinnern^^.

Wobei: So wie ich mich wieder kenne, wird meine Grafikausgabe wohl nur auf ASCII-Art beschränkt und ein Konsolenprogramm sein... Mal schauen, was ich zusammenkriegen werde...

Ich hab auch mal angefangen, was in Python zu basteln. Das Programm erzeugt SVGs als Ausgabe. Die Platzierung der Gänge und Räume funktioniert eigentlich schon gut, es könnten allerdings noch mehr Gänge wegfallen, damit der Dungeon interessanter wird.

Eine Beispielausgabe gibt es hier. Der rote Raum ist der Startraum, der blau der Endraum und die gelben sind Bossräume. Der Algorithmus zum bestimmen der selbigen ist aber noch ziemlich primitiv, das werde ich wohl noch verbessern müssen (Es ist einfach der erste generierte Raum der Startpunkt und der letzte der Endpunkt, auch wenn die direkt nebeneinander liegen).

@DFYX
Versuchs mal damit:
http://gebackene-ente.at/nudelsalat/...erator_1.5.zip
Ansich war im Code eh nichts 1.6 spezifisches bis auf die @Override notation die das 1.5jdk wohl noch nicht hat.

@Thomas
Hab einfach mal die brutalen System.outs entfernt. Ja, das Programm hat leider noch Bugs und der Code macht rapid prototyping alle Ehre aber was solls. ^^
Ich erwarte von dir Morgen auch ne Abgabe! :p

Zitat:

---

Zitat von Jesus_666

Zeigt unter Firefox 3.0.7 (OS X) nicht immer was an; manchmal kommt nur eine schwarze Fläche. Genauer gesagt: Immer dann, wenn vorher die Werbung angezeigt wurde.

---

Das habe ich ja genau gemeint. ^^ Daher muss man ja auch die Cookies aktiviert haben, damit beim zweiten Mal die Werbung nicht mehr kommt, irgendwie macht die, das onload kaputt oder so.

@Manuel: Wir haben keine Woche mehr. :eek:

Wer ist Thomas?

Es laeuft zur Zeit eine Umfrage, ob wir den Contest um eine Woche verlaengern wollen.
Also wenn ihr noch etwas Zeit braucht, kein Problem unsererseits.

Ich möchte nur nochmal dran erinnern, dass der Contest fast vorbei ist und bis jetzt fast niemand von denen, die mitmachen wollten, auch was abgegeben hat. Verlinkt also bitte Euere Meisterwerke.

Dann will ich mal den Anfang machen und meinen Beitrag hier einstellen. Ich hab doch nicht mehr wirklich was daran gemacht, vielleicht tue ich ja noch was und editiere das dann *shrug*

Klick mich!

Für die Bedienungsanleitung einfach generate.py --help ausführen. Viel Spaß damit :D

EDIT:
So, für csg das ganze auch nochmal als Zip ;)

EDIT 2:
Und auch noch ein Windows Binary für Whiz :P

EDIT 3:
Ich weise hier mal drauf hin, das nur Größen jenseits von 200 Pixeln halbwegs Sinn machen. Draunter funktioniert das Programm eventuell nicht richtig. Aber wer will schon einen Minidungeon :P

Jetzt hätte ich mich fast mit dem Termin vertan - Ich dachte, Abgabe ginge bis morgen Abend >_>''

Egal, hier ist mein halbwegs fertiger Beitrag. Nich so schön und komplex geworden, wie ich es mir zuerst gewünscht hatte, aber wenigstens etwas:

http://www.npshare.de/files/521c8e42...-Generator.rar

Ich liefer' nichts ab – der erste Algo (stumpf Rechtecke in die Map stanzen) ist so primitiv, daß ich nicht motiviert war, ihn zuende zu programmieren; der zweite (tilebasiertes rekursives Wachstum) produziert ab und zu Müll und ich kriege in der Zeit weder Backtracking noch eine sinnvolle Gewichtung der Tiles noch eine Abbruchbedingung implementiert; der dritte (Dungeon als Graph mit den Räumen als Kanten) ist nicht mal angefangen. Gibt von mir also nichts bewertbares.

Zumindest in die Top3 sollten wirs damit alle schaffen.

Leute, ist das echt euer ernst, dass es nach dem so viel versprechenden Anfang nur DREI Abgaben gibt ? Und das, obwohl wir eine Woche verlaengert haben ? Oder hab ich wen uebersehen ?

Braucht ihr vielleicht nochmals mehr Zeit ? Ich finde das irgendwie sehr schade.

Zitat:

---

Zitat von Ineluki

Leute, ist das echt euer ernst, dass es nach dem so viel versprechenden Anfang nur DREI Abgaben gibt ? Und das, obwohl wir eine Woche verlaengert haben ? Oder hab ich wen uebersehen ?

Braucht ihr vielleicht nochmals mehr Zeit ? Ich finde das irgendwie sehr schade.

---

Dachte auch wir hätten heute noch Zeit genau wie csg, denn zuerst war ja 09.03.2009 23:59:59 und dann 16.03.2009 00:00:00, was ja 6 Tage sind und ich hab das nicht überprüft ^^ Ich wollte heute versuchen einen Algorithmus zu implementieren. (Viel Zeit für den Rest verbraucht ^^")

Jetzt macht den Kram mal fertig, besser spät als nie. Bringt ja nichts, wenn wir nur drei Einsendungen haben. Mal schaun, ich werd mich an meins gleich auch nochmal ransetzen.

Zitat:

---

Zitat von Jesus_666

Ich liefer' nichts ab – der erste Algo (stumpf Rechtecke in die Map stanzen) ist so primitiv, daß ich nicht motiviert war, ihn zuende zu programmieren; [...]

---

Ging mir ähnlich. Meine erste Idee war auch überaus simpel. Es gibt einen Gang und die Räume liegen rechts, links oder direkt auf dem Gang. Sieht dann etwa so aus. :p
Hab's zwar soweit fertig gemacht, aber sehenswert ist das Ergebnis halt nicht. Der Aufwand war auch entsprechend gering. Für etwas Komplexeres hat mir dann leider die Zeit gefehlt.
edit: Eine offizielle Abgabe ist das nicht.

freundliche Grüße, Rolus

Zitat:

---

Zitat von Ineluki

Leute, ist das echt euer ernst, dass es nach dem so viel versprechenden Anfang nur DREI Abgaben gibt ? Und das, obwohl wir eine Woche verlaengert haben ? Oder hab ich wen uebersehen ?

---

Ehrlich gesagt wundert es mich, dass es doch so viele sind.

edit: und ich muss sagen, dass bis jetzt noch kein Programm läuft und ich habe auch keine Lust, da stundenlang nun Debugging zu betreiben, um herauszufinden, warum es nicht läuft.
Ausserdem hab ich auch keine Lust, extra noch was installieren zu müssen (z.B. Python).

@ Rolus: Dein Script erzeugt kein Output.

Zitat:

---

Zitat von Whiz-zarD

@ Rolus: Dein Script erzeugt kein Output.

---

Ach, ich Narr. Habe vergessen die Grafiken beizulegen. Und sinnvolle Fehlermeldungen macht mein kurzes Script natürlich nicht. Danke für den Hinweis. Habe die Grafiken dazu gelegt und es nochmal hochgeladen. Zum Testen auch noch mal auf Funpic.

freundliche Grüße, Rolus

Rolus: OMG. Das ist ein... verammt _langweiliger_ Dungeon. xD

Und ich musste feststellen, dass die Umsetzung, wie ich sie mir gedacht habe, doch aufwändiger ist, als ich dachte, so dass ich es sein lassen musste, auch aus Zeitmangel. Ich hab dafür aber auch 'ne Ausrede, 5h Theaterprobe/tag lassen nicht mehr viel Muße fürs Coden übrig.

Ich wäre übrigens ganz froh, wenn ein paar leute Screens ihrer Ergebnisse posten würden, interessiert mich.
Es gibt übrigens wieder erwarten durchaus brauchbare Online-Generatoren für sowas.

Ich bin jetzt nicht wirklich richtig fertig, hoffe jedoch, dass es trotzdem präsentierbar ist. :P

http://drakes.dr.ohost.de/dungeon_genotype/

Parameter:
rooms : Anzahl Räume (default: 10)
seed : Startseed (default: set by php)
collision : on / off (default: off)

z.B.:
http://drakes.dr.ohost.de/dungeon_ge...5&collision=on

collision ist auf default auf off, da sonst das ganze relativ langsam läuft (durch Portale geht trotzdem). Ausserdem ist noch keine Garantie da, dass sich die Räume nicht überschneiden und ein durchqueren unmöglich machen (falls collision auf on) ^^". Die Quelldateien werde ich auf Wunsch nachreichen, Zeit habe ich jetzt gerade aber keine.

Hier ist, was der Wachstumsalgorithmus mit einer Rekursionstiefe von 32 Schritten hervorbringt. Der Kram ist natürlich arg beta und der finale Output würde hübscheres HTML erzeugen.

[Ergebnis] [mit Debugoutput (Achtung, große Datei)]

Was ich habe:
- Das Programm hat eine Liste von Tiles, jeweils mit erlaubten Nachbartiles.
- Es wird ein Tile gelegt und dann (sofern welche definiert sind und der Zielort frei ist) nach Norden, Osten, Süden und Westen weitergebaut.
- Wenn ein Tile gelegt werden soll, wird bei allen Nachbarn geprüft, ob diese das zu legende Tile erlauben.
- Wenn kein passendes Tile gelegt werden kann, wird "Geröll" (auf der Karte rot) gelegt. Dies ist ein Fehlerfall.

Was fehlt:
- Ich habe momentan nur die nötigen Tiles, um Räume zu modellieren. Gänge würden andere Tiles erfordern.
- Wenn kein passendes Tile gelegt werden kann, sollte das Programm Backtracking verwenden (sprich: das Legen des letzten Tiles rückgängig machen).
- Die Liste der Nachbartiles sollte gewichtet sein, so daß beispielsweise Wände dazu neigen, lieber andere Wände statt Ecken zu legen.
- Diese Gewichtung sollte eigentlich auch noch adaptiv sein, damit Räume nur kurz bevorzugt wachsen und dann auf einen Abschluß zustreben.
- Dadurch, daß der Zustand jedes Tiles im Speicher bleibt (weil ja alles rekursiv läuft) ist der Speicheraufwand bei großen Maps verhältnismäßig enorm. Das könnte man kompensieren, indem man blockweise arbeitet (es wird versucht, einen Block von X×X Tiles zu füllen; dann wird der Block als komplett angesehen und daneben weitergebaut).

Was momentan gar nicht modelliert ist:
- Der Algorithmus wächst einfach vor sich hin und ist nicht in der Lage, eine bestimmte Anzahl von Räumen zu erzeugen.


Eventuell wäre es allgemein einfacher, einen großen Haufen Tileblöcke vorzudefinieren und einfach die aneinanderzupappen.


PS:
So, hier habe ich noch einen Durchlauf mit 256 Schritten und etwas getweakten Listen (leere Flächen werden doppelt so gern angelegt). Achtung, die Seite selbst ist über ein Megabyte groß.
[Ergebnis 256]

Öhm Leute, wie wär's mal damit, den Thread endlich zuzumachen und einen Umfrage auf? Der Contest ist jetzt bald schon ne Woche vorbei...

So liebe Teilnehmer ...

Wir waren mit der Abgabezeit mehr als grosszuegig und haben Euch noch die letzte Woche spendiert. Heute Abend machen wir definitiv die Umfrage fuer die Abstimmung auf. Wer es bis dahin nicht geschafft hat, etwas abzugeben, der wird es wohl auch nicht mit einer weiteren Woche Zeit schaffen.

Ich habe erfahren, daß mein Skript zur Wahl steht, obwohl es gar nicht die Bedingungen erfüllt. Naja, wenn ihr meint...

Hier ist der Code. PHP5.
Zip, bzip2'd tarball, LZMA/7zip


BTW; das, was vorher blau war, ist jetzt graubraun. Das ist die einzige Änderung gegenüber dem demonstrierten Kram (abgesehen von Kommentaren). Das Blau kriegt man zurück, indem man in Zeile 206 das "0h" durch "0x" ersetzt. Blau war ursprünglich als Signalfarbe für noch nicht bearbeitete (oder als Einschluß leer gebliebene) Felder gedacht, aber im Output sieht's aus, als sei da Wasser geplant. Daher die Umfärbung.


Edit: Die Links waren kaputt. Gefixt.