Fallende Blöcke und komplexe Formen

10

Ich habe derzeit ein einfaches Tetris-ähnliches Spiel und bin auf ein Problem gestoßen, das ich nicht lösen kann.

Im Gegensatz zu Tetris, wo es eine einzelne fallende Form gibt, habe ich mehrere, möglicherweise ineinandergreifende Formen, die fallen müssen. Ich muss ihre endgültigen Positionen berechnen. Folgendes berücksichtigen:

Beispiele für das Problem der fallenden Blöcke

  1. Um die endgültige Position der grünen Form zu berechnen, scanne ich einfach nach jedem Quadrat, bis ich auf ein anderes Quadrat oder die Kante des Bretts stoße. Erledigt

  2. Für mehrere einfache Formen arbeite ich mich nach oben. Somit muss sich das Rot nicht bewegen, das Orange sinkt um eins, das Grün um drei. Erledigt

  3. Ich weiß nicht, wie ich die ineinandergreifenden grünen und roten Formen behandeln soll. Mit der Logik von # 2 würden wir am Ende in der Luft "stecken bleiben". Wenn ich nach der grünen Form scanne, stoße ich auf die rote und bewege mich daher nicht und umgekehrt nach der roten. Die Lösung könnte darin bestehen, die beiden Formen als eine zu behandeln.

  4. Ähnlich wie bei # 3 könnte es mir in diesem Szenario auch gelingen, die Objekte als eins zu behandeln.

  5. Im Gegensatz zu # 3 und # 4 konnte ich die Form nicht als eine behandeln, da die orange Form ein Quadrat zu hoch schweben würde ...

  6. Eine weitere Variante von Problem Nr. 6.

Es könnte andere Szenarien geben, in denen ich viele verschiedene Formen habe, die sich in immer komplexeren Szenarien verweben, aber ich denke, dass das Obige die grundlegendsten Teile des Problems abdeckt.

Ich habe das Gefühl, dass es eine elegante Lösung gibt, die ich noch nicht gefunden / mir ausgedacht habe, und wäre für jeden Einblick, jede Idee oder jede Ressource sehr dankbar.

LÖSUNG

Die Lösung, die ich gefunden habe, ist in der Tat elegant. Basierend auf der Antwort von @ user35958 unten habe ich die folgende rekursive Funktion (Pseudocode) erstellt.

function stop(square1, square2){
    // Skip if we're already stopped
    if(square1.stopped){
        return;
    }
    // Are we comparing squares?
    if(!square2){
        // We are NOT comparing squares, simply stop.
        square1.stopped = true;
    } else {
        // Stop IF
        // square1 is directly above square2
        // square1 is connected to square2 (part of the same complex shape)
        if(square1.x == square2.x && square1.y == (square2.y+1) || isConnected(square1, square2)){
            square1.stopped = true;
        }
    }
    // If we're now stopped, we must recurse to our neighbours
    stop(square1, squareAbove);
    stop(square1, squareBelow);
    stop(square1, squareRight);
    stop(square1, squareDown);
}

Animiertes GIF, das jeden Durchgang der Lösung zeigt

Zusammenfassen:

  • Wenn wir ein Quadrat "stoppen", stoppen wir auch:
    • JEDES Quadrat darüber. IMMER.
    • Nachbarquadrat, mit dem wir verbunden sind (dh dieselbe Form).
  • Wir stoppen die gesamte untere Reihe und die Funktion wiederholt sich durch die Quadrate.
  • Wir wiederholen, bis alle Quadrate gestoppt sind.
  • Dann animieren wir.

Animiertes GIF, das jeden Durchgang der logischen Sequenz zeigt

oodavid
quelle
Ich stelle mir vor, wenn Sie 5 gelöst hätten, wären auch 6 gelöst. Tatsächlich glaube ich, dass das Lösen von 5 wahrscheinlich alle diese Situationen lösen würde.
UnderscoreZero
+1 danke fürs teilen. Erstaunliche Lösung.
Ich
Cheers ashes999, ich denke, ich brauche eine neue Animation mit Pfeilen, die zeigen, wie die
Stopplogik

Antworten:

4

Nun, Sie müssen Formen nicht unbedingt als eine behandeln, wenn zwischen sich bewegenden und ruhenden Formen unterschieden wird. Eine Form (A) könnte eine Form (B) direkt darunter erkennen, und wenn sie sich bewegt, könnte die B-Form sehen, ob sich etwas direkt darunter befindet, und wenn es eine ruhende Form gibt, ruhen A und B jetzt und Wenn es nichts gibt, bewegen sich beide nach unten, aber wenn es eine sich bewegende Form gibt, wird diese neue Form von A und B als A behandeltes B behandelt, also ist sie irgendwie rekursiv. Beachten Sie, dass die niedrigsten Formen bei jedem Schritt zuerst nach Formen suchen müssen, die darunter liegen.

Für Problem Nr. 6 ist die grüne Form die niedrigste sich bewegende Form, und es würde sich herausstellen, dass die einzige Form, die direkt darunter liegt, die rote Form ist. Dann würde die rote Form nichts direkt darunter erkennen und sie würden sich nach unten bewegen . Sobald die grüne Form an die orange Form angrenzt, würde sie ruhen, und die rote Form würde sich nach unten bewegen und dann die ruhende grüne Form erkennen, und sie würde auch ruhen.

awsumpwner27
quelle
Habe ich Recht, wenn ich denke, dass wir annehmen müssen, dass nicht alle Formen ruhen, bis wir das Gegenteil beweisen?
Oodavid
Ich habe gerade einige Zeit damit verbracht, darüber nachzudenken, und ich muss sagen, es klingt nach einer sehr guten Technik. Ich werde es morgen / am Wochenende versuchen und sehen, wie es ausgeht.
Oodavid
3

Es scheint, dass das Problem mit den Fällen Nr. 5 und Nr. 6 von einer einzigen Wurzel herrührt: Sie führen nur einen Durchgang von Bewegungsprüfungen durch. Sie sollten die Dinge weiter nach unten bewegen (nennen wir es einen "Schwerkraftpass"), bis Sie wissen, dass sich nichts bewegt hat.

In Fall 6 würde dies beispielsweise passieren, wenn Sie mehrere Durchgänge verwenden:

  • Orange bewegt sich nach unten
  • Grün bewegt sich nach unten
  • Orange bewegt sich nach unten
  • Grün bewegt sich nach unten
  • Orange bewegt sich nach unten
  • Nichts bewegt sich nach unten (fertig!)

Diese Strategie der Mehrfachgravitationsdurchgänge könnte auch # 5 lösen, obwohl sie in den Fällen # 3 und # 4 nicht hilft, in denen Sie sie anscheinend wie ein Stück behandeln müssen.

Um zu unterscheiden, wann zwei oder mehr Teile als ein einzelnes Teil behandelt werden sollen, ist es meiner Meinung nach am einfachsten, zu prüfen, ob sich im kombinierten Raum aller Teile "Löcher" befinden. Wenn ja, kann es als mehrere Teile behandelt werden.

Asche999
quelle
1
Bei # 3 und # 4 kann es auch Variationen geben, bei denen beispielsweise 2 oder 3 Formen vollständig von einer größeren "C" -Form umschlossen sind. Wenn Sie herausfinden, ob Teile koaguliert sind, kann dies zu weiteren Problemen führen. Ich werde es versuchen und sehen, was daraus wird! Cheers @ ashes999
oodavid
@oodavid Ihre Anforderungen / Design scheint mir unnötig kompliziert. Beginnen Sie mit etwas Einfacherem und arbeiten Sie sich nach oben, während Sie diese Probleme lösen.
Asche999
Nahhhh, das obige Problem ist eine gründlich vereinfachte / abstrahierte Art, ein viel komplexeres Problem zu beschreiben. Ich mache das für den Nervenkitzel der Jagd!
Oodavid