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

W kolejnej, ósmej już części tego kursu, zaczniemy uczyć bohaterów niezależnych czegoś o otaczającym ich świecie. Poznamy metody pozwalające kierować postać przez labirynty. Posłuży nam do tego algorytm wyszukiwania ścieżek A-Star.

Reprezentacja mapy

Graf, po którego krawędziach poruszają się postacie, jest najczęściej spotykaną reprezentacją dostępności terenu. Stosowany jest w grach do dnia dzisiejszego. Niewątpliwą zaletą takiej reprezentacji jest prostota i niskie zapotrzebowanie na zasoby.

Graf nawigacyjny w grze Gothic, źródło: Link

A-Star

A-Star to algorytm oparty na znanej metodzie Dijkstry, wykorzystywany w przypadkach, gdy możemy na grafie wprowadzić dodatkową miarę odległości (potraktowanie wierzchołków jako punktów w przestrzeni temu odpowiada).

Oznaczenia:

G - graf
s, e - wierzchołki: początkowy i końcowy
m(x,y) - odległość w przyjętej metryce, pomiędzy wierzchołkami x i y
d(x,y) - długość obecnie najkrótszej ścieżki, pomiędzy wierzchołkami x i y
h(x) - heurystyka, przybliżenie długości ścieżki, od wierzchołka x do wierzchołka końcowego*
*Spełnia zależność h(x) <= d(x,y) + h(y), czyli nie zawyża długości ścieżki. W przestrzeni euklidesowej można przyjąć, że h(x) = m(x,e).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Oznacz wszystkie wierzchołki grafu G jako nieodwiedzone
Nadaj wierzchołkowi startowemu s priorytet h(s)
 
Dopóki istnieje nieodwiedzony wierzchołek:
      Weź nieodwiedzony wierzchołek v o najniższym priorytecie      
      Jeżeli v = e:
            trasa została odnaleziona, zakończ algorytm.
    
      Dla każdego nieodwiedzonego sąsiada v' wierzchołka v powtórz:  
              oblicz koszt k = d(s, v) + m(v, v')          
              Jeżeli k < d(s, v'):
                    d(s, v') = k
                    nadaj wierzchołkowi v' priorytet k + h(v')
      
      Oznacz v jako odwiedzony

W poniższej aplikacji możemy zobaczyć, które węzły i w jakiej kolejności są odwiedzane przez algorytm:

Nanosząc powstały graf na mapkę w grze, damy postaciom możliwość poruszania się pomiędzy określonymi wierzchołkami grafu. Zauważmy jednak, że postać rzadko znajduje się na którymś z wierzchołków. Aby algorytm zadziałał, możemy dodać nową krawędź, łączącą postać z najbliższym dostępnym wierzchołkiem grafu.

Po zastosowaniu takiego rozwiązania postacie potrafiłyby co prawda poruszać się po świecie i (przy dobrze stworzonym grafie) ich trasy wyglądałyby przekonująco. Jednak informacja o terenie, niesiona przez taką strukturę, ogranicza się do pewnego zbioru odcinków. Gdyby coś stanęło na krawędzi grafu, wówczas postać musiałaby zostać oznaczona jako niedostępna i algorytm musiałby znaleźć inną trasę.

Postać mogłaby też się zatrzymać i czekać lub taranować przeszkodę. Byłoby to całkiem pożądane zachowanie, w przypadku wąskich korytarzy, lecz co, gdy coś zablokuje krawędź grafu w otwartej przestrzeni? Ponadto musimy jeszcze pamiętać o systemie sztucznej inteligencji, który musi sobie radzić z poruszaniem w trakcie dynamicznych sytuacji, np. walki.

W przypadku braku dokładniejszych informacji o terenie wokół postaci, często tworzy się ogromną liczbę dobrze rozmieszczonych wierzchołków grafu. Z punktu widzenia projektanta map, rozwiązanie takie wymaga sporego wysiłku. Od strony programistycznej, nawigację w dynamicznych sytuacjach można ratować za pomocą rzucania promieni na siatkę kolizyjną (swoiste "czułki" postaci). Pozwala to, w miarę dokładnie, poruszać się po terenie nieobjętym wierzchołkami grafu i unikać np. ścian. Może to jednak doprowadzić do sytuacji, w których postać nie będzie potrafiła wrócić do grafu w prosty sposób.

Rozwiązaniem będzie dostarczenie innego typu informacji. W tym celu użyjemy techniki siatek nawigacyjnych (NavMesh). Każdy, kto tworzył mody do nowszych gier, z pewnością już się z nią zetknął. Technika ta zaczęła być powszechnie stosowana stosunkowo niedawno z uwagi na skupienie głównego nurtu wokół polepszania grafiki i faktu, że rozwiązanie oparte o sam graf jakoś się sprawdzało.