Tworzenie gry w C# z użyciem silnika Ogre - cz.8

28.10.2011 - Mateusz Osowski
TrudnośćTrudność

Siatki nawigacyjne

Oprócz dokładnej powierzchni terenu, siatki nawigacyjne mogą zawierać informacje o strefach taktycznych, obszarach, w których postać może się przeczołgać niezauważona etc.

Z fragmentami powierzchni możemy wiązać różne dodatkowe dane. W przypadku pojawienia się przeszkód w terenie, ich uwzględnienie w siatce nawigacyjnej można sprowadzić do usunięcia z siatki fragmentu obszaru zajmowanego przez przeszkodę. Stworzenie siatek nawigacyjnych jest przede wszystkim bardzo proste - dla większości obszaru możemy użyć modelu jeszcze prostszego od siatki kolizyjnej (skopiować geometrię podłoża i po prostu usunąć zbędne wierzchołki).

Technika siatek nawigacyjnych, ogólnie rzecz ujmując, polega na zastąpieniu wierzchołków grafu całymi wielokątami wypukłymi. W naszej implementacji ograniczymy się do uniwersalnych wielokątów wypukłych - trójkątów. W dalszym ciągu przydatny będzie algorytm A-Star. Ponieważ jedyną informacją, jaką będziemy czerpać z siatki, będzie ukształtowanie terenu, naszym edytorem może być dowolny program do modelowania siatek 3D, np. Blender.

Proces znajdowania ścieżki na siatce nawigacyjnej podzielimy na dwa etapy:

1. Wyznaczanie trójkątów trasy
Po ustaleniu, w którym z trójkątów znajduje się postać i punkt docelowy, do akcji wkroczy algorytm A-Star. W wyniku jego działania dostaniemy ścieżkę - ciąg trójkątów.

2. Wyznaczanie najkrótszej ścieżki na łańcuchu trójkątów
Sam łańcuch trójkątów nie determinuje dobrej ścieżki, gdyż pojawia się pytanie: którędy poprowadzić trasę? Po środkach trójkątów? Po środkach krawędzi łączących kolejne trójkąty? Nie. Znając punkt wyjściowy i końcowy, użyjemy algorytmu, który można nazwać lejkowym, z uwagi na sposób jego działania. Algorytm ten znajdzie najkrótszą ścieżkę w przestrzeni wyznaczonych trójkątów. W wyniku dostaniemy ciąg punktów, które postać będzie musiała odwiedzić.

Podstawy teoretyczne

Algorytm lejkowy

Jest to bardzo prosty algorytm, który pozwala nam wyszukać punkty najkrótszej ścieżki, przy zadanej trasie "wyższego rzędu". Jako dane wejściowe algorytm ten przyjmuje punkt startowy i ciąg tzw. portali (w naszym przypadku portalami będą krawędzie łączące kolejne trójkąty).

Algorytm lejkowy polega na odnajdywaniu pierwszego portalu, który nie będzie już widziany z punktu startowego, patrząc przez wszystkie poprzednie portale. Po znalezieniu takiego portalu, nowym punktem startowym staje się pierwszy punkt, z którego ten portal jest widoczny. Procedura ta jest powtarzana, dopóki nie będzie widoczny ostatni portal.

Oznaczenia:

S - punkt startowy
pL(i), pR(i) - lewy i prawy wierzchołek i-tego portalu
n - liczba portali
A - aktualny punkt, z którego szukamy pierwszego niewidocznego portalu
L, R - wierzchołki wyznaczające (wraz z A) aktualnie najwęższy kąt widoczności (kąt L-A-R)
Li, Ri - indeksy portali, które jako ostatnie zawężały kąt L-A-R (z lewej i prawej strony)

Przetwarzając i-ty portal, możemy kąt L-A-R zwężać, ustalając nowe L lub R na podstawie wierzchołków portalu. Jeżeli zaś i-ty portal już nie znajduje się w zasięgu tego kąta (jest już niewidoczny z punktu A przez poprzednie portale), wówczas, w zależności od strony po której ten i-ty portal zniknął, dodajemy aktualne L lub R do ścieżki wynikowej. Przesuwamy A (punkt, z którego patrzymy) w miejsce L lub R i resetujemy kąt widoczności. Następnie wracamy do szukania kolejnego, niewidocznego portalu, zaczynając od nowo ustalonego punktu A.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
i = 0
 
A = S
zresetuj kąty
 
dopóki i != n:
 
  jeśli 
  kąt jest zresetowany   
    lub    
  pL(i) leży na prawo od L względem A 
  (czyli nowy portal może zawężać kąt LAR, słowem kąt pL(i)-A-R jest mniejszy niż L-A-R):
    
      jeśli pL(i) leży na prawo od R względem A
      (czyli nowy portal jest jednak poza kątem LAR):
      
          dodaj do ścieżki punkt R
          i = Ri
          A = R
          zresetuj kąty
          pomiń krok pętli
        
      w przeciwnym wypadku
      (gdy  pL(i) faktycznie zawęża kąt, czyli jest pomiędzy L a R):
          L = pL(i)
          Li = i
        
        analogiczną czynność z uwzględnieniem odwrotnego 
        kierunku powtarzamy dla pR(i) przesuwamy iterator i.

Dla lepszego zrozumienia zasady działania tego algorytmu, przetestujmy go, wraz z A-Starem, na trójkątach w tej aplikacji:

Przejdźmy teraz do implementacji klas pomocniczych.


5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com