Om du är en spelutvecklare har du kanske alltid velat implementera A* för att hitta vägen till en karaktär (eller fiende). Jag vet att jag för ett par år sedan gjorde det, men med min programmeringsnivå på den tiden hade jag problem med de aktuella artiklarna där ute. Jag ville skriva det här som en enkel introduktion med ett tydligt källkodexempel till A* pathfinding så att vem som helst lätt kan plocka upp det och använda det i sitt spel.
En viktig aspekt av A* är f = g + h. Variablerna f, g och h finns i vår Node-klass och beräknas varje gång vi skapar en ny nod. Jag ska snabbt gå igenom vad dessa variabler betyder.
- F är nodens totala kostnad.
- G är avståndet mellan den aktuella noden och startnoden.
- H är det heuristiska – uppskattade avståndet från den aktuella noden till slutnoden.
Låt oss ta en titt på en snabb grafik för att illustrera detta.
Awesome! Låt oss säga att node(0) är vår startposition och node(19) är vår slutposition. Låt oss också säga att vår nuvarande nod är vid den röda rutan node(4).
G
G är avståndet mellan den nuvarande noden och startnoden.
Om vi räknar bakåt kan vi se att node(4) är 4 rutor bort från vår startnod.
Vi kan också säga att G är 1 mer än vår modernod (node(3)). Så i det här fallet för node(4) är currentNode.g = 4.
H
H är det heuristiska – uppskattade avståndet från den aktuella noden till slutnoden.
Så låt oss beräkna avståndet. Om vi tar en titt ser vi att om vi går över 7 platser och upp 3 platser har vi nått vår slutnod (node(19)).
Låt oss tillämpa Pythagoras sats! a² + b² = c². När vi har tillämpat detta ser vi att currentNode.h = 7² + 3². Eller currentNode.h = 58.
Men måste vi inte tillämpa kvadratroten på 58? Nej! Vi kan hoppa över den beräkningen på varje nod och ändå få samma resultat. Smart!
Med en heuristik måste vi se till att vi faktiskt kan beräkna den. Det är också mycket viktigt att heuristiken alltid är en underskattning av den totala vägen, eftersom en överskattning kommer att leda till att A* söker sig igenom noder som kanske inte är de ”bästa” när det gäller f värde.
F
F är den totala kostnaden för noden.
Så låt oss addera h och g för att få den totala kostnaden för vår nod. currentNode.f = currentNode.g + currentNode.h. Eller currentNode.f = 4+ 58. Eller currentNode.f = 62.
Dags att använda f = g + h
Okej, så det var mycket arbete. Nu med allt detta arbete, vad ska jag använda detta f-värde till?
Med detta nya f-värde kan vi titta på alla våra noder och säga: ”Hej, är detta den bästa noden jag kan välja att gå vidare med just nu?”. I stället för att gå igenom alla noder kan vi välja de noder som har den bästa chansen att föra oss till vårt mål.
Här är en grafisk illustration. Överst har vi Dijkstras algoritm, som söker utan detta f-värde, och nedanför har vi A* som använder detta f-värde.
Dijkstras algoritm
Så tar vi en titt på Dijkstras algoritm, ser vi att den bara fortsätter att söka. Den har ingen aning om vilken nod som är ”bäst”, så den beräknar vägar för dem alla.
A*-algoritm
Med A* ser vi att när vi väl kommit förbi hindret prioriterar algoritmen den nod som har lägst f och den ”bästa” chansen att nå slutet.