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

28.10.2011 - Mateusz Osowski
TrudnośćTrudność

Implementacja algorytmu A-Star

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;  
NavMesh.cs

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);
  
NavMesh.cs

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;
NavMesh.cs, AStar()

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);
      }                                       
    }
  }
}
NavMesh.cs, AStar()

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.

Implementacja algorytmu lejkowego

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>>();
NavMesh.cs

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));
}
NavMesh.cs

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;
NavMesh.cs

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;
      }
    }
NavMesh.cs, Funnel()

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;
}
NavMesh.cs, Funnel()

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

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com