YAMG - Yet Another Maze Generator

Hallo,

hier möchte ich euch ein kleines Projekt vorstellen, was vorgestern entstanden ist: YAMG - Yet Another Maze Generator.

Mit diesem Programm könnt ihr Perfekte Labyrinthe erstellen - Irrgärten, die von einem beliebigen Punkt zu einem anderen genau einen Weg haben und keine Zyklen enthalten.
Natürlich könnt ihr diese auch lösen lassen ...

m0rius

Schlagworte: YAMG, Yet Another Maze Generator, Perfektes Labyrinth, Labyrinth, Irrgarten, Irrgärten, Maze, Perfect maze, Maze generator

Hier ein Screenshot von einem ungelösten Irrgarten ...

... und hier ein gelöster Irrgarten:

Edit: Bild angehängt 😄 ...

Es wäre besser, wenn man die labyrinthe aus dem programm selber audrucken könnte. und am besten noch ein zweites blatt mit der lösung.

EDIT: Außerdem wäre es besser ein großes Rätsel multithreaded zu erstellen.

Gruß pdelvo

Hallo pdelvo,

kommt noch 😃 ... Vielleicht hat jemand bei der Gelegenheit einen Vorschlag für ein Icon? Ich habe keins gefunden, was passt und mir gefallen hat ...

m0rius

Schick.

Jedoch bekomme ich folgende Ausnahme bei grösseren Bildern:

[PRE]System.ArgumentException: Ungültiger Parameter.
   bei System.Drawing.Bitmap..ctor(Int32 width, Int32 height, PixelFormat format)
   bei System.Drawing.Bitmap..ctor(Int32 width, Int32 height)
   bei YAMG.MainForm.DrawMaze()
   bei YAMG.MainForm._tbarCellWidth_Scroll(Object sender, EventArgs e)[/PRE]

Bei grossen Bilder wäre ein asyncroner Erstellungsprozess auch nicht schlecht.
Ausserdem mag ich Deutsch lieber. Du kannst ja bei diesem Programm erste Versuche mit Lokalisierung machen.

Jetzt fehlt nur noch eine praktische Anwendung, da das Lösen im Moment schwer ist, ohne den Bildschirm zu bemalen 🤔****

Vielleicht hat jemand bei der Gelegenheit einen Vorschlag für ein Icon?

Nimm doch ein generiertes Labyrinth bspw. mit der Grösse 4x4.

mfg
SeeQuark

Hallo SeeQuark,

die praktische Anwendung kommt mit dem Drucken 😉.

Ja, ich glaube, ich sollte den Erstellungsprozess wirklich in nen anderen Thread auslagern. Wann genau kriegst du denn die Exception bzw. was sind "größere" Bilder?

Zum Icon: Gute Idee ...

m0rius

Moin,

ohne das Programm jetzt ausprobiert zu haben (bin auf der Arbeit) - Vielleicht habe ich das übersehen, aber gibt es eine Kennzeichnung von Start- und Endpunkt?

Gruß,
Markus 😃

die praktische Anwendung kommt mit dem Drucken

Und ein OnTheFly-Lösen? Mit den Pfeiltasten? Das wäre imho auch was.

was sind "größere" Bilder

200x200. Zoom auf Maximal, eventuell auch niedriger, geht schwer zu testen.

mfg
SeeQUark

Noch ein Fehler. Ich bekomme manchmal einen Fehler, wenn eine seite 1 ist. "Der Stapel ist leer" heißt es.

Gruß pdelvo

Hallo Spontifixus,

nein, gibt es noch nicht. Ziel ist es aber (an der Lösung zu erkennen), von links oben nach rechts unten zu gelangen.

Hallo SeeQuark,

hm. Mal sehen ...

Seltsam, ich bekomme selbst bei größeren Bildern keine Exception.

Hallo pdelvo,

danke für den Hinweis ... Ich hatte das schonmal getestet, allerdings lief es da noch ...

m0rius

Ja - anhand der Lösung habe ich mir das auch gedacht. Nur versucht man so ein Labyrinth ja in der Regel ohne Lösung zu lösen. Mein Vorschlag hier: Einfach den Außenstrich des Kästchens weglassen, dass den Eingang und den Ausgang bildet. So weiß man gleich wos losgeht...

Gruß,
Markus 😃

Hallo Spontifixus,

drin 😃.

Edit: Die ArgumentException, die gefeuert wurde, weil die Bitmap zu groß war, ist nun auch raus (Ich habe die Maximalgröße verringert ... Mal ehrlich, wer braucht schon Irrgärten in der Größenordnung 1500 * 1500 mit Zellen 100px * 100px ...).

m0rius

Wow, sieht klasse aus!

Mich tät halt der Code interessieren, wie man sowas generiert - da ist nix zu machen?

Ansonsten das mit der Start-End - Markierung ist nicht drin.

Ich fänd auch als Grafik glaub hübscher, wenn der Weg dann als Linie gezeichnet würde.
Oder vlt runde Punkte, jdfalls, dass nicht das ganze Kästchen ausgefüllt ist.

Zum am Bildschirm probieren hättichn Vorschlag zum Design: Cursor-Tasten bestimmen, welches Kästchen als nächstes betreten wird, und Entf löscht den jeweils letzten Schritt.

Hallo ErfinderDesRades,

der Algorithmus zum Generieren ist extrem einfach! Jede Zelle (Klasse Cell) speichert die (boolschen) Zustände isIntact aller Wände ab.1.Setze den Zustand aller Wände aller Zellen auf isIntact. 1.Wähle eine zufällige Zelle als Startzelle aus. 1.Wähle eine zufällige Nachbarzelle der jetzigen Zelle aus, deren Wände nicht komplett zerstört sind. 1.Sollte so eine Zelle nicht existieren, geh' rekursiv eine Ebene zurück (s. Punkt 7). 1.Reiß' die Wände zwischen diesen beiden Zellen ein. 1.Wähle die neue Zelle als jetzige Zelle. 1.Punkt 3 rekursiv abarbeiten.

m0rius

und das generiert ein Labyrinth mit genau einem Weg von oben links nach unten rechts??

Hallo ErfinderDesRades,

die Irrgärten (streng genommen sind es keine Labyrinthe, weil diese nur aus einem einzigen gewundenen Weg ohne Abzweigungen bestehen), die dadurch generiert werden, sind perfekt. Das bedeutet, dass es von jedem Punkt zu jedem anderen Punkt nur einen (!) einzigen Weg gibt. Der Einstiegspunkt links oben bzw. der Ausstiegspunkt rechts unten sind von mir gewählt und "geschummelt", da beim Zeichnen des Labyrinths einfach nur die schwarzen Linien nicht gezeichnet werden - generiert wird letzten Endes ein intakter Außenrand.

m0rius

hi m0rius

Ist der Quellcode verfügbar?
Würde da gerne mal dahinter sehen wie du das gemacht hast.
Ich habe selbst einmal angefangen mit einem solchen Projekt aber hab es dann sein lassen weil ich irgendwie nicht mehr weiter kam.
Kannst dich ja per PN melden.

Gruss Narnaja

Hallo Narnaja, ErfinderDesRades,

klar könnt ihr den Quellcode haben, s. Anhang 😃.

m0rius

Hallo zusammen,

hier noch das Klassendiagramm zum Projekt (mittlerweile hätte ich vieles sicher anders gelöst, aber naja.).

m0rius

Vielen Dank für den Quellcode.
Werde mir den heute Abend mal anschauen wie du das gelöst hast, bin schon ganz gespannt.

Gruss Narnaja

siehe auch Maze Tools - Labyrinth generator und Spiel