Zaznajomię was z podstawowymi zagadnieniami w tej dziedzinie, oraz przedstawie kod wykonany w XNA 4.0
Jak na razie poniżej zamieszczam linki do kursów z których korzystałem i kod programu z dorobionym przeze mnie graficznym wskazaniem terenu i nieco przerobioną klasą pathfinding.
Jeśli dopiero zaczynasz przygodę z wyszukiwaniem ścieżek w swoich aplikacjach i nie znasz ogólnej zasady działania takich algorytmów to zapraszam na stronę:
http://www.policyalmanac.org/games/aStarTutorial_pl.htm
znajdziecie tam zasadę działania algorytmu A*(A star) - jednego z najpopularniejszych algorytmów szukających ścieżek.
Natomiast co do implementacji tego algorytmu do swojego kody w XNA, albo gdzie indziej wykorzystując język C#, zapraszam do odwiedzenia strony:
http://xnatd.blogspot.com/2011/06/pathfinding-tutorial-part-1.html
wersja tłumaczona przez google:)
znajdziecie tam 3 części kursu(po angielsku, ale da radę dowiedzieć się o co chodzi, przeglądając 1 link który podałem) z którego możecie nauczyć się jak dodać do własnej gry klasę odpowiedzialną za wyszukiwanie ścieżek.
Na końcu autor umieszcza kod działającej aplikacji, ja (w celach edukacyjnych oczywiście:>) przerobiłem go na postać bardziej zjadliwą graficznie, czyli taką która pokazuje trasę w postaci czerwonych punktów na mapie. Dodatkowo chciałem uzyskać efekt którego brakowało w aplikacji autora czyli możliwość przechodzenia naszego algorytmu po skosie.
Link do mojej wersji programu na chomikuj
Stworzenie tego było dosyć proste, oto moje zmiany dotyczące szukania ścieżki po skosie:
1) zmieniłem rozmiar tablicy sąsiadów żeby się wszystkie możliwości zmieściły:
// We
only want to store nodes
//
that can be walked on.
if
(node.Walkable == true)
{
node.Neighbors = new SearchNode[8];
searchNodes[x, y] =
node;
}
Następnie dodałem gdzie szukać nowych sąsiadów:
//
An array of all of the possible neighbors this
//
node could have. (We will ignore diagonals for now.)
Point[]
neighbors = new Point[]
{
new
Point (x, y - 1), //
The node above the current node
new Point (x, y + 1), // The node below the current node.
new Point (x - 1, y), // The node left of the current node.
new Point (x + 1, y), // The
node right of the current node
new Point (x - 1, y - 1), // The node above the current node
new Point (x + 1, y + 1), // The node below the current node.
new Point (x - 1, y + 1), //
The node left of the current node.
new Point (x + 1, y - 1), // The node right of the current node
};
//
Reverse the path and transform into world space.
for
(int i = closedList.Count - 1; i >= 0; i--)
{
finalPath.Add(new Vector2(closedList[i].Position.X
* 32,
closedList[i].Position.Y * 32));
}
finalPath.Add(new Vector2(endNode.Position.X
* 32,endNode.Position.Y * 32));
return
finalPath;
}
I to by było na tyle:) teraz możemy cieszyć się wyświetlaną kompletną ścieżką do celu włącznie.
Jeszcze sterowanie mojej aplikacji:
L.P myszy - ustawieni punktu startu
P.P myszy - ustawienie punktu końca
Ś.P myszy - szukanie trasy
Pozdrawiam Silver.
