Jak szybko obliczyć obszar wzroku w grze w kafelkach 2D?

Mam matrycę płytek, na niektórych z nich są przedmioty. Chcę obliczyć, które kafelki są widoczne dla gracza, a które nie, i muszę to zrobić dość wydajnie (aby obliczało się wystarczająco szybko, nawet gdy mam duże matryce (100 x 100) i dużo obiektów).

Próbowałem to zrobić algorytmem liniowym Bresenhama , ale było to powolne. Dało mi to także kilka błędów:

----XXX-        ----X**-     ----XXX-
-@------        -@------     -@------
----XXX-        ----X**-     ----XXX-
(raw version)   (Besenham)   (correct, since tunnel walls are 
                              still visible at distance)

(@ is the player, X is obstacle, * is invisible, - is visible)

Jestem pewien, że da się to zrobić - w końcu mamy NetHack, Zangband i wszyscy jakoś poradzili sobie z tym problemem :)

Jaki algorytm możesz do tego polecić?

Na moje potrzeby zdefiniuję widoczny w następujący sposób: kafelek jest widoczny, gdy przynajmniej część (np. Narożnik) kafelka można połączyć ze środkiem płytki gracza za pomocą linii prostej, która nie przecina żadnej przeszkody.

Twoja definicja widocznego jest następująca:

płytka jest widoczna, gdy przynajmniej część (np. narożnik) płytki można połączyć ze środkiem płytki gracza za pomocą prostej linii, która nie przecina żadnej przeszkody

Możesz wdrożyć tę koncepcję dosłownie, śledząc promienie z kafelka gracza i przecinając je ze sceną. Zrywasz z każdej iteracji, gdy promień uderza w przeszkodę (lub przekracza określony próg odległości), ponieważ jesteś zainteresowany tylko kafelkami, które gracz może zobaczyć bezpośrednio. Podzielę dla ciebie proces:

1. Określ poziom precyzji, który chcesz nadać algorytmowi. Będzie to liczba promieni, które będziesz śledzić.
2. Podziel pełne koło 360 stopni przez wybraną precyzję, aby wiedzieć, o ile stopni ma się obracać między poszczególnymi promieniami.
3. Zaczynając od 0 stopni i zwiększając o wartość określoną w kroku 2, utwórz promień o początku na środku płytki gracza i kierunku określonym przez bieżący kąt.
4. Dla każdego promienia, zaczynając od płytki gracza, idź wzdłuż promienia, aż trafisz na płytkę przeszkody. Dodaj ten kafelek do widocznej listy kafelków i przejdź do następnego promienia. Możesz także dodać maksymalną odległość, aby „zrezygnować” w przypadku braku kolizji.

Oto zdjęcie przedstawiające 3 przykładowe promienie. Ciemniejsze płytki są „wynikiem” każdego promienia, tzn. Miejsca, w którym nastąpiło zderzenie. Powinieneś jednak powtórzyć to w kółko:

Dostosuj maksymalną odległość i liczbę promieni do wydajności. Za mało, a za dużo tęsknisz za płytkami, a wydajność spadnie. Ponadto, im bardziej promienie muszą się przemieszczać, tym większy będzie „błąd” i tym większa precyzja będzie potrzebna.

Edytować

Sprawdź następujący samouczek dotyczący raycastingu, w szczególności krok 3 i krok 4, aby pomóc Ci zaimplementować bit skrzyżowania algorytmu:

http://www.permadi.com/tutorial/raycast/rayc7.html

Wolałbym rzucać promienie cienia zamiast linii promieni wzroku.

Powiedzmy, że jest to obszar widoku (obszar potencjalnie widoczny)

######################
#####.............####
###................###
##..................##
#....................#
#....................#
#..........@.........#
#....................#
#....................#
##..................##
###................###
#####.............####
######################

# Bloki nie są widoczne, podczas gdy. są widoczne

Połóżmy przeszkodę X:

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXXX...........#
##..................##
###....X...........###
#####.............####
######################

Masz listę X, które znajdują się w obszarze widoku, a następnie zaznaczasz jako ukryty każdy kafelek za każdą z tych przeszkód: gdy przeszkoda jest oznaczona jako ukryta, usuwasz ją z listy.

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXX*...........#
##......##..........##
###....*#..........###
#####.###.........####
######################

W powyższym przykładzie widać cień rzucony przez skrajną prawą dolną ścianę oraz sposób, w jaki cień ten usuwa ukrytą przeszkodę z listy przeszkód, które musisz sprawdzić (X musi sprawdzić; * zaznaczony).

Jeśli posortujesz listę za pomocą partycji binarnej, aby najpierw sprawdzić X najbliższego X, możesz nieznacznie przyspieszyć sprawdzanie.

Możesz użyć pewnego rodzaju algorytmu „bitew morskich”, aby sprawdzić blok Xs jednocześnie (w zasadzie szukając adiacent X, który jest w kierunku, który może poszerzyć stożek cienia)

[EDYTOWAĆ]

Aby poprawnie rzucić cień, potrzebne są dwa promienie, a ponieważ płytka jest prostokątna, można założyć wiele założeń przy użyciu dostępnych symetrii.

Współrzędne promienia można obliczyć za pomocą prostej przestrzeni dzielącej się wokół płytki przeszkody:

Każdy prostokątny obszar stanowi wybór tego, który z narożników płytki należy traktować jako krawędź stożka cienia.

Rozumowanie to można dalej wykorzystać, aby połączyć wiele sąsiadujących ze sobą płytek i pozwolić im rzucić jeden szerszy stożek w następujący sposób.

Pierwszym krokiem jest upewnienie się, że żadne przeszkody nie są skierowane w stronę obserwatora, w takim przypadku zamiast tego rozważana jest najbliższa przeszkoda:

Jeśli żółta płytka jest przeszkodą, płytka staje się nową czerwoną płytką.

Teraz rozważmy górną krawędź stożka:

Niebieskie płytki są potencjalnymi kandydatami do poszerzenia stożka cienia: jeśli co najmniej jedna z nich jest przeszkodą, promień można przesunąć za pomocą przestrzeni rozdzielającej wokół tej płytki, jak pokazano wcześniej.

Zielona płytka jest kandydatem tylko wtedy, gdy obserwator znajduje się powyżej pomarańczowej linii, która następuje:

To samo oznacza drugi promień i inne pozycje obserwatora dotyczące czerwonej przeszkody.

Podstawową ideą jest objęcie jak największej powierzchni dla każdego rzutu stożka i jak najszybsze skrócenie listy przeszkód do sprawdzenia.

Problem, który próbujesz rozwiązać, nazywa się czasem Field of View, w skrócie FOV. Jak wspomniałeś jako roguelikes, powinieneś rzucić okiem na to, co wiki RogueBasin ma do powiedzenia na ten temat (są nawet linki do implementacji): http://www.roguebasin.com/index.php?title=Field_of_Vision

Istnieje kilka różnych algorytmów o różnych zaletach i wadach - bardzo przydatne porównanie jest dostępne również w RogueBasin: http://www.roguebasin.com/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds

Znalazłem też to, które ma działającą wersję demo:

http://www.redblobgames.com/articles/visibility/

Http://blogs.msdn.com/b/ericlippert/archive/2011/12/12/shadowcasting-in-c-part-one.aspx może się przydać wraz z resztą serii .