Dacă sunteți un dezvoltator de jocuri, poate că v-ați dorit dintotdeauna să implementați A* ca traseu al personajului (sau inamicului). Știu că acum câțiva ani am făcut-o, dar cu nivelul meu de programare de la acea vreme am avut probleme cu articolele actuale existente. Am vrut să scriu acest articol ca o introducere ușoară, cu un exemplu clar de cod sursă pentru A* pathfinding, astfel încât oricine să o poată lua cu ușurință și să o folosească în jocul lor.
Un aspect important al A* este f = g + h. Variabilele f, g și h se află în clasa noastră Node și sunt calculate de fiecare dată când creăm un nou nod. Voi trece rapid în revistă ce înseamnă aceste variabile.
- F este costul total al nodului.
- G este distanța dintre nodul curent și nodul de început.
- H este euristica – distanța estimată de la nodul curent la nodul final.
Să aruncăm o privire la un grafic rapid care să ne ajute să ilustrăm acest lucru.
Frumos! Să spunem că node(0) este poziția noastră inițială și node(19) este poziția finală. Să mai spunem că nodul nostru curent se află în pătratul roșu node(4).
G
G este distanța dintre nodul curent și nodul de start.
Dacă numărăm înapoi, putem vedea că node(4) se află la 4 spații distanță de nodul nostru de start.
De asemenea, putem spune că G este cu 1 mai mult decât nodul nostru părinte (node(3)). Deci, în acest caz pentru node(4), currentNode.g = 4.
H
H este euristica – distanța estimată de la nodul curent până la nodul final.
Așa că hai să calculăm distanța. Dacă aruncăm o privire, vom vedea că dacă mergem peste 7 spații și în sus cu 3 spații, am ajuns la nodul final (node(19)).
Să aplicăm Teorema lui Pitagora! a² + b² = c². După ce am aplicat-o, vom vedea că currentNode.h = 7² + 3². Sau .
.
Dar nu trebuie să aplicăm rădăcina pătrată la 58? Nu! Putem sări peste acest calcul pe fiecare nod și tot vom obține același rezultat. Inteligent!
Cu o euristică, trebuie să ne asigurăm că o putem calcula efectiv. De asemenea, este foarte important ca euristica să fie întotdeauna o subestimare a drumului total, deoarece o supraestimare va duce la căutarea de către A* prin noduri care s-ar putea să nu fie „cele mai bune” din punct de vedere al valorii f.
F
F este costul total al nodului.
Acum să adunăm h și g pentru a obține costul total al nodului nostru. currentNode.f = currentNode.g + currentNode.h. Sau currentNode.f = 4+ 58. Sau currentNode.f = 62.
Este timpul să folosim f = g + h
În regulă, deci a fost multă muncă. Acum, cu toată această muncă, la ce voi folosi această valoare f?
Cu această nouă valoare f, putem să ne uităm la toate nodurile noastre și să spunem: „Hei, este acesta cel mai bun nod pe care îl pot alege pentru a merge mai departe chiar acum?”. În loc să parcurgem fiecare nod, le putem alege pe cele care au cele mai mari șanse de a ne duce la obiectivul nostru.
Iată un grafic pentru a ilustra. În partea de sus, avem Algoritmul lui Dijkstra, care caută fără această valoare f, iar mai jos avem A*, care folosește această valoare f.
Algoritmul lui Dijkstra
Așa că aruncând o privire asupra algoritmului lui Dijkstra, vedem că acesta doar continuă să caute. Nu are nicio idee despre care nod este „cel mai bun”, așa că calculează căi pentru toate.
Algoritmul A*
Cu A*,vedem că odată ce am trecut de obstacol, algoritmul dă prioritate nodului cu cea mai mică f și cea mai „bună” șansă de a ajunge la capăt.
.