Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web development, networking and server security. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

Pathfinding pentru incepatori

De Patrick Lester (Actualizat in 18 iulie 2005)


Acest articol a fost tradus in albaneza, chineza, franceza, germana, portugheza, rusa, sarba, si spaniola. Alte traduceri sunt binevenite. A se vedea adresa de email la partea de jos a acestui articol.

A * (pronuntat A-star) algoritm poate fi complicat pentru incepatori. Desi exista mai multe articole pe web, care explica A * cele mai multe, sunt scrise pentru cei care au inteles deja elementele de baza. Acest articol este pentru incepatori adevarat.  

Acest articol nu incearca sa se lucreze definitiva cu privire la subiect. In schimb, descrie fundamentele si te pregateste sa iasa si sa cititi toate aceste alte materiale si sa inteleaga ce este vorba. Link-uri la unele dintre cele mai bune sunt furnizate la sfarsitul acestui articol, in conformitate cu Lecturi suplimentare.

In cele din urma, acest articol nu este un program specific. Tu ar trebui sa poata sa se adapteze ceea ce e aici la orice limbaj de calculator. Dupa cum s-ar putea astepta, cu toate acestea, am inclus o legatura intr-un program de proba, la finalul acestui articol. Pachetul de proba contine doua versiuni: una in C + + si unul in Blitz Basic. Acesta contine, de asemenea, executabile daca doriti doar sa vedeti A * in actiune.

Dar suntem noi insine de a reusi. Sa incepem cu inceputul...

Introducere: zona de cautare

Sa presupunem ca avem pe cineva care vrea pentru a ajunge din punctul A in punctul B. Sa presupunem ca un perete separa cele doua puncte. Acest lucru este ilustrat mai jos, cu verde, fiind punctul de plecare A, si rosu fiind B punctul final, si patrate albastre umplut fiind zid intre.


[Figura 1]

Primul lucru pe care ar trebui sa observati este ca ne-am impartit in zona noastra de cautare intr-o grila patrat. Simplificarea zona de cautare, asa cum am facut aici, este primul pas in pathfinding. Aceasta metoda reduce special in zona noastra de cautare intr-o simpla doua matrice dimensionale. Fiecare element din matrice reprezinta una dintre patrate de pe grila, iar statutul sau este inregistrata ca walkable sau unwalkable. Calea este gasit de imaginind care patrate trebuie sa luam pentru a obtine de la A la B. Dupa ce este gasit calea, persoana noastra se muta de la centrul de un patrat, la centrul de viitor, pana la tinta este atinsa.

Aceste puncte de centru sunt numite "noduri". Cand ai citit despre pathfinding in alta parte, veti vedea de multe ori oamenii discuta noduri. De ce nu suna doar le grinzi? Deoarece este posibil sa imparta zona dvs. pathfinding in ceva, altele decat patrate. Ele ar putea fi dreptunghiuri, hexagoane, triunghiuri, sau orice forma, intr-adevar. Si nodurile ar putea fi plasat oriunde in forme - in centru sau de-a lungul marginilor, sau oriunde altundeva. Suntem folosind acest sistem, cu toate acestea, deoarece aceasta este cea mai simpla.

Incepand de cautare

Dupa ce ne-am simplificat zona nostru de cautare intr-un numar de gestionat de noduri, asa cum am facut cu aspectul grila de mai sus, urmatorul pas este de a efectua o cautare pentru a gasi calea cea mai scurta. Facem acest lucru pornind de la punctul A, verificarea patrate adiacente, si, in general, cautarea pasiva pana cand vom gasi tinta noastra.

Vom incepe cautarea prin a face cu urmatorul text:

  1. Incepe la punctul de plecare A si adaugati-o la o "lista deschisa" de patrate care urmeaza sa fie luate in considerare. Lista deschis este un fel de lista de cumparaturi. Chiar acum exista doar un articol de pe lista, dar vom avea mai tarziu. Acesta contine patrate care ar putea cadea pe calea pe care doriti sa le ia, dar poate nu. Practic, aceasta este o lista de patrate care trebuie sa fie verificat.
  2. Uita-te la toate patratele accesibile sau walkable adiacente la punctul de plecare, ignorand grinzi cu pereti, apa, teren sau alte activitati ilegale. Adaugati-le la lista de deschis, de asemenea. Pentru fiecare dintre aceste piete, cu exceptia punctul A ca "patrat-mama" sale. Chestia asta patrat mama, este important atunci cand vrem sa urmareasca calea noastra. Acesta va fi explicata mai tarziu.
  3. Arunca patrat pornind de la o lista deschis, si adaugati-l la o "lista inchisa" de patrate care nu aveti nevoie sa se uite la din nou pentru acum.
In acest moment, ar trebui sa ai ceva de genul urmatoarea ilustratie. In aceasta ilustratie, patrat de culoare verde inchis, in centru este patrat de pornire. Acesta este subliniat in albastru deschis pentru a indica faptul ca piata a fost adaugat la lista de inchis. Toate patrate adiacente sunt acum pe lista deschisa de patrate pentru a fi verificate, si sunt prezentate in verde deschis. Fiecare are un pointer gri care indica inapoi la mama, care este patrat de pornire.


[Figura 2]

Apoi, vom alege unul din patratele adiacente de pe lista deschisa si mai mult sau mai putin repetati procesul de mai devreme, dupa cum este descris mai jos. Dar care patrat alegem? Una cu cel mai mic cost F.

Calea de punctare

Cheie pentru a stabili care patrate pentru a folosi atunci cand imaginind calea este urmatoarea ecuatie:

F = G + H

unde

Calea noastra este generata in mod repetat de catre trece printr-lista noastra de deschise si alegerea patrata, cu cel mai mic scor F. Acest proces va fi descris in detaliu mai mult un pic mai departe in articol. Prima data l et ne uitam mai atent la modul in care vom calcula ecuatia.

Dupa cum este descris mai sus, G este costul miscare pentru a trece de la punctul de plecare pentru a patrat dat folosind calea generate pentru a ajunge acolo. In acest exemplu, vom atribui un cost de la 10 la fiecare patrat orizontale sau verticale sa mutat, si un cost de 14 pentru o miscare diagonala. Noi folosim aceste numere, deoarece distanta reala pentru a muta pe diagonala este radacina patrata a 2 (nu??va speriati), sau aproximativ 1.414 de ori costul de a muta orizontal sau vertical. Noi folosim 10 si 14 pentru simplitate. Raportul este de aproximativ drept, si ne evita pentru a calcula radacini patrate si sa evitam zecimale. Aceasta nu este doar pentru ca suntem prosti si nu-mi place matematica. Folosind aceste numere intregi ca este mult mai repede pentru calculator, de asemenea. Dupa cum veti afla in curand, pathfinding poate fi foarte lent, daca nu folositi scurtaturi cum ar fi acestea.

Din moment ce suntem calcul al costului G de-a lungul unui traseu specific unui patrat dat, cale pentru a afla costul G de care patrat este de a lua costul G ale societatii-mama, si apoi se adauga 10 sau 14, in functie de faptul daca este sau diagonale ortogonale (non-diagonal), din care patrat mama. Nevoie de aceasta metoda va deveni evident un pic mai departe in acest exemplu, asa cum am obtine mai mult de un patrat distanta de piata de pornire.

H poate fi estimat la o varietate de moduri. Metoda pe care le folosim aici se numeste metoda de Manhattan, in cazul in care va calcula numarul total de patrate mutat orizontal si vertical, pentru a ajunge in piata tinta din piata actuala, ignorand miscare diagonala, si ignorand orice obstacole care ar putea fi in mod. Am multiplica apoi totalul de 10, costul nostru pentru a muta un patrat pe orizontala sau pe verticala. Aceasta este (probabil) a solicitat metoda de Manhattan, pentru ca este ca calcularea numarului de blocuri de oras de la un loc in altul, in cazul in care nu aveti posibilitatea sa taie in bloc diagonala.

Citind acest descriere, s-ar putea ghici ca euristica este doar o estimare aproximativa a distanta ramasa intre piata actuala si tinta "in linie dreapta." Acest lucru nu este cazul. Suntem de fapt, incearca sa estimeze distanta ramasa de-a lungul drum (care este de obicei mai departe). Mai aproape de estimarea noastra este de a distanta ramasa reale, cu atat mai repede va fi algoritmul. Daca am supraestimeaza aceasta distanta, cu toate acestea, nu este garantat pentru a ne da calea cea mai scurta. In astfel de cazuri, avem ceea ce se numeste o "euristica inadmisibil."

Punct de vedere tehnic, in acest exemplu, metoda de Manhattan este inadmisibila, deoarece supraestimeaza usor distanta ramasa. Dar il vom folosi oricum, deoarece este mult mai usor de inteles pentru scopurile noastre, si pentru ca este doar o supraestimare usoara. Cu ocazia rara in cazul in care calea de rezultat nu este cel mai scurt posibil, acesta va fi aproape la fel de scurt. Vrei sa stii mai multe? Puteti gasi ecuatii si note suplimentare pe euristica aici.

F se calculeaza prin adaugarea G si H. Rezultatele primul pas in cautarea noastra poate fi vazut in ilustratia de mai jos. Scorurile F, G, H si sunt scrise in fiecare patrat. Dupa cum este indicat in patrat la dreapta imediata a patrat de pornire, F este tiparita in stanga sus, G este tiparita in stanga jos, si H este tiparita in dreapta jos.


[Figura 3]

Deci, sa ne uitam la unele dintre aceste piete. In piata, cu litere in ea, G = 10. Acest lucru se datoreaza faptului ca acesta este doar un patrat din piata de pornire intr-o directie orizontala. Patrate imediat de mai sus, mai jos, si la stanga patrat de pornire au toate acelasi scor G din 10. Patrate diagonala au scoruri de G 14.

Scorurile H sunt calculate prin estimarea distanta Manhattan la patrat rosu-tinta, se deplaseaza numai pe orizontala si pe verticala, ignorand perete, care este in mod. Folosind aceasta metoda, patrat la dreapta imediat de la inceperea este de 3 patrate de la patrat rosu, pentru un scor de 30 H. Patrat imediat deasupra acestui patrat este de 4 patrate departe (amintiti-va, numai deplaseaza orizontal si vertical), pentru un scor de 40 H. Puteti vedea, probabil, modul in care scorurile H sunt calculate pentru alte piete.

Scorul F pentru fiecare patrat, din nou, este pur si simplu calculata prin adaugarea G si H impreuna.

Continuarea cautare

Pentru a continua cautarea, vom alege pur si simplu cel mai mic scor F patrat de la toate cele care sunt pe lista deschisa. Noi facem apoi cu urmatorul text patrat selectat:

4) Arunc-o din lista deschisa si adaugati-l la lista inchisa.

5) Verificati toate patrate adiacente. Ignorarea cele care sunt pe lista inchisa sau unwalkable (teren cu ziduri, apa, teren sau alte activitati ilegale), se adauga la lista de patrate deschise in cazul in care nu sunt pe lista deja deschisa. Asigurati-patrat selectat "mama" a patrate noi.

6) In cazul in care un patrat adiacent este deja pe lista deschisa, verificati pentru a vedea daca aceasta cale in acest patrat este una mai buna. Cu alte cuvinte, verificati pentru a vedea daca scorul G pentru care patrat este mai mica daca vom folosi patrat curent pentru a ajunge acolo. Daca nu, nu fac nimic.
Pe de alta parte, in cazul in care costul G a noua cale este mai mic, schimba-mama a patrat adiacente la patrat selectate (in diagrama de mai sus, schimba directia de indicatorul de la punctul la patrat selectionat). In cele din urma, se recalculeaza atat scorurile F si G din acel patrat. Daca acest lucru pare confuz, veti vedea ca este ilustrat mai jos.

Ok, deci hai sa vedem cum functioneaza acest lucru. A noastra initiala 9 patrate, ne-am lasat 8 pe lista deschisa dupa patrat de pornire a fost trecut la lista inchisa. Dintre acestea, cea cu cel mai mic cost F este una la dreapta imediata a patrat de plecare, cu un F scor de 40. Deci, vom selecta aceasta piata ca patrat urmatoarea noastra. illustration . Este evidentiati in albastru, in urmatoarea ilustratie.


[Figura 4]

In primul rand, am o picatura din lista noastra de deschis si sa il adaugati la lista noastra inchis (de aceea e acum evidentiate in albastru). Apoi vom verifica patrate adiacente. Ei bine, cei de la dreapta imediata a acestei patrat sunt patrate de perete, asa ca am ignora aceste. Una la stanga imediata este patrat de pornire. Asta e pe lista inchisa, asa ca am ignora faptul ca, de asemenea.

Celelalte patru patrate sunt deja pe lista de deschis, asa ca avem nevoie pentru a verifica daca aceste cai de a patrate sunt mai bine folosind acest patrat pentru a ajunge acolo, folosind scores G, punctul nostru de referinta. Sa ne uitam la dreapta patrat de mai sus patrat noastre selectate. Scorul sau de G circulante este de 14. Daca in schimb am trecut prin piata actuale pentru a ajunge acolo, scorul G ar fi egal cu 20 (10, care este punctajul G pentru a ajunge la patrat actuale, plus 10 mai mult pentru a merge pe verticala la o chiar deasupra ei). Scorul AG de 20 este mai mare de 14, deci acest lucru nu este o cale mai buna. Asta ar trebui sa faca sens daca te uiti la diagrama. Este mult mai directa pentru a ajunge la acel patrat din piata de pornire prin mutarea pur si simplu un patrat pe diagonala pentru a ajunge acolo, mai degraba decat se deplaseaza orizontal cu un patrat, si apoi pe verticala un patrat.

Cand ne-am repeta acest proces pentru toate cele 4 de patrate adiacente deja pe lista deschisa, se constata ca nici una din caile sunt imbunatatite de a merge prin piata actuale, asa ca nu schimba nimic. Deci, acum ca ne-am uitat la toate patratele adiacente, am terminat cu aceasta piata, si gata pentru a trece la urmatorul patrat.

Asa ca trecem prin lista de patrate de pe lista noastra de deschis, care este acum in jos la 7 patrate, si am alegeti una cu cel mai mic cost F. Interesant, in acest caz, exista doua patrate, cu un scor de 54. Deci, care alegem? Nu conteaza cu adevarat. In scopul de viteza, acesta poate fi mai rapid pentru a alege ultima le-ati adaugat la lista deschisa. Acest prejudecatile cautare in favoarea patrate care se gasite mai tarziu in cautare, atunci cand au ajuns mai aproape de tinta. Dar nu conteaza cu adevarat. (Tratamentului diferentiat al legaturilor este motivul pentru care doua versiuni ale unui * poate gasi cai diferite de lungime egala.)

illustration . Asa ca haideti sa o alegeti pe cea de mai jos doar, si la dreapta patrat de plecare, asa cum se arata in urmatoarea ilustratie.


[Figura 5]

De data aceasta, atunci cand vom verifica patrate adiacente vom descoperi ca unul la dreapta imediat este un patrat de perete, asa ca am ignora acest lucru. Acelasi lucru este valabil pentru cea de mai sus doar ca. Noi, de asemenea, ignora patrat chiar sub peretele. De ce? Pentru ca nu poti ajunge la acel patrat direct din piata actuale, fara de taiere pe un colt al peretelui din apropiere. Ai nevoie pentru a merge in jos si apoi sa treaca la acel patrat, se deplaseaza in jurul valorii de colt in acest proces. (Nota:.. Aceasta norma pe colturi de taiere este optionala utilizarea acestuia depinde de modul in care nodurile sunt plasate)

Asta lasa cinci piete altele. Celelalte doua patrate de mai jos patrat actuale nu se afla deja pe lista de deschis, asa ca le-am adauga si patrat curent devine mama lor. Dintre celelalte trei piete, doua sunt deja pe lista de inchis (patrat de pornire, iar cea de mai sus doar piata actuala, atat evidentiate in albastru, in diagrama), asa ca am sa le ignore. Si ultimul patrat, la stanga imediata a patrat actuale, este verificat pentru a vedea daca scorul G este orice mai mica daca te duci prin piata actuale pentru a ajunge acolo. Nr zaruri. Asa ca am terminat si gata pentru a verifica patrat urmator de pe lista noastra de deschis.

illustration below. Am repeta acest proces pana cand vom adauga patrat tinta la lista inchisa, moment in care se pare ceva de genul ilustratia de mai jos.

 
[Figura 6]

illustration . Retineti ca patrat mama pentru patrat doua patrate de mai jos patrat incepand sa schimbat de la ilustratia precedenta. Inainte de aceasta au avut un scor G de 28 si a subliniat din nou la patrat de mai sus, si spre dreapta. Acum are un scor de 20 de puncte si la patrat chiar deasupra ei. Acest lucru sa intamplat undeva de-a lungul drum pe noastre de cautare, in cazul in care scorul G a fost verificat si sa dovedit a fi mai mic cu ajutorul unui nou drum - asa-mama a fost pornit si scorurile G si F au fost recalculate. In timp ce aceasta schimbare nu pare prea important in acest exemplu, exista o multime de situatii posibile in cazul in care aceasta verificare constanta va face toate diferenta in determinarea celor mai bune calea catre tinta.

Deci, cum putem determina calea? Simplu, doar incepe la patrat rosu tinta, si locul de munca inapoi in miscare de la un patrat la mama, in urma sageti. Acest lucru va lua in cele din urma va inapoi la patrat de plecare, si asta e calea ta. illustration . Ar trebui sa arate ca imaginea de mai jos. Trecerea de la patrat incepe de la A la B destinatie patrat este pur si simplu o chestiune de trecerea de la centrul de fiecare patrat (nodul) la centrul patrat urmatoare pe calea, pana cand ajunge la tinta.


[Figura 7]

Rezumatul metodei * A

Bine, acum ca ati trecut prin explicatia, sa se metodei pas-cu-pas intr-un singur loc:

1) Adauga patrat de pornire (sau nod) pentru a deschide lista.

2) Se repeta cu urmatorul text:

a) Uita-te pentru cel mai mic cost cu o schimbare patrat F pe lista deschisa. Ne referim la acest lucru ca pe piata actuala.

b) Comutati la lista inchisa.

c) Pentru fiecare din cele 8 patrate adiacente la aceasta piata actuale...

  • In cazul in care nu este walkable sau in cazul in care se afla pe lista inchisa, ea ignora. In caz contrar, procedati in felul urmator.

  • In cazul in care nu este pe lista deschisa, se adauga la lista de deschis. Asigurati-patrat actuale mama din aceasta piata. Inregistrati F, G, H si costurile de patrat.

  • In cazul in care se afla pe lista deja deschisa, verificati pentru a vedea daca aceasta cale in acest patrat este mai bine, folosind G cost cu o schimbare ca masura. Un cost mai mic G inseamna ca aceasta este o cale mai buna. Daca este asa, schimbati-mama a patrat la patrat actuale, si se recalculeaza scorurile G si F a patrat. Daca sunteti pastrarea lista deschis sortate in functie de scor F, ar putea fi necesar sa recurga lista a tine cont de schimbare.

d) Stop cand:

  • Adauga patrat tinta la lista inchisa, caz in care drumul a fost gasit (a se vedea nota de mai jos), sau
  • Nu reusesc sa gasiti cele patrat tinta, si deschide lista este goala. In acest caz, nu exista nici o cale.   

3) Salvati calea. De lucru inapoi din piata-tinta, du-te de la fiecare patrat la patrat mama pana cand ajungeti la patrat de pornire. Aceasta este calea ta.

Nota: In versiunile anterioare ale acestui articol, sa sugerat ca se poate opri atunci cand piata tinta (sau nod) a fost adaugat la lista de deschis, mai degraba decat lista inchisa. Facand acest lucru va fi mai rapid si va oferi aproape intotdeauna calea cea mai scurta, dar nu intotdeauna. Situatii in cazul in care faci acest lucru ar putea face o diferenta atunci cand sunt cost cu o schimbare circulatie pentru a trece de la al doilea la ultimul nod la ultima (tinta), nodul poate varia in mod semnificativ - ca in cazul unui rau de trecere intre doua noduri, de exemplu.

Note privind punerea in aplicare

Acum, ca ati inteles metoda de baza, aici sunt unele lucruri suplimentare sa se gandeasca atunci cand sunt scris propriul program. Unele dintre urmatoarele materiale de referinta a programului-am scris in C + + si Blitz de baza, dar punctele sunt la fel de valabile in alte limbi.

1. Alte unitati (de evitare a coliziunilor): Daca se intampla sa te uiti atent la codul de exemplul meu, veti observa ca ignora complet alte unitati de pe ecran. Unitatile trec prin dreptul reciproc. In functie de joc, acest lucru poate fi acceptabila sau nu poate. Daca doriti sa ia in considerare alte unitati in algoritmul de pathfinding si-au a le muta in jurul valorii de una de alta, va sugerez sa luati in considerare doar unitatile care fie sunt oprite sau adiacent la unitatea de pathfinding in momentul in care calea este calculat, tratarea locatiile lor actuala, ca unwalkable. Pentru unitatile adiacente, care sunt in miscare, aveti posibilitatea sa descurajeze coliziuni prin sanctionarea noduri care se afla de-a lungul caile lor, incurajand astfel unitatea de pathfinding pentru a gasi o ruta alternativa (descris mai in temeiul # 2).

Daca alegeti sa ia in considerare alte unitati care sunt in miscare, nu si adiacent la unitatea de pathfinding, va trebui sa dezvolte o metoda pentru estimarea in cazul in care acestea vor fi la un moment dat, in timp, astfel incat acestea sa poata fi pacalit in mod corespunzator. In caz contrar, va trebui, probabil, cu poteci ciudat in cazul in care unitatile de zig-zag, pentru a evita alte unitati care nu sunt acolo.

De asemenea, veti, desigur, nevoia de a dezvolta unele cod detectarea coliziunilor, deoarece, indiferent cat de bun este calea de la momentul in care este calculat, lucrurile se pot schimba in timp. Atunci cand se produce o coliziune o unitate trebuie sa calculeze, fie o cale noua sau, in cazul in care alte unitati se misca si nu este un cap-la coliziune, asteptati pentru cealalta unitate sa iasa din calea inainte de a continua cu calea de curent.

Aceste sfaturi sunt, probabil, suficient pentru a obtine ai inceput. Daca doriti sa aflati mai multe, aici sunt cateva link-uri pe care le-ar putea gasi de ajutor:

2. Cost Variabila Terrain: In acest tutorial si programul meu de insotire, teren este doar unul din doua lucruri - walkable sau unwalkable. Dar ce se intampla daca aveti teren, care este walkable, dar la un cost mai mare miscare? Mlastini, dealuri, scari intr-o temnita, etc - toate acestea sunt exemple de teren, care este walkable, dar la un cost mai mare decat teren plat, deschis. In mod similar, un drum ar putea avea un cost mai mic decat miscare a terenului din jur.

Aceasta problema este usor de manipulat prin adaugarea cost cu o schimbare in teren, atunci cand se calculeaza costul G de orice nod dat. Pur si simplu adaugati un cost bonus la ganglionii astfel. Un algoritm de pathfinding * este deja scris pentru a gasi calea de cel mai mic cost si trebuie sa manipuleze acest lucru cu usurinta. In exemplul simplu am descris, atunci cand terenul este de numai walkable sau unwalkable, A * va cauta cel mai scurt, calea cea mai directa. Dar, intr-un mediu teren variabila-cost cu o schimbare, calea de cel mai mic cost ar putea implica calatorie o distanta mai mare - ca a lua un drum in jurul valorii de o mlastina, mai degraba decat arat direct prin ea.

Un aspect interesant este ceva suplimentar profesionistii apel fel ca cu costurile de teren variabile descrise mai sus, ati putea crea un sistem de punct suplimentar si se aplica la poteci pentru scopuri AI "cartografiere influenta.". Imaginati-va ca aveti o harta cu o gramada de unitati de aparare o trecere printr-o zona montana. De fiecare data cand computerul trimite cineva pe o cale prin care trec, ea devine omorat. Daca ati fi dorit, se poate crea o harta influenta care sanctionate noduri in cazul in care o multime de masacru are loc. Acest lucru ar invata computerul sa favorizeze mai sigure cai, si ajuta sa evite situatiile in care mut, pastrand trimiterea de trupe printr-o cale special, doar pentru ca este mai scurta (dar, de asemenea, mult mai periculos).

Cu toate acestea, o alta utilizare posibila este penalizeaza nodurile care se afla de-a lungul cailor de unitati din apropiere in miscare. Unul dintre dezavantajele A * este ca atunci cand un grup de unitati incercam sa gasim cai pentru o locatie similara, exista, de obicei, o cantitate semnificativa de suprapunere, ca una sau mai multe unitati sa incercati sa luati rute identice sau similare pentru destinatiile lor. Adaugarea de o sanctiune cu noduri deja "sustinut" de catre alte unitati vor contribui la asigurarea unui grad de separare, si pentru a reduce coliziuni. Nu trata noduri, cum ar fi unwalkable, cu toate acestea, deoarece inca mai doresc mai multe unitati pentru a putea sa-si inghesuie prin pasaje stramt in singur fisier, daca este necesar. De asemenea, ar trebui sa sanctioneze numai caile de unitati care sunt in apropierea unitatii de pathfinding nu, toate filierele, sau vei primi un comportament ciudat, ca unitati dodging evita cai de unitati care nu sunt nici pe aproape de ei la momentul respectiv. De asemenea, ar trebui sa sanctioneze numai calea de noduri care se afla de-a lungul partea actuale si viitoare de o cale, nu, noduri anterioare calea pe care au fost deja vizitat si lasati in urma.

3. Manipulare Domenii neexplorat: Ai jucat vreodata un joc pentru PC in cazul in care computerul mereu stie exact ce cale sa ia, chiar daca harta nu a fost inca explorate? In functie de joc, pathfinding ca este prea bun poate fi nerealista. Din fericire, aceasta este o problema care se pot fi tratate destul de usor.

Raspunsul este de a crea o separat "knownWalkability" matrice pentru fiecare dintre diferitii actori si adversarii de calculator (fiecare jucator, nu, fiecare unitate - care ar necesita memorie de computer mult mai mult). Fiecare matrice ar contine informatii despre domeniile in care jucatorul a explorat, cu restul de harta presupus a fi walkable pana la proba contrarie. Prin aceasta abordare, unitati vor rataci in jos se termina mort si sa faca alegeri gresite similare, pana cand au invatat drumul lor in jurul valorii. Odata ce harta este explorat, cu toate acestea, pathfinding ar functiona in mod normal.

4. Trasee mai facila: in timp ce un * va oferi in mod automat cel mai scurt, calea de costul cel mai mic, acesta nu va oferi in mod automat calea de fluida cautati. Uitati-va la calea de finala calculata in exemplul nostru (in figura 7). Pe aceasta cale, chiar primul pas este de mai jos, si la dreapta de patrat de pornire. Nu ar fi calea noastra lina in cazul in care primul pas a fost, in schimb, in mod direct de mai jos patrat patrat de pornire?

Exista mai multe modalitati de a aborda aceasta problema. In timp ce se calculeaza calea pe care ar putea penaliza noduri in cazul in care exista o schimbare de directie, adaugand o sanctiune cu scorurile lor G. Alternativ, aveti posibilitatea sa executati prin calea ta dupa ce se calculeaza, in cautarea de locuri in cazul in care alege un nod adiacent ar da o cale care arata mai bine. Pentru mai multe informatii cu privire la intreaga problema, a verifica afara Spre Pathfinding mai realist, un articol (gratuit, dar inregistrarea este necesar), la Gamasutra.com de Marco Pinter.

5. Non-patrat Domenii de cautare: In exemplul nostru, am folosit un layout simplu 2D patrat. Nu aveti nevoie pentru a utiliza aceasta abordare. Ai putea folosi zone de forma neregulata. Ganditi-va la risc tabla de joc, si tarile din acest joc. Ai putea concepe un scenariu pathfinding pentru un joc in genul asta. Pentru a face acest lucru, va trebui sa creati un tabel pentru stocarea de tarile care sunt adiacente, care, si un cost G asociat cu trecerea de la o tara la alta. Tu ar trebui, de asemenea a veni cu o metoda de estimare a H. Orice altceva ar fi tratate la fel ca in exemplul de mai sus. In loc de a folosi patrate adiacente, v-ar privi pur si simplu tarile invecinate in tabelul de la adaugarea de noi elemente la lista deschise.

In mod similar, se poate crea un sistem de punct de referinta pentru trasee pe o harta teren fix. Punctele de traseu sunt parcurse de obicei puncte de pe o cale, poate pe un drum sau tunel-cheie intr-o temnita. Ca designer de joc, ai putea pre-atribui aceste puncte de referinta. Doua puncte de referinta ar putea fi considerate "adiacente" unul de altul in cazul in care nu au nici un obstacol in calea linia directa intre acestea. Ca si in exemplul de risc, v-ar salva aceste informatii adiacenta intr-un tabel de cautare de un anumit tip si sa-l utilizati atunci cand generarea de noi elemente deschide lista. Tu ar inregistra apoi costurile asociate G (probabil prin utilizarea distanta in linie directa intre noduri) si costa H (probabil folosind o distanta de linie directa de la nodul la gol). Orice altceva ar proceda ca de obicei.

Amit Patel a scris un scurt articol patrundem in unele alternative. Pentru un alt exemplu de cautare pe o harta RPG izometric utilizand o zona non-patrati cautare, a verifica afara meu articol doua nivele A Pathfinding *.

Some Speed Tips: As you develop your own A* program, or adapt the one I wrote, you will eventually find that pathfinding is using a hefty chunk of your CPU time, particularly if you have a decent number of pathfinding units on the board and a reasonably large map. 6 Unele Sfaturi Viteza:. Asa cum va dezvolta propriul program de A *, sau sa adapteze cea pe care am scris, veti gasi in cele din urma ca este pathfinding folosind o bucata de timp hefty procesorului dumneavoastra, mai ales daca aveti un numar decent de unitati vorbeasca despre acest bord si o harta destul de mare. Daca ai citit chestii pe net, veti gasi ca acest lucru este valabil chiar si pentru profesionistii care design-jocuri, precum Starcraft sau Age of Empires. Daca vezi lucrurile incep sa incetineasca din cauza pathfinding, aici sunt cateva idei care ar putea accelera lucrurile:

  • Luati in considerare o harta mai mica sau mai putine unitati.
  • Niciodata sa nu faci calea de constatare pentru mai mult de cateva unitati la un moment dat. In schimb le-a pus intr-o lista de asteptare si a raspandirii lor pe mai multe cicluri de joc. Daca jocul se executa la, sa zicem, 40 de cicluri pe secunda, nimeni nu va observa vreodata. Dar ei vor observa daca jocul pare sa incetineasca fiecare data intr-un timp atunci cand o gramada de unitati sunt calcul toate filierele, in acelasi timp.
  • Luati in considerare utilizarea patrate mai mari (sau oricare ar fi forma pe care o utilizati) pentru harta dvs.. Acest lucru reduce numarul total de noduri cautat pentru a gasi calea. Daca sunt ambitioase, aveti posibilitatea sa elaboreze doua sau mai multe sisteme de pathfinding, care sunt utilizate in situatii diferite, in functie de lungimea traseului. Aceasta este ceea ce fac profesionistii, folosind suprafete mari pentru drumuri lungi, si apoi trecerea la cautari mai fina folosind patrate mai mici / zone atunci cand va apropiati de tinta. Daca sunteti interesat de acest concept, a verifica afara meu articol doua nivele A Pathfinding *.
  • Pentru trasee mai lungi, ia in considerare elaborarea unor cai precalculated care sunt hardwired in joc.
  • Luati in considerare de pre-prelucrare de harta pentru a vedea ce zone sunt inaccesibile din restul hartii. Eu numesc aceste zone "insule". In realitate, ele pot fi insule sau orice alta zona care este altfel pereti oprit si inaccesibile. Unul dintre dezavantajele A * este ca, daca-i spui sa caute cai pentru astfel de zone, se va cauta pe harta ansamblu, oprindu-se doar atunci cand fiecare nod accesibil patrat / au fost transformate prin liste deschise si inchise. Asta poate deseuri o multime de timp CPU. Acesta poate fi prevenita prin stabilirea, in prealabil care sunt zonele inaccesibile (prin intermediul unei rutina de inundatii-fill sau similare), ca informatiile de inregistrare intr-o serie de vreun fel, si apoi verificand-l inainte de a incepe o cautare cale.
  • Intr-un aglomerat, labirint-cum ar fi mediu, considera nodurile etichetare care nu duc nicaieri cum se termina mort. Aceste zone pot fi manual de pre-desemnate in editorul harta dvs. sau, daca sunt ambitioase, ai putea dezvolta un algoritm pentru a identifica aceste zone in mod automat. Orice colectie de noduri intr-o anumita zona fundatura ar putea fi dat un numar unic de identificare. Atunci ai putea ignora in siguranta atunci cand totul se termina mort pathfinding, oprindu-se doar sa ia in considerare noduri intr-o zona fundatura in cazul in care locatia de pornire sau de destinatie se intampla sa fie in zona special fundatura in cauza.

7. Mentinerea Deschidere lista:

Aceasta este de fapt unul dintre elementele cele mai consumatoare de timp a algoritmului A * pathfinding. De fiecare data cand a accesa lista deschis, aveti nevoie pentru a gasi patrat care are cel mai mic cost F. Exista mai multe moduri de ai putea face acest lucru. Ai putea salva elementele calea dupa cum este necesar, si pur si simplu trece prin toata lista de fiecare data cand aveti nevoie pentru a gasi cel mai mic cost cu o schimbare patrat F. Acest lucru este simplu, dar foarte lent pentru drumuri lungi. Acest lucru poate fi imbunatatita prin mentinerea unui lista sortata si hapsan pur si simplu primul punct de pe lista de fiecare data cand aveti nevoie cel mai mic cost cu o schimbare F-patrat. Cand am scris programul meu, aceasta a fost prima metoda am folosit.

Acest lucru va lucra destul de bine pentru harti mici, dar aceasta nu este solutia cea mai rapida. Un grav * programatori care doresc ceva real utilizati viteza numit un heap binar, iar acest lucru este ceea ce am folosi in codul meu. Din experienta mea, aceasta abordare va fi de cel putin 2-3 ori mai repede in cele mai multe situatii, si geometric mai rapid (10 + ori mai repede), pe trasee mai lungi. Daca sunt motivati pentru a afla mai multe despre gramezi binare, a verifica afara articolul meu, Utilizarea Heaps binar in Pathfinding A *.



Un alt obstacol posibil este modul in care clar si sa mentina structuri de date intre apeluri pathfinding. Eu personal prefer sa stoca totul in matrice. In timp ce nodurile pot fi generate, inregistrate si mentinute intr-o dinamic, orientat-obiect mod, mi se pare ca suma de timp necesar pentru a crea si sterge astfel de obiecte adauga un nivel suplimentar, inutile de regie, care incetineste lucrurile jos. Daca utilizati tablouri, cu toate acestea, veti avea nevoie pentru a curata lucrurile intre apeluri. Ultimul lucru pe care va dori sa faca in astfel de cazuri este petrece timpul zero ING totul dupa un apel pathfinding, mai ales daca aveti o harta mare.

Am evita aceasta regie prin crearea unei matrice 2d numit whichList (x, y), care desemneaza fiecare nod pe harta mea, fie ca pe lista de deschis sau inchis lista. Dupa pathfinding incercari, nu zero, aceasta matrice. In schimb am reseta valorile onClosedList si onOpenList in fiecare apel pathfinding, incrementare atat de cinci sau ceva similar pe fiecare cale constatare incercare. In acest fel, algoritmul poate ignora ca autogunoiere orice date ramase de la incercarile anterioare pathfinding. Sa pastrez, de asemenea, valori cum ar fi costurile F, G si H in matrice. In acest caz, scriu pur si simplu peste orice valori pre-existente, si nu deranjez de compensare matrice atunci cand am terminat.

Stocare a datelor in matrice multiple consuma mai multa memorie, desi, deci nu este un compromis. In cele din urma, trebuie sa folositi orice metoda pe care sunt cel mai confortabil cu.

8. Algoritmul lui Dijkstra: In timp ce A * este, in general, considerat a fi cel mai bun algoritm de pathfinding (a se vedea declama de mai sus), exista cel putin un algoritm care are alte utilizari sale - algoritmul lui Dijkstra. Lui Dijkstra este in esenta acelasi ca A *, cu exceptia nu exista nici o euristica (H este intotdeauna 0). Pentru ca nu are nici o euristice, acesta cauta prin extinderea in mod egal in toate directiile. Pe masura ce s-ar putea imagina, din cauza acestei lui Dijkstra, de obicei se termina pana explora o zona mult mai mare inainte de tinta este gasit. Acest lucru il face, in general, mai lent decat A *.

Deci, de ce-l folosesc? Uneori, nu stim in cazul in care destinatia noastra tinta este. Spune aveti o unitate de resurse de colectare care trebuie sa mergem sa luam niste resurse de vreun fel. Acesta poate sti unde sunt mai multe zone de resurse, dar vrea sa mearga la cel mai apropiat. Aici, lui Dijkstra este mai buna decat A *, deoarece nu stim care dintre ele este cel mai apropiat. Singura noastra alternativa este de a folosi in mod repetat A * pentru a gasi distanta pana la fiecare, si apoi alegeti aceasta cale. Exista, probabil, nenumarate situatii similare, in cazul in care stim ce fel de locatie am putea fi in cautarea, doriti sa gasiti cel mai apropiat, dar nu stiu unde este sau care s-ar putea fi cel mai apropiat.

Lecturi suplimentare

Bine, acum aveti elementele de baza si un sentiment de unele dintre concepte avansate. In acest moment, as sugera trecere prin vad in codul sursa mea. Pachetul contine doua versiuni, una in C + + si unul in Blitz Basic. Ambele versiuni sunt comentat foarte intens si ar trebui sa fie destul de usor de urmat, relativ vorbind. Aici este link-ul.

Daca nu aveti acces la C + + sau Blitz de baza, cele doua fisiere exe mici pot fi gasite in C + + versiunea. Versiunea de baza Blitz pot fi rulate prin descarcarea versiune demo gratuita a Blitz Basic 3D (nu Blitz Plus) la Blitz Basic site-ul web.

Tu ar trebui sa ia in considerare, de asemenea, prin citirea paginilor web de mai jos. Acestea ar trebui sa fie mult mai usor de inteles acum ca ati citit acest tutorial.

  • Amit lui A * Pagini : Aceasta este o pagina foarte larg de referinta de Amit Patel, dar poate fi un pic confuz, daca nu ati citit acest articol prima. Ei bine merita verificat. A se vedea in special proprii Amit lui ganduri pe aceasta tema.
  • Mutari inteligent: Gasirea Calea inteligenta : Acest articol de Stout Bryan la Gamasutra.com necesita inregistrare pentru a citi. Anul este gratuita si bine meritat doar pentru a ajunge la acest articol, cu atat mai putin alte resurse care sunt disponibile acolo. Program scris in Delphi de Bryan m-au ajutat sa invete A *, si este inspiratia din spatele meu Un program *. Ea descrie, de asemenea, unele alternative la A *.
  • Analiza Terrain : Acesta este un program avansat, dar interesant, articol de Dave Pottinger, un profesionist la studiourile Ensemble. Acest tip a coordonat dezvoltarea de Age of Empires si Age of Kings. Nu va asteptati sa inteleaga totul aici, dar este un articol interesant care ar putea da cateva idei proprii. Acesta include unele discutii MIP-mapping, cartografiere influenta, si alte cateva avansate de AI / pathfinding concepte.

Unele alte site-uri in valoare de verificat:

De asemenea, am foarte recomanda urmatoarele carti, care au o multime de articole pe teme pathfinding si alte AI. Ei au, de asemenea, CD-uri cu mostre de cod. Am propria-i atat. In plus, daca le-ati cumparat de la Amazon, prin aceste link-uri, voi primi cativa banuti de la Amazon. :)

Ei bine, asta este. Daca se intampla sa scrie un program care utilizeaza oricare dintre aceste concepte, mi-ar placea sa-l vad. I se poate ajunge la

Published (Last edited): 13-09-2011 , source: http://www.policyalmanac.org/games/aStarTutorial.htm