[Aufgabenstellung] Programmierwettbewerb Nr. 5

[Brother John]

Bei mir geht’s auch ganz gut voran. Es war ein bisschen Setup-Arbeit nötig, weil ich ja beim Generieren und Lösen komplett von der Geometrie abstrahiert sein will. Das betrifft hauptsächlich den Graph und das Umwandeln einer bestimmten Geometrie (z.B. das klassische rechteckige Feld) in den Graphen.

Rechteckfeld->Graph steht. Der Generieralgo steht in einer ersten Version, ist allerdings noch komplett unkonfigurierbar. Da viel Zufall im Spiel ist, ist’s echt mies, für die Generierung Tests zu schreiben. Ja, ich könnte einen deterministischen Mock-Zufallsgenerator bauen, dependency injection, etc. … aber ach nö, lass mal. Wird auch so funktionieren. Evtl. kriege ich was äquivalentes durch die ganzen geplanten Konfig-Optionen eh rein.

Als nächstes muss eine Visualisierung her. Ich schau mir jetzt also wirklich ernsthaft Qt Quick und QML an. Oft geplant, aber bisher nie umgesetzt.

 

[Der3Geist]

Ich hab mich für eine Relativ Simple methode entschieden.

Spoiler

Mein Labyrinth besteht aus einem Array, um die Karte zu Generieren Laufe ich in zufällige Richtungen über die Karte und wenn an der Position eine Wand ist ohne einen Gang dahinter wird dieses Feld auch zum Gang.
Für mich die Einfachste lösung um schnell ein Zufallslabyrinth zu erstellen
Im unterschied zu den Bisherigen Lösungen hier im Thread sind bei mir Wege und Wände immer 1 Feld groß, was das Raster etwas vereinfacht.

Zur Beobachtung zeige ich das ganze als Grafik in einer PictureBox an.

Dabei habe ich mich für Visual Basic 6 entschieden, weils gerade noch Installiert ist und ich damit schnell was zusammen Basteln kann.
Eine Automatische Löse Funktion wird es nicht geben, aber ein Spiel in der Draufsicht inkl. Gegnern.

 

[KaPiTN]

@Der3Geist:

Ich habe Deinen Post nicht gelesen.

Ich bitte alle alles was mit Lösungsansätzen zu tun hat in Spoiler zu setzen und darüber darauf hinzuweisen, daß derlei enthalten ist!

Ich selber habe noch keinen Algorithmus zu Ende gedacht, sondern bin erst einmal einer intuitiver Idee gefolgt, weil ich auf das Ergebnis gespannt war.

Leider nicht das was ich mir erhofft habe. Da muß ich jetzt nochmal richtig hart die grauen Zellen bemühen.

 

[KaPiTN]

Man habe ich da jetzt mit offsets frickeln müssen. Ich generiere in 2 Schleifen ein Grid und in first column und first row weichen die Pixelentfernungen von denen der andern Kästen ab, bei gleichen Abständen bei den Koordinaten.

So kann man auch seine Zeit vertun. Aber das sollte jetzt soweit in Ordnung sein.

Die gute Nachricht, Ich habe noch einen Fehler entdeckt. Ich habe Zellen vergessen aus der Liste der um das bereits bestehende Labyrinth befindlichen Zellen wieder raus zunehmen. Daher diese großen Räume, weil Zellen mehrfach verarbeitet wurden.

Nach der Behebung dieses Fehlers, scheint meine gewählte Methode ein doch ansprechendes Ergebnis zu liefern.

 

[BurnerR]

So, habe den Spaghetti code jetzt in eine sinnvolle Struktur gepackt.
Was den Algo angeht, da bin ich auf interessante Dinge bezüglich Performance gestoßen, da hab ich bisschen experimentiert und bisschen optimiert. Jetzt gehen jedenfalls auch größere Labyrinthe recht schnell (bisher ausprobiert bis 600x600), die passen dann allerdings nicht mehr sinnvoll auf den Bildschirm. Dabei belasse ich es erst einmal und mache die anderen Punkte morgen weiter .
Bin auch interessiert was die Gründe sind für die diversen Performances. Ist ein rekursiver Algorithmus der je nach Implementierung sehr langsam war wenn auf mehreren Threads gearbeitet wurde. Werde ich mal noch nachhalten was dahinter steckt, aber erstmal weiter am Produkt arbeiten .


PS.:

Nach der Behebung dieses Fehlers, scheint meine gewählte Methode ein doch ansprechendes Ergebnis zu liefern.

Sieht mega gut aus und definitiv besser als das was der von mir verwendete Algo z.B. generiert.

 

[Brother John]

Erster Erfolg! Die Algo-Performance hätte auf Anhieb schlechter sein können. 20.000 Zellen brauchen grob eine Sekunde. Skaliert aber nicht besonders toll, definitiv O(autsch).

Das Malen ist auch nicht gerade flott, aber zum weiter Rumspielen erstmal gut genug.



OK, Eingang und Ausgang fehlen noch. Aber das ist trivial, weil man die frei wählen kann.

@KaPiTN
Das Freiflächenproblem … und der Grund dafür … das kenn ich doch. So einen Bug hatte ich auch drin.

Dein letztes Bild schaut schon echt gut aus. Schön gleichmäßig, bis auf die freie erste Zeile. War das Zufall oder liegt das am Algo?

@BurneR

Spoiler

Ich meine, in deinen Labyrinthen so einige lange gerade Linien zu sehen? Hat dein Algo zufällig was damit zu tun, das Feld immer wieder zu zerteilen?

 

[BurnerR]

@BurneR

Spoiler

Ich meine, in deinen Labyrinthen so einige lange gerade Linien zu sehen? Hat dein Algo zufällig was damit zu tun, das Feld immer wieder zu zerteilen?

Spoiler

Ganz genau so ist es :-). Bin bei meinen Recherchen darauf gestoßen und ich fand den Algo spontan sehr sympathisch und habe deswegen eben jenen genommen.

Habe heute viel umgestellt und ausprobiert, damit auch teilweise generierte Dungeon dargestellt werden können. Aber ich denke ich mache das doch nochmal anders als heute gedacht .

 

[KaPiTN]

Dein letztes Bild schaut schon echt gut aus. Schön gleichmäßig, bis auf die freie erste Zeile. War das Zufall oder liegt das am Algo?

Spoiler

Das ist kein Zufall. Ich füge Zellen zu den Gängen hinzu, die an den vorhanden Gängen anliegen. Das ist natürlich am Anfang extrem wenig, fange ich doch mit nur einer Zelle an. Somit wird da anderseits sehr viel lokal konzentriert hinzugefügt.

Ich könnte mal ausprobieren an mehreren Stellen anzufangen, in der Hoffnung, daß sich das zusammenfügt. Vielleicht zerhaut es aber auch alles.

 

[Roin]

Nachdem mein erster Ansatz zu keinem guten Ergebnis geführt hat, habe ich nun einen zweiten Ansatz ausprobiert.
Dabei scheine ich aber noch einen Logikfehler zu haben.
Weiteres dazu im Spoiler:

Spoiler

Ich wähle nun zufällig ein Feld in meinem Grid aus und mache dieses zu einem Weg.
Nun wähle ich einen zufälligen Nachbarn aus, der bisher kein Weg ist und mache diesen zu einem Weg. Den neuen Weg nutze ich als neuen Startpunkt und iteriere so lange, bis ich keine neuen Wege mehr hinzufüge.
Nach aktuellem Muster erzeuge ich damit aber nur einen rechteckigen Block in meinem Labyrinth und es entsteht gar kein Labyrinth. Ich wandle auch nicht alle Felder in Wege um sondern nur so 10% oder so.
Da stehe ich derzeit auf dem Schlauch wo mein eigentlicher Fehler wohl ist...

EDIT:
Ich denke, eines meiner Probleme ist, dass ich Felder als WEG oder WAND verwende und dann eigentlich zwei Schritte gehen müsste oder sowas in der Richtung. Das kriege ich mit meinem derzeitigen Ansatz aber nicht ohne weiteres hin.

Aktuell sieht es dann jetzt so aus. Muss also wohl noch weiter überlegen, wie ich meinen Algorithmus verbessern kann... Ich habe es mir definitiv einfacher vorgestellt mir selber was auszudenken.

 

[Der3Geist]

@Roin

Spoiler

Gleiche Methode Verwende ich auch.
Dein Fehler ist, wie du schon richtig erkannt hast, du müsstest immer im 2èr rasten gehen.
Der Startpunkt ist dann Quasi eine durch 2 Teilbare Zahl.

Dann Zufällig in eine Richtung gehen, Hoch, Runter , Links oder Rechts das Übernächste Feld Prüfen (Wand oder Keine Wand)
Wenn es eine Wand ist, das Feld zum Weg machen und das Feld zwischen deinem Ausgangspunkt auch zum weg machen.

Dann die Neue Position als Ausgangspunkt für den nächsten schritt nehmen.

 

[KaPiTN]

Nach aktuellem Muster erzeuge ich damit aber nur einen rechteckigen Block in meinem Labyrinth und es entsteht gar kein Labyrinth.

Spoiler

Du gehst bei jedem Schritt immer nur von einem Feld aus, wenn ich das richtig verstanden habe. Bei mir siehst Du in der ersten Zeile, was bei wenigen Zellen passiert. Ich fange auch mit einer Zelle an, aber in jedem Schritt kommt eine weitere dazu. Bei dauerhaft nur einer Zelle ist der Effekt natürlich größer und es entsteht gar kein Labyrinth.

 

[Roin]

@Der3Geist:
Genau das habe ich jetzt gemacht. Dadurch ist dann das Bild aus meinem letzten Post entstanden. Da fehlt mir also noch ein weiterer Schritt.

@KaPiTN:

Spoiler

Meine Schrittweite habe ich inzwischen auf zwei angepasst. Wenn es doof läuft, erhalte ich dann dennoch nur ein "U" am oberen Rand oder so. Ich werde da also wohl noch eine weitere Schleife mit Zufallkram einbauen, damit auch noch große Blöcke aus Wänden irgendwie labyrinthisiert (was ein tolles Wort) werden.

Bestes Ergebnis bisher (pures Glück beim RNG):
Anhang anzeigen 58267

 

[KaPiTN]

Bei Interesse würde ich mal spoilern, wie ich bisher vorgehe.

 

[Roin]

@KaPiTN:
Ich denke, das ist nicht nötig, außer du möchtest dich natürlich mitteilen.

Ich habe jetzt noch eine weitere Schleife mit eingebaut.
Am Ende komme ich jetzt auf sowas:

Das ist zwar noch nicht ganz das, was ich gerne haben möchte, aber es kommt dem schon ein gutes Stück näher.

Das Zeichnen übernimmt übrigens weiterhin eine Exceltabelle für mich. Meine eigentliche Ausgabe ist ein Block aus X oder nicht X

Edit:
Ich erzeuge jetzt ganz vernünftige Labyrinthe. Eine Sache, die ich allerdings noch nicht "schön" hinbekommen habe ist den Start und Endpunkt schön zu wählen.
Den wähle ich aktuell zufällig auf dem Labyrinth-Rahmen. Er kann aber direkt nebeneinander liegen oder nur 3 Schritte durch das Labyrinth führen. Ich bin mir nicht sicher, wie und ob ich das lösen möchte.

Spoiler

Ich habe festgestellt, dass manchmal bei mener Erzeugung noch ein Bug auftritt. Er startet in dem Zug bei dem roten Feld und geht dann nach links. Dadurch landet er auf der Außenkante rechts (Array Zugriff in Python. -1 ist das letzte Element...).
Ich dachte, ich habe das abgefangen. Muss ich also doch nochmal suchen.

EDIT2:
In meinem Labyrinth kann nun ein Spieler rumlaufen!

 

[Brother John]

Bei Interesse würde ich mal spoilern, wie ich bisher vorgehe.

Selbstverständlich besteht da Interesse.

Eine Sache, die ich allerdings noch nicht "schön" hinbekommen habe ist den Start und Endpunkt schön zu wählen.

Ich hab das so gelöst, dass ich ein Tor links oder oben zufällig erzeuge und ein zweites rechts oder unten. Und dann gibts noch Spezialfälle, damit die beiden Tore nicht nah beieinander z.B. rechts oben in der Ecke liegen. Ich denke, das sollte recht gut funktionieren.

Algo-Spoiler:

Spoiler

Btw: Lass mich für deine Art Labyrinth noch »zelluläre Automaten« als Stichwort in den Raum schmeißen. Ich vermute, wie du aktuell rechnest ist da recht nah dran.

So, und ich hatte ja Bestagons versprochen. Bittesehr:



Ist gar nicht so trivial zu malen, der sechskantige Scheiß! Aber hübsch isser!

 

[Rakorium-M]

Hatte im alten Jahr auch ein paar Tage Zeit, eine Lösung zu basteln:

Spoiler

Mein Ansatz basiert im Prinzip auf der Idee, Labyrinthe als Graphen zu formulieren, die Brother John in #3 formuliert hat. Der Rest ist ohne weitere Recherche zusammengebastelt und liefert ein möglichst kompliziertes Labyrinth, das genau eine Lösung hat. Zum Lösen wird ganz klassisch A* verwendet.

Aktuell hab ich 450 Zeilen Go dafür geschrieben. Ist aktuell eine Konsolenanwendung, eventuell bastel ich noch eine GUI dafür. Zusätzliche Features: Größe einstellbar, Lösung wird ebenfalls berechnet.

 

[Roin]

@Brother John:
Cool gemacht. Ich werde es nicht angehen, aber nur, weil es mit meiner Array-Struktur vermutlich etwas umständlich ist das umzusetzen.

@Rakorium-M:
Einen Lösungsbutton muss ich auch noch einbauen. Das habe ich bisher nicht gemacht. Aber man kann bei mir ebenfalls die Größe anpassen und...
*Trommelwirbel*

Spoiler

ein blauer Punkt kann durch das Labyrinth gesteuert werden und die Schritte werden gezählt.

Das sind bei mir inzwischen ungefähr 450 Zeilen Python Code, wobei ungefähr 100 auf die Zeichenroutine und die Spielsteuerung entfallen. Natürlich sind da auch eine ganze Menge leere Zeilen und ein paar Kommentare drin.

 

[BurnerR]

Ich hab jetzt eingebaut, dass das Labyrinth schrittweise dargestellt wird (Generiert wird das Labyrinth vorab vollständig). Als nächsten Schritt soll man dann parallel zum Bauen da schon durchlaufen. So weiß man quasi nicht von Anfang an die Route, sondern muss anhand der weiter weg liegenden Passages raten, wo es ca. hin gehen soll. So jedenfalls die Grundidee.

Anhang anzeigen 58274

 

[Roin]

@BurnerR: Dein Anhang funktioniert für mich nicht. Da gibts einen Fehler vom ngb.
Aber eine ansatzweise ähnliche Idee habe ich auch noch in Planung.

Spoiler

Undzwar dass der Spieler nur einen kleinen Bereich, also vielleicht 3x3 Felder sieht und sich auf dem Feld dann bewegt.
Und je nach Schwierigkeit kann der die besuchten Felder sich merken oder anzeigen lassen usw.

Ich habe noch weitere Ideen, ich weiß nur nicht, ob ich noch eine davon umsetzen werde. Mein Urlaub ist fast rum...

 

[KaPiTN]

Irgendwie habe ich Zweifel entwickelt, daß es an zu wenig Zellen liegen soll, daß die erste Zeile komplett ohne Mauern ist.

Nur ein Bild, kein Spoiler.

Spoiler

Da müßte doch eher um die Startzelle herum Lücken bleiben, also nicht nur ein Effekt auf die Reihe, sondern auch auf die Spalte.

Ich habe mal die Startzelle in einer andere Reihe gewählt und siehe da:

Nur ein Bild, kein Spoiler.

Spoiler

Das erscheint mir dann doch eindeutig zu sein, daß hier ein Bug vorliegt, und es nicht die Methode ist.

Und schnell war klar, daß ich auf der Suche nach Nachbarzellen die erste Zeile ignoriert habe.

Und schon ist das Ergebnis gleichmäßiger:

Nur ein Bild, kein Spoiler.

Spoiler

Selbstverständlich besteht da Interesse.

Spoileralarm

Spoiler

Ich kann gar nicht erklären, warum das genau funktioniert. Ich habe da keine Theorie erdacht.

Nach tagelangem Grübeln hatte ich die Intention, daß das erstellen des Labyrinths ähnlich sein könnte, wie bei einem Tier, daß versuchen sollte, durch das Labyrinth zu kommen, also daß das Erstellen nicht so sehr verschieden sein könnte, wie die Lösung.

Ein Tier würde an einer Stelle anfangen und Gänge buddeln.

Aber jetzt müßte man ja per Zufall entscheiden, wann ein Gang zu Ende ist. (Und noch viel schwieriger, man müßte sich überlegen, wie man jetzt wieder zu einem Knotenpunkt/Abzweigung zurück kommt).

Da war dann erst einmal wieder Ende Gelände.

Aber am nächsten Tag überlegt ich, wenn ich ja eh den Zufall ins Spiel bringen muß, dann teleportiere ich die Maus per Zufall an Stellen, wo sie weiterbuddeln soll. Das kann dann durch aus da sein, wo sie gerade ist und der Gang wird länger, oder halt woanders.

Und die Umsetzung dieser Idee ist dann doch recht einfach.

Ich erstelle 3 Listen:
a) Eine Liste mit allen Zellen des Grids
b) Eine Liste mit allen Zellen des Labyrinths/(der Gänge)
c) Eine Liste mit allen Zellen, die an das Labyrinth/die Gänge angrenzen.

Ich lege eine Zelle als Start fest und habe somit dann eine Zelle in der Liste B. Für die Zelle suche ich dann die umliegenden Nachbarzellen, die außerhalb liegen und packe sie in Liste C.

Solange die Liste C Elemente enthält, wähle ich eines davon zufällig aus, packe es in Liste B, pack die umliegenden Nachbarn in Liste C und entferne das Element selber aus dieser Liste.