Update: Dies wird ein de Brujin Torus genannt, aber ich muss noch einen einfachen Algorithmus in C # herausfinden.
Ich muss alle Werte eines 3x3-Bit-Rasters so dicht wie möglich kombinieren. Mit einem 3x3-Bit-Raster meine ich ein 3x3-Raster, bei dem jeder Platz dem Lochstanzkonzept in dieser Frage ähnelt:
Finden Sie alle Kombinationen von 3x3 lochpunch
Ich möchte alle 512 (eigentlich 256, weil das mittlere Bit immer eingeschaltet ist) mögliche Werte packen, so dass sie sich in einem einzigen NxM-Gitter überlappen.
Unvollständiges Beispiel:
Dieses Beispiel packt ~ 25 der möglichen Werte in ein 7x7 Raster.
%Vor%Ich habe viele verschiedene Techniken von Hand ausprobiert, konnte aber keinen einfachen Algorithmus finden.
Also würde ich gerne ein C # -Programm schreiben, um dies zu erstellen, aber ich habe auch keinen einfachen Weg gesehen.
Es gibt nicht einmal einen offensichtlichen Brute-Force-Ansatz, der mir möglich erscheint. Es scheint so, als würde jeder Brute-Force-Versuch 512 erreichen! Kombinationen im schlimmsten Fall.
Jede Kante hat nur 8 mögliche Werte.
%Vor%Dies wird tatsächlich für ein 2D-Kachel-basiertes Spiel verwendet werden.
Das Spiel hat N mögliche Bodenstücke. Da der Untergrund in jeder Situation auftreten kann, muss der Designer angeben, welche Kachel für die jeweilige Situation ausgewählt werden sollte.
Ein kompaktes Gitter, das alle möglichen Situationen enthält, ist der effizienteste Weg, um zu spezifizieren, welche Kachel in jeder Situation zu verwenden ist und eliminiert jegliche Redundanz.
Das obige ist das Basismuster, das den Ausdruck von 4 Situationen erlaubt, und ich werde dies ändern, um andere ASCII-Werte zu verwenden, um das Ergebnis darzustellen, das in jeder Situation verwendet werden sollte:
%Vor%Wo A, G, H jeweils ein bestimmtes Muster repräsentieren, das für jede Situation verwendet werden sollte.
Wenn also das folgende Muster gefunden wird:
%Vor%Dies entspricht dem Muster, das zu "A" oben führt, daher wird in dieser Situation "A" verwendet.
%Vor%Der Zweck ist, einen erschöpfenden Ausdruck dessen zu haben, was jede mögliche Situation bewirken würde.
Ich konnte dies versuchen und fand die Ergebnisse zu zufällig, um die Ziele zu erreichen. Als Mensch war es schwierig, in jeder Situation die richtigen Werte zu wählen, oder die Desorganisation. Die manuelle Gruppierung ähnlicher Muster funktioniert immer noch besser.
Betrachten wir jede height-3-Spalte als eine einzelne Zahl zwischen 0 und 7, was wir tun können, da es 8 mögliche height-3-Spalten gibt. Jetzt ist das Packen aller 512 möglichen 3x3-Muster in das minimal mögliche 3xN-Gitter gleichbedeutend mit dem Finden einer de Bruijn-Sequenz mit Parametern B (8, 3) . Dieses Gitter hat die Größe 3x514 : nach dem ersten 3x3 kostet uns jedes weitere 3x3 nur noch 1 extra Spalte, was für ein Raster der Höhe 3 offensichtlich am besten möglich ist.
Ausgehend von dieser Wikipedia-Seite scheint es der effizienteste Weg zu sein, eine Reihe von de Bruijn-Sequenzen B (8, 1), B (8, 2), B (8, 3) durch Finden aufzubauen Eulersche Zyklen im de Bruijn-Graphen der vorherigen Sequenz (da der andere vorgeschlagene Algorithmus die Suche nach einem Hamilton-Pfad beinhaltet, der ein NP-vollständiges Problem ist, das dem Problem des reisenden Verkäufers entspricht).
Es gibt auch de Bruijn tori , 2D-Analogien von de Bruijn-Sequenzen, die sich Ihrem Ziel des Packens direkt nähern NxN-Raster Allerdings ist auf dieser Seite nicht klar, wie oder ob es möglich ist, einen de Bruijn-Torus für 3x3-Muster zu konstruieren (sie sagen nur, dass es bekannt ist, dass sie für quadratische Muster gleicher Größe konstruiert werden können ). und dass ein Torus für ein quadratisches Muster mit ungerader Größe nicht selbst quadratisch sein kann - also vermutlich ist NxN out), und außerdem ist es wahrscheinlich, dass die starke Eindeutigkeitsbedingung, die sie erfüllen, für Ihre Anwendung unnötig ist.
Die folgende 520-Bit-Zeichenfolge enthält alle 3x3-Bitmuster als zusammenhängende Untersequenzen:
%Vor%Oder, wenn Sie bevorzugen, j_random_hacker's Version:
%Vor%Oder Sie könnten Platz sparen und einfach die Zahlen von 0 bis 511 verwenden, die bei den meisten Computern alle 9-Bit-Muster sind.
"Ein kompaktes Gitter, das alle möglichen Situationen enthält, ist der effizienteste Weg, um festzulegen, welche Kachel in jeder Situation verwendet werden soll, und eliminiert jegliche Redundanz."
Ich bin geneigt, anderer Meinung zu sein.
Unabhängig davon, wie das Ergebnis Ihrer Faltübung aussieht, erfordert die Indizierung, um ein gegebenes 3x3-Muster zu erhalten, 8-Bit-Indizes, da es genau 256 Tile-Adjazenzsituationen gibt. Wenn Ihre kompakte Darstellung mehr als 256 Muster enthält, dh wenn unerwünschte oder redundante Muster eingemischt sind, benötigen Sie mehr als acht Bits für die Indexierung.
Ein 8-Bit-Byte kann jedoch bereits alle möglichen Nachbarschaftssituationen darstellen, wenn Sie es als Bitmaske behandeln und die acht Bits den acht äußeren Kacheln eines 3x3-Gitters in irgendeiner Weise zuordnen. Dies bedeutet, dass das gefaltete Master-Grid - de Bruijn-Stil oder anders - überflüssig ist und entbehrlich ist.
Tags und Links algorithm c# bit-packing