Als je een spel ontwikkelaar bent, heb je misschien altijd al A* willen implementeren als karakter (of vijand) pathfinding. Ik weet dat ik dat een paar jaar geleden heb gedaan, maar met mijn niveau van programmeren op dat moment had ik problemen met de huidige artikelen die er zijn. Ik wilde dit schrijven als een gemakkelijke introductie met een duidelijk broncode voorbeeld voor A* pathfinding, zodat iedereen het gemakkelijk kan oppakken en gebruiken in hun spel.
Een belangrijk aspect van A* is f = g + h. De f, g, en h variabelen zitten in onze Node klasse en worden iedere keer berekend als we een nieuwe node maken. Ik zal snel doornemen wat deze variabelen betekenen.
- F is de totale kostprijs van het knooppunt.
- G is de afstand tussen het huidige knooppunt en het beginknooppunt.
- H is de heuristische – geschatte afstand van het huidige knooppunt tot het eindknooppunt.
Laten we eens kijken naar een snelle grafiek om dit te helpen illustreren.
Afgrijselijk! Laten we zeggen dat node(0) onze beginpositie is en node(19) onze eindpositie. Laten we ook zeggen dat ons huidige knooppunt zich op het rode vierkant node(4) bevindt.
G
G is de afstand tussen het huidige knooppunt en het beginknooppunt.
Als we terugtellen, kunnen we zien dat node(4) 4 velden verwijderd is van ons beginknooppunt.
We kunnen ook zeggen dat G 1 meer is dan ons beginknooppunt (node(3)). Dus in dit geval voor node(4), currentNode.g = 4.
H
H is de heuristisch – geschatte afstand van het huidige knooppunt tot het eindknooppunt.
Dus laten we de afstand berekenen. Als we even kijken zien we dat als we over 7 velden gaan en 3 velden omhoog, we ons eindknooppunt hebben bereikt (node(19)).
Laten we de Stelling van Pythagoras toepassen! a² + b² = c². Nadat we deze hebben toegepast, zullen we zien dat currentNode.h = 7² + 3². Of currentNode.h = 58.
Maar hoeven we de vierkantswortel niet toe te passen op 58? Nope! We kunnen die berekening op elk knooppunt overslaan en toch dezelfde uitkomst krijgen. Slim!
Met een heuristiek, moeten we er zeker van zijn dat we het ook echt kunnen berekenen. Het is ook heel belangrijk dat de heuristiek altijd een onderschatting is van het totale pad, want een overschatting zal ertoe leiden dat A* door knooppunten zoekt die misschien niet de ‘beste’ zijn in termen van f waarde.
F
F is de totale kostprijs van het knooppunt.
Dus laten we h en g optellen om de totale kostprijs van ons knooppunt te krijgen. currentNode.f = currentNode.g + currentNode.h. Of currentNode.f = 4+ 58. Of currentNode.f = 62.
Tijd om f = g + h
Okee, dus dat was een hoop werk. Met al dat werk, waar ga ik deze f waarde voor gebruiken?
Met deze nieuwe f waarde, kunnen we naar al onze knooppunten kijken en zeggen, “Hé, is dit het beste knooppunt dat ik kan kiezen om nu mee verder te gaan?”. In plaats van elk knooppunt te doorlopen, kunnen we die knooppunten kiezen die de beste kans hebben om ons doel te bereiken.
Hier is een grafiek om het te illustreren. Bovenaan hebben we Dijkstra’s algoritme, dat zoekt zonder deze f-waarde, en onderaan hebben we A*, dat deze f-waarde wel gebruikt.
Dijkstra’s Algoritme
Als we dus kijken naar Dijkstra’s algoritme, zien we dat het gewoon blijft zoeken. Het heeft geen idee welk knooppunt ‘het beste’ is, dus berekent het paden voor hen allemaal.
A*-algoritme
Met A* zien we dat zodra we voorbij het obstakel zijn, het algoritme voorrang geeft aan het knooppunt met de laagste f en de ‘beste’ kans om het einde te bereiken.