Znajdowanie niezakończonych płytek w grze opartej na kafelkach

Pracuję nad grą opartą na kafelkach 2D, a teraz staram się uzyskać 2d równowartość woluminów cienia. Mam problem ze znalezieniem powierzchni, które powinny rzucać cienie. Z dowolnego miejsca w grze muszę znaleźć albo niezamknięte twarze, albo całą płytkę.

Moje pytanie brzmi: czy mogę znaleźć te płytki / krawędzie tak szybko, jak to możliwe, biorąc pod uwagę punkt?

W społeczności roguelike wiele pracy poświęcono temu problemowi.

Oto strona z listą niektórych algorytmów i bibliotek, które mogą ci pomóc. http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

To nie jest pełna odpowiedź, ale mam nadzieję, że pomoże.

Czy twoja mapa / kafelek jest ustawiony statycznie czy dynamicznie? Jeśli jest statyczny, zdecydowanie zachęcam do przetwarzania offline i wstępnego obliczania tak dużo, jak to możliwe. Możesz to zrobić w dowolny sposób (raycasting lub coś mądrzejszego), ale tak naprawdę nie zależy ci na robieniu bardzo szybko, ponieważ wszystko to stanie się offline, gdy „upiec” swoje poziomy. Możesz albo dokładnie obliczyć, które kafelki są widoczne z każdego miejsca, albo utworzyć jakiś większy region i wszystkie kafelki potencjalnie widoczne z każdego regionu.

Następnie w czasie wykonywania zapytanie o widoczne kafelki powinno być bardzo proste i bardzo szybkie.

Oczywiście, jeśli masz dynamicznie tworzone poziomy, nie ma to w ogóle zastosowania :-)

Możesz zobaczyć, jak zaimplementowałem to dla roguelike C # tutaj . Kod nie jest wysoce zoptymalizowany, ale wydaje mi się, że jest wystarczająco szybki i (co ważniejsze) powinien być dość łatwy do odczytania. Zasadniczo robi prosty algorytm rzucania cienia, który działa po jednym oktanie na raz.

Nie jestem pewien, na jakiej platformie się znajdujesz, ale tak naprawdę nie mogę wymyślić żadnej platformy, która nie byłaby wystarczająco szybka, aby po prostu rozwinąć krąg wokół twoich podmiotów emitujących światło (chyba że jest ich dużo) i wykryć, czy kafelek, który ma zostać „wykreślony” w algorytmie koła, jest kafelkiem stałym, a zatem blokuje światło. Odtąd będzie to nieco trudniejsze, ponieważ będziesz musiał śledzić segmenty koła, które są zatkane lub nie, ale tak właśnie zrobiłbym. Inną opcją byłoby rzucanie promieni w kółko (ponownie dość szybko) w przestrzeni rozdzielczości kafelków i zatrzymywanie każdego promienia, gdy trafi on w solidny kafelek.