Yksi tähän mennessä yhteinen asia kaikissa esimerkeissämme on sankarin tyhmä. Jos käsketisit häntä liikkumaan vasemmalle, hän menisi vasemmalle. Varmasti tyhmä on mukavaa armeijassa, mutta sankarillamme pitäisi olla jonkinlaiset aivot löytääkseen tiensä maailman vaarojen läpi. Tehdään siis polunhakua.
Ennen kuin teemme sen, ehkä olisi hyvä idea sanoa ääneen ja selkeästi, mikä on polunhaku. Pathfinding on löytää polku laatta A laatta B. Huh, se meni hyvin. Eikä mennyt päivääkään.
Monet polut
Polunhaku on itse asiassa hyvin monimutkainen asia. Mutta se on myös erittäin hyödyllinen asia. Voimme käyttää samaa järjestelmää paitsi sankarille, myös kaikille muille pelin esineille. Kuvittele peli, jossa on monia vihollisia, he kaikki haluavat löytää polun sankarimme luo ja lopulta tappaa sankarin (he eivät olisi vihollisia, jos he eivät haluaisi tappaa sankaria).
Tässä esimerkissä odotamme sankarin löytävän polun laatasta, jolla hän tällä hetkellä seisoo, polulle, jossa hiirtä klikattiin. Älä mene lankaan sekoittamaan mitä tahansa polkua lyhimpään polkuun. Mikä tahansa polku löytyy, vaikka ihmettelemme karttaa satunnaisesti (kuten vihollisemme tekivät luvussa 9). Se saattaa viedä aikaa, mutta lopulta polku laatalta A laattaan B löytyy. Nyt lyhin polku tarkoittaa, että löydämme polun, joka vie vähemmän askeleita kuin mikään muu polku. Ihminen tekee niin koko ajan, jos menet kotiin töistä, löydät lyhimmän reitin työn ja kodin välillä ja käytät sitä. Ellet halua vierailla pubissa matkalla kotiin.
Joissakin tapauksissa laattojen määrä ei välttämättä ole yhtä suuri niiden ylittämiseen tarvittavien askelten määrässä. Kuten voisi olla tie- ja suo- ja metsälaatat, ja tielaatalla käveleminen vie varmasti vähemmän aikaa kuin suolla käveleminen. En mene tällaiseen tilanteeseen liian syvälle, mutta tarvitset A* (A-tähti) -algoritmin löytääksesi polkuja tällaisista kartoista. Useita Flashin A*-koodeja on vapaasti saatavilla Internetissä, vain hae niitä.
Reitin etsiminen voi kestää hyvin kauan. Erityisesti suuremmilla kartoilla, joissa on paljon haettavaa ruutua, polun löytäminen voi kestää useita sekunteja. Kuten tiedät, Flash ei ole kovin tehokas, ja jos pelisi pysähtyy silloin tällöin löytääkseen polkuja, sitä ei voi enää pelata. Ennen kuin lisäät polunhaun peliisi, mieti. Tarvitsetko todella sitä? Voitko tehdä sen nopeammin? Voitko huijata luodaksesi ei niin täydellisiä, mutta silti mukavia polkuja?
Hengitä ensin
Leveyshaun pseudokoodi on selkeästi selitetty tässä linkissä ja lue upea artikkeli täältä. Esimerkkini seuraa pseudokoodia.
Lainaan yllä olevaa sivua (ohita se, jos luit selityksen linkistä):
“Tämä on erittäin kallis, mutta suhteellisen selkeä algoritmi. Se alkaa aloituspisteestä Lähde ja löytää polun tavoitteeseen Kohde. Peruslähestymistapa on ottaa jokainen lähtöpisteen naapuri ja ottaa sitten jokainen naapuri näistä naapureista. , ja sitten näiden naapurien naapurit, ja niin edelleen, laajentamalla ruutuja (solmuja), kunnes lopulta yksi niistä on tavoite Joka kerta kun solmua tarkastellaan, sen naapurit työnnetään jonoon jossa solmut otetaan huomioon, on naapuri toisensa jälkeen.
Eli aloitamme 0:lla. Kaikki sen naapurit 1-8 laitetaan jonoon. Sitten ensimmäinen elementti (1) poistetaan jonosta ja sen naapurit 9-13 laitetaan jonoon. Seuraava elementti (2) poistetaan sitten jonosta ja sen naapurit (eli 14) laitetaan jonoon. Sitten (3) poistetaan jonosta ja sen naapurit 15-17 asetetaan jonoon; (4) riisutaan ja sen naapurit 18 puetaan päälle; ja niin edelleen.”
Koodaa ensin hengitys
Käytämme pohjana luvun 17 esimerkkiä. Rakenna kartta samalla tavalla kuin aiemmin, käyttämällä buildMap-toimintoa. Myöskään työtoimintoihin ei tarvita muutoksia. Ensimmäinen uusi asia tulee olemaan getTarget-toiminto. Kun olemme varmistaneet, että kävelykelpoista ruutua napsautettiin, päivitämme kohdelaatan ja kutsumme uutta findPath-toimintoa:
function getTarget() {
if(peli[“t_”+peli.hiiri+”_”+peli.xhiiri].käveltävä){
peli.targetx=peli.xhiiri;
peli.targety=peli.hiiri;
if(!char.moving){
findPath(char.xtile, char.ytile, game.targetx, game.targetty);
}muu{
game.clicked=true;
}
}
}
Tarkistamme, liikkuuko sankari parhaillaan laatalta toiseen. Tämä johtuu siitä, että annamme pelaajan napsauttaa lavalla milloin tahansa, vaikka sankari liikkuisi parhaillaan laatalta toiselle, mutta sankari päättää ensin nykyisen liikkeensä ja saavuttaa laatan keskustan. Kun olemme keskellä, tarkistamme game.clicked ja kutsumme findPath-funktion, jos käyttäjä on napsauttanut.
Kuten ehkä jo arvasitkin, findPath-funktio tekee päätyön etsintäpolulla.
function findPath(startx, starty, targetx, targety){
polku={};
path.Unchecked_Neighbours=[];
polku.tehty = false;
polku.nimi=”solmu_”+aloitus+”_”+aloitusx;
polku[polku.nimi]={x:aloitusx, y:aloitus, vierailtu:true, parentx:null, parenty:null};
polku.Unchecked_Neighbours[polku.Unchecked_Neighbours.length]=polku[polku.nimi];
while(path.Unchecked_Neighbours.length>0) {
var N = polku. Tarkistamaton_Naapurit.shift();
if (N.x == targetx ja N.y == targety) {
tee_polku(N);
polku.tehty = tosi;
tauko;
}else {
N.vierailtu=true;
addNode (N, N.x+1, N.y);
addNode (N, N.x-1, N.y);
addNode (N, N.x, N.y+1);
addNode (N, N.x, N.y-1);
}
}
poista polku;
if (polku.tehty) {
palauttaa tosi;
}else {
palauttaa väärä;
}
}
Katsotaan mitä täällä tapahtuu. Funktio vastaanottaa 4 muuttujaa: sekä aloitus- että kohderuutujen x- ja y-koordinaatit. Sitten luomme uuden “polku”-objektin ja Unchecked_Neighbours-taulukon. “polku”-objekti on väliaikainen esineemme, joka pitää sisällään kaikenlaisia osia etsiessämme polkua. Polunhaun lopussa poistamme “polku”-objektin ja jätämme kaiken jälleen selväksi.
“done” -ominaisuutta käytetään lopussa tarkistamaan, olemmeko todella löytäneet polun (done on totta) vai onko pelaaja tyhmästi napsauttanut jotakin laatta, jolle mikään polku ei pääse (done on false).
Sitten luomme ensimmäisen solmumme aloituspaikkaan ja lisäämme sen Unchecked_Neighbours -taulukkoon. Jokaisella solmuobjektilla on useita tärkeitä ominaisuuksia. solmu.x säilyttää x-asemansa ja node.y y-asemansa. node.visited on totta, kun solmu on jo käsitelty, tällä tavalla emme palaa jo etsimiimme ruutuihin. node.parentx ja parenty viittaavat solmuun, johon saavutimme nykyisessä solmussa. Jos esimerkiksi astuimme ruudulle 1_2 ruudusta 1_3, niin sen emox on 1 ja vanhemmuus on 3. On tärkeää muistaa yläsolmu, koska sen avulla voimme itse rakentaa polkutaulukon myöhemmin, kun meillä on löysi polun.
Nyt aloitamme main while -silmukan, joka jatkuu, kunnes Unchecked_Neighbours -taulukko on tyhjä. Otamme sitten ensimmäisen elementin Unchecked_Neighbours-taulukosta (shift-komento) ja tarkistamme, onko kyseinen solmu kohde. Jos se on kohde, olemme löytäneet polun ja kutsumme funktiota make_path, asetamme “done” -ominaisuuden arvoksi tosi ja katkaisemme silmukan.
Jos se ei valitettavasti ollut kohteena, meidän on jatkettava etsimistä. Asetamme solmun “vieraillut”-ominaisuuden arvoksi tosi ja lisäämme kaikki sen naapurit addNode-funktiolla.
function addNode (ob, x, y){
polku.nimi=”solmu_”+y+”_”+x;
if(peli[“t_”+y+”_”+x].kelpoinen){
if (polku[polku.nimi].vieraillut != tosi) {
polku[polku.nimi]={x:x, y:y, vierailtu:false, parentx:ob.x, parenty:ob.y};
polku.Unchecked_Neighbours[polku.Unchecked_Neighbours.length]=polku[polku.nimi];
}
}
}
AddNode-funktio saa “ob” nykyiseksi solmuksi ja x/y uudelle solmulle, jota olemme lisäämässä. Luomme uuden solmun vain, jos kyseinen ruutu on kävelykelpoinen eikä siinä ole vielä käyty. Uusi solmu saa sitten parentx- ja vanhempien ominaisuudet ob-solmulta.
Päättääksemme polkumme meidän on itse asiassa luotava sankarimme käytettäväksi polkutaulukko. Älä sekoita tätä polkutaulukkoa findPath-funktiossa käytettyyn polkuobjektiin. Ja jos haluat löytää useita polkuja useille liikkuville objekteille, on parempi liittää polku jokaiseen objektiin eikä peliobjektiin, kuten olemme tehneet täällä:
function make_path(ob){
peli.polku=[];
while (ob.parentx!=null){
peli.polku[peli.polku.length]=ob.x;
peli.polku[peli.polku.length]=ob.y;
ob=polku[“solmu_”+ob.parenty+”_”+ob.parentx];
}
char.moving=true;
}
While-silmukka jatkuu, kunnes solmun parentx on nolla, mikä tarkoittaa, että se on alkuperäinen aloitussolmu, jossa hero tällä hetkellä on. Lisäämme kunkin solmun x- ja y-aseman polkutaulukkoon ja teemme sitten sen emosta nykyinen solmu. Lopulta laitoimme char liikkumaan uudelleen. SKoska lisäämme sekä x- että y-paikan erikseen, polkutaulukko sisältää tietoja jossain muodossa tässä muodossa:
[targetx, targety, monta vaihetta tässä, firststepx, firststepy]
Meidän on myös käytettävä polkutaulukkoa moveChar-funktiossa. Kun olemme laskeneet ruudun, jossa merkkien keskus on (xtile- ja ytile-arvot), muuta koodia:
if(game.clicked){
game.clicked=false;
findPath(char.xtile, char.ytile, game.targetx, game.targetty);
palata;
}
if(game.path.length>0){
peli.targety=peli.polku.pop();
peli.targetx=peli.polku.pop();
if(game.targetx>ob.xtile){
ob.dirx=1;
ob.diry=0;
}else if(peli.targetx<ob.xtile){
ob.dirx=-1;
ob.diry=0;
}else if(game.targety>ob.ytile){
ob.dirx=0;
ob.diry=1;
}else {
ob.dirx=0;
ob.diry=-1;
}
}muu{
ob.moving=false;
palata;
}
Täällä tarkistamme, onko pelaaja napsauttanut jotakin laatta, kun olimme kiireisiä siirtyessämme laatalta toiseen. Jos pelaaja todella on napsauttanut (pelaajat ovat tällaisia, he napsauttavat koko ajan), kutsumme findPath-funktion ja palaamme.
Mutta jos pelaaja ei ole napsauttanut, tarkistamme, onko meillä polkua jäljellä jatkaaksemme liikkumista. Joten jos polkutaulukko sisältää joitain elementtejä, poistamme LAST-elementin taulukosta pop-komennolla ja määritämme sen kohteelle. Kiinnitä huomiota tähän, viimeinen elementti menee y:hen ja sitten otetaan viimeinen elementti uudelleen ja määritetään se targetx:lle. Nyt verrataan sankarin nykyistä sijaintia seuraavaan laattaan, jonka päälle hänen pitäisi astua ja vaihtaa dirx/diry, jotta sankari liikkuisi oikein.
Ota huomioon, että tämä haku on erittäin hidasta. Se saattaa jopa kaataa Flash-soittimen, jos käytät sitä suurilla kartoilla. Haluat ehkä lisätä jonkin ajastimen findPath-silmukkaan sen katkaisemiseksi, kun tarpeeksi vaiheita on suoritettu, mutta polkua ei ole vielä löydetty. Suurissa kartoissa saattaa myös olla hyvä idea käyttää reittipisteitä ennalta lasketuilla poluilla, jotta polun etsimiseen kuluu vähemmän aikaa.
