Jos olet pelinkehittäjä, olet ehkä aina halunnut toteuttaa A*:n hahmon (tai vihollisen) polunmäärityksen. Tiedän, että pari vuotta sitten tein niin, mutta silloisella ohjelmointitasollani minulla oli ongelmia nykyisten artikkeleiden kanssa. Halusin kirjoittaa tämän helppona johdantona selkeän lähdekoodiesimerkin kera A*-polunvalvonnasta, jotta kuka tahansa voi helposti ottaa sen käyttöönsä ja käyttää sitä pelissään.
Yksi A*:n tärkeä osa-alue on f = g + h. Muuttujat f, g ja h ovat Node-luokassamme ja ne lasketaan joka kerta, kun luomme uuden solmun. Käyn nopeasti läpi, mitä nämä muuttujat tarkoittavat.
- F on solmun kokonaiskustannus.
- G on nykyisen solmun ja alkusolmun välinen etäisyys.
- H on heuristinen – arvioitu etäisyys nykyisestä solmusta loppusolmuun.
Katsotaanpa nopeaa grafiikkaa havainnollistamaan tätä.
Hienoa! Sanotaan, että node(0) on lähtöpisteemme ja node(19) on loppupisteemme. Sanotaan myös, että nykyinen solmumme on punaisen neliön node(4) kohdalla.
G
G on nykyisen solmun ja alkusolmun välinen etäisyys.
Jos laskemme taaksepäin, näemme, että node(4) on 4 välilyönnin etäisyydellä alkusolmustamme.
Voidaan myös sanoa, että G on 1 välilyönnin verran enemmän kuin kantasolmumme (node(3)). Eli tässä tapauksessa node(4):lle currentNode.g = 4.
H
H on heuristinen – arvioitu etäisyys nykyisestä solmusta loppusolmuun.
Lasketaan siis etäisyys. Jos katsomme, huomaamme, että jos menemme yli 7 välilyöntiä ja ylös 3 välilyöntiä, olemme saavuttaneet loppusolmun (node(19)).
Sovelletaan Pythagoraan lausetta! a² + b² = c². Kun olemme soveltaneet tätä, näemme, että currentNode.h = 7² + 3². Tai currentNode.h = 58.
Mutta eikö meidän tarvitse soveltaa neliöjuurta 58:aan? Ei! Voimme jättää tuon laskutoimituksen väliin jokaisessa solmussa ja saada silti saman tuloksen. Fiksua!
Heuristiikalla meidän on varmistettava, että voimme todella laskea sen. On myös hyvin tärkeää, että heuristiikka on aina kokonaispolun aliarviointi, sillä yliarviointi johtaa siihen, että A* etsii solmujen kautta solmuja, jotka eivät välttämättä ole farvon kannalta ”parhaita”.
F
F on solmun kokonaiskustannus.
Lasketaan siis h ja g yhteen, jotta saamme solmumme kokonaiskustannukset. currentNode.f = currentNode.g + currentNode.h. Tai currentNode.f = 4+ 58. Tai currentNode.f = 62.
Aika käyttää f = g + h
Vai niin, siinä oli paljon työtä. Nyt kaiken tämän työn jälkeen, mihin aion käyttää tätä f-arvoa?
Tämän uuden f-arvon avulla voimme tarkastella kaikkia solmujamme ja sanoa: ”Hei, onko tämä paras solmu, jonka voin valita eteenpäin juuri nyt?”. Sen sijaan, että kävisimme läpi jokaisen solmun, voimme valita ne, joilla on parhaat mahdollisuudet päästä tavoitteeseemme.
Tässä on havainnollistava grafiikka. Ylhäällä on Dijkstran algoritmi, joka etsii ilman tätä f-arvoa, ja alhaalla on A*, joka käyttää tätä f-arvoa.
Dijkstran algoritmi
Katsellaan siis Dijkstran algoritmia, huomaamme, että se vain jatkaa etsimistä. Sillä ei ole aavistustakaan siitä, mikä solmu on ’paras’, joten se laskee polkuja kaikille.
A*-algoritmi
A*:n avulla näemme, että kun pääsemme esteen ohi, algoritmi asettaa etusijalle solmun, jolla on pienin f ja ’paras’ mahdollisuus päästä perille.