Jak wykryć „pokoje” w grze z przewijaniem 2D?

Chcę stworzyć system, który rozpoznaje określone typy budynków i pokoi, które można stworzyć w grze, na przykład sposób, w jaki Terraria wykrywa „rezydencje”. W tej grze dom można zbudować w świecie opartym na kafelkach, budując strefę bloków spełniających zestaw warunków:

1. Strefa jest całkowicie odizolowana od „zewnętrznego” bloków umieszczonych przez gracza.
2. Strefa może pasować do prostokąta 5x7.
3. w zamkniętym obszarze znajduje się co najmniej jeden stół, jedno źródło światła i krzesło.
4. Ze strefy prowadzą drzwi.
5. Terraria ma zarówno warstwę płytki pierwszego planu, jak i tła. Całe tło strefy musi być wypełnione blokami umieszczonymi przez gracza.

Jak mogę skutecznie wykryć, kiedy gracz zbudował obszar o odpowiedniej wielkości i jak mogę skutecznie sprawdzić, czy obszar zawiera wszystkie wymagane meble / elementy?

Przykład strefy wewnętrznej, która spełnia wszystkie wymagania mieszkaniowe:

Nie znam Terrarii, ale można to łatwo zrobić za pomocą algorytmu wypełniania zalewem .

Zamiast piksela sprawdzasz kafelki, a dla każdego sprawdzanego kafelka oceniasz, czy algorytm może kontynuować sprawdzanie innych kafelków, jednocześnie zapisując w tablicy lub liście, które obiekty znajdują się podczas procesu.

Algorytm zaczyna się od kafelka, w którym znajduje się postać. Możesz zacząć co 1 sekundę, 2 ... to kwestia drobiazgów, aby znaleźć najlepszy interwał.

Dobrym pomysłem jest również zapobieganie zbyt długiemu działaniu algorytmu, co można osiągnąć poprzez ograniczenie liczby kafelków, które algorytm może uruchomić na uruchomienie, w przeciwnym razie algorytm spowoduje długie opóźnienia, gdy postać znajduje się na otwartym obszarze.

Edytować

Jak stwierdzono w komentarzach, możesz użyć innych podejść do momentu uruchomienia algorytmu, na przykład kiedy gracz zmienia płytkę lub płytki posiadające am I modified?zmienną, która, jeśli true, uruchamia algorytm. Należy jednak zachować ostrożność przy takim podejściu:

• Co się stanie, jeśli płytka, która jest częścią pokoju, ale nie płytką, w której znajduje się twoja postać, zostanie zmodyfikowana? Może kafelek został zmieniony przez innego gracza, wydarzenie środowiskowe lub upłynął okres użytkowania kafelka. Twoja postać nie będzie świadoma modyfikacji i nie wykona algorytmu w celu wykrycia zaktualizowanego pokoju, co jest podatne na błędy.

Możesz zastosować jakieś podejście do wykrywania tych modyfikacji na kafelkach, których nie ma twoja postać, ale wykonywanie algorytmu w odstępach czasu jest najprostszym podejściem i mniej podatnym na błędy. Pamiętaj tylko, aby nie wykonywać wypełniania zalewaniem dla każdej klatki.

Koniec edycji

Jak powiedział @Ferreira da Selva, wypróbuj algorytm wypełniania zalania. Chociaż podczas uruchamiania algorytmu można użyć kilku różnych kryteriów, aby ustalić, czy jest on zamknięty.

Na przykład dla każdego kafelka sprawdzasz, czy jest kafelek tła, a jeśli nie, to wiesz, że nie jest on zamknięty. Możesz też wykonać odroczone wykonanie poprzez rozdzielenie go na kilka ramek, zmniejszając w ten sposób obciążenie procesora i zmniejszając opóźnienie. Lub możesz stworzyć limit wielkości pokoju, do którego gracz musiałby się stosować.

Zastosowanie ich kombinacji pozwoli ci to zrobić bardziej wydajnie i efektywnie.

Istnieją 2 trudne problemy w informatyce. Nazewnictwo rzeczy, unieważnienie pamięci podręcznej i błędy indywidualne.

Jest to problem z unieważnieniem pamięci podręcznej.

Jeśli masz zapis „jest to w środku”, za każdym razem, gdy blok zostanie umieszczony lub usunięty, bardzo łatwo jest go zaktualizować i jego region poprzez wypełnienie zalewowe.

Aby to zoptymalizować, możesz mieć zestaw poziomów „insideness”.

„Komórka” to region otoczony blokami umieszczonymi przez gracza (do pewnego rozmiaru).

„Pokój” to komórka z kafelkami w tle.

„Wewnątrz” jest pokój z drzwiami, światłem i krzesłem.

Po umieszczeniu bloku pierwszego planu umieszczonego przez gracza wykonaj marsz w prawo / w lewo, aby sprawdzić, czy powstaje nowa komórka. Po usunięciu bloku pierwszoplanowego umieszczonego przez gracza sprawdź, czy nie niszczy on żadnych komórek - jeśli tak, sprawdź, czy powstaje nowa komórka, łącząc te dwie.

Po utworzeniu lub nieformowaniu nowej komórki sprawdź, czy jest to pokój lub wnętrze.

Komórki mogą śledzić, ile płytek tła musi pomieścić. Następnie prosta liczba, gdy komórka jest tworzona, kafelek tła jest dodawany lub usuwany z komórki, może ustalić, czy jest to pokój.

Podobnie komórki mogą śledzić, ile krzeseł i źródeł światła (a właściwie wszelkiego rodzaju obiektów) znajduje się w nich. Zatem kontrola wewnętrzna jest banalna.

Można również dokonać liczby wejść.

Więc wzbogacamy mapę o „komórki”. Po dodaniu lub usunięciu kafelków sprawdzamy komórkę lokalizacji i zwiększamy / zmniejszamy liczbę komórek.

Użyj chodzenia zgodnie z ruchem wskazówek zegara / przeciwnie do ruchu wskazówek zegara, aby zdefiniować wnętrze i zewnątrz komórki, gdy blok pierwszego planu jest dodawany lub usuwany. Ponieważ wielkość komórek jest ograniczona, ten spacer będzie wymagał ograniczonej liczby kroków.

Jako bonus możesz teraz tanio rozmawiać o „bogatych” pokojach, „pokoju jest błogosławiony świętą fontanną” lub o czymkolwiek innym o pokoju, ponieważ pokoje zawierają w sobie liczbę typów obiektów. (Lub, ponieważ pokoje mają ograniczony rozmiar, po prostu wykonaj iterację; to usunie pamięć podręczną).

Każda lokalizacja znajduje się w co najwyżej jednej komórce, więc możesz przechowywać identyfikator komórki każdej lokalizacji na głównej mapie.

Korzystając z algorytmu wypełniania zalewem, utwórz również zmienną, która będzie zwiększać się przy każdym zaznaczonym kafelku, więc jeśli jest wyższa niż 35 (7 * 5, maksymalny rozmiar pokoju), to po prostu przestaje sprawdzać!