NukeBoards

Kursy - [TGF] Kolizja płaskim detektorem
BROO - 18-04-2007, 23:47
: Temat postu: [TGF] Kolizja płaskim detektorem
Celem kursu jest zapoznanie się z najbardziej podstawowymi sposobami obsługi detektora poszukującego przeszkody na drodze.

Dokładna detekcja kolizji jest bardzo istotnym elementem podczas budowy silnika gry (na przykład dokładna detekcja, czy skacząca postać właśnie wylądowała na gruncie). Możemy bez większych oporów nauczyć postać przemieszczać się z bardzo dużą prędkością, na przykład 100 pikseli na jedną pętlę TGF - co przekłada się na 5000 pikseli na sekundę!

Problemy mogą pojawić się, kiedy będziemy chcieli zaaplikować taką dokładną detekcję na przykład wszystkim pociskom wystrzeliwanym przez gracza. A może chcemy również zbudować ruch platformowy dla przeciwników poruszanych dzięki sztucznej inteligencji? Może ich pociski również będą musiały latać dość szybko i dokładnie? Wtedy już mówimy nie o jednym, lecz o ponad stu obiektach aktywnych, każdy poruszający się z prędkością osiągającą na przykład 40 pikseli! Gra może wtedy zwalniać - w takim przypadku potrzebujemy optymalizować silnik.

Zestaw danych
Mechanizm wykonania przesunięcia z detekcją kolizji potrzebuje następujących elementów:
:arrow: przemieszczenia do wykonania (licznik "dy")
:arrow: obiektu Fast Loop (Fast Loop Object "FL")
:arrow: obiektu aktywnego symulującego postać w ruchu platformowym (OA "G")
:arrow: obiektu detektora kolizji (OA "det")

Do obejrzenia źródła gry odsyłam do dołączonego pliku źródłowego: http://www.republika.pl/tymczasownik/kpd.zip

Słowem wstępu
Teraz przejdź do oglądania kodu źródłowego. Pierwsze zdarzenie służy wyborowi rodzaju detekcji, jaki chcesz sprawdzić (po prostu wybierz grupę zdarzeń do uaktywnienia). Drugie zdarzenie służy do ustalania prędkości kulki w danej chwili (grawitacja przyspiesza kulkę).

A teraz czas na omówienie poszczególnych detekcji.

FL G & det (1px)
Jest to metoda dokładnego sprawdzania, piksela po pikseli, czy jest przeszkoda poniżej. Działa to w ten sposób:

Kod:
1. Zawsze
-> Uruchom pętlę #1 na tyle kroków, o ile pikseli trzeba się przemieścić
2. Na pętlę #1
-> Przemieść obiekt DET o pikselę w dół
-> Przemieść obiekt G o pikselę w dół
3. Na pętlę #1
+ jeżeli detektor zderzył się z tłem
-> Podnieś obiekt DET o pikselę do góry
-> Ustaw pozycję obiektu G na pozycję DET
-> Zakończ działanie pętli #1


Jeżeli prędkość wynosi 6, to Fast Loop wykona maksymalnie 6 kroków pętli. Podczas tych kroków maksymalnie 12+2 (+2 jeśli za ostatnim przemieszczeniem w dół napotka na przeszkodę) przemieszczenia jakichś obiektów, a także sprawdzi warunek nakładania się maksymalnie 6 razy.
Prędkości 'α' odopowiada:
:arrow: maksymalnie α kroków pętli
:arrow: maksymalnie 2α+2 przemieszczeń obiektów
:arrow: maksymalnie α sprawdzeń nakładania

Te liczby nie napawają optymizmem, spróbujmy coś poprawić...

FL det (1px)
Czy dostrzegasz, iż w edytorze zdarzeń obiekt "G" nie bierze czynnego udziału? Jest on tylko przesuwany tu i ówdzie. Należy to wykorzystać, że on nas nie interesuje. Oto poprawka:

Kod:
1. Zawsze
-> Uruchom pętlę #1 na tyle kroków, o ile pikseli trzeba się przemieścić
2. Na pętlę #1
-> Przemieść obiekt DET o pikselę w dół
3. Na pętlę #1
+ jeżeli detektor zderzył się z tłem
-> Podnieś obiekt DET o pikselę do góry
-> Zakończ działanie pętli #1
4. Zawsze
-> Ustaw pozycję obiektu G na pozycję DET


Przecież my w ogóle nie potrzebujesz nawet ruszać tego obiektu "G" Gracza podczas dokładnej detekcji kolizji! Dopiero, kiedy jesteś pewien ostatecznego położenia gracza, możesz przesunąć jego pozycję tam, gdzie należy. Dla TGF to właściwie wszystko jeden wysiłek, czy chcesz przesunąć obiekt o jedną pikselę, czy o 10 pikseli.

Tak jak w poprzednim przypadku, czas na bilans... Prędkości 'α' odopowiada:
:arrow: maksymalnie α kroków pętli
:arrow: maksymalnie α+2 przemieszczeń obiektów
:arrow: maksymalnie α sprawdzeń nakładania

Przemieszczenia obiektów: jeśli masz do czynienia z przemieszczeniem o 6 pikseli, to najmniej optymistyczny scenariusz przewiduje 8 przemieszczeń: 6 przemieszczeń DET w dół, jeden w górę (gdy przy ostatnim przemieszczeniu natrafi na ląd) oraz zawsze wykonywane przemieszczenie "G" na pozycję, jaką powinien zajmować. Więc jest mniej operacji - świetnie! Ale, czy możemy jeszcze przyspieszyć? Spróbujmy...

FL G & det 2x (-1px)
Jeżeli ustawisz sobie grubość detektora na 2 piksele, to masz pewność, że gdybyś przesuwał detektor o 2 piksele, to na pewno nie umknie jego uwadze żadna, choćby najcieńsza bariera. Czemu? Bo jest za gruby!

Czas na omówienie kolejnego sposobu. Uważaj! W tym przykładzie wartość licznika DY będzie zerowana przez proces przemieszczenia się.

Kod:
1. Zawsze
-> Uruchom pętlę #1 na tyle kroków, o ile pikseli trzeba się przemieścić
2. Na pętlę #1
-> Przemieść obiekt G o 2 piksele w dół
-> Przemieść obiekt DET o 2 piksele w dół
-> Odejmij od licznika DY wartość 2
3. Na pętlę #1
+ jeżeli detektor zderzył się z tłem
-> Zakończ działanie pętli #1
4. Na pętlę #1
+ Wartość licznika DY < 2
-> Ustaw pozycję obiektu G na Poz("G") + Wartość("DY")
-> Ustaw pozycję obiektu DET na Poz("DET") + Wartość("DY")
-> Zakończ działanie pętli #1
5. jeżeli detektor zderzył się z tłem
-> Podnieś obiekt DET o pikselę do góry
-> Ustaw pozycję obiektu G na pozycję DET
6. jeżeli detektor zderzył się z tłem
-> Podnieś obiekt DET o pikselę do góry
-> Ustaw pozycję obiektu G na pozycję DET


Dziwne rozwiązanie? Na pierwszy rzut oka wygląda na szybsze, niż detekcja piksela po pikseli. Jeżeli chcesz się przemieścić o 7 pikseli, to będzie to wyglądało tak:
:arrow: DY = 7 -> przesuń się o 2px w dół -> Ustaw DY na 5
:arrow: DY = 5 -> przesuń się o 2px w dół -> Ustaw DY na 3
:arrow: DY = 3 -> przesuń się o 2px w dół -> Ustaw DY na 1
:arrow: DY = 1 < 2 -> koniec pętli -> Teraz wykonają się zdarzenia (5 i 6), które odpowiadają za ewentualne wynurzanie się z tła.

Teraz się zastanawiasz może, dlaczego, skoro jeden krok pętli przesuwa o 2px... dlaczego liczba kroków pętli jest równa liczbie pikseli do przesunięcia, a nie liczbie dwa razy mniejszej?! Cóż, żadna różnica, pętla i tak zostanie wyłączona ręcznie przed wykonaniem ostatniego kroku.

Bilans... Prędkości 'α' odopowiada:
:arrow: maksymalnie (α/2)+1 = β kroków pętli
:arrow: maksymalnie 2*(β+2) = α+6 przemieszczeń obiektów
:arrow: maksymalnie (β+2) = α+3 sprawdzeń nakładania

Ale trzeba wprowadzić poprawkę tak, jak na początku porównywane przykłady...

FL det 2x (-1px)
Nie będę omawiał go, ponieważ różnice są analogiczne, jak w przypadku dwóch pierwszych sposobów przemieszczeń.

Bilans... Prędkości 'α' odopowiada:
:arrow: maksymalnie (α/2)+1 = β kroków pętli
:arrow: maksymalnie (β+2)+1 = α/2+4 przemieszczeń obiektów
:arrow: maksymalnie (β+2) = α/2+3 sprawdzeń nakładania

Współczynnik przy α wynosi tylko 1/2 w przypadku przemieszczania! Od razu lepiej. Może pójdziesz dalej? To da się jeszcze przyspieszyć.

FL G & det 4x (-1px)
Tutaj działanie jest analogiczne do przypadku przesuwania po dwie piksele, jednak trochę inaczej rozwiązana jest ostateczna korekta "wynurzania się z gruntu"

Kod:
1. Zawsze
-> Uruchom pętlę #1 na tyle kroków, o ile pikseli trzeba się przemieścić
2. Na pętlę #1
-> Przemieść obiekt G o 4 piksele w dół
-> Przemieść obiekt DET o 4 piksele w dół
-> Odejmij od licznika DY wartość 4
3. Na pętlę #1
+ jeżeli detektor zderzył się z tłem
-> Zakończ działanie pętli #1
-> Uruchom pętlę #2 na 4 kroki
4. Na pętlę #1
+ Wartość licznika DY < 4
-> Ustaw pozycję obiektu G na Poz("G") + Wartość("DY")
-> Ustaw pozycję obiektu DET na Poz("DET") + Wartość("DY")
-> Zakończ działanie pętli #1
-> Uruchom pętlę #2 na Wartość("DY") kroki (bo na tyle pikseli mógł się max zapaść)
5. Na pętlę #1 jeżeli detektor zderzył się z tłem
-> Podnieś obiekt DET o pikselę do góry
-> Ustaw pozycję obiektu G na pozycję DET


Bilans... Prędkości 'α' odopowiada:
:arrow: maksymalnie (α/4)+4 kroków pętli
:arrow: maksymalnie 2* ((α/4)+4) = α/2+8 przemieszczeń obiektów
:arrow: maksymalnie (α/4)+4 sprawdzeń nakładania

Oraz wersja z poprawkami:

FL det 4x (-1px)

Bilans... Prędkości 'α' odopowiada:
:arrow: maksymalnie (α/4)+4 kroków pętli
:arrow: maksymalnie (α/4)+5 przemieszczeń obiektów
:arrow: maksymalnie (α/4)+4 sprawdzeń nakładania

Współczynnik przy alfa wynosi 1/4! To bardzo niewiele, przy dużych przemieszczeniach na pewno takie rozwiązanie jest lepsze, niż poprzednie, bo ilość operacji do wykonania rośnie wolniej.

FL G & det 12x (-1px)
Jest dokładnie analogiczny do przypadku FL G & det 4x (-1px)...

Bilans... Prędkości 'α' odopowiada:
:arrow: maksymalnie (α/12)+12 kroków pętli
:arrow: maksymalnie 2* ((α/12)+12) = α/6+24 przemieszczeń obiektów
:arrow: maksymalnie (α/12)+12 sprawdzeń nakładania

Oraz wersja poprawiona...

FL det 12x (-1px)

Bilans... Prędkości 'α' odopowiada:
:arrow: maksymalnie (α/12)+12 kroków pętli
:arrow: maksymalnie (α/12)+13 przemieszczeń obiektów
:arrow: maksymalnie (α/12)+12 sprawdzeń nakładania

Współczynnik przy α wynosi tylko 1/12, ale co z tego, gdy liczba kroków pętli tak czy siak będzie duża, nawet dla małych przemieszczeń? To rozwiązanie jest dobre tylko wtedy, gdy chodzi o naprawdę duże przemieszczenia obiektów (i oczywiście te obiekty są grube na 12 pikseli, bądź przeszkody są tak grube, bądź jedno i drugie jest dość grube, wiesz o co chodzi, na przykład detektor 7px oraz ląd 5px jest już nieprzenikalny bo 7+5=12px grubości)

Wyniki badań
Sucha teoria... te liczby naprawdę nic nie mówią. Teraz to, co jest naprawdę przydatne, czyli wykres, który pokaże, ile to czasu naprawdę trwa.

http://www.republika.pl/t...ab_detekcja.gif


Wnioski

Widać, że dla małych przemieszczeń najlepsze są metody przesuwu o 1px, a dla większych kolejno: 2px, 4px i 12px. To chyba daje do myślenia? Na moim komputerze (P3 666) osiągnięcie wartości 80 przekłada się na 1,6 sekundy oczekiwania, na przesunięcie 1000 obiektów! Czyli zawieszka kompa gwarantowana. Gdyby było 100 takich obiektów, to 0,16 sekundy oczekiwania zamiast 0,02 sekundy pętli TGF powoduje, że gra zwalnia ośmiokrotnie! Posiadacze szybszych komputerów też mogą poczuć różnicę, więc tym bardziej zachęcam do optymalizacji!


18 IV 2007 21:43
BROO