Identifizieren von Quad-Mustern in einem zweidimensionalen Array

7

In der Tech-Demo, die ich erstellen möchte, werden vom Spieler Blöcke im Tetrominoe-Stil platziert. Zu diesem Zeitpunkt prüft das Spiel, ob sie ein Quad mit vorhandenen Formen auf dem Brett erstellt haben (ein 2D-Array). In diesem Fall sollte das Quad auf irgendeine Weise verarbeitet werden.

Ich habe ein 2D-Array wie folgt:

[ [0, 0, 0, 1, 1, 1],
  [0, 1, 1, 1, 1, 1],
  [1, 0, 0, 1, 1, 1],
  [1, 0, 0, 1, 0, 1] ]

Und ich muss 'Quad'-Muster wie das in der oberen rechten Ecke identifizieren, z

[ [1, 1, 1],
  [1, 1, 1],
  [1, 1, 1] ]

Ich bin mir nicht sicher, wie ich das am besten machen kann. Ich habe mir einige zweidimensionale Array-Muster-Matching-Algorithmen angesehen, die alle das 2D-Array in 1D zu reduzieren scheinen, und dann einen 1D-Textsuchalgorithmus (z. B. KMP) verwendet, um Übereinstimmungen zu identifizieren. Meine Probleme mit dieser Idee sind, dass das Quad jede Größe haben kann, solange es rechteckig und größer als ein beliebiges Minimum ist (in meinem Fall 2 x 2).

Ich dachte auch darüber nach, für jede Position der neu platzierten Tetrominoe eine Variante des 4-Wege-Flutfüllungsalgorithmus oder der Kennzeichnung verbundener Komponenten zu verwenden. Aber ich bin mir nicht ganz sicher, wie ich dem Pfad am besten folgen und die Grenzen eines Quads festlegen soll (zum Beispiel, um dies zu erfassen:

[ [1, 1, 1],
  [1, 1, 1],
  [1, 1, 1] ]

aus dieser:

[ [1, 1, 1, 1],
  [1, 1, 1, 0],
  [1, 1, 1, 0] ]

Meine letzte ist jedoch vielleicht eine Überflutung, um alle miteinander verbundenen Teile zu erhalten, nachdem eine Tetrominoe gelandet ist, und dann die gezackten Kanten abzurunden, indem Sie möglicherweise die Anzahl der Nachbarn jedes Blocks überprüfen. Wenn es 1 ist, entfernen Sie sie und wiederholen Sie den Vorgang, bis alle verbleibenden übrig sind Blöcke haben 2 oder mehr Nachbarn. Aber das scheint langsam zu sein.

Hat jemand Erfahrung mit diesem Problem oder Hinweise, wie diese Aufgabe am besten gelöst werden kann? Ich bin sicher, es gibt einen gemeinsamen oder zumindest anwendbaren Algorithmus, ich weiß es einfach nicht!

Codierungshände
quelle
2
Oh, bringt Erinnerungen an meine Highschool-Tage am IOI zurück. Ich erinnere mich, dass ich genau dasselbe Problem mit so etwas gelöst habe: Für jede Zelle speichere ich die maximale Box, die ich von diesem Punkt aus machen kann, indem ich nur nach links und unten gehe; und ich fange an, dies iterativ von der unteren linken Ecke nach oben und rechts zu füllen. Die Lösung ist O (n) für insgesamt n Zellen. Ich werde versuchen, es später zu codieren.
Panda Pyjama
Das wäre nützlich :)
Codinghands

Antworten:

7

Ich habe es gezeichnet.

Einige Szenarien berücksichtigen nur quadratische Quads

Was alles bedeutet

  • Farbige Hintergründe sind das Layout ausgefüllter Quadrate unmittelbar nach dem Platzieren eines Blocks.
  • Rote Kreise sind Stellen, die möglicherweise die obere linke Ecke eines Quad sein können.
  • Rote Linien befinden sich auf Quadraten um eine potenzielle Ecke, die ausgefüllt werden müssen, damit die Form ein Quad ist.
  • Rote Kreuze sind Orte, die überprüft wurden und als leer befunden wurden. (In den letzten beiden Diagrammen habe ich sie mit dem roten Kreis verbunden, von dem aus die Prüfung durchgeführt wurde.)

Was ist passiert?

Im ersten Diagramm (grün) hat es fantastisch geklappt. In der allerersten oberen linken Ecke, die wir überprüft haben, sind rechts unten Quadrate ausgefüllt, die einen 2x2Block bilden. Wenn wir versuchen, noch ehrgeiziger zu sein und einen 3x3Block zu bilden, stellen wir fest, dass einige davon (die roten Kreuze) nicht gefüllt sind. Alles was wir haben ist ein 2x2.

Im zweiten Diagramm (blau) lief es auch leicht. Außer diesmal stimmte sogar der zweite Umriss unten rechts auf allen Quadraten überein: Wir haben einen 3x3Block. Der Versuch, einen 4x4Fehler zu machen, schlägt fehl, da nicht alle Felder gefüllt sind.

Im dritten Diagramm (lila) haben wir nichts. Wir hatten keine ausgefüllten Quadrate mehr, um die Ecke zu platzieren, bevor wir eines fanden, das einen Umriss unten rechts hat.

Im vierten Diagramm (gelb) funktionierten die Dinge nach einigen Versuchen. Die ersten drei Quadrate, in die wir Ecken einfügen wollten, hatten keinen Umriss unten rechts. Der vierte tat es jedoch. Dies gibt uns eine 2x2. Der Versuch, eine zu erhalten, 3x3schlägt wie im ersten Diagramm fehl.

Wie würden Sie das umsetzen?

Wenn Ihre Ecke ist grid[0][0], nbesteht der Umriss unten rechts aus Quadraten, in denen eine oder beide Koordinaten liegen n.

n-te Umrisse unten rechts bis zu 3

Dies verallgemeinert Folgendes: Wenn sich Ihre Ecke in befindet grid[x][y], ist der Umriss unten rechts eine Vereinigung dieser Quadratsätze:

  • grid[x+n][yVariable], wo y <= yVariable < y+n(die rechte Seite)
  • grid[xVariable][y+n], wo x <= xVariable < x+n(die Unterseite)
  • und schließlich grid[x+n][y+n](die untere rechte Ecke)

Es sollte einfach sein, diese zu durchlaufen. Wenn Sie ein Quad haben, geben die Koordinaten der oberen rechten und unteren rechten Ecke an, wo es sich befindet.

Das funktioniert aber nur für Quadrate!

Verallgemeinern auf Rechtecke

Diese drei oben genannten Aufzählungspunkte können auch einzeln überprüft werden:

separate Überprüfung der Seiten

Dies bedeutet natürlich, dass sich aus jedem Überprüfungszustand 3 (anstelle von 1) mögliche weitere Zustände entwickeln können:

die drei Prüfzustände, die sich aus einem trivialen Zustand ergeben

Jeder dieser drei Zustände kann durch ein ähnliches Verfahren weiter auf bis zu drei Zustände erweitert werden.

Ihr Code könnte die beiden anderen Zustände für später speichern und den ersten bis zur Erschöpfung verarbeiten, bevor Sie mit dem nächsten fortfahren. Am Ende wäre das Quad mit der größten Fläche die Ausgabe. (Dies ist in der Computerfachsprache ein Depth-First - Traversal eines trinären Baum.)

Anko
quelle
Vielen Dank für die umfassende Antwort! Ich brauche etwas Zeit, um es durchzuarbeiten, ohne Zweifel habe ich ein paar dumme Anschlussfragen :) wirklich geschätzt!
Codinghands
1
Okay, ein paar Dinge nach einigem manischen Kritzeln in meinem Pad ... gibt es eine Möglichkeit, dies für eine Rechteckform (3 x 5, 2 x 4) zu verallgemeinern? Gibt es auch einen Sonderfall, in dem wir das Gitter [0,0] auf ein 2x2-Gitter prüfen (dh n = 1), da yVariable die Einschränkung y <yVariable <y + n (y ist 0, y + n) aufheben muss 1) sein. Oder nicht einmal ein Sonderfall - um ein Quad am Gitter [0,0] zu bestätigen, müssen wir [0,1] (unten), [1,0] (rechts) und [1,1] (unten rechts) überprüfen ). Also muss yVar 0 sein, was y entspricht ... Obwohl meine Mathematik schrecklich ist :(
Codinghands
1
@coding In der Tat ist die Ungleichung ein Tippfehler: Ich meinte y <= yVariable < y+n! Ich werde das beheben!
Anko
1
@coding Ich habe die Antwort bearbeitet, um Rechtecke abzudecken, allerdings in geringerer Tiefe. Ist es verständlich?
Anko
Ich werde überprüfen, wenn es nicht 4 Uhr morgens ist und berichten!
Codinghands
0

Nur als Folge - ich habe schließlich ein paar Lösungen codiert, von denen eine im Grunde eine Javascript-Implementierung des in diesem Artikel über Dr. Dobbs beschriebenen Maximal Rectangle-Algorithmus war . Mein Problem schien im Grunde das Problem zu sein, das dieser Algorithmus auf den Punkt bringen soll!

Ich habe ein kurzes Blog-Stück darüber geschrieben, wie ich es in Javascript gemacht habe, und den daraus resultierenden Code, der hier in meinem Blog verfügbar ist .

Codierungshände
quelle