Edellisessä luvussa luomamme hengenvetoon perustuva haku ei ole liian nopea. Siksi tällä kertaa tarkastelemme nopeampaa algoritmia, joka mahdollistaisi suurempien karttojen käytön hidastamatta peliä:
Paras ensin
Saatat muistaa viimeisestä luvusta, kuinka hengityksen ensimmäinen haku laajensi kaikkia solmuja joka suuntaan. Sillä ei ollut aavistustakaan, missä kohde oli, se näytti kaikkialta. Siksi polun löytäminen kesti ikuisuuden. Se löysi lyhimmän polun joka kerta, mutta ollaan rehellisiä, mikä on tärkeämpää, täydellisen polun löytäminen vai pelattavan pelin tekeminen?
Joten otetaan käyttöön paras ensin -haku. Tällä kertaa yritämme nähdä kuinka kaukana kohde on nykyisestä solmusta ja liitämme arvioidun etäisyyden jokaiseen solmuun.
hinta = Math.abs(x-targetx)+Math.abs(y-targetty);
Laskemme kuinka monta askelta on kohdistettu nykyisestä ruudusta sekä x- että y-suunnassa ja lisäämme askeleita molemmista suunnista.
Toinen ero on, että pidämme Unchecked_Neighbours-taulukon lajiteltuna halvimman kustannustason solmusta kohteeseen (sen pitäisi olla lähellä kohdetta) korkeimman kustannustason solmuun. Lajittelemalla taulukkoa katsomme aina kohteen suuntaan ennen kuin siirrymme muihin suuntiin. Mutta varoita, vaikka paras ensin -haku löytää aina polun, mutta se ei aina ole lyhin reitti. Se on silti paljon nopeampi useimmissa kartoissa kuin A*.
Parhaat koodit
Ota koodi viimeisestä luvusta (tut22) ja muuta findPath-funktiota. Meidän on lisättävä kustannukset ensimmäiseen solmuun:
var cost = Math.abs(aloitusx-targetx)+Math.abs(aloituskohde);
polku[polku.nimi]={x:aloitusx, y:aloitus, vanhempix:nolla, parenty:nolla, kustannus:hinta};
ja meidän on välitettävä kohde addNode-funktiolle:
addNode (N, N.x+1, N.y, targetx, targety);
addNode (N, N.x-1, N.y, targetx, targety);
addNode (N, N.x, N.y+1, targetx, targety);
addNode (N, N.x, N.y-1, targetx, targety);
Muista, että addNode-funktiossa kohde välitetään myös sille:
function addNode (ob, x, y, targetx, targety){
polku.nimi=”solmu_”+y+”“+x; if(peli[“t“+y+”_”+x].kelpoinen){
if (polku[polku.nimi].kustannus==määrittelemätön) {
var cost = Math.abs(x-targetx)+Math.abs(y-targetty);
polku[polku.nimi]={x:x, y:y, parentx:ob.x, parenty:ob.y, cost:cost};
for(var i=0; i=polku. Tarkistamattomat_naapurit.pituus) {
polku.Unchecked_Neighbours[polku.Unchecked_Neighbours.length]=polku[polku.nimi];
}
}
}
}
Tarkistamme, onko solmu jo luotu ja jos sen uusi solmu, hinta lasketaan.
Uuden solmun tekemisen jälkeen alamme kiertää Unchecked_Neighbours-taulukon läpi ja vertailla nykyisen solmun kustannuksia taulukon kunkin elementin hintaan. Katkaisemme silmukan, jos olemme löytäneet taulukosta solmun, jolla on korkeammat kustannukset. Lisäämme uuden solmun kyseiseen kohtaan taulukkoon.
Last if -lause tarkistaa, olemmeko käyneet läpi koko taulukon löytämättä yhtään kalliimpaa solmua. Tämä tarkoittaa, että lisäämme uuden solmumme taulukon loppuun.
Nopeammin, nopeammin
Jos polun etsintä kestää edelleen liian kauan, koska sinulla on suuret kartat, voit harkita joidenkin karttojen osien laskemista etukäteen tai reittipisteiden käyttämistä nikereiden ohjaamiseen kartan yhdestä osasta toiseen katsomatta kaikkia laattoja.
Michael G. on luonut erittäin nopean polunhakujärjestelmän käyttämällä ennalta laskettuja polkuja. Voit lukea siitä täältä. Hän laskee kaikki polut jokaisesta laatasta jokaiseen laattaan ja tallentaa ne karttoihin. Kun char haluaa mennä pelin aikana laatalta toiseen, hänen tarvitsee vain valita polku ja kävellä.
Reittipistejärjestelmä leikkaa kartan käytännössä pienemmiksi kartoiksi, jotka olisi yhdistetty ennalta määritettyihin polkuihin. Sitten sinun on löydettävä vain, mikä minikartan aloitusruutu ja kohdelaatta kuuluvat, ja käytä muistiin tallennettua polkua päästäksesi aloitusminikarttasta kohteeseen. Tämä mahdollistaa polut myös todella todella suurille kartoille.
Toinen tapa laskea suurempia polkuja hidastamatta peliä olisi jakaa polun laskeminen useille kehyksille. Sinun pitäisi katkaista polunhakusilmukka tiettyjen vaiheiden jälkeen, muistaa nykyinen tila, ajaa sitten pelin toinen koodi ja seuraavassa kehyksessä jatkaa polun etsimistä. Andre Michelle on lähettänyt erittäin hienon esimerkin tästä ideasta täällä.
