Finden von Mustern in Puzzle-Spielen

Question

Ich habe mich gefragt, welche sind die am häufigsten verwendeten Algorithmen zum Finden von Mustern in Puzzle-Spielen durch Gitter von Zellen angepasst.

Ich weiß, dass hängt von vielen Faktoren, wie die Art von Mustern, die Sie erkennen wollen, oder die Regeln des Spiels ... aber ich wollte wissen, welche die am häufigsten verwendeten Algorithmen in dieser Art von Problemen sind .. .

Zum Beispiel Spiele wie Spalten, Bejeweled, sogar Tetris.

Ich möchte auch wissen, ob die Erkennung von Mustern durch "rohe Gewalt" (wie das Scannen aller Raster versucht, drei benachbarte Zellen der gleichen Farbe zu finden) ist am schlimmsten, dass bestimmte Algorithmen in sehr kleinen Gittern, wie 4 X 4 zum Beispiel (und wieder weiß ich, dass es von der Art des Spiels und Regeln abhängt ...)

Welche Strukturen werden häufig in dieser Art von Spielen verwendet?

Answer 1

Es ist immer Domain-abhängig. Aber es gibt auch zwei Situationen, in denen Sie diese Art von Suchen durchführen. Eine Situation ist nach einem Zug (eine Änderung des Spielfelds durch den Spieler) und die andere wäre, wenn/wenn sich das ganze Spielfeld verändert hat.

In Tetris müssten Sie nicht die gesamte Platine scannen, nachdem ein Stück fallen gelassen wurde. Sie müssen nur die Reihen suchen, die das Stück berührt.

In einem Match-3-Spiel wie Bejeweled, bei dem du zwei benachbarte Steine ​​gleichzeitig austauschst, solltest du zuerst eine lokalisierte Suche in jeder Richtung um jedes geänderte Feld durchführen, um zu sehen, ob Teile ausgelöst wurden. Dann wird das Spiel neue zufällige Stücke auf das Brett werfen. Jetzt könnten Sie dieselbe lokalisierte Suche um jedes geänderte Quadrat ausführen, aber das könnte eine Menge von if Anweisungen beinhalten und könnte sogar langsamer sein, wenn Sie einfach das gesamte Board von oben links nach unten rechts scannen. Dies hängt von Ihrer Implementierung ab und würde eine Profilerstellung erfordern.

Wie Adrian sagt, genügt ein einfaches 2D-Array. Häufig können Sie jedoch einen "Rahmen" aus Pixeln um dieses Array herum hinzufügen, um das Suchen nach Mustern zu vereinfachen. Ohne einen Rahmen müssten Sie if Anweisungen entlang der Randquadrate haben, die sagen: "Nun, wenn Sie in der oberen Reihe sind, suchen Sie nicht nach oben (und gehen Sie vom Array weg)".Mit einem Rahmen um es herum, können Sie sicher nur alles durchsuchen: Speichern Sie sich if Anweisungen, sparen Sie sich verzweigen, speichern Sie sich Pipeline-Probleme, die Suche schneller.

Zu Jon: solche Dinge spielen in Hochleistungseinstellungen sogar auf modernen Maschinen eine Rolle, wenn Sie einen Suchalgorithmus zum Spielen/Lösen des Spiels erstellen. Wenn dies der Fall ist, möchten Sie, dass die zugrunde liegende Simulation so schnell wie möglich ausgeführt wird, um in den wenigsten Zyklen so tief wie möglich zu suchen.

Answer 2

In Bezug auf Algorithmen: Es hängt sicherlich vom Spiel ab. Zum Beispiel für Tetris, müssten Sie nur jede Zeile scannen, wenn sie dieselbe Farbe hat. Ich kann nicht einmal an etwas denken, das in diesem Fall nicht dem Brute-Force-Ansatz entspricht. Aber für die meisten Gelegenheitsspiele sollte rohe Gewalt vollkommen in Ordnung sein. Die Mustererkennung sollte im Vergleich zur Grafik- und Soundverarbeitung vernachlässigbar sein.

Zu den Strukturen: Ein einfaches 2D-Array sollte ausreichen, um die Platine darzustellen.

Answer 3

Angesichts der durchschnittlichen Computergeschwindigkeit in diesen Tagen, wenn es in Echtzeit ist, wie der Benutzer das Spiel spielt, wird es wahrscheinlich keine Rolle spielen (EDIT: nur für sehr kleine Spielbretter). Sicher, es würde von der Komplexität der Spiellogik abhängen, aber auch davon, wie schnell der Code auf dem Zielrechner laufen wird (d. H. Ist dies ein JavaScript-Webseitenspiel oder eine in C++ geschriebene Windows-Anwendung).

Wenn dies etwas wie die Simulation von Spielstrategien ist, dann verwende einen Algorithmus, der effizienter ist.

Eine effizientere Strategie könnte darin bestehen, inkrementelle Änderungen am Spielbrett zu verfolgen, anstatt jedes Mal das gesamte Brett neu zu scannen.