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.
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.
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ć.
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.
Dla uproszczenia, siatki nawigacyjne wczytywać będziemy z plików modeli o formacie Wavefront OBJ. Blender posiada możliwość eksportowania siatek do takich plików. Nie zawierają one wielokątów innych niż trójkąty ani wektorów normalnych i współrzędnych mapowania tekstury. A więc mamy tu same wierzchołki i trójkąty.
Plik w formacie, który będziemy wczytywać, wyglądać może tak:
1 2 3 4 5 6 7 | v -1.545366 -0.900851 3.587488 v 0.156301 -0.900851 3.879202 v 1.979517 -0.900851 3.976441 v 3.632565 -0.900851 4.195228 f 1 2 3 f 1 3 4 |
Na początku pliku pojawiają się pozycje wierzchołków poprzedzone literą v, a następnie informacje o trójkątach - trzy indeksy wierzchołków, licząc od 1, poprzedzone literą f.
Implementowany przez nas algorytm będzie działać tylko w dwóch wymiarach, a konkretnie na płaszczyźnie XZ. Ponieważ często będziemy odmierzać kąty między wektorami w tej przestrzeni, stwórzmy prostą pomocniczą klasę statyczną. Zawierać będzie ona metody przyjmujące wektory 3D, lecz zwracające wynik operacji (na tychże wektorach) na płaszczyźnie XZ:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | class Op2D { public static Vector3 XZ = new Vector3(1,0,1); public static float Cross(Vector3 a, Vector3 b) { Vector3 axz = (a * XZ).NormalisedCopy; Vector3 bxz = (b * XZ).NormalisedCopy; return new Vector2(axz.x, axz.z).CrossProduct(new Vector2(bxz.x, bxz.z)); } public static float TriArea(Vector3 a, Vector3 b) { return 0.5f * (a * XZ).CrossProduct(b * XZ).Length; } public static float Dist(Vector3 a, Vector3 b) { return ((a * XZ) - (b* XZ)).Length; } } |
Siatka będzie się składać z trójkątów, ale przydatne dla nas będą także informacje o krawędziach. Stworzymy więc, dla trójkąta i krawędzi, osobne struktury:
1 2 3 4 5 6 7 | public class NavMesh { public class Edge { public Vector3 A, B; public List<Triangle> Triangles = new List<Triangle>(); } |
Krawędź, oprócz swoich wierzchołków, przechowywać będzie listę trójkątów. Dlaczego listę, a nie dwa trójkąty? Choćby dlatego, że w przypadku siatek nawigacyjnych nie musimy mówić o rozmaitościach.
Mogą istnieć krawędzie, które łączą trzy wielokąty. Przykładem są schody, pod które można wejść. Te trzy wielokąty to: schody, podłoga przed schodami i podłoga pod schodami. Zwróćmy uwagę na to, że względnie złożone geometrycznie obiekty (tu schody) reprezentować możemy w siatce nawigacyjnej jako pojedyncze prostokąty (2 trójkąty).
Trójkąt stanowią trzy krawędzie. Struktura trójkąta:
1 2 3 4 5 6 7 8 9 | public class Triangle { public Edge U, V, W; public float Area; public Vector3 Center; public bool IsVisited; public float Cost; public Triangle Previous; |
Jest to mała klasa, która jest ściśle związana z klasą NavMesh, dlatego możemy uczynić ją wewnętrzną klasą w NavMesh. U,V,W to krawędzie tworzące trójkąt. Posługujemy się referencjami, aby krawędzie były współdzielone przez sąsiadujące trójkąty. Pola Center, IsVisited, Cost i Previous są bezpośrednio związane z algorytmem A-Star.
W trakcie jego wykonywania, Cost będzie przechowywać aktualny, najmniejszy koszt dotarcia (najkrótszą trasę), od punktu startowego do środka trójkąta. Zaś pole Previous to referencja na poprzedni, w najkrótszej trasie, trójkąt. Przy określaniu, czy punkt należy do trójkąta, będzie nam potrzebna znajomość pola trójkąta.
Jedna z najprostszych (niekoniecznie najszybsza) metod sprawdzania, czy punkt należy do trójkąta, to obliczenie sumy pól trzech trójkątów, powstałych w wyniku połączenia każdej z krawędzi badanego trójkąta z punktem:
Jeżeli suma pól tych trójkątów (A,B i C) jest większa, niż pole rozpatrywanego trójkąta, punkt z pewnością do niego nie należy. W przeciwnym przypadku - należy (co widzimy na rysunku).
Oto implementacja takiego prostego sprawdzenia:
1 2 3 4 5 6 7 8 9 10 | public bool IsPointInside(Vector3 pt) { float area = 0; area += Op2D.TriArea(U.A - pt, U.B - pt); area += Op2D.TriArea(V.A - pt, V.B - pt); area += Op2D.TriArea(W.A - pt, W.B - pt); if (area > Area * 1.001f) return false; return true; } |
Biorąc pod uwagę możliwość wystąpienia błędów numerycznych, porównujemy sumę pól z epsilonowo większą wartością.
Pole trójkąta, a przy okazji jego środek, obliczać będzie następująca metoda:
1 2 3 4 5 6 | public void CalcArea() { Center = (U.A+U.B + V.A+V.B + W.A+W.B) / 6.0f; Area = Op2D.TriArea(U.B - U.A, V.B - V.A); } } |
W linii nr 3 zapisu tej metody wliczamy oba końce każdej z krawędzi, ponieważ nie znamy kolejności wierzchołków krawędzi, a chcemy mieć pewność, że wszystkie wierzchołki uwzględnimy podczas obliczania średniej.
Zakończyliśmy implementację klasy Triangle. Możemy teraz kontynuować implementację klasy NavMesh.
Wierzchołki, krawędzie i trójkąty będziemy przechowywać w następujących kolekcjach:
1 2 3 | public List<Vector3> Vertices = new List<Vector3>(); public List<Edge> Edges = new List<Edge>(); public List<Triangle> Triangles = new List<Triangle>(); |
Dodajmy również funkcję, dodającą krawędź do siatki:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | public Edge AddEdge(Vector3 a, Vector3 b) { Edge edge = Edges.Find(e => e.A == a && e.B == b || e.A == b && e.B == a); if (edge != null) return edge; else { edge = new Edge(); edge.A = a; edge.B = b; Edges.Add(edge); return edge; } } |
Ponieważ listę krawędzi będziemy chcieli stworzyć podczas wczytywania pliku siatki, a kolejność wierzchołków tych krawędzi może być różna, tworzymy funkcję, która nie doda do kolekcji krawędzi odwróconych, ponadto zwróci referencję na nowoutworzoną lub znalezioną, istniejącą krawędź. Tymi referencjami wypełnimy pola obiektu trójkąta.
Wczytywanie danych z pliku:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public void LoadFromOBJ(string fname) { string[] lines = File.ReadAllLines(fname); string[] tokens; for (int i = 0; i < lines.Length; i++) { if (lines[i][0] == 'v') { tokens = lines[i].Split(' '); Vector3 vertex = new Vector3(); vertex.x = Single.Parse(tokens[1], System.Globalization.CultureInfo.InvariantCulture); vertex.y = Single.Parse(tokens[2], System.Globalization.CultureInfo.InvariantCulture); vertex.z = Single.Parse(tokens[3], System.Globalization.CultureInfo.InvariantCulture); Vertices.Add(vertex); } |
Platforma .NET zapewnia nam możliwość łatwego wczytania linii z pliku jako tablicy stringów. Jeżeli pierwszą literą linii jest v, rozdzielamy linię na listę słów względem spacji, a następnie parsujemy słowa (drugie, trzecie i czwarte jako float). Następnie dodajemy wierzchołek do listy. By uprościć kod, nie sprawdzamy poprawności i liczby słów po literze "v". Zakładamy, że pliki generowane automatycznie przez eksportery są poprawne.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | else if (lines[i][0] == 'f') { tokens = lines[i].Split(' '); int v1 = Int32.Parse(tokens[1]) - 1; int v2 = Int32.Parse(tokens[2]) - 1; int v3 = Int32.Parse(tokens[3]) - 1; Triangle tri = new Triangle(); tri.U = AddEdge(Vertices[v1], Vertices[v2]); tri.V = AddEdge(Vertices[v2], Vertices[v3]); tri.W = AddEdge(Vertices[v3], Vertices[v1]); tri.U.Triangles.Add(tri); tri.V.Triangles.Add(tri); tri.W.Triangles.Add(tri); Triangles.Add(tri); tri.CalcArea(); } } } |
W przypadku litery f na początku linii, odczytujemy trzy liczby całkowite, będące indeksami wierzchołków tworzących trójkąt, numerując od 1. Używamy wcześniej napisanej metody AddEdge do odnalezienia lub utworzenia nowych obiektów krawędzi i "informujemy" te krawędzie o nowym trójkącie. Tak jak w przypadku wierzchołka - nie sprawdzamy poprawności danych; zakładamy, że każdy wielokąt jest trójkątem i nie jest z nim związany żaden wektor normalny ani współrzędne mapowania tekstur.
W algorytmie A-Star węzłom grafu - w naszym przypadku mówimy o trójkątach - nadajemy priorytet w oparciu o odległość dzielącą je od punktu końcowego. W każdym przebiegu pętli wybieramy do przetwarzania węzeł o najniższym priorytecie. Naturalną strukturą do takiego zastosowania jest tzw. kolejka priorytetowa, często implementowana jako kopiec albo tablica list elementów o danym priorytecie. Platforma .NET nie dostarcza nam takiej struktury, więc musimy sami ją zaimplementować. Użyjemy w tym celu kopca binarnego.
Ustalmy zasady:
Implementacja kolejki priorytetowej
Kolejka będzie typem generycznym. Choć priorytet ma z góry zadany typ float, uogólnienie typu elementu nie skomplikuje, a wręcz skróci kod. Tablica będzie listą par priorytet-element. Często będziemy zamieniać elementy miejscami, dlatego też implementujemy metodę Swap().
1 2 3 4 5 6 7 8 9 10 | public class PriorityQueue<E> { List<Pair<float, E>> Tree = new List<Pair<float, E>>(); public void Swap(int i, int j) { Pair<float, E> tmp = Tree[i]; Tree[i] = Tree[j]; Tree[j] = tmp; } |
Dodanie elementu do kolejki:
1 2 3 4 5 6 7 8 9 10 | public void Push(float p, E e) { Tree.Add(new Pair<float, E>(p, e)); int i = Tree.Count - 1; while (i != 0 && Tree[i/2].first > Tree[i].first) { Swap(i, i/2); i /= 2; } } |
Operacja dodawania polega na dorzuceniu elementu na koniec tablicy. Wówczas staje się on ostatnim liściem na najniższym poziomie drzewa. Następnie przywracamy porządek kopca, wypychając element ku wyższym poziomom drzewa, dopóki nie dotrze on w miejsce korzenia lub jego rodzic będzie miał niższy priorytet (zgodnie z zasadami).
Operacja Pop() ma zwracać element o najniższym priorytecie (zgodnie z zasadami jest to korzeń drzewa i posiada indeks 0) i usuwać go z kopca. Na początku zapamiętujemy element. Następnie zamieniamy go z ostatnim liściem w drzewie i ucinamy ten liść skracając tablicę. Musimy też przywrócić porządek kopca, ponieważ ostatni liść, który zwykle ma duży priorytet, wskoczył na miejsce usuniętego korzenia. Robimy to, spychając ten element w dół drzewa, tak długo, aż wszystkie jego dzieci będą miały wyższe priorytety (co jest też trywialnie spełnione, gdy element stanie się liściem). W którą stronę spychamy element? W stronę dziecka o niższym priorytecie, ponieważ stanie się ono rodzicem swojego obecnego brata.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | public E Pop() { E popped = Tree[0].second; Swap(0, Tree.Count - 1); Tree.RemoveAt(Tree.Count -1); int i = 0; while (true) { int lower = i; if (i*2 < Tree.Count && Tree[i*2].first < Tree[lower].first) lower = i * 2; if (i*2+1 < Tree.Count && Tree[i*2+1].first < Tree[lower].first) lower = i * 2 + 1; if (lower != i) { Swap(i, lower); i = lower; } else break; } return popped; } |
Przydadzą się nam dodatkowe, pomocnicze operacje:
1 2 3 4 5 6 7 8 9 10 | public void Clear() { Tree.Clear(); } public bool IsEmpty() { return Tree.Count == 0; } } |
Przyszedł moment, w którym zajmiemy się implementacją algorytmu A-Star. Będzie on operować na następujących obiektach:
1 2 3 | PriorityQueue<Triangle> SearchQueue = new PriorityQueue<Triangle>(); public List<Triangle> TriPath = new List<Triangle>(); public Vector3 StartPt, EndPt; |
Są to pola klasy NavMesh. Zastosowanie kolejki już omówiliśmy. TriPath będzie przechowywać uzyskaną przez A-Star ścieżkę trójkątów.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | public void AStar(Vector3 start, Vector3 end) { StartPt = start; EndPt = end; Triangle startTri = Triangles.Find(tri => tri.IsPointInside(start)); Triangle endTri = Triangles.Find(tri => tri.IsPointInside(end)); if (startTri == null || endTri == null) { return; } Triangles.ForEach(tri => tri.IsVisited = false); Triangles.ForEach(tri => tri.Cost = 0); SearchQueue.Clear(); TriPath.Clear(); if (startTri == null || endTri == null) return; SearchQueue.Push((start - end).Length, startTri); |
Implementację zaczynamy od wyszukania dwóch trójkątów, w których znajdują się punkt startowy i punkt docelowy. Następnie czyścimy flagę odwiedzenia i długość aktualnej trasy wszystkich trójkątów. W przypadku, gdy któryś z punktów znajduje się poza siatką, przerywamy wykonywanie algorytmu. W przyszłości, gdy taka możliwość będzie mogła przypadkowo zaistnieć (np. po wprowadzeniu eksplozji, która może wyrzucić obiekty w miejsca nieobjęte siatką), można będzie wyszukać trójkąty najbliższe tym punktom. Najlepiej jednak zapobiegać takim sytuacjom, tworząc siatkę w sposób staranny.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | while (!SearchQueue.IsEmpty()) { Triangle currTri = SearchQueue.Pop(); if (currTri == endTri) { while (currTri != startTri) { TriPath.Insert(0, currTri); currTri = currTri.Previous; } TriPath.Insert(0, startTri); break; } if (currTri.IsVisited) continue; currTri.IsVisited = true; |
Omówmy teraz główną pętlę algorytmu. Wybieramy trójkąt o najniższym priorytecie. Jeśli jest to trójkąt końcowy, to znaczy, że trafiliśmy do celu i posiadamy już optymalną trasę, którą odtwarzamy cofając się do trójkąta startowego po polach Previous. Jeżeli to nie jest trójkąt końcowy, ale został już odwiedzony (trójkąt mógł trafić na kolejkę już wcześniej, z niższym priorytetem, gdyż mogła znaleźć się do niego trasa krótsza), to pomijamy go. W każdym innym przypadku, oznaczamy go jako odwiedzony i przechodzimy do analizy jego sąsiadów:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | foreach (Triangle neighbour in currTri.U.Triangles.Concat(currTri.V.Triangles.Concat(currTri.W.Triangles))) { if (neighbour.IsVisited) continue; float nCost = currTri.Cost + (neighbour.Center - currTri.Center).Length; if (nCost < neighbour.Cost || neighbour.Cost == 0) { neighbour.Cost = nCost; neighbour.Previous = currTri; SearchQueue.Push(nCost + (end - neighbour.Center).Length, neighbour); } } } } |
Listę wszystkich sąsiadów otrzymujemy konkatenując ze sobą listy trójkątów dzielących trzy krawędzie aktualnie odwiedzanego trójkąta. Pomijamy już odwiedzonych sąsiadów (na listę odwiedzonych sąsiadów trafi m.in. trójkąt currTri, który został oznaczony jako odwiedzony). W wierszu nr 5 obliczamy koszt dotarcia do sąsiada przez aktualnie przetwarzany trójkąt.
Warto zauważyć, że koszt podróży między sąsiednim trójkątami określamy jako odległość między ich środkami ciężkości. Jest to jedna z możliwości, inną jest na przykład obliczanie odległości między środkami krawędzi. Dlatego też uzyskana przez algorytm trasa będzie optymalna, ale przy założeniu, że poruszamy się przez środki trójkątów. Nie jest to dużym problemem, ponieważ na ogół, przy dobrej siatce będzie to trasa bliska optymalnej. Gorsze przypadki możemy usprawiedliwić tym, że ludzie nie zawsze przemieszczają się w sposób optymalny.
Gdy koszt dotarcia do sąsiada przez trójkąt currTri okaże się lepszy, niż ostatnio obliczony, lub jest to pierwsza obliczona trasa, zastępujemy informację sąsiada, a jego Previous zaczyna wskazywać na currTri.
Sąsiad trafia do kolejki z priorytetem, będącym przybliżonym kosztem całkowitym trasy prowadzącej przez niego (kosztem trasy dotarcia do niego przez trójkąt currTri, w sumie z odległością od jego środka, do punktu końcowego). Dzięki temu algorytm chętniej przegląda trójkąty przybliżające go do celu, co pozwala uniknąć przeglądania sporej części siatki.
To już jest A-Star w całej okazałości. Dostarcza nam listę trójkątów najkrótszej trasy, jednak trzeba mieć na uwadze to, że rozkład trójkątów w siatce ma duże znaczenie, ponieważ od niego zależy pozycja środków trójkątów. Następny algorytm zajmie się odnalezieniem nakrótszej trasy wewnątrz otrzymanego ciągu trójkątów. Tym razem dostaniemy już ciąg punktów.
Zanim zaczniemy szukać ścieżki, musimy wydobyć krawędzie łączące kolejne trójkąty. Będziemy je przechowywać w takiej oto liście:
1 | public List<Pair<Vector3, Vector3>> Portals = new List<Pair<Vector3, Vector3>>(); |
Nie będziemy trzymać referencji na obiekty krawędzi (Edge), ponieważ w algorytmie lejkowym ma znaczenie kolejność wierzchołków krawędzi, tzn. musimy wiedzieć, który jest lewy, a który prawy względem obecnej pozycji. Ustalanie tego, na podstawie danych z obiektu Edge wewnątrz głównej pętli algorytmu, skomplikowałoby kod.
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 | public void GetPortals() { Portals.Clear(); for (int i = 0; i < TriPath.Count - 1; i++) { Pair<Vector3, Vector3> portal = new Pair<Vector3, Vector3>(); if (TriPath[i].U == TriPath[i+1].U || TriPath[i].U == TriPath[i+1].V || TriPath[i].U == TriPath[i+1].W) portal = new Pair<Vector3, Vector3>(TriPath[i].U.A, TriPath[i].U.B); else if (TriPath[i].V == TriPath[i+1].U || TriPath[i].V == TriPath[i+1].V || TriPath[i].V == TriPath[i+1].W) portal = new Pair<Vector3, Vector3>(TriPath[i].V.A, TriPath[i].V.B); else portal = new Pair<Vector3, Vector3>(TriPath[i].W.A, TriPath[i].W.B); if (Op2D.Cross(portal.first - TriPath[i].Center, portal.second - TriPath[i].Center) < 0) { Vector3 tmp = portal.first; portal.first = portal.second; portal.second = tmp; } Portals.Add(portal); } Portals.Add(new Pair<Vector3,Vector3>(EndPt, EndPt)); } |
Ta metoda wydobywa krawędzie łączące kolejne trójkąty i dodaje je do listy portali, nadając wierzchołkom odpowiednią kolejność. Posiadamy tylko listę trójkątów, ale wiedząc, że każde dwa kolejne z nich są sąsiadami, możemy określić ich wspólną krawędź. Sprawdzamy prawie wszystkie możliwości.
Po ustaleniu wspólnej krawędzi sprawdzamy, po której stronie pierwszego wierzchołka względem środka trójkąta znajduje się drugi wierzchołek. Chcemy aby pierwszy był po lewej stronie, a drugi po prawej. Jeżeli jest na odwrót, tj. iloczyn wektorowy ma wartość ujemną, to zamieniamy wierzchołki miejscami.
Na końcu dodajemy specjalny portal, który w istocie jest punktem końcowym. Uprości to algorytm, ponieważ nie będziemy musieli rozważać specjalnego przypadku widoczności punktu końcowego - wystarczy, że widoczny jest ostatni portal.
1 2 3 4 5 6 7 8 | public List<Vector3> Funnel() { List<Vector3> path = new List<Vector3>(); Vector3 right, left, current; int rightId, leftId; right = left = current = StartPt; rightId = leftId = 0; |
Na początku ustalamy punkt startowy jako aktualny punkt tzw. widoku. Right i left będą wierzchołkami wyznaczającymi (wraz z punktem widoku) kąt widoczności portali. Jeżeli right lub left jest tym samym co punkt widoku, uznajemy go za jeszcze nie ustalony. Wraz z analizą kolejnych portali, kąt może ulec zawężeniu: rightId i leftId przechowują indeksy wierzchołków, które ostatnio zawężały kąt z prawej bądź lewej strony.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | for (int i = 0; i < Portals.Count; i++) { if (left == current || Op2D.Cross(left - current, Portals[i].first - current) >= 0) { if (Op2D.Cross(right - current, Portals[i].first - current) > 0) { path.Add(right); current = left = right; i = leftId = rightId; continue; } else { left = Portals[i].first; leftId = i; } } |
Analizujemy i-ty portal
1. Jeśli lewy wierzchołek kąta jest nieustalony, lub jeśli od tego wierzchołka do lewego końca portalu trzeba wykonać zwrot w prawo (nie w lewo, iloczyn wektorowy jest większy lub równy zeru), to znaczy, że ten portal może być jeszcze widoczny i zawęża kąt widzenia na następne portale swoim lewym wierzchołkiem. Upewniamy się, czy ten lewy wierzchołek portalu znajduje się wewnątrz kąta.
2. Jeżeli wierzchołek portalu leży na prawo od prawego wierzchołka kąta, to cały ten portal znajduje się poza zasięgiem "wzroku". Wówczas dodajemy do ścieżki prawy wierzchołek wyznaczający kąt, czyli ten, za którym "schował się" portal (gdybyśmy patrzyli z tego wierzchołka, to byśmy ten portal zobaczyli). Nowym punktem widoku zostaje więc prawy wierzchołek kąta. Same wierzchołki resetujemy i cofamy się w analizie do portalu, tuż za nowym punktem widoku.
3. Jeżeli lewy wierzchołek portalu znajduje się pomiędzy lewym a prawym wierzchołkiem kąta, to znaczy, że portal jest wciąż widoczny z aktualnego punktu widoku, lecz zawęża on nam widok na następne portale.
4. Jeżeli pierwszy warunek nie został spełniony, to znaczy, że lewy koniec portalu leży poza kątem widoczności, ale po jego lewej stronie. Możemy przejść do sprawdzania prawego wierzchołka:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | if (right == current || Op2D.Cross(right - current, Portals[i].second - current) <= 0) { if (Op2D.Cross(left - current, Portals[i].second - current) < 0) { path.Add(left); current = right = left; i = rightId = leftId; continue; } else { right = Portals[i].second; rightId = i; } } } path.Add(EndPt); return path; } |
Po czym dokonujemy podobnych sprawdzeń, tym razem patrząc na prawy wierzchołek portalu. Jeżeli algorytm dotrze do ostatniego portalu, kończy swoje działanie i zwraca ścieżkę.
Nasz nowy zestaw algorytmów przetestujemy skupiając się na natychmiastowych efektach, dopisując tymczasową gałąź do drzewa decyzyjnego postaci. Strukturę drzewa dotyczącą przemieszczania się postaci rozplanujemy lepiej w kolejnych częściach cyklu.
Dobrze jest umieć wykorzystywać dopiero co zaimplementowane części programu w miarę możliwości 'na brudno', ponieważ ma to dokładnie takie same zalety jak pisanie na brudno wypracowania do szkoły - pozwala wyłapać błędy i lepiej zaprojektować ostateczną wersję.
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 30 31 32 33 34 35 36 37 | public CharacterDecTree() { ... DecTree.FirstFail followPathNode = new DecTree.FirstFail( new DecTree.Assert(ch => ch.FollowPathOrder), new DecTree.Job(ch => { if (Op2D.Dist(ch.Position, ch.WalkPath[0]) < 0.5f) { ch.WalkPath.RemoveAt(0); } if (ch.WalkPath.Count == 0) { ch.FollowPathOrder = false; return true; } else { ch.Orientation = Quaternion.Slerp( 0.2f, ch.Orientation, Vector3.UNIT_Z.GetRotationTo( (Op2D.XZ * (ch.WalkPath[0] - ch.Position)).NormalisedCopy), true ); ch.Velocity = ch.Orientation * Vector3.UNIT_Z * ch.Profile.WalkSpeed; ch.AnimBlender.SetAnimSet("Walk"); } return false; } )); ... Children.Add(pickItemNode); Children.Add(followPathNode); Children.Add(walkNode); Children.Add(idleNode); } |
Gałąź zawiera działanie zakodowane 'na sztywno'. Dopiszemy do klasy postaci następujące pola: listę WalkPath
zawierającą scieżkę, po której ma przejść postać i flagę FollowPathOrder
sterującą nowym zachowaniem. Działanie polega na zbliżaniu się do kolejnych punktów ścieżki na odległość mniejszą od 0.5m. Obrót postaci będzie gładki, dzięki interpolacji sferycznej.
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 | static void Main(string[] args) { NavMesh navMesh = new NavMesh(); navMesh.LoadFromOBJ("Navmesh.obj"); ... while (true) { ... if (Engine.Singleton.IsKeyTyped(MOIS.KeyCode.KC_P)) { navMesh.AStar(npc.Position, player.Position); if (navMesh.TriPath.Count > 1) { navMesh.GetPortals(); npc.WalkPath = navMesh.Funnel(); npc.FollowPathOrder = true; } } ... } ... } |
W powyższym fragmencie kodu tworzymy nowy obiekt NavMesh, ładujemy dane z pliku, a wciśnięcie klawisza P wykona algorytmy znajdujące trasę od jedynego w grze bohatera niezależnego do postaci gracza i wyda rozkaz przejścia tej trasy temu bohaterowi.
Udało nam się zaimplementować kluczowy fragment sztucznej inteligencji. Bohater niezależny nie gubi się już, podążając za postacią gracza. Wciąż jednak są to dość surowe algorytmy. Wraz z drzewami decyzyjnymi, stanowią one podstawę tego, czym zajmować się będziemy w kolejnych częściach kursu. Zbliża się też moment, w którym zaczniemy tworzyć mechanizmy walki w grze.
Odnośniki:
[1] http://informatyka.wroc.pl/node/742
[2] http://informatyka.wroc.pl/node/785
[3] http://informatyka.wroc.pl/node/788
[4] http://informatyka.wroc.pl/node/846
[5] http://informatyka.wroc.pl/node/1130
[6] http://informatyka.wroc.pl/node/1139
[7] http://informatyka.wroc.pl/node/1267
[8] http://informatyka.wroc.pl/node/1279
[9] http://www.piranha-bytes.com/gothic2/content_english/makingof_filler.php
[10] http://informatyka.wroc.pl/upload/mogre/cz8kod1.zip
[11] http://informatyka.wroc.pl/upload/mogre/cz8zasoby1.zip