Jestliže jste vývojáři her, možná jste vždy chtěli implementovat A* jako hledání cesty postavy (nebo nepřítele). Vím, že před několika lety jsem to chtěl, ale s mou tehdejší úrovní programování jsem měl problémy s aktuálními články. Chtěl jsem tento článek napsat jako jednoduchý úvod s jasným příkladem zdrojového kódu do A* pathfindingu, aby si ho každý mohl snadno osvojit a použít ve své hře.
Jedním z důležitých aspektů A* je f = g + h. Proměnné f, g a h jsou v naší třídě Node a počítají se při každém vytvoření nového uzlu. V rychlosti projdu, co tyto proměnné znamenají.
- F je celková cena uzlu.
- G je vzdálenost mezi aktuálním uzlem a počátečním uzlem.
- H je heuristika – odhadovaná vzdálenost od aktuálního uzlu ke koncovému uzlu.
Podívejme se na krátký graf, který nám to pomůže ilustrovat.
Paráda! Řekněme, že node(0) je naše výchozí pozice a node(19) je naše koncová pozice. Řekněme také, že náš aktuální uzel je v červeném čtverci node(4).
G
G je vzdálenost mezi aktuálním uzlem a počátečním uzlem.
Pokud počítáme zpětně, vidíme, že node(4) je od našeho počátečního uzlu vzdálen 4 políčka.
Můžeme také říci, že G je o 1 větší než náš rodičovský uzel (node(3)). V tomto případě tedy pro node(4) platí currentNode.g = 4.
H
H je heuristická – odhadovaná vzdálenost od aktuálního uzlu ke koncovému uzlu.
Počítejme tedy vzdálenost. Když se podíváme, zjistíme, že když přejdeme přes 7 políček a o 3 políčka nahoru, dosáhli jsme našeho koncového uzlu (node(19)).
Použijeme Pythagorovu větu! a² + b² = c². Po její aplikaci zjistíme, že currentNode.h = 7² + 3². Neboli currentNode.h = 58.
Nemusíme však použít odmocninu z 58? Ne! Tento výpočet můžeme v každém uzlu vynechat a stále dostaneme stejný výstup. Chytré!“
Při heuristice se musíme ujistit, že ji skutečně můžeme vypočítat. Je také velmi důležité, aby heuristika vždy podhodnocovala celkovou cestu, protože nadhodnocení povede k tomu, že A* bude hledat průchozí uzly, které nemusí být „nejlepší“ z hlediska hodnoty f.
F
F jsou celkové náklady uzlu.
Složíme tedy h a g, abychom získali celkové náklady našeho uzlu. currentNode.f = currentNode.g + currentNode.h. Nebo currentNode.f = 4+ 58. Nebo currentNode.f = 62.
Čas použít f = g + h
Dobře, tak to bylo hodně práce. Teď, když jsme si dali tolik práce, k čemu použiji tuto hodnotu f?“
S touto novou hodnotou f se můžeme podívat na všechny naše uzly a říct: „Hele, je tohle ten nejlepší uzel, který si teď můžu vybrat, abych s ním mohl pokračovat?“. Místo abychom procházeli všechny uzly, můžeme vybrat ty, které mají největší šanci nás dovést k cíli.
Tady je graf pro ilustraci. Nahoře máme Dijkstrův algoritmus, který hledá bez této hodnoty f, a dole máme A*, který tuto hodnotu f používá.
Dijkstrův algoritmus
Takže se podíváme na Dijkstrův algoritmus, vidíme, že prostě pokračuje v hledání. Netuší, který uzel je „nejlepší“, takže počítá cesty pro všechny.
Algoritmus A*
Při použití algoritmu A* vidíme, že jakmile se dostaneme přes překážku, algoritmus upřednostní uzel s nejnižší f a „nejlepší“ šancí dostat se na konec.