Ukośna linia wzroku z dwoma rogami

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.

Skrzynia na brzegu linii wzroku

Chcę, aby kafelek między dwiema ścianami został oznaczony jako nieprawidłowy.

Pożądany rezultat

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/

— Ash Blue
źródło

Czy zmienia to punkt początkowy i końcowy? Może wtedy możesz zaakceptować wyniki, jeśli oba obliczenia zwrócą nie zasłoniętą linię wzroku. Możesz również znaleźć niektóre artykuły LOS pomocne w RogueBasin.

— thalador

Tak czy inaczej, te dwa czarne bloki po przekątnej 4-5 nie są w pierwszej kolejności połączone ze ścianą, i mówię to, ponieważ domyślnie zezwalasz na ruch po przekątnej. Musisz albo zaokrąglić tę przekątną, aby stała się ścianą sąsiadującą, albo sprawić, by liniał wyprostował się po przekątnych ruchów zamiast iść po przekątnej jak 2-3 i 4-5.

— Patrick Hughes

Przerzucenie go brzmiało jak dobry pomysł, ale nie rozwiązuje problemu. Jedyne, co mogę wymyślić, to sprawdzić i sprawdzić, czy jeden z dwóch rogów jest pusty. Wydaje się jednak drogi.

— Ash Blue

„Wydaje się kosztowne” nigdy nie jest wystarczającym uzasadnieniem, aby czegoś nie spróbować. „Będzie zbyt kosztowne” ogólnie, zakładając, że możesz udowodnić, że coś będzie zbyt wolne.

— Mokosha

Wymagana jest tylko zmiana wymaganego algorytmu, jeśli jeśli zarówno X, jak i Y zmieniają się w tym samym kroku, najpierw zmieniają X, a następnie zmieniają Y, to całkowicie wyeliminuje przekątne.

— Patrick Hughes

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)

— Pieter Geerkens
źródło

Naprawdę kopię Rzucanie Cieni, ale mam problem. Problem ze znalezieniem jakichkolwiek informacji na temat skalowania algorytmu do pracy z osią Z. Przepraszam, że o tym wspominam, ale czy masz jakieś sugerowane zasoby, dzięki którym będzie działać w 3D?

— Ash Blue

@AshBlue: patrz uzupełnienie powyżej

— Pieter Geerkens

Patrzę na twoją bazę kodów. Ma w sobie świetne rzeczy, ale nie wydaje mi się, aby algorytm rysowania linii podobny do Bresenhama był dostosowany do heksów. Czy robisz to z LOS?

— MLProgrammer-CiM

@EfEs: FieldOfView jest zwróconym obiektem; ShadowCastingFov * .cs generuje pole widzenia poprzez rzucanie cieni. Jeśli masz szczegółowe pytania dotyczące kodu, najlepiej zadać je w sekcji Dyskusje na stronie; bardziej ogólne pytania, z przyjemnością odpowiadam tutaj.

— Pieter Geerkens,

@PieterGeerkens Pytanie możesz znaleźć tutaj gamedev.stackexchange.com/questions/57087/…

— MLProgrammer-CiM

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:

wprowadź opis zdjęcia tutaj

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ą.

— Davy8
źródło

Jestem pewien, że wyższa rozdzielczość będzie wyglądać dokładnie tak samo jak oryginał. Dzieląc siatkę na mniejszą siatkę, uzyskujesz taką samą reprezentację wizualną, tylko z mniejszą siatką. Każdy pojedynczy kwadrat staje się tylko 4 mniejszymi kwadratami w tym samym miejscu.

— MichaelHouse

@ Byte56 Prawidłowo, miałem na myśli, że po podzieleniu zostanie zastosowana dodatkowa logika w celu dodania dodatkowych bloków do tej kopii. Logiką tego jest ćwiczenie pozostawione czytelnikowi.

— Davy8

Można łatwo wygenerować siatkę wysokiej rozdzielczości, rozmazując oryginał. Następnie określ próg, powiedzmy, 0.5dla 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.

— danijar