Jeśli jesteś programistą gier, być może zawsze chciałeś zaimplementować A* jako pathfinding postaci (lub wroga). Wiem, że kilka lat temu to zrobiłem, ale z moim poziomem programowania w tamtym czasie miałem problemy z aktualnymi artykułami na ten temat. Chciałem napisać to jako łatwe wprowadzenie z jasnym przykładem kodu źródłowego do A* pathfinding, tak aby każdy mógł go łatwo podnieść i użyć w swojej grze.
Jednym z ważnych aspektów A* jest f = g + h. Zmienne f, g oraz h znajdują się w naszej klasie Node i są obliczane za każdym razem, gdy tworzymy nowy węzeł. Szybko omówię, co te zmienne oznaczają.
- F to całkowity koszt węzła.
- G to odległość między bieżącym węzłem a węzłem początkowym.
- H to heurystyczna – szacunkowa odległość od bieżącego węzła do węzła końcowego.
Przyjrzyjrzyjmy się szybkiej grafice, która pomoże to zilustrować.
Awesome! Załóżmy, że node(0) jest naszą pozycją początkową, a node(19) jest naszą pozycją końcową. Powiedzmy również, że nasz bieżący węzeł znajduje się w czerwonym kwadracie node(4).
G
G to odległość między bieżącym węzłem a węzłem początkowym.
Jeśli policzymy wstecz, możemy zobaczyć, że node(4) jest oddalony o 4 miejsca od naszego węzła początkowego.
Możemy również powiedzieć, że G jest o 1 więcej niż nasz węzeł nadrzędny (node(3)). Czyli w tym przypadku dla node(4), currentNode.g = 4.
H
H jest heurystyczną – szacowaną odległością od bieżącego węzła do węzła końcowego.
Obliczmy więc odległość. Jeśli się przyjrzymy, zobaczymy, że jeśli przejdziemy przez 7 przestrzeni i w górę o 3 przestrzenie, to dotarliśmy do naszego węzła końcowego (node(19)).
Zastosujmy Twierdzenie Pitagorejskie! a² + b² = c². Po zastosowaniu tego twierdzenia zobaczymy, że currentNode.h = 7² + 3². Albo currentNode.h = 58.
Ale czy nie musimy zastosować pierwiastka kwadratowego do 58? Nie! Możemy pominąć to obliczenie na każdym węźle i nadal uzyskać to samo wyjście. Sprytne!
W przypadku heurystyki musimy się upewnić, że faktycznie możemy ją obliczyć. Bardzo ważne jest również to, że heurystyka jest zawsze niedoszacowaniem całkowitej ścieżki, ponieważ przeszacowanie doprowadzi do tego, że A* będzie szukał przez węzły, które mogą nie być „najlepsze” pod względem fwartości.
F
F to całkowity koszt węzła.
Zsumujmy więc h i g, aby uzyskać całkowity koszt naszego węzła. currentNode.f = currentNode.g + currentNode.h. Lub currentNode.f = 4+ 58. Lub currentNode.f = 62.
Czas użyć f = g + h
W porządku, więc to było dużo pracy. Teraz z całą tą pracą, do czego zamierzam użyć tej wartości f?
Z tą nową wartością f możemy spojrzeć na wszystkie nasze węzły i powiedzieć: „Hej, czy to jest najlepszy węzeł, który mogę wybrać, aby przejść do przodu w tej chwili?”. Zamiast przechodzić przez każdy węzeł, możemy wybrać te, które mają największą szansę na doprowadzenie nas do naszego celu.
Tutaj jest grafika, aby to zilustrować. Na górze mamy Algorytm Dijkstry, który wyszukuje bez tej wartości f, a poniżej mamy A*, który używa tej wartości f.
Algorytm Dijkstry
Przyglądając się więc algorytmowi Dijkstry, widzimy, że on po prostu szuka. Nie ma pojęcia, który węzeł jest 'najlepszy’, więc oblicza ścieżki dla nich wszystkich.
Algorytm A*
Z A*,widzimy, że po ominięciu przeszkody, algorytm nadaje priorytet węzłowi z najniższą f i 'najlepszą’ szansą dotarcia do końca.