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

28.10.2011 - Mateusz Osowski
TrudnośćTrudność

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

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

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

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

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.

Kolejka priorytetowa

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:

  • Priorytetami są wartości typu float,
  • Kopiec jest drzewem binarnym przechowywanym w postaci tablicy,
  • Rodzic ma zawsze mniejszą wartość priorytetu niż jego dzieci,
  • Liście mogą występować tylko w ostatnim lub przedostatnim "wierszu" drzewa i są ułożone szczelnie, bez przerw,
  • Korzeń drzewa jest elementem tablicy o indeksie 0,
  • Lewe dziecko elementu i ma indeks 2i, zaś prawe 2i+1,

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

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

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

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

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com