Mam problemy z wydajnym określeniem, czy duże pokoje są szczelnie zamknięte w pokojach 3D opartych na wokselach. Jestem w punkcie, w którym starałem się jak najlepiej rozwiązać problem, nie prosząc o pomoc, ale nie starałem się wystarczająco zrezygnować, więc proszę o pomoc.
Aby wyjaśnić, zapieczętowany jest fakt, że w pokoju nie ma dziur. Istnieją uszczelniacze tlenowe, które sprawdzają, czy pomieszczenie jest uszczelnione, i uszczelniają w zależności od poziomu wejściowego tlenu.
Właśnie tak to robię:
- Zaczynając od bloku nad płytką uszczelniacza (otwór wentylacyjny znajduje się na górnej powierzchni uszczelniacza), rekurencyjnie wykonaj pętlę we wszystkich 6 sąsiednich kierunkach
- Jeśli sąsiadująca płytka jest pełną, nie próżniową płytką, przejdź przez pętlę
- Jeśli sąsiadująca płytka nie jest pełna lub jest płytką próżniową, sprawdź, czy sąsiednie bloki są rekurencyjne.
- Za każdym razem, gdy sprawdzany jest kafelek, zmniejsz licznik
- Jeśli liczba osiągnie zero, jeśli ostatni blok sąsiaduje z płytką próżniową, zwróć, że obszar jest otwarty
- Jeśli licznik osiągnie zero, a ostatni blok nie jest płytką próżniową lub pętla rekurencyjna kończy się (nie pozostały płytki próżniowe), zanim licznik wyzeruje, obszar jest zaplombowany
Jeśli obszar nie jest zamknięty, ponownie uruchom pętlę z pewnymi zmianami:
- Sprawdzanie sąsiadujących bloków pod kątem płytki „oddychającego powietrza” zamiast płytki próżniowej
- Zamiast używać licznika malejącego, kontynuuj, dopóki nie zostaną znalezione sąsiadujące płytki „oddychającego powietrza”.
- Po zakończeniu pętli ustaw każdy zaznaczony blok na płytkę próżniową.
Oto kod, którego używam: http://pastebin.com/NimyKncC
Problem:
Sprawdzam to co 3 sekundy, czasem uszczelniacz będzie musiał przejść przez setki bloków, a duży świat z wieloma uszczelniaczami tlenu, te wielokrotne pętle rekurencyjne co kilka sekund mogą być bardzo trudne dla procesora.
Zastanawiałem się, czy ktoś z większym doświadczeniem w optymalizacji może mi pomóc, a przynajmniej wskazać właściwy kierunek. Wielkie dzięki.
Odpowiedzi:
Najlepsze rozwiązanie będzie zależeć od wielu czynników, takich jak oczekiwana wielkość pokoju.
Podejście 1:
Możesz użyć A *, aby znaleźć ścieżkę od otworu wentylacyjnego do płytki powyżej otworu wentylacyjnego / samego otworu wentylacyjnego lub do płytki, która jest znana jako szczepionka. Jeśli ścieżka zostanie znaleziona, pokój jest rozszczelniony. Nie różni się to tak bardzo od obecnego podejścia, ale powinno być szybsze. Po znalezieniu zrób „wypełnienie zalewowe”, aby ustawić płytki jako próżnię.
Podejście 2:
Być może twoja zewnętrzna struktura jest mniej kompletna - biorąc pod uwagę, że istnieje powierzchnia, w której znajdują się pokoje, nie musisz poruszać się we wszystkich 6 kierunkach, więc powinieneś podróżować wzdłuż powierzchni, oznacz każdą płytkę jako próżnię, którą podróżujesz.
źródło
Czy podczas wyszukiwania rekurencyjnego upewniasz się, że nie sprawdzasz wielokrotnie tego samego woksela? Nie potrafię odróżnić od sposobu, w jaki opisałeś swój algorytm, ale powinieneś mieć jakąś flagę wskazującą, czy rekurencyjnie rozwinąłeś woksel, więc nie rób tego więcej niż raz.
I jak powiedział Byte56, powinieneś także sprawdzać, czy nie ma wycieków, gdy rzeczy się zmieniają. To może znacznie zminimalizować ilość pracy, którą wykonujesz, w zależności od częstotliwości zmian. Możliwe jest nawet buforowanie informacji między kolejnymi wywołaniami algorytmu, co może trywializować ilość obliczeń wykonanych po pierwszym wywołaniu.
Edytować:
Przejrzałem część twojego kodu. Wygląda na to, że używasz LinkedList, aby wskazać, czy woksel został już sprawdzony, jak w moim pierwszym akapicie. Możesz uzyskać lepsze wyniki, jeśli użyjesz do tego czegoś innego niż LinkedList. Może wypróbuj HashSet lub coś takiego? Powinno to zmniejszyć złożoność metody sprawdzania z O (n) do O (1).
źródło