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:
Aby obliczyć ostateczną pozycję zielonego kształtu, po prostu skanuję każdy kwadrat, aż uderzę w inny kwadrat lub krawędź planszy. Gotowy
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
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.
Podobnie jak w punkcie 3, w tym scenariuszu mógłbym również odnieść sukces, traktując obiekty jako jeden.
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 ...
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.
źródło
Odpowiedzi:
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.
źródło
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ść:
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.
źródło