Wang Tiling implementiert und optimiert

vorhergehende Artikel in: Verschiedenes
11.03.2021

Ich habe mich - inspiriert durch Operation Mindfuck beim letztjährigen Chaos-Congress - mit Tilings in der Ebene beschäftigt.

Meine Beschäftigung danmit sah so aus, dass ich zunächst das von bleeptrack vorgestellte Erweiterung des Truchet-Tiling implementierte:

Screenshot Skalierbare Truchet Tilings

Der Gist, der dieses und ähnliche Bilder erzeugt ist hier zu finden.

Da ich mich inzwischen an dem Thema festgelesen hatte wollte ich als nächstes das Tiling mittels Wang-Dominos ausprobieren.

Mittels dieses Gists kam unter anderem dieses Ergebnis heraus:

Screenshot Wang Domino Tiling

Dieser Gist hat aber einen Nachteil: Ich bin hier naiv herangegangen und erzeuge diese Tilings, indem ich in jeder Zeile von links nach rechts fortschreite und für jede Zelle des Grid bestimme wie die obere und linke Kachel an der angrenzenden Seite eingefärbt ist. Anschließend bestimme ich alle möglichem Konfigurationen (Kacheln und Orientierungen), die unter Beachtung der Regeln an diese Stelle im Grid passen würden, wähle aus allen diesen Kandidaten zufällig einen aus und platziere ihn im Grid. Danach gehts mit der nächsten Position weiter. Tut man das so, laufen viele Versuche in Sackgassen, die dadurch definiert sind, dass sich Stellen im Grid finden, für die keine Kandidaten gefunden werden können. Im nächsten Bild sieht man für 1000 Tilings wie viele Fehlversuche zu verschmerzen waren: die Fehlversuche verden aufakkumuliert bis ein Tiling erfolgreich abgeschlossen werden konnte. Jedes Tiling bestand dabei aus horizontal 35 und vertikal 24 Kacheln:

Screenshot Darstellung der Anzahl von Versuchen für ein erfolgreiches Wang-Dominop Tiling mit dem naiven Verfahren.

Das Verfahren hatte klare Defizite - ich hatte aber keine Lust, hierfür ein komplettes Backtracking zu implementieren und legte das Ganze daher zur Seite. Später kam mir allerdings noch eine Idee, wie ich das Verfahren ohne Backtracking verbessern könnte. Nachdem ich diese Idee implementiert hatte, ergab sich - wieder für 1000 Renderings - die Anzahl der Fehlversuche wie folgt (man beachte die geänderte Y-Skala!):

Screenshot Darstellung der Anzahl von Versuchen für ein erfolgreiches Wang-Dominop Tiling mit dem verbesserten Verfahren.

Damit sank der "Ausschuss" deutlich ab - in einen Bereich, den ich tolerieren kann. Anschließend probierte ich noch einige Strategien aus wie etwa eine, die die Ausbildung großer zusammenhängender Farbflächen begünstigen sollte - Ergebnisse davon sind weiter unten zu sehen:

Im folgenden Bild kann man sehen, dass das Verhältnis von Fehlversuchen zu erfolgreichen Renderings von dieser Strategie nicht ungünstig beeinflusst wird:

Screenshot Darstellung der Anzahl von Versuchen für ein erfolgreiches Wang-Dominop Tiling mit dem verbesserten Verfahren und dem Versuch der Erzeugung möglichst großer zusammenhängender Farbflächen.


Screenshots

Artikel, die hierher verlinken

GeoJson Stadtplan-Generator

10.04.2021

Ich habe mich wieder einmal mit dem Generieren von Testdaten beschäfigt - dieses Mal sollte es eine Karte eines urbanen Gebietes, sozusagen ein Stadtplan sein.

Spielen mit Perspektive

14.03.2021

Und wieder habe ich mich mit einer netten kleinen Spielerei beschäftigt, aus der man hübsche Bilderchen erzeugen kann...

Alle Artikel rss Wochenübersicht Monatsübersicht Github Repositories Gitlab Repositories Mastodon Über mich home xmpp


Vor 5 Jahren hier im Blog

  • Virtuelles Netzwerklabor

    11.01.2017

    Nachdem ich hin und wieder vor der Herausforderung stehe, Anwendungen unter realen Netzwerkbedingungen zu testen, habe ich bereits vor längerer Zeit begonnen, ein virtuelles Netzwerklabor aufzubauen...

    Weiterlesen...

Neueste Artikel

  • Stratum-1-NTP-Server Links

    Ich habe meinen eigenen Stratum-1-NTP-Server mittels eines GPS-Empfängers, einer Adapterschaltung und einem Raspi gebaut. Hier fasse ich einige nützliche Links zu diesem Themengebiet zusammen

    Weiterlesen...
  • EBCMS threaded und mit mehr Markdown-Unterstützung

    Mein eigener Static Site Generator hat in den letzten Wochen einige größere Umbauten erfahren

    Weiterlesen...
  • Fork der BeanShell wegen Trojan Source

    Es gibt inzwischen einen von mir erstellten Fork des originalen Repository, in dem ich die Komponente zur Darstellung der Konsole gegen die ausgetauscht habe, die in der sQLshell in den Plugins MDIJavaEditor und MDISqlEditor zum Einsatz kommt - dadurch wird wenigstens durch das Syntax-Highlighting auf problematische Stellen im Code hingewiesen.

    Weiterlesen...

Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.

Wer daran teilhaben und eventuell sogar davon profitieren möchte, muß damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.

Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...

PS: Meine öffentlichen GitHub-Repositories findet man hier.