Match-Three-Puzzlespiel-Algorithmus

Ich versuche selbst ein Match-Three-Puzzlespiel wie "Call of Atlantis" zu schreiben. Der wichtigste Algorithmus besteht darin, alle möglichen Match-Three-Möglichkeiten herauszufinden. Gibt es Open Source-Projekte, auf die verwiesen werden kann? Oder irgendwelche Schlüsselwörter zum Algorithmus? Ich versuche nach einem schnelleren Algorithmus zu suchen, um alle Möglichkeiten zu berechnen.

Regeln:

• Diagonalen zählen nicht.
• Die Größe beträgt 8x8

Vielen Dank.

Ich habe geholfen, eines dieser Spiele auf eine Handheld-Plattform zu portieren. Rückblickend auf ihren KI-Code zum Auffinden von Potenzialen: yipe, es ist kompliziert, brutal (vierfach verschachtelte Schleife, ruft sich gelegentlich rekursiv auf usw.) und erscheint auf den ersten Blick überhaupt nicht cache-freundlich.

(Ein Teil dieser Komplexität ergibt sich aus dem Versuch, die Stärke des Umzugs im Kontext zu bewerten: längere Ketten höher bewerten, nach Combos suchen usw.)

Aber es muss nicht wirklich "optimal" sein; Wir haben den Code nicht einmal berührt, als wir ihn portiert haben. Es wurde nie im Profiler angezeigt.

Wenn man es sich jetzt ansieht, passt sogar bei einem 32-Bit-Wort pro Zelle (und ich denke, sie haben tatsächlich ein Byte pro Zelle verwendet) die gesamte Karte in einen winzigen L1-Cache, und Sie können viele überschüssige Lesevorgänge für zwischengespeicherte Inhalte durchführen, ohne dass dies Auswirkungen hat Framerate zu viel. Zumal Sie diesen gesamten Vorgang nur einmal ausführen müssen, wenn sich die Kartenkonfiguration ändert. (Ein großes Theta, das herumschwebt, n^2ist nicht so schrecklich schlecht mit einem sehr niedrigen n, ganz zu schweigen von dem kleinen Multiplikator angesichts des zwischengespeicherten Speichers.)

Nachdem dies gesagt wurde: Lassen Sie uns zur Unterhaltung versuchen, das Problem zu parallelisieren. Beginnend mit bitweisen Operationen.

Angenommen, Sie haben eine Bitmaske, die alle Teile (wir nennen sie Steine) in einer Reihe darstellt, die von einem bestimmten Typ sind (wir werden Farben verwenden, um Typen zu unterscheiden). Wir werden uns zunächst nur rote Steine ​​ansehen und uns später Gedanken über die Kosten für die Berechnung der Bitmaske machen.

// Let's assume top right indexing.
// (The assumption is not necessary, --
//    it just makes the left-shift and right-shift operators 
//    look like they're pointing in the correct direction.)

// this is for row 2
col index  76543210
color      BRRGYRBR // blue, red, red, green, yellow, ...
"red" bits 01100101

Wir für die Serie suchen, der nur einen Swap benötigt eine Reihe von 3. Mit freundlicher Genehmigung Kaj zu werden, das eines von drei Kombinationen ist, im Grunde: XoX, oXXoder XXowo Xist ein passender Stein und oist etwas anderes.

(Diese Idee stammt aus dem wunderbaren Hacker's Delight-Buch . Siehe auch das fxtbook, wenn Sie an solchen Dingen Gefallen finden .)

// using c-style bitwise operators:
// & is "and"
// ^ is "xor"
// | is "or"
// << and >> are arithmetic (non-sign-extending) shifts

redBitsThisRow = redBitsRows[2]

// find the start of an XoX sequence
startOfXoXSequence = redBitsThisRow & (redBitsThisRow << 2);
// for our example, this will be 00000100

// find any two stones together in a row
startOfXXSequence = redBitsThisRow & (redBitsThisRow << 1);
// for our example, this will be 01000000

Es ist nützlicher, die Positionen der fehlenden Steine ​​zu kennen, nicht den Beginn der XX- oder XoX-Sequenz:

// give us any sequences that might want a stone from the left
missingLeftStone = startOfXXSequence << 1;
// for our example, this will be 10000000

// give us any sequences that might want a stone from the right
missingRightStone = startOfXXSequence >> 2;
// for our example, this will be 00010000

// give us any sequences that might want a stone from the top or bottom
missingTopOrBottomStone = missingRightStone | missingLeftStone | (startOfXoXSequence >> 1)
// for our example, this will be 10010010

(Ungefähr 1 Last und 9 ALU-Anweisungen - 5 Schichten, 2 Ors, 2 Ands - mit einer schrecklichen CPU ohne Inline-Shifter. Auf vielen Architekturen sind diese Schichten möglicherweise kostenlos.)

Können wir diese fehlenden Stellen füllen?

// look to the left, current row
leftMatches = redBitsThisRow & (missingLeftStone << 1)

// look to the right, current row
rightMatches = redBitsThisRow & (missingRightStone >> 1)

// look on the row above
topMatches = redBitsRow[1] & missingTopOrBottomStone

// look on the row below
bottomMatches = redBitsRow[3] & missingTopOrBottomStone

(Weitere 2 Ladevorgänge und 6 ALU-Anweisungen - 4 ands, 2 Schichten - mit einer fehlerhaften CPU. Beachten Sie, dass Zeile 0 und Zeile 7 Probleme verursachen können. Sie können diese Berechnungen verzweigen oder die Verzweigung durch Zuweisen vermeiden Platz für zwei zusätzliche Zeilen, eine vor 0 und eine nach 7, und lassen Sie sie auf Null.)

Jetzt haben wir mehrere "Übereinstimmungs" -Varianten, die die Position eines Steins angeben, der ausgetauscht werden kann, um eine Übereinstimmung zu erzielen.

Dies setzt eine intrinsische oder sehr billige Inline-Methode voraus:

swapType = RIGHT_TO_LEFT;
matches = leftMatches;
while ( (colIdx = ctz(matches)) < WORD_BITS ) {
   // rowIdx is 2 in our examples above
   workingSwaps.insert( SwapInfo(rowIdx, colIdx, swapType) );
   // note that this SwapInfo construction could do some more advanced logic:
   //   run the swap on a temporary board and see how much score it accumulates
   //   assign some sort of value based on preferring one type of match to another, etc

   matches = matches ^ (1<<colIdx); // clear the match, so we can loop to the next
}
// repeat for LEFT_TO_RIGHT with rightMatches
// repeat for TOP_TO_BOTTOM with topMatches
// repeat for BOTTOM_TO_TOP with bottomMatches

Beachten Sie, dass keine dieser Bitlogiken in Little-Endian- oder Big-Endian-Umgebungen zusammenbrechen sollte. Bei Boards, die breiter als Ihre Maschinenwortgröße sind, wird es viel schwieriger. (Sie könnten mit so etwas experimentieren std::bitset.)

Was ist mit Spalten? Es ist möglicherweise am einfachsten, nur zwei Kopien der Tabelle zu haben, eine in Zeilenreihenfolge und eine in Spaltenreihenfolge. Wenn Sie Zugriff auf Getter und Setter haben, sollte dies trivial sein. Es macht mir nichts aus, zwei Arrays auf dem neuesten Stand zu halten, schließlich wird ein Set rowArray[y][x] = newType; colArray[x][y] = newType;und das ist einfach.

... aber verwalten rowBits[color][row]und colBits[color][col]wird unausstehlich.

Kurz gesagt , wenn Sie rowBitsund haben colBits, können Sie denselben Code ausführen, wobei rowBits stattdessen auf colBits zeigen. Pseudocode unter der Annahme, dass in diesem Fall die Boardbreite = Boardhöhe = 8 ist ...

foreach color in colors {
    foreach bits in rowBits, colBits {
        foreach row in 0..7 { // row is actually col the second time through
            // find starts, as above but in bits[row]
            // find missings, as above
            // generate matches, as above but in bits[row-1], bits[row], and bits[row+1]
            // loop across bits in each matches var,
            //    evaluate and/or collect them, again as above
        }
    }
}

Was ist, wenn wir uns nicht die Mühe machen wollen, ein schönes 2D-Array in Bits umzuwandeln? Mit einer 8x8-Karte, 8 Bit pro Zelle und einem 64-Bit-fähigen Prozessor können wir möglicherweise damit durchkommen: 8 Zellen = 8 Bytes = 64 Bit. Wir sind jetzt an unsere Boardbreite gebunden, aber das scheint vielversprechend.

Angenommen, "0" ist reserviert, Steine ​​beginnen bei 1 und gehen zu NUM_STONE_TYPES einschließlich.

startOfXXSequence = rowBytes ^ (rowBytes << (8*1))
// now all bytes that are 0x00 are the start of a XX sequence

startOfXoXSequence = rowBytes ^ (rowBytes << (8*2))
// all bytes that are 0x00 are the start of a XoX sequence

Beachten Sie, dass hierfür kein Durchgang pro Farbe erforderlich ist. In erhalten BRBRBRGYwir eine startOfXoXSequence, die so etwas wie sein könnte 0x00 00 00 00 aa bb cc dd- die oberen vier Bytes sind Null, was darauf hinweist, dass dort eine mögliche Sequenz beginnt.

Es wird spät, also werde ich hier aufhören und möglicherweise später wiederkommen - Sie können diesen Weg mit xors fortsetzen und Tricks des ersten Null-Bytes erkennen, oder Sie könnten sich einige ganzzahlige SIMD- Erweiterungen ansehen .

Sie überdenken das Problem. In einer einzelnen 8er-Zeile gibt es 6 mögliche Positionen für ein Match-3, sodass es für das gesamte 8x8-Board nur 96 mögliche Match-3-Positionen gibt. Das Überprüfen von 96 Möglichkeiten beansprucht eine unbedeutende Menge an CPU-Zeit. Sie verwenden wahrscheinlich tausendmal mehr Taktzyklen, indem Sie nur einen Frame zeichnen.

Wenn Sie nach zwei benachbarten Swap-Zügen suchen, die Match 3s ergeben können ... Für jede mögliche Position gibt es höchstens 3 mögliche Swaps, die ein Match 3 ergeben können, wenn für jede mögliche Position bereits 2 passende Teile vorhanden sind Auf der Linie sind höchstens 23 Züge zu berücksichtigen, und für das gesamte Board sind 112 Züge zu berücksichtigen. Das Überprüfen von 112 Zügen ist auch eine unbedeutende Menge an CPU-Zeit.

Es gibt nur wenige Kombinationen, die eine Übereinstimmung ergeben können. XX mit einem unter oder über der Mitte (und um 90 Grad gedreht) und xx. mit einem rechts oder oben auf dem '.' (und die auf beiden Achsen gedrehten und gespiegelten Varianten. Das ergibt 14 verschiedene Suchmuster, die ein (max. 4x3) Raster mit dem 8x8-Raster abgleichen müssen. Ich würde das Muster nur brutal erzwingen und entlang des 8x8-Rasters schieben und überprüfen wenn die Orte , wo es ein x gleich sind. wenn ja , es ist eine Menge , die eine dreifache erstellen können.
so im Allgemeinen (zum Beispiel) gleiten

....
xx , x
....
oder (anotheher Beispiel)
. x.
x. ...
x.

auf ganzer Linie - wenn alle drei x-Positionen das gleiche Symbol haben, ist dies ein möglicher Zug.
Und das mal 14 für alle möglichen Züge.

Wenn Geschwindigkeit wirklich ein Problem ist, würde ich sagen, versuchen Sie etwas wie:

• Iterieren Sie das gesamte Raster von oben links.

• Aktivieren Sie an jedem Punkt des Rasters bis einschließlich der 6. Spalte eine Kachel rechts und unten (Sie müssen nicht links und oben prüfen, da Sie dies getan haben).

• Wenn Sie die 7. Spalte erreichen, überprüfen Sie nur nach unten. (Es gibt keinen Platz für 3 Personen, wenn nur 2 Spalten vorhanden sind.)

• Wenn sie übereinstimmen, versuchen Sie, eine weitere Kachel entlang / nach unten zu überprüfen. Wenn dies nicht der Fall ist, gehen Sie zum nächsten Plättchen.

• Wenn Sie die 8. Spalte beendet haben, gehen Sie eine Zeile nach unten.

Für ein 8x8-Raster ist jedoch nicht viel Optimierung erforderlich. Eine einfachere Form wäre (ähnlich):

• Iterieren Sie das gesamte Raster von oben links.

  • Aktivieren Sie an jedem Punkt des Rasters bis einschließlich der 6. Spalte eine Kachel rechts und unten (Sie müssen nicht links und oben prüfen, da Sie dies getan haben).

  • Wenn sie übereinstimmen, versuchen Sie, eine weitere Kachel entlang / nach unten zu überprüfen. Wenn dies nicht der Fall ist, gehen Sie zum nächsten Plättchen. Behandeln Sie Out-of-Board-Fehler als "nicht gleich".

  • Wenn Sie die 8. Spalte beendet haben, gehen Sie eine Zeile nach unten.

Dies würde einen viel einfacheren Code in der for-Schleife ermöglichen, da Sie keine if-Struktur mit etwas Code auf einer Seite und leicht angepasstem Code darunter haben.

Es ist nicht sehr hübsch oder elegant, aber ich habe ein Match-3-Spiel in JavaScript geschrieben . Im Quellcode von GitHub sehen Sie die Match-3-Logik direkt in Ihrem Webbrowser: https://github.com/richtaur/bombada/blob/master/htdocs/js/match3.js#L184