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

28.10.2011 - Mateusz Osowski
TrudnośćTrudność

Implementacja klas pomocniczych

Przechowywanie danych

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.

Pomocnicze operacje w 2D

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

Implementacja klasy NavMesh i jej klas wewnętrznych

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

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

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

Biorąc pod uwagę możliwość wystąpienia błędów numerycznych, porównujemy sumę pól z epsilonowo większą wartością.

???Inną, lepszą obliczeniowo, choć bardziej złożoną metodą takiego testu, jest obliczanie współrzędnych barycentrycznych punktu. Obliczanie to sprowadza się do rzutowania wektora poprowadzonego z wybranego wierzchołka trójkąta, do testowanego punktu na dwie krawędzie wychodzące z tego wierzchołka. Jeżeli suma długości powstałych w wyniku rzutowania wektorów będzie większa niż 0.5, to punkt leży poza trójkątem. Pozostaniemy jednak przy pierwszej metodzie z uwagi na jej większą intuicyjność i prostotę implementacji.


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

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.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com