• Hallo liebe Userinnen und User,

    nach bereits längeren Planungen und Vorbereitungen sind wir nun von vBulletin auf Xenforo umgestiegen. Die Umstellung musste leider aufgrund der Serverprobleme der letzten Tage notgedrungen vorverlegt werden. Das neue Forum ist soweit voll funktionsfähig, allerdings sind noch nicht alle der gewohnten Funktionen vorhanden. Nach Möglichkeit werden wir sie in den nächsten Wochen nachrüsten. Dafür sollte es nun einige der Probleme lösen, die wir in den letzten Tagen, Wochen und Monaten hatten. Auch der Server ist nun potenter als bei unserem alten Hoster, wodurch wir nun langfristig den Tank mit Bytes vollgetankt haben.

    Anfangs mag die neue Boardsoftware etwas ungewohnt sein, aber man findet sich recht schnell ein. Wir wissen, dass ihr alle Gewohnheitstiere seid, aber gebt dem neuen Board eine Chance.
    Sollte etwas der neuen oder auch gewohnten Funktionen unklar sein, könnt ihr den "Wo issn da der Button zu"-Thread im Feedback nutzen. Bugs meldet ihr bitte im Bugtracker, es wird sicher welche geben die uns noch nicht aufgefallen sind. Ich werde das dann versuchen, halbwegs im Startbeitrag übersichtlich zu halten, was an Arbeit noch aussteht.

    Neu ist, dass die Boardsoftware deutlich besser für Mobiltelefone und diverse Endgeräte geeignet ist und nun auch im mobilen Style alle Funktionen verfügbar sind. Am Desktop findet ihr oben rechts sowohl den Umschalter zwischen hellem und dunklem Style. Am Handy ist der Hell-/Dunkelschalter am Ende der Seite. Damit sollte zukünftig jeder sein Board so konfigurieren können, wie es ihm am liebsten ist.


    Die restlichen Funktionen sollten eigentlich soweit wie gewohnt funktionieren. Einfach mal ein wenig damit spielen oder bei Unklarheiten im Thread nachfragen. Viel Spaß im ngb 2.0.

[Aufgabenstellung] Programmierwettbewerb Nr. 5

MingsPing

NGBler

Registriert
15 Juli 2013
Beiträge
346
Dynamischer Dungeon / Dynamisches Labyrinth

EINLEITUNG

Unendlich viel Spielspaß? Kein Level gleicht dem anderen?

Das klingt zu gut, um wahr zu sein?
Das ngb machts möglich! Wir beginnen gerade noch rechtzeitig im Jahr 2020 den 5. forumsinternen Programmierwettbewerb.

viewer.php


ANFORDERUNGEN

Es soll ein Programm geschrieben werden, das zufällig generierte (dynamische) Labyrinthe erstellt. Welche Form diese haben (2d/3d, Quadrate/sonstige Bausteine), ist euch überlassen. Eine Grafikausgabe ist nicht zwingend, wäre aber toll. Im Prinzip reicht eine Kommandozeilenausgabe.

Mögliche Features:
- Schwierigkeitsparameter: wie "verwinkelt" soll das Labyrinth sein?
- Größe einstellbar
- mehrere Wege zum Ziel möglich? Mehrere Ziele?
- Räume im Labyrinth
- Fog of War
- Sechsecke (because Hexagons are Bestagons, danke an Brother John)

Wie hier angedacht, könnten daraufhin weitere Challenges entstehen; vielleicht ist es sinnvoll, das beim Implementieren mitzubedenken.


START

ab jetzt!


ENDE

10.01.2021


Viel Spaß und haut in die Tasten!

MingsPing
 

KaPiTN

♪♪♫ wild at heart ♪♫♫♪

Registriert
14 Juli 2013
Beiträge
29.138
So. Ich habe jetzt mal die wichtigsten Klassen angelegt und lasse das Grid zeichnen. Die Zellgröße sollte noch von der Gridgröße abhängig gemacht werden.

Ich habe mal zur Demozwecken eine höhere Refreshrate eingebaut, aber wie man im zweiten Video sieht, geht das natürlich auch schneller.
Ich benutze keine fremde Engine, sondern habe ein Bitmap, welches ich mit dem in Windows integrierten Grafiksystem GDI+ manipuliere.

Beim Generieren des Labyrinths werden die "Mauern" "eingerissen". Ich habe da eine Idee, aber ob ich damit weit(er) komme, sehe ich wohl erst, wenn sie implementiert sein wird.




[video=picflash;Maze2020-12-2420-55-30DQ3W1O.mp4]https://www.picflash.org/picture.php?key=DQ3W1O&action=show[/video]

[video=picflash;Maze2020-12-2420-48-46I6WKOE.mp4]https://www.picflash.org/picture.php?key=I6WKOE&action=show[/video]

Ich sehe gerade, daß ich in beiden Fällen zufällig 26 für Breite/Höhe eingestellt habe. Aber ich schwöre, daß das von dem numericUpDown abhängt und nicht hart gecodet ist. ;) :D
 

Brother John

(schein)heilig
Veteran

Registriert
1 Aug. 2013
Beiträge
235
Ein paar Vorüberlegungen nach ein bisschen rumgoogeln:

Ich will garantiert lösbare Labyrinthe, also muss der Generieralgo »perfect« sein, d.h. jeder beliebige Punkt des Labyrinths ist mit jedem beliebigen anderen Punkt durch genau einen Weg verbunden. Dann kann man generieren und sich beliebig zwei Stellen am Rand aussuchen, die Start und Ziel darstellen. Da »perfect« gibt es immer einen Weg zwischen den beiden, ganz egal wo sie liegen.

Stellt sich raus, Labyrinthe sind Graphen. Ha! Mal wieder ein Graph, da fühlt man sich gleich wie zuhause. :D Und wenn ich das schon richtig verstehe, ist der durch einen perfect Generieralgo erzeugte Lösungsweg ein »spanning tree« über die Nodes im Graph. Soso. Ein Baum. Das geht ja nahtlos weiter mit den Standard-Datenstrukturen.

Da die üblichen Algos im Prinzip Graph-Verarbeitung sind, spielt die Geometrie keine oder zumindest keine wesentliche Rolle. Das ist gut, weils die Algoimplementierung flexibel hält. Im Moment schwebt mir ein Graph vor, dessen Nodes mit zwei Arten von Kanten verbunden sein können: offen (Weg) und geschlossen (Wand). Im klassischen rechtwinkligen Labyrinth hätte dann jede Node 2, 3 oder 4 Kanten – für Hexagons entsprechend bis zu 6 Kanten. Das geometrische Layout ergibt sich daraus, welche Kanten mit welchen anderen Kanten verbunden sind. Aber das muss den Algo nicht interessieren sondern wird erst später für die graphische Darstellung interessant.

Jamis Buck: "Algorithms" is Not a Four-Letter Word (RubyConf 2011): Knapp 40min Vortrag, ein Spaziergang durch eine ganze Reihe von Generieralgos. Sehr unterhaltsam und lohnt sich inhaltlich. Ich nehm daraus mit, mich auf Growing Tree zu konzentrieren, weil seine Flexibilität echt attraktiv ist.
 

Roin

Freier Denker

Registriert
22 Juli 2013
Beiträge
581
Wenn ich loslege, werde ich erstmal versuchen einen Algorithmus zu erzeugen, der mir irgendwas in Richtung Labyrinth erzeugt ohne vorher nach bereits existierenden Algorithmen zu gucken und einen davon nachzubauen. Ich möchte sehen, wie weit ich mit freiem Denken komme. Vielleicht ist am Ende mein Algorithmus ja einem der anerkannten Algorithmen ähnlich, das wird sich dann zeigen.

Ich werde mich erstmal auf Quadrate als Einheiten festlegen. Entsprechend sind die dann eine Wand oder ein freies Feld / Weg.
Mal sehen wie weit ich damit dann so komme.

Wenn ich zu gar keinem Ergebnis komme, werde ich aber auch irgendwann mal Wikipedia befragen.
 

Roin

Freier Denker

Registriert
22 Juli 2013
Beiträge
581
Ich habe gerade mal 15min angefangen Code zu schreiben.
Also eine Ausgabe für ein zweidimensionales Array zu schreiben, wo x oder " " verwendet wird um Weg oder Wand darzustellen ist nicht kompliziert.
Aber entweder bin ich zu müde oder stehe auf dem Schlauch, wie ich denn nun sinnvoll beginne mit diesem Array zu interagieren.

Entweder schreibe ich eine Klasse, welche ein "Feld" darstellt, das seine Position kennt und seine Nachbarn oder ich schreibe eine Klasse, welche das komplette Labyrinth darstellt und für jedes Feld auch seine Nachbarn bestimmen kann und sowas.
Ich bin mir derzeit nicht sicher, was sinnvoller umzusetzen ist. Performance bei den "kleinen" Dungeons (20x20 oder so) sollte ja erstmal kein Problem darstellen. Selbst bei 100x100 denke ich, dass es noch ok sein sollte.
Ich habe mir übrigens Python(3) zum Umsetzen ausgesucht.

EDIT:
Mein erster Ansatz funktioniert schonmal nicht zu lösbaren Labyrinthen.
Das sieht dann nämlich so aus:
Labyrinth1.jpg Ich habe die Ausgabe einfach mit in Excel kopiert. ist etwas hübscher als die reinen Zeichen :D
 
Zuletzt bearbeitet:

KaPiTN

♪♪♫ wild at heart ♪♫♫♪

Registriert
14 Juli 2013
Beiträge
29.138
Entweder schreibe ich eine Klasse, welche ein "Feld" darstellt, das seine Position kennt und seine Nachbarn oder ich schreibe eine Klasse, welche das komplette Labyrinth darstellt und für jedes Feld auch seine Nachbarn bestimmen kann und sowas.
Ich bin mir derzeit nicht sicher, was sinnvoller umzusetzen ist. Performance bei den "kleinen" Dungeons (20x20 oder so) sollte ja erstmal kein Problem darstellen. Selbst bei 100x100 denke ich, dass es noch ok sein sollte.

Da bin ich mal auf den späteren Austausch gespannt, weil ich da kein oder sehe, wenn auch nicht in beiden Fällen mit Klassen, und wieweit da die Möglichkeiten vielleicht sprachabhängig sind.

Ich heute mich heute, vielmehr gestern abend, auch nur etwas mit Kleinscheiß rumgeschlagen, weil da was bei der Pixelschubserei nicht wie erwartet funktionierte.
 

Brother John

(schein)heilig
Veteran

Registriert
1 Aug. 2013
Beiträge
235
Ich sehe durchaus die Möglichkeit zum oder, je nachdem mit welchen Beschränkungen man arbeitet.
Wenn man sich z.B. auf die klassischen quadratischen 2D-Zellen festlegt und dicke Wände hat, dann kann man die »Wer ist Nachbar«-Info implizit in die Datenstruktur reinbacken: 2D-Array. Jede Zelle braucht dann noch ein Flag ob sie Wand ist oder Weg, und fertig. Supersimpel und ein interessanter Ansatz, weil er anders funktioniert als die Standard-Generieralgos. Die arbeiten mit Wänden zwischen den Zellen.

[rant]
Ansonsten ging’s mir gestern Abend ähnlich wie dir, KaPiTN. Kleinscheiß. Mir war’s ja bewusst, dass der random-Header der C++-Standardlibrary nicht gerade ein Leuchtturm der Benutzbarkeit ist. Aber wie schlimm die Situation ist, hat mich doch ein bisschen geschockt. Ohne intensive Recherche vorher lege ich meine Hand dafür ins Feuer, dass man den Header erstmal grob falsch benutzt und sich damit schlechten Zufall eintritt. Und dann gibt es Toolchains (ältere MinGWs), bei denen std::random_device deterministisch ist! W.T.F!? Schlimmer wird’s nur dadurch, dass der Standard gar nicht vorschreibt, dass ein random_device tatsächlich Zufall liefern muss *nach Luft schnapp*. Ein intensives Postmortem für die Lib wäre interessant. Daran könnten wir sicher einiges darüber lernen, warum Standardisierungsprozesse manchmal grob daneben gehen.
[/rant]
 

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
Ich hab bisschen herum geschaut und was gefunden, das ich ganz cool finde. Ich werde auch mehr ein 'maze' als ein Dungeon bauen. Zuerst implementiere ich einen bestehenden Algo, den ich ganz cool fand und der vor allem mit so einer kleinen fixen Idee für einen 'spin' von mir recht gut kompatibel scheint. Ich glaube allerdings, dass meine Idee keinen Spaß machen wird die zu Spielen :D.
Ich werde keinen Graph als Datenstruktur hernehmen, sondern tatsächlich ein 2D Array.
 

KaPiTN

♪♪♫ wild at heart ♪♫♫♪

Registriert
14 Juli 2013
Beiträge
29.138
failure is always an option

Das war's an dieser Stelle. Der Kleinscheiß hat sich als großer Scheiß herausgestellt.

Ich hatte gedacht, ich zeichne einmal das Grid und übermale dann die Mauern, die ich nicht mehr benötige. Aber das klappt schon deshalb nicht, weil ich keine Möglichkeit für einen harten Strich finde. Ist der Strich breiter, gibt es neben dem schwarzen Kern noch einen grauen Rand und der bleibt, wenn ich weiß mit den gleichen Daten drüber male. Und auch mit anderen Daten konnte ich nur häßliche Effekte erzeugen


Viel Zeitverschwendung, weil man nicht einsehen will, daß das nicht (so) geht. (Sturheit) Statt da so hartnäckig zu sein, hätte ich mich direkt entschließen sollen, halte jedesmal das Grid komplett neu zu Zeichnen. :m Kostet ja nichts.

Allerdings ist jetzt erst mal die Luft raus. :D
 

Der3Geist

always feed the fish

Registriert
14 Juli 2013
Beiträge
2.702
Ort
Hessen
Ich hatte gedacht, ich zeichne einmal das Grid und übermale dann die Mauern, die ich nicht mehr benötige. Aber das klappt schon deshalb nicht, weil ich keine Möglichkeit für einen harten Strich finde. Ist der Strich breiter, gibt es neben dem schwarzen Kern noch einen grauen Rand und der bleibt, wenn ich weiß mit den gleichen Daten drüber male.

Das liegt wohl eher an deinem Grafikformat.
Versuch mal ein Format ohne Komprimierung.
 

theSplit

1998
Veteran Barkeeper

Registriert
3 Aug. 2014
Beiträge
28.561
@KaPiTN: Das sieht nach schwer nach Anti-Aliasing bzw. Subpixel Sampling aus.

Versuch mal was passiert, wenn du das Grid aligneds - also auf volle Pixel aufrunden und nicht in den Nackommastellenbereich kommen/zeichnen.
 

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
Ich werd wohl doch einen Graph nehmen... :D. Bin mir da etwas uneins, aber ich denke das ist insgesamt besser.
Ich bau das ganze ja in Julia.. bin noch so ein bisschen am auskundschaften der diversen Packages gewesen heute. Bisschen mit Canvas herum gespielt, aber ich glaube ich mache das nicht alles auf einem einzelnen Canvas, sondern teile das auf.
 

KaPiTN

♪♪♫ wild at heart ♪♫♫♪

Registriert
14 Juli 2013
Beiträge
29.138

Der3Geist

always feed the fish

Registriert
14 Juli 2013
Beiträge
2.702
Ort
Hessen
Was soll welche Komprimierung bewirken?

Mir ist es schon öfters Passiert, das ich bei Bitmap Karten im JPG Format z.b. Farbverläufe und Verschmierungen hatte, das weder die Pixelkollision noch ein genaues Auslesen der Pixelfarbe Funktionierte.
Früher musste ich solche Bilder als BMP Speichern.
Mittlerweile Verwende ich für die Transparenz PNG.

In Visual Basic hatte ich ähnliche Probleme, wenn ich ein Picture Objekt hatte, welches z.b. eine Pixelmap geladen hatte, das dort obwohl BMP oder PNG Format Farbverläufe vorhanden waren,
welche mich Stunden an Fehlersuche kosteten.
 

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
Er malt ja vermutlich in einen Canvas rein. Vermutlich verwendet die Lib per default unabhängig von Anti-Aliasing einen Line-Drawing Algorithmus, der etwas vergleichbares macht.

Ich bin fürs erste Zufrieden mit dem drawing, ich mach mich jetzt an den Algo.
Screenshot from 2020-12-27 13-42-43.png
Die Mauern außen rum werden schon gezeichnet, aber es fehlt noch ein kleines Offset, damit man die auf jeden Fall immer sieht.
Kurz nach dem Beitrag hier hat mein Programm den ganzen Computer mehr oder minder abstürzen lassen dank Grafikkartentreiber-Bug (Vermutung, jdfs. hat Nouveau Treiber Fehler geworfen), lol.
 
Zuletzt bearbeitet:

KaPiTN

♪♪♫ wild at heart ♪♫♫♪

Registriert
14 Juli 2013
Beiträge
29.138
@Der3Geist:

Derlei Probleme hatte ich mit Bitmaps bislang nicht. Das Übermalen statt neu zu zeichnen ist wohl generell keine gute Idee.

Um sicher zu gehen, habe ich mal direkt auf dem Anwendungsfenster gemalt. Und auch hier bleiben Schatten, wenn ich einen schwarzen strich mit einem weißen übermale.

 

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
So, hatte grad nochmal etwas Zeit. Erste Version fertig:
Screenshot from 2020-12-27 18-38-49.png
Bin sehr zufrieden, hat dann doch ganz gut geklappt alles. Der Algo ist allerdings dringend refactor-bedürftig :D.

Hier noch ein Beispiel für 64x64 und 128x128
Screenshot from 2020-12-27 18-44-57.png
Screenshot from 2020-12-27 18-46-48.png
Leider ist die Zeichen-Routine nicht sehr performant, sehr langsam wenn man die Fenstergröße ändert :D.
 
Zuletzt bearbeitet:

MingsPing

NGBler

Registriert
15 Juli 2013
Beiträge
346
  • Thread Starter Thread Starter
  • #19
Habe auch angefangen! Ich benutze Racket, ein Lisp-Dialekt.
So wie @Roin möchte ich es auch erstmal handhaben, und versuchen, eigene Algorithmen zu finden. Wenn ich dann merke, dass die nix taugen, bemühe ich Google ;-)

Stand jetzt steht das Grid-Grundgerüst und Zeichnen-Funktionen.

Der erste Algorithmus, der einfach zufällig Wände erscheinen lässt, kreiert so etwas zum Beispiel:

dungeonRandomWalls.PNG

(noch ohne Erkennung, ob überhaupt ein Start-Ziel-Weg vorhanden ist)
 

BurnerR

Bot #0384479

Registriert
20 Juli 2013
Beiträge
5.504
So, nachdem ich die Zeichen-Performance verbessert habe mit kleinen Anpassungen klappt das jetzt super schnell mit dem Zeichnen, auch bei 128x128. Ich bau jetzt gerade meinen Spaghetti Code um zu einer sinnvollen Struktur und habe darüber sinniert, was ich als nächstes machen möchte.

* Zum einen progge ich ja in Julia und da scheint es sehr angemessen, stark auf die Performance zu schauen bzw. auch besonders große Mazes zu unterstützen (bezogen auf den Maze Generier-Algo den ich mir ausgeschaut habe). Aktuell wird das Maze noch eher langsam erstellt, jede Änderung direkt in den zugrundeliegenden Graphen (ja, hab ich dann doch gemacht :D) geschrieben. Das baue ich als aller erstes um und vllt. gehen dann auch schon Mazes 256x256 u.ä..
* Danach will ich das Generieren in einen eigenen Prozess auslagern, welcher Zwischenergebnisse pusht, so das man einerseits beim Bauen zugucken kann aber andererseits auch schon los laufen kann wenn man will.
* Ich denke ich such mir einen Maze-Solver raus, der kann dann auch schon mal los laufen während das Maze noch gebaut wird, so kann man beim Bauen und beim Lösen parallel zugucken :D.
* Ich spiele ein wenig mit dem Gedanken, einen Maze-Solver zu schreiben, welcher die Eigenschaften berücksichtigt, die ein Maze hat, das mit dem genutzten Algo gebaut worden ist. Da bin ich noch nicht ganz sicher, ob das gut geht, mal sehen.
 
Zuletzt bearbeitet:
Oben