Falling Blocks i złożone kształty

Obecnie mam prostą grę podobną do Tetris i napotkałem problem, którego nie mogę rozwiązać.

W przeciwieństwie do Tetrisa, w którym występuje pojedynczy spadający kształt, mam wiele potencjalnie powiązanych ze sobą kształtów, które muszą spaść; Muszę obliczyć ich końcowe pozycje. Rozważ następujące:

1. Aby obliczyć ostateczną pozycję zielonego kształtu, po prostu skanuję każdy kwadrat, aż uderzę w inny kwadrat lub krawędź planszy. Gotowy

2. W przypadku wielu prostych kształtów wspinam się po tablicy. W ten sposób okazuje się, że czerwony nie musi się poruszać, pomarańczowy spada o jeden, zielony zmniejsza o trzy. Gotowy

3. Nie wiem, jak traktować powiązane ze sobą zielone i czerwone kształty. Stosując logikę # 2, w końcu „utknęliśmy” unosząc się w powietrzu. Jeśli skanuję w poszukiwaniu zielonego kształtu, napotykam czerwony, a zatem nie ruszam się i odwrotnie w przypadku czerwonego. Rozwiązaniem może być traktowanie tych dwóch kształtów jako jednego.

4. Podobnie jak w punkcie 3, w tym scenariuszu mógłbym również odnieść sukces, traktując obiekty jako jeden.

5. W przeciwieństwie do # 3 i # 4 nie mogłem traktować kształtu jako jednego, ponieważ pomarańczowy kształt skończyłby się zbyt wysoko o jeden kwadrat ...

6. Kolejna odmiana problemu nr 6.

Mogą istnieć inne scenariusze, w których mam wiele kształtów, które przeplatają się w coraz bardziej złożonych scenariuszach, ale myślę, że powyższe obejmuje najbardziej podstawowe części problemu.

Wydaje mi się, że istnieje eleganckie rozwiązanie, z którym jeszcze się nie spotkałem / wymyślę i byłbym bardzo wdzięczny za wszelkie informacje, pomysły i zasoby.

ROZWIĄZANIE

Rozwiązanie, które wymyśliłem, jest naprawdę eleganckie, na podstawie poniższej odpowiedzi @ user35958 stworzyłem następującą funkcję rekurencyjną (pseudo kod)

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);
}

Animowany GIF przedstawiający każde przejście rozwiązania

Podsumować:

• Kiedy „zatrzymujemy” kwadrat, zatrzymujemy również:
  • DOWOLNY kwadrat nad nim. ZAWSZE.
  • Sąsiedni kwadrat, z którym jesteśmy połączeni (tj. Ten sam kształt).
• Zatrzymujemy cały dolny rząd, a funkcja powtarza się przez kwadraty.
• Powtarzamy, aż wszystkie kwadraty zostaną zatrzymane.
• Następnie animujemy.

Cóż, nie musisz traktować kształtów jako jednego, jeśli istnieje różnica między kształtami w ruchu a kształtami w spoczynku. Kształt (A) może wykryć kształt (B) bezpośrednio pod nim, a jeśli się porusza, wówczas kształt B może następnie sprawdzić, czy coś jest bezpośrednio pod nim, a jeśli jest kształt spoczynkowy, to A i B spoczywają teraz, i jeśli nic nie ma, oboje przesuwają się w dół, ale jeśli jest ruchomy kształt, to nowy kształt będzie traktowany przez A i B jako A traktowany B, więc jest to rodzaj rekurencji. Pamiętaj, że dla każdego kroku najniższe kształty muszą najpierw sprawdzić kształty poniżej nich.

Tak więc dla problemu nr 6 zielony kształt jest najniższym ruchomym kształtem i zobaczyłby, że jedynym kształtem, który jest bezpośrednio pod nim, jest kształt czerwony, więc czerwony kształt nie wykryłby niczego bezpośrednio pod nim i poruszałyby się w dół . Gdy zielony kształt przylega do kształtu pomarańczowego, spoczywa, a czerwony kształt przesuwa się w dół, a następnie wykrywa spoczynkowy zielony kształt, a także odpoczywa.

Wygląda na to, że problem z przypadkami nr 5 i nr 6 wynika z jednego katalogu głównego: wykonujesz tylko jedno przejście kontroli ruchu. Powinieneś przesuwać rzeczy w dół (nazwijmy to „przejściem grawitacyjnym”), dopóki nie dowiesz się, że nic się nie poruszyło.

Na przykład, w przypadku 6, tak by się stało, gdybyś użył wielu przejść:

• Orange przesuwa się w dół
• Zielony przesuwa się w dół
• Orange przesuwa się w dół
• Zielony przesuwa się w dół
• Orange przesuwa się w dół
• Nic się nie przesuwa (gotowe!)

Ta strategia wielokrotnych przejść grawitacyjnych może również rozwiązać # 5, chociaż nie pomoże w przypadkach # 3 i # 4, w których wydaje się, że musisz traktować je jak jeden kawałek.

Aby odróżnić, kiedy dwa lub więcej elementów należy traktować jako jeden element, myślę, że najłatwiejszym algorytmem jest sprawdzenie, czy w połączonej przestrzeni wszystkich elementów są jakieś „dziury”. Jeśli są, można je traktować jako wiele elementów.