Raycasting

Co jakiś czas nachodzi mnie ochota na nieco kreatywnego kodowania, aby odbić się od monotonii pracy. Czuć było od jakiegoś czasu, że taki okres nadchodzi. Wzięła mnie chęć na ponowne wynajdowanie koła. ;)

W wolnych chwilach przeglądałem zasoby Internetu w poszukiwaniu materiałów na temat sposobu działania wczesnych silników 3D (dokładniejszym określeniem może będzie jednak 2,5D).

Oczywiście najsławniejszym prekursorem tej technologii był John Carmack i głównie w kierunku stworzonych przez niego gier skierowałem swoje poszukiwania.
Co prawda już przed jego pomysłami istniała koncepcja gier w 3D, jednak dopiero od Wolfenstein 3D i później Doom nastąpił rozkwit tego gatunku. Więc nawet mimo tego, że John Carmack być może wcale nie był pierwszy (moja wiedza może mieć dziury), to jego wkład w rozwój tych technologii jest niezaprzeczalny. Tak samo, jak chociażby Ken Silverman, który już miał przetarte szlaki, jednak jego silnik Build3D także sporo namieszał na rynku.

Tak więc idea powstała - chcę stworzyć własny silnik 3D.

Silnik Wolfenstein'a jest pod tym względem o tyle ciekawy, że nie jest to 3D. Gra wydana w 1992 roku. Procesory 486, to wciąż w miarę świeży produkt. Pod tym względem był to piękny okres dla programistów. Ograniczona moc obliczeniowa oznaczała, że kreatywność jest najważniejsza. I właśnie takim kreatywnym rozwiązaniem był silnik gry opierający się na technice Raycasting'u.

Mapy poziomów, to dwuwymiarowy widok "z góry”. Analogię można sprowadzić do kartki w kratkę, w której zamalowujemy poszczególne kratki. Krawędzie zamalowanych kratek, to ściany poziomu. Gdy zamalowanymi kratkami otoczymy jakiś obszar, uzyskujemy poziom, po którym można się przemieszczać.

Kawałek magii, który zamalowaną kartkę papieru potrafi zmienić w wiarygodny widok 3D, to właśnie Raycasting.

Kropka na powyższym rysunku oznacza pozycję gracza. Kratki zamalowane, to ściany. Czerwona linia, wskazuje kierunek, na który jest skierowany wzrok postaci. Linie niebieskie tworzą tzw. "Field of View”, czyli obszar, który będzie widoczny na ekranie. Każda z tych 3 linii, to właśnie "promień” wysłany z pozycji gracza, którego zadaniem jest zmierzyć odległość do najbliższej ściany. Promienie zaznaczone na niebiesko są skrajnymi krawędziami tworzonego obrazu. Pomiędzy nimi znajduje się określona ilość promieni, z których stworzony jest następnie obraz 3D. Ich ilość równa jest ilości kolumn pikseli generowanego obrazu. W ten sposób każdy promień, to informacja do wyświetlenia jednej kolumny pikseli w generowanym widoku. Dzięki posiadanej informacji o odległości do najbliższej ściany możliwe jest na jej podstawie narysowanie linii o określonej wysokości. Grupa takich linii narysowana z kolejnych promieni tworzy efekt ściany z symulacją perspektywy.

Tyle teorii, teraz rezultaty. Kodowanie tego algorytmu było ciekawym doświadczeniem. Proste obliczenie odległości okazało się dosyć złożonym algorytmem, gdzie drobne pomyłki w implementacji dawały dosyć komiczne rezultaty:

Po znalezieniu i poprawieniu usterek na szczęście zaczęło to już przypominać oczekiwany rezultat:

Pojawił się jednak jeszcze jeden problem, ale dzięki wcześniejszej lekturze wiedziałem o tym, że wystąpi. W grze Wolfenstein3D, czy jakiekolwiek grze FPP, gdy ustawimy się przed ścianą, jest ona równa na całej szerokości ekranu. Jednak efekt uzyskany przeze mnie był inny:

Efekt podobny do tych, które można uzyskać w fotografii za pomocą obiektywu FishEye.
Przyczyną jest różna długość promieni docierających od pozycji gracza do ściany w zależności od ich kąta, pod którym są skierowane.

Czerwona linia, to kierunek, w którym skierowany jest wzrok gracza. Jest to także faktyczna odległość od tej ściany. Jednak pozostałe promienie, które do ściany docierają pod coraz mniejszym kątem, mają do przebycia dłuższą drogę, przez co symulowana perspektywa prawidłowo ścianę w kolejnych kolumnach zmniejsza, aby oddać tą zmianę odległości. Prosta naprawa tego "błędu”, to ustalenie kąta pomiędzy liczonym promieniem, a kierunkiem patrzenia (czerwona linia) i pomnożenie obliczonej odległości przez cosinus tego kąta. Efektem będzie obliczenie dla wszystkich promieni znajdujących się pomiędzy skrajnymi niebieskimi takiej samej odległości od ściany, jak dla promienia oznaczonego na czerwono.

Rezultat:

Na koniec pierwszego dnia mierzenia się z silnikiem uzyskany efekt jest całkiem zadowalający. Można się już dowolnie przemieszczać po załadowanej mapie. Jeśli wkrótce pojawi się kolejny dzień pozwalający na zabawę, dodana zostanie obsługa tekstur ścian i przy pomyślnych wiatrach być może także sufitu/podłogi (materiały przeczytane, ale jeszcze nie do końca przetrawione). Potrzebna będzie także obsługa kolizji ze ścianami, aby skończyć z efektem ducha.
Jeśli uda się zrealizować ten plan, będę chciał zamknąć ten projekt poprzez utworzenie jakiejś formy gameplay'u z możliwością wczytywania map i dołączyć edytor poziomów. Na razie nie planuję wprowadzania przeciwników i sztucznej inteligencji (celem tego projektu jest stworzenie silnika 3D, a nie FPS'a), więc potencjalny gameplay będzie opierał się bardziej na jakiejś formie próby przejścia labiryntu.

Co dalej?

Gdy uda się zamknąć ten pomysł, następny pojedynek zapewne stoczę z kolejnym flagowym produktem ID Software, czyli Doom. Zanim zacząłem dogłębnie zapoznawać się z tymi produktami "od kuchni”, sądziłem, że był on niewielkim krokiem naprzód w porównaniu do Wolfenstein 3D. Na pierwszy rzut oka wydaje się, że zyskaliśmy tylko teksturę i możliwość zmiany wysokości podłogi/sufitu, oraz większą dowolność w kształtowaniu ścian. Jednak zmiany są dużo dalej idące, co w zasadzie oznacza pisanie silnika zupełnie od nowa. Trzeba będzie w końcu zacząć zapoznawać się z BSP ;)

Program do ściągnięcia: Wilk v.0.2

Sterowanie klasyczne: strzałki, shift, alt.