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:

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:

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:

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!):

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:

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