Pole Widzenia: Jak Gracze NPC Naprawdę Cię Widzą

Widzenie świata przez pryzmat trójkątów

Nadaj grze postać z oczami i musisz odpowiadać na zadania geometryczne sześćdziesiąt razy na sekundę: które fragmenty mapy ten punkt widzi w danym momencie? Brute-force'owy sposób – rzucanie promieni do każdego piksela i sprawdzanie, co się z nich odbija – jest zdecydowanie zbyt wolny. Efektywnym rozwiązaniem jest cieniowanie: rzuca się promienie tylko do rogów przeszkód, sortuje się punkty uderzenia według kąta względem widza i łączy je w jeden wielokąt. Wszystko, co znajduje się wewnątrz tego wielokąta, jest widoczne; wszystko poza nim ukryte za ścianą.

Jest to ta sama rodzina algorytmów wykorzystywana w grach strategicznych w mechanice mgły wojny, latarniczych wiązkach w grach horrorowych i sprawdzaniach zasięgu wzroku, które sprawiają, że gry stealth działają: jeśli wielokąt zawierający pozycję gracza zawiera również pozycję strażnika, strażnik zasadniczo może widzieć gracza.

Dlaczego rogi, a nie piksele

Poligon widzialności jest w pełni zdefiniowany przez rogi każdego obiektu na scenie, oraz przez dwa promienie wychodzące od najbardziej zewnętrznych krawędzi każdej sylwetki. Dla każdego rogu, promień emitowany przez obserwatora albo dokładnie zatrzymuje się w tym rogu (niczego dalej w tym kierunku nie jest widoczne), albo przechodzi dalej, aż uderzy w inny obiekt. Zatem algorytm rzuca jeden promień bezpośrednio na każdy rog oraz dwa dodatkowe promienie pod kątem odchylenia po obu stronach, aby złapać cienką warstwę przestrzeni otwierającą się tuż za krawędzią:

dla każdego rogu obiektu c: rzut promień pod kątem(c) - epsilon rzut promień pod kątem(c) rzut promień pod kątem(c) + epsilon posortuj wszystkie punkty uderzenia według kąta połącz je w kolejności → poligon widzialności Sortowanie po kącie wokół NPC przekształca rozrzucone przecięcia promieni/ścian w jedną, spójną formę. Użyj sortowania 'fan-sort' punktów uderzenia, przejdź wokół nich raz, a każda para kolejnych punktów plus obserwator tworzy jeden trójkąt poligonu – narysuj wszystkie trójkąty jako wypełnioną figurę i otrzymasz jasną, świetlistą część, którą widzi gracz, z ostrymi krawędziami cieni dokładnie w rogach przeszkód.

for each obstacle corner c:
  cast ray at angle(c) - epsilon
  cast ray at angle(c)
  cast ray at angle(c) + epsilon
sort all hit points by angle
connect them in order  →  visibility polygon

Dodawanie konika widzenia i zasięgu

Pełny poligon widzialności 360° modeluje wszechwidzące sensory; rzeczywistych NPC patrzą w jedną stronę z ograniczonym konikiem i maksymalną odległością widzenia. Obie to tanie dodatki: przycinaj promienie rzucane do kątów wewnątrz [orientacja - fov/2, orientacja + fov/2], a ogranicz każdą długość promienia do zasięgu wzroku, traktując samą granicę zasięgu jako krzywą "barierę", której łuk wypełnia się dodatkowymi promieniami, aby poligon widzialności zamykał się płynnie zamiast kończyć ostre krawędzi.

visible = angle_in_fov(target, npc.facing, npc.fovAngle)
       and distance(npc.pos, target) < npc.sightRange
       and not blocked_by_any_obstacle(npc.pos, target)

Od geometrii do rozgrywki

Po uzyskaniu poligonu widzialności, mechanika ukrywania się niemalże wypada bez problemów. Test punktu w poligonie informuje, czy gracz jest aktualnie widoczny. Gromadzenie czasu spędzonego wewnątrz konwoli przed wyzwoleniem pełnego stanu czujności (zamiast natychmiastowego wykrycia) sprawia, że przemierzanie obok strażnika wydaje się sprawiedliwe, a nie arbitralne – większość granych na zasadach ukrywania się wykorzystuje wskaźnik podejrzeń, który wypełnia się podczas przebywania gracza wewnątrz poligonu i wypala się, gdy opuszcza go.

Ten sam poligon widzialności może napędzać również propagację dźwięku i światła: blask latarki, promień hałasu wystrzału przeciętego z zasięgu wzroku lub obracający się konweksja kamery bezpieczeństwa – wszystkie to identyczne obliczenia rzucania cieni z różnymi promieniami, zakresem i częstotliwością aktualizacji.

Uwagi dotyczące wydajności

Dla sceny z *n* narożnikami przeszkód algorytm sortuj i usuń (sort-and-sweep) powyżej działa w czasie O(n log n) na każde zapytanie, dominując tym samym sortowanie kątów – wystarczająco szybko, aby ponownie obliczać każdy klatkę dla kilkudziesięciu NPC względem kilkuset segmentów ścian, co dokładnie robi symulacja na tej stronie z prostokątnymi przeszkodami, które można przeciągnąć i zmienić rozmiar. W dużych grach otwarttych zamiast tego statyczna struktura widzialności jest prekomputowana raz (podwójny graf nawigacyjny, lub podział poziomu na portale/komórki) i uruchamiane są tylko per-frame promienie czystego dla ruchomych przeszkód, ponieważ ponowne sortowanie tysięcy narożników sześćdziesiąt razy na sekundę dla każdego strażnika rzeczywiście się sumuje.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Field of View i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.