Autor Wątek: Optymalne podejście do wyświetlenia FOWa (Fog Of War'a)  (Przeczytany 4308 razy)

Offline Adam B

  • Użytkownik

# Maj 09, 2016, 22:14:33
Hej,

W projekcie, który właśnie robię zaimplementowałem FOWa.

Efekt można zobaczyć na:
http://supertowerdefence.pl/
+ wybrać obojętnie jaki zapis gry. np "map save" ma ponad 1200 obiektów to też można sprawdzić wydajność.


Na jaki problem natrafiłem?

Dla dużej ilości obiektów (np 1000) samo przygotowanie modelu dla renderowania FOWa zajmuje prawie połowę czasu modułu renderującego - zgroza:(

Jaka to u mnie działa:
 1) FOW to mapa z kafelków o rozdzielczości 40/40px,
 2) wartość kafelka 1 - rysuj maksymalnego FOW, wartość 0 - nie rysuj, wartości pomiędzy 0-1 to cieniowanie FOWa na krawędziach widoczności (taki mały bajer)
 3) dla każdego obiektu w team1 (czyli moje jednostki) nadaje dla kafelków FOWa (w zasięgu promienia widoczności) odpowiednie wartości od 0 do 1 - liczę to na zasadzie (kwadratu - żeby nie było pierwiastków) odległości kafelka do obiektu.
 4) dzięki takiemu podejściu jeżeli obiekt porusza się w obrębie jednego kafelka to FOW i tak jest przeliczany w zależności od dokładnej pozycji obiektu - dzięki temu na krawędziach jest "w miarę płynny" efekt cieniowania podczas poruszania się obiektów.
 5) co klatkę renderowania kasuje całego FOWa do wartości 1 i proces powtarzam od nowa.

Szukam pomysłów na optymalizację podejścia które zastosowałem, nawet przy zmniejszeniu jakości rozwiązania.

Jakie mam pomysły na optymalizację:
 1) liczyć efekt względem środka kwadratu FOWa, a nie względem pikseli,
 2) nie liczyć wartości dla kafelków FOWa w locie tylko przygotować tablice z wartościami w zależności od zasięgu widoczności - pewnie będzie kilka jednostek z kilkoma zasięgami widoczności więc danych do zapamiętania będzie mało. Takie preliczone tablice bym nanosił na kafelki FOWa, zamiast liczyć wszystko w locie.
 3) jeżeli dla danego kafelka FOWa dla takiej samej lub większej wartości "zasięgu widzenia" wartości FOWa zostały już ustalone (naniesione na mape FOWa) to przejść do kolejnego obiektu - powinno to znacznie poprawić wydajność kiedy dużo jednostek jest blisko siebie.
 4) aby zachować ładne cieniowanie renderer by animował moc FOWa - żeby były płynne przejścia w sensie jeżeli jest zmiana stanu z 1 na 0 (lub odwrotnie) to efekt jest płynny, ale dba o to już inny moduł + podpiąć to do eventu "onChangeFOWValue" aby animować tylko te kafelki, które tej animacji potrzebują.
 5) dla dużych map można zapamiętywać, które kafelki wymagają zresetowania FOWa, aby nie resetować całej mapy bo to nie ma sensu.

Dodatkowo myślę nad innymi optymalizacjami, jednocześnie nie mam przekonania czy nie będzie to powodowało pogorszenia wydajności:
 - przetrzymywanie informacji ile jest do granicy widzialności, z każdej ze stron lub do najbliższej granicy i jeżeli więcej niż to co ma widzieć aktualny obiekt to też go pomijać..

Nie wiem czy moje podejście jest w ogólne dobre - może istnieją jakieś lepsze, o których nie pomyślałem?
Trochę przybijające jak prosty efekt typu FOW zajmuje dla dużej ilości obiektów znaczny czas przygotowania modelu dla renderera.. :(

Pozdrawiam,
Adam

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Adam B

  • Użytkownik

# Maj 10, 2016, 00:37:54
Po wprowadzeniu optymalizacji:

1) liczyć efekt względem środka kwadratu FOWa, a nie względem pikseli,
2) nie liczyć wartości dla kafelków FOWa w locie tylko przygotować tablice z wartościami w zależności od zasięgu widoczności - pewnie będzie kilka jednostek z kilkoma zasięgami widoczności więc danych do zapamiętania będzie mało. Takie preliczone tablice bym nanosił na kafelki FOWa, zamiast liczyć wszystko w locie.

Nie uzyskałem zauważalnej róznicy +/-1-2% wydajności - więc nic.

W środku funkcji przypisującej wartości do kafelka jest jeszcze sprawdzenie czy dany index kafelka istnieje (Math.min i Math.max) moze to sprawdzenie dużo kosztuje - potestuje.


Podsumowanie:
Na teraz wychodzi, że same obliczenia nie są kosztowne - problemem jest ilość operacji na całej mapie FOW. Bardzo dużo obiektów działa na tych samych kafelkach wpisując do nich wartość 0 - czyli kafelek widoczny..

Nowa myśl:
Moze duzo lepszym podejściem będzie dodanie eventu dla obiektu typu: "onTileChange" i aktualizowanie mapy FOWa przez obiekt po takim evencie? Nawet jak zaznaczę 1000 obiektów i wszystkie będą się poruszać to event dla pojedynczego obiektu będzie się średnio wywoływał raz na kilka/kilkanaście klatek więc teoretycznie powinien być duży zysk wydajności..

Problemem w tym podejściu może okazać się jednak większa podatność na błędy - no ale z tym trzeba się jakoś uporać.

EDIT:
W tym podejściu mapa FOW by miała inne wartości: 0 - niewidoczny kafelek, 1 i więcej - widoczny. Jeżeli kafelka by była w zasięgu widzenia 10 obiektów to miała by wartość 10.
« Ostatnia zmiana: Maj 10, 2016, 00:41:42 wysłana przez Adam B »

Offline koirat

  • Użytkownik

# Maj 10, 2016, 11:30:40
Sprawdzasz FOW co frame ?

Offline Adam B

  • Użytkownik

# Maj 10, 2016, 15:27:46
tak

Offline lethern

  • Użytkownik

# Maj 10, 2016, 16:46:10
Myślę że możesz połączyć oba rozwiązania - to znaczy wyliczanie FOW z położenia obiektu (nie z środka kawelka) jak i liczenie FOW *rzadziej* niż co klatkę, np. 5 razy na sekundę - dla mechaniki jak i człowieka to powinno wystarczyć (chyba że masz jednostkę, która porusza się szybciej niż 5 kafli na sekundę) - no... do przemyślenia

Przy okazji.. jak jest w innych grach? wydaje mi się, że FOW jest pewną mapą, która aktualizuje się przy poruszaniu jednostki, gdzie jestem skłonny uwierzyć, że
1) sprawdza się czy jednostka odkryła nowy teren, jeśli tak to ten teren się dodaje do "widocznego"
2) rzadko sprawdza się czy jakiś teren nie jest już widoczny (jednostka zginęła, odsunęła się itd.), w starcraft2 wydaje mi się, że teren "znika" gdzieś dopiero po 2 sekundach
3) troche kombinowane, ale może da się określić: jednostka znajduje się w "zasięgu" widoczności większej niż ona sama daje, więc można ją pominąc z obliczeń (może jakiś algorytm "otoczki wypukłej" na zbiorze jednostek będzie mniej kosztowny niż obecne podejście - chociaż ta "otoczka" może nie być wypełniona w środku :D)
« Ostatnia zmiana: Maj 10, 2016, 16:54:05 wysłana przez lethern »

Offline koirat

  • Użytkownik

# Maj 10, 2016, 20:39:13
Jeśli chcesz naprawdę szybko:

Tworzysz grida bitowego który zapisuje jaki teren jest odkryty (niekoniecznie aktualnie obserwowany przez jednostkę). Updatujesz tylko wtedy kiedy jednostka się ruszy. Nie koniecznie w każdym framie.
Stosujesz operator OR na tym gridzie i masce bitowej zasięgu widoku jednostki.

Kafelki sprawdzane czy są widziane przez jednostkę obliczasz jedynie dla kafelków widocznych na ekranie.

Dodatkowo stosujesz quad-tree z uwzględnieniem zasięgu wzroku jednostki żeby nie sprawdzać dla każdej jednostki czy widzi dany kafelek na ekranie.
« Ostatnia zmiana: Maj 10, 2016, 20:41:12 wysłana przez koirat »

Offline Adam B

  • Użytkownik

# Maj 10, 2016, 23:21:13
Jeśli chcesz naprawdę szybko:

Tworzysz grida bitowego który zapisuje jaki teren jest odkryty (niekoniecznie aktualnie obserwowany przez jednostkę). Updatujesz tylko wtedy kiedy jednostka się ruszy. Nie koniecznie w każdym framie.
Stosujesz operator OR na tym gridzie i masce bitowej zasięgu widoku jednostki.

Kafelki sprawdzane czy są widziane przez jednostkę obliczasz jedynie dla kafelków widocznych na ekranie.

Dodatkowo stosujesz quad-tree z uwzględnieniem zasięgu wzroku jednostki żeby nie sprawdzać dla każdej jednostki czy widzi dany kafelek na ekranie.

1) Czy grid bitowy czy oparty na intach - to nie ma roznicy za duzej.
2) A jak kafelka ma sprawdzac czy jest widoczna przez jednostke ? W czasie budowania struktury "prawdopodobnych" do sprawdzenia kolizji np. spatial hashing czy quad-tree musialbym do kafelka dodawać takie informacje - wydaje mi się, że nie różni się to od tego co teraz robie jakoś mocno.. sprawdzam jakie kafelki są w polu widzenia jednostek.

Generlanie to obiektu musza określać jakie kafelki są widoczne bo to obiekty mają "zasięg widzenia".
Myślę, że tu nie chodzi o optymalizacje tego co jest - bo ile wycisne ? 20% 50% zaoptymalizuje ? To dalej będzie za wolno... Bardziej potrzebna jest inna metoda..



Offline Adam B

  • Użytkownik

# Maj 10, 2016, 23:25:32
Myślę że możesz połączyć oba rozwiązania - to znaczy wyliczanie FOW z położenia obiektu (nie z środka kawelka) jak i liczenie FOW *rzadziej* niż co klatkę, np. 5 razy na sekundę - dla mechaniki jak i człowieka to powinno wystarczyć (chyba że masz jednostkę, która porusza się szybciej niż 5 kafli na sekundę) - no... do przemyślenia

Przy okazji.. jak jest w innych grach? wydaje mi się, że FOW jest pewną mapą, która aktualizuje się przy poruszaniu jednostki, gdzie jestem skłonny uwierzyć, że
1) sprawdza się czy jednostka odkryła nowy teren, jeśli tak to ten teren się dodaje do "widocznego"
2) rzadko sprawdza się czy jakiś teren nie jest już widoczny (jednostka zginęła, odsunęła się itd.), w starcraft2 wydaje mi się, że teren "znika" gdzieś dopiero po 2 sekundach
3) troche kombinowane, ale może da się określić: jednostka znajduje się w "zasięgu" widoczności większej niż ona sama daje, więc można ją pominąc z obliczeń (może jakiś algorytm "otoczki wypukłej" na zbiorze jednostek będzie mniej kosztowny niż obecne podejście - chociaż ta "otoczka" może nie być wypełniona w środku :D)

Sprawdzanie czy jednostka odkryła nowy teren bez kasowania tego co wcześniej było niczym się nie różni od wykasowania wszystkich informacji i zbudowania ich od nowa.  Przynajmniej nie widzę tutaj optymalizacji..

Rozbicie na kilka kroków - może powodować przycięcia.. Generalnie ogólnego rozbijania ze liczę po 10% i po 10 obliczeniach (klatkach/petlach logicznych) wyświetlam efekt chciałbym uniknąć.. To nie jest optymalizacja - to jest rozłożenie słabo działającego algorytmu jaki mam teraz w czasie.

Offline Adam B

  • Użytkownik

# Maj 11, 2016, 00:28:44
Zakładając, że:
N - ilość obiektów
M - ilość tilesów z jakiej składa się cała mapa (zakładam na teraz, że 15000 - kiedy mapa ma 5 ekranów wysokości i szerokości)
P - średnia ilość tilesów jaką widzi/odkrywa obiekt - okolo 81. (9x9 tilesów)

Teraz złożoność algorytmu to:
N * P co daje średnio 81N. Co dla 1000 obiektów daje wynik 81000 obliczeń.

Jeżeli obiekty widziały by obszar kwadratowy wymyśliłem algorytm w najgorszym przypadku o złożoności:
N+M co daje 16000 tysięcy obliczeń.

W przypadku lepszym (nie cała mapa jest odsłonięta) to:
N + "potencjalna ilość odsłoniętych kafelków" - powiedzmy w sumie z 5000 obliczeń.

Muszę zastanowić się jak to przełożyć kiedy kształtem widoczności jednostki jest okrąg, a nie kwadrat.
Jak coś wymyślę zaraportuję.

Offline koirat

  • Użytkownik

# Maj 11, 2016, 01:06:35
1) Czy grid bitowy czy oparty na intach - to nie ma roznicy za duzej.
Nie wiem w czym piszesz ale zazwyczaj ma (jak jest dobrze zrobione).

2) A jak kafelka ma sprawdzac czy jest widoczna przez jednostke ? W czasie budowania struktury "prawdopodobnych" do sprawdzenia kolizji np. spatial hashing czy quad-tree musialbym do kafelka dodawać takie informacje - wydaje mi się, że nie różni się to od tego co teraz robie jakoś mocno.. sprawdzam jakie kafelki są w polu widzenia jednostek.
Jednostki są zapisane w quad-tree (przynależność do quad tree zależy też od zasięgu widzenia jednostki), wiesz na jakie quad tree akurat patrzysz. Pobierasz wszystkie jednostki z tych quad tree. I teraz masz przykładowo takie opcje:

Albo dla każdej jednostki liczysz jakie komórki są obserwowane.
Albo dla każdej jeszcze nie obserwowanej komórki sprawdzasz czy nie jest ona obserwowana przez którąś z jednostek.


Generlanie to obiektu musza określać jakie kafelki są widoczne bo to obiekty mają "zasięg widzenia".
Myślę, że tu nie chodzi o optymalizacje tego co jest - bo ile wycisne ? 20% 50% zaoptymalizuje ? To dalej będzie za wolno... Bardziej potrzebna jest inna metoda..
Ale inna metoda na oszacowanie co jest obserwowane czy inna metoda na wyświetlenie FOW ?