Ha játékfejlesztő vagy, talán mindig is szeretted volna az A*-ot karakter (vagy ellenség) útkeresésként megvalósítani. Tudom, hogy pár évvel ezelőtt én is akartam, de az akkori programozási szintemmel gondjaim voltak az aktuális cikkekkel. Ezt úgy akartam megírni, mint egy egyszerű bevezetést egy világos forráskód példával az A* útkeresésről, hogy bárki könnyen fel tudja venni és használni tudja a játékában.
Az A* egyik fontos aspektusa a f = g + h. Az f, g és h változók a Node osztályunkban vannak, és minden alkalommal kiszámításra kerülnek, amikor új csomópontot hozunk létre. Gyorsan átveszem, hogy mit jelentenek ezek a változók.
- F a csomópont teljes költsége.
- G az aktuális csomópont és a kezdő csomópont közötti távolság.
- H a heurisztikus – becsült távolság az aktuális csomópont és a végcsomópont között.
Nézzünk egy gyors grafikont, ami ezt szemlélteti.
Félelmetes! Tegyük fel, hogy node(0) a kezdőpozíciónk és node(19) a végpozíciónk. Mondjuk azt is, hogy az aktuális csomópontunk a piros négyzetben node(4) van.
G
G az aktuális csomópont és a kezdő csomópont közötti távolság.
Ha visszaszámolunk, akkor láthatjuk, hogy node(4) 4 mezőre van a kezdő csomópontunktól.
Mondhatjuk azt is, hogy G 1-gyel több, mint a szülő csomópontunk (node(3)). Tehát ebben az esetben node(4) esetében currentNode.g = 4.
H
H a heurisztikus – becsült távolság az aktuális csomóponttól a végcsomópontig.
Számítsuk ki tehát a távolságot. Ha megnézzük, akkor azt látjuk, hogy ha 7 mezőn túl és 3 mezővel feljebb megyünk, akkor elértük a végcsomópontunkat (node(19)).
Megpróbáljuk alkalmazni a Pitagorasz-tételt! a² + b² = c². Miután ezt alkalmaztuk, látni fogjuk, hogy currentNode.h = 7² + 3². Vagy currentNode.h = 58.
De nem kell alkalmaznunk a négyzetgyököt 58-ra? Nem! Ezt a számítást minden csomóponton kihagyhatjuk, és így is ugyanazt a kimenetet kapjuk. Okos!
Egy heurisztikával meg kell győződnünk arról, hogy valóban ki tudjuk-e számítani. Az is nagyon fontos, hogy a heurisztika mindig alulbecsülje a teljes útvonalat, mivel a túlbecslés ahhoz vezet, hogy az A* olyan csomópontokat keres át, amelyek nem biztos, hogy a f érték szempontjából a “legjobbak”.
F
F a csomópont teljes költsége.
Adjuk össze tehát h-t és g-t, hogy megkapjuk a csomópontunk teljes költségét. currentNode.f = currentNode.g + currentNode.h. Vagy currentNode.f = 4+ 58. Vagy currentNode.f = 62.
Az f = g + h
Jól van, ez így elég sok munka volt. Most ezzel a sok munkával, mire fogom használni ezt a f értéket?
Ezzel az új f értékkel megnézhetjük az összes csomópontunkat, és azt mondhatjuk: “Hé, ez a legjobb csomópont, amit most kiválaszthatok a továbblépéshez?”. Ahelyett, hogy minden csomóponton végigfutnánk, kiválaszthatjuk azokat, amelyek a legjobb eséllyel visznek el minket a célunkhoz.
Itt egy grafikon a szemléltetéshez. Fent van a Dijkstra-algoritmus, amely e f érték nélkül keres, alul pedig az A*, amely használja ezt a f értéket.
Dijkstra algoritmusa
Szóval vessünk egy pillantást Dijkstra algoritmusára, azt látjuk, hogy csak folytatja a keresést. Fogalma sincs, hogy melyik csomópont a “legjobb”, ezért mindegyiknek kiszámítja az útvonalat.
A* algoritmus
A*-algoritmusnál azt látjuk, hogy amint túljutunk az akadályon, az algoritmus azt a csomópontot részesíti előnyben, amelynek a legkisebb f és a “legjobb” esélye van arra, hogy elérje a célt.