Obecnie używam algorytmu liniowego Bresenhama dla linii wzroku. Problem polega na tym, że znalazłem przypadek, w którym gracze mogą patrzeć przez ściany. Występuje, gdy gracz patrzy między dwoma rogami ściany ze szczeliną po drugiej stronie pod określonymi kątami.
Chcę, aby kafelek między dwiema ścianami został oznaczony jako nieprawidłowy.
Jaki jest najszybszy sposób modyfikacji algorytmu linii Bresenhama, aby rozwiązać ten problem? Jeśli nie ma dobrego rozwiązania, czy istnieje lepszy algorytm? Wszelkie pomysły są mile widziane. Pamiętaj, że rozwiązanie powinno także obsługiwać technologię 3d.
Edycja: Moim prostym rozwiązaniem było sprawdzenie, czy oba rogi są zamknięte, gdy zmienią się współrzędne xiy linii. Działający kod źródłowy i interaktywne demo ukończonego produktu można znaleźć na stronie http://ashblue.github.io/javascript-pathfinding/
źródło
Odpowiedzi:
Eric Lippert napisał doskonałą serię na temat generowania linii wzroku w C # z rzucaniem cienia na prostokątnej planecie planszowej.
Między innymi Eric zajął się różnymi pytaniami, na które należy odpowiedzieć na temat wymagań dotyczących pola widzenia, które dają różne wyniki i podają przykłady kilku różnych wyników. Jeden z artykułów dotyczy dogłębnie okoliczności „rozglądania się za rogiem”, która pojawiła się we wczesnej wersji jego algorytmu.
Mam dostosowany algorytm Erica do heksagonalnej siatki tutaj , i to z powodzeniem stosowany na dużych siatek sześciokątnych (> 400 x 700) z rozbudowaną promieniu widoczności (> 60 heksów). Ta implementacja oblicza i wyświetla pełne pole widzenia tak szybko, jak mogę mrugać, za pomocą jednego procesora i7. Jest to z pewnością wystarczająco szybki dla wszelkich zastosowań, których spodziewam się położyć.
Aktualizacja - Linia wzroku z wysokością:
Implementacja siatki sześciokątnej połączona z powyższym oblicza linię wzroku z wysokością, a nie tylko przeszkodami. Uwagi do dokumentacji omawiają również dodatkową decyzję, która musi zostać podjęta w odniesieniu do obliczeń wysokości: Wysokość docelowa i wysokość obserwatora. Domyślnym wyborem jest wyrównywanie obu, co tworzy symetryczne pole widzenia, ale można również wybrać widok ziemia-ziemia i oczy obserwatora-ziemia. (Kod jest Open Source na licencji MIT)
źródło
Co jeśli do obliczeń LOS masz oddzielną siatkę „wyższej rozdzielczości”, która wypełnia luki w rogach. Myślałem o czymś takim:
Po lewej stronie znajduje się oryginalna blokowa sekcja 4 kwadratów.
Po prawej jest wersja „wysokiej rozdzielczości”, ponieważ widać, że każdy oryginalny kwadrat został podzielony na ćwiartki, a jeden z rogów został wypełniony. Nie jestem pewien, czy algorytm wygenerował to, ale można go wstępnie obliczyć z bieżącej mapy.
Oznacza to, że przestrzeń współrzędnych jest czterokrotnie, ale nie przewiduję, że będzie to istotny problem z wydajnością.
źródło
0.5
dla komórek o wysokiej rozdzielczości, które mają być wypełnione lub nie. Tak więc używanie siatki wysokiej rozdzielczości wydaje mi się dość hackerskie.