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:
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
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
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.
Ähnlich wie bei # 3 könnte es mir in diesem Szenario auch gelingen, die Objekte als eins zu behandeln.
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 ...
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.
quelle
Antworten:
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.
quelle
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:
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.
quelle