Share
Pathfinding este omniprezent în jocuri. Deci, este important să înțelegem implicațiile care sunt prezente când se utilizează algoritmi precum A *. În acest tutorial vom aborda o metodă relativ nouă pentru căutarea unor lumi bazate pe rețele: Jump Point Search, care poate accelera A * prin ordine de mărime.
Notă: Deși acest tutorial este scris folosind AS3 și Flash, ar trebui să puteți utiliza aceleași tehnici și concepte în aproape orice mediu de dezvoltare a jocului.
Această implementare se bazează pe articolul original și pe articolul despre JPS găsit aici: Jump Point Search.
Implementarea bazată pe Lua, Jumper, a fost folosită pentru a ajuta la unele aspecte ale implementării.
Faceți clic pe SWF pentru a vă concentra, apoi deplasați mouse-ul peste zonele non-blocante ale hărții pentru ca NPC-urile să încerce să ajungă la ele. Apăsați Space pentru a comuta între A *, Jump Point Search și ambele.
Fără Flash? Consultați în schimb videoclipul YouTube:
Implementarea demonstrativă de mai sus utilizează AS3 și Flash cu Starling Framework pentru redarea accelerată a GPU și biblioteca poligonal-ds pentru structurile de date.
Pathfinding este adesea folosit în jocuri video și ești sigur că te vei bate în ea la un moment dat în timpul carierei tale de dezvoltare a jocului. Utilizarea sa principală este de a oferi comportament inteligent în mișcare entităților artificiale (NPC), pentru a evita ca acestea să se lovească de lucruri (adesea).
În unele jocuri, avatar-ul jucătorului este, de asemenea, supus traseului de traseu (jocuri de strategie, multe RPG-uri și jocuri de aventură). Așadar, puteți presupune că problema traseului de drum este rezolvată, dar, din nefericire, nu este cazul; nu există nici un glonț de argint pe care să-l puteți folosi și pur și simplu să-l faceți cu el.
Și chiar și în jocurile mari AAA, veți găsi în continuare lucruri amuzante precum:
Este posibil să nu existe un glonț de argint, dar există un glont: algoritmul A * (stea). În acest tutorial vom vedea o scurtă trecere în revistă a lui A * și cum să-l grăbești folosind un alt algoritm, Jump Point Search.
În primul rând avem nevoie de o modalitate de a reprezenta lumea jocurilor noastre într-un mod care poate fi folosit de un algoritm de căutare.
Unul dintre cele mai importante lucruri pe care trebuie să le iei în considerare atunci când te gândești la modul de abordare a jocului este reprezentare mondială. Cum se păstrează datele din zonele acceptabile și obstacolele organizate cu structuri de programare în memorie?
Cea mai simplă reprezentare pe care o puteți utiliza este o structură bazată pe grid, unde nodurile de cale sunt organizate într-o rețea și pot fi reprezentate de o matrice 2D. Vom folosi această reprezentare în acest tutorial. În mod specific, va fi o reprezentare a opțiunilor în grilă: permite mișcarea în direcții drepte și diagonale.
Cerințele dvs. ar putea fi diferite, astfel că este posibil ca această structură să nu vă fie potrivită. Bine este faptul că, cu unele procesare (de obicei făcut offline) puteți schimba reprezentările pathfinding la alte formate. Alternative la abordarea bazată pe rețea ar include lucruri precum poligonul (obstacolele reprezentate de poligoane) sau ochiurile de navigație (zone de navigație reprezentate de poligoane); acestea pot reprezenta aceleași date cu mai puține noduri.
Alte date care pot fi stocate în reprezentarea hărților sunt cheltuieli: cât costă călătoria de la un nod la altul. Acest lucru poate fi folosit pentru AI pentru a determina calea care, de exemplu, preferă drumurile peste terenul obișnuit (ceea ce face ca costul drumului să fie mai mic decât terenul).
Jump Point Search este proiectat special pentru o reprezentare a hărților pe o grilă cu opt căi, așa că vom folosi asta. De asemenea, în forma sa de vanilie nu acceptă hărți ponderate. (În secțiunea finală voi discuta despre un posibil mod de a remedia acest lucru.)
Acum, avem o reprezentare la nivel mondial să examinăm rapid implementarea A *. Este un algoritm de căutare a grafului ponderat, care utilizează euristicile (puțin "sugestii") despre cum să căutați cel mai bine zona de la nodul de început până la capătul nodului.
Vă recomandăm să verificați această vizualizare a algoritmilor de căutare:
PathFinding.js - vizual. Redarea cu acesta poate spori intuiția dvs. din ceea ce face de fapt algoritmul - plus este distractiv!
Pentru trasarea pe traseu folosind A * în grilaj rectangular facem următoarele:
1. Gasiti nodul cel mai apropiat de pozitia dumneavoastra si declarati nodul de start si puneti-l in lista deschisa. 2. În timp ce există noduri în lista deschisă: 3. Alegeți nodul din lista deschisă având cel mai mic scor F. Puneți-l pe lista închisă (nu doriți să o luați din nou). 4. Pentru fiecare vecin (celula adiacentă) care nu se află în lista închisă: 5. Setați părintele său la nodul curent. 6. Calculați scorul G (distanța de la nodul de pornire la acest vecin) și adăugați-l în lista deschisă 7. Calculați scorul F adăugând euristică la valoarea G.postări asemănatoare
Heuristica se bazează, în esență, pe o șansă ca nodul care va fi evaluat să conducă la obiectiv. Heuristica poate face o mare diferență în eficiența algoritmilor de trasare a traseului deoarece acestea tind să limiteze numărul de noduri care trebuie să fie vizitate. Vom folosi distanța Manhattan pentru scopurile noastre (ceea ce înseamnă că nodurile mai aproape de obiectiv vor avea un număr mai mic):
funcția privată manhattanDistance (start: Nod, sfârșit: nod): int return Math.abs (end.x - start.x) + Math.abs (end.y - start.y);
Aceasta este mai mult sau mai puțin. Oprim algoritmul când găsim nodul de țintă și apoi urmărim folosind variabila parentală a nodului pentru a construi calea.
Algoritmi de căutare pot fi utilizați și pentru alte lucruri. A * este un algoritm de căutare grafic general ponderat și poate fi folosit pe orice astfel de grafic. Acest lucru poate acoperi și alte domenii ale AI, cum ar fi găsirea măsurilor optime pentru a atinge anumite obiective: a arunca o bomba sau a alerga pentru adăpost și a încerca să se strecoare în spatele unui inamic?
În dezvoltarea jocurilor avem nevoie să facem lucrurile repede, atunci când actualizăm jocurile la 60 de cadre pe secundă, la fiecare milisecundă. Chiar dacă A * se comportă destul de bine pentru anumite utilizări, există nevoia de a face mai rapid sau de a folosi mai puțină memorie.
Alegerea reprezentării este primul lucru care va avea un impact asupra performanței căutării și a alegerii algoritmului pathfinding. Dimensiunea graficului care este căutat va avea o mare corelație cu modul în care efectuează traseul dvs. de traseu (ceea ce are sens, este mai ușor să vă găsiți în camera dvs. decât într-un oraș mare).
Apoi, veți lua în considerare optimizările la nivel mai înalt, care implică, de obicei, gruparea datelor în regiuni mai mici și apoi căutarea acestora în timp ce căile de rafinare ulterioare în regiunile mai mici călătorite. De exemplu, dacă doriți să mergeți la un restaurant dintr-un oraș vecin, mai întâi luați în considerare modul în care ajungeți din orașul dvs. în acel oraș și, odată ce vă aflați în acel oraș, limitați căutarea în zona în care se află restaurantul , ignorând restul. Acest lucru ar include lucruri cum ar fi mlaștini, eliminați sfârșitul mort și HPA *.
La cel mai jos nivel trebuie să faceți căutarea. Ați ales reprezentarea datelor și posibilele abstracții și apoi conectați-le într-un algoritm care va alege nodurile, călătorind aici și acolo, căutând scopul. Acești algoritmi sunt de obicei bazați pe algoritmul de căutare A * cu posibile modificări. În cazurile mai simple, puteți să scăpați folosind A * drept, care vă oferă simplitatea. Am furnizat o implementare bazată pe grilă în descărcarea sursei.
Deoarece acest tutorial este despre implementarea Jump Point Search, graficul de trasare a traseului va fi reprezentat cu o grilă. În mod specific, trebuie să fie o rețea de opt căi, deoarece algoritmul o folosește în mod direct.
Ce înseamnă căutarea în Jump Point este de a elimina o mulțime de noduri intermediare în anumite tipuri de combinații ale rețelei. Ea sare peste o grămadă dintre acestea pe care le-ați adăuga la lista deschisă și lista închisă, precum și alte calcule, în favoarea unei mai multe procesări atunci când alegeți următorul nod.
Ca și cu A *, alegem din scena deschis nodul cu cel mai mic scor F. Dar aici lucrurile încep să devină interesante. În loc să alegem nodurile adiacente, vom numi această funcție ca să o facem pentru noi:
funcția identifică succesorii (actual: nod, început: nod, sfârșit: nod): Vector.succesori var: Vector. = Vector nou. (); Var vecinii: Vector. = nodeNeighbors (actual); pentru fiecare (var vecin: Nod în vecini) // Direcția de la nodul curent la vecin: var dX: int = clamp (neighbour.x - current.x, -1, 1); var dY: int = clemă (vecin.y - curent.y, -1, 1); // Încercați să găsiți un nod pentru a sări la: var jumpPoint: Node = salt (curent.x, curent.y, dX, dY, început, sfârșit); // Dacă se găsește adăugați-o în listă: if (jumpPoint) successors.push (jumpPoint); succesori retur;
Ceea ce face acest lucru este eliminarea nodurilor care nu sunt interesante pentru calea noastră. Pentru aceasta folosim direcția de la părinte ca principală îndrumare. Iată exemple de tăiere a nodurilor pe care le ignorăm pentru direcțiile orizontale și verticale:
Exemplu de situație de tăiere orizontală.
În cod, acest lucru se va încheia ca o serie de dacă declarații de verificare pentru aceste situații. Puteți vedea exemplul aici, descriind cazul corect din imagine:
dacă _world.isBlocked (curent.x + direcțiaX, curent.y)) if (_world.isBlocked (curent.x, curent.y + 1)) // a crea un nod cu noua poziție neighbours.push (Node.pooledNode (curent.x + direcțiaX, curent.y + 1));
După ce am ales vecinul, încercăm să găsim un punct de salt, care este un nod care poate fi atins de cel curent, dar nu neapărat într-un singur mod. Pentru ao pune mai formal, ceea ce face JPS este eliminarea simetriei dintre căi - fiecare are o permutare diferită a acelorași mișcări:
Deci, pentru spațiile mari deschise putem câștiga uriașe. Iată cum funcționează metoda de salt:
(cX: int, cY: int, dX: int, dY: int, start: nod, cap: nod): nod // cX, cY - Poziția nodului curent, dX, nod pe care îl vom lua în considerare: var nextX: int = cX + dX; var urmăY: int = cY + dY; // Daca este blocat, nu putem sari aici daca (_world.isBlocked (nextX, nextY)) returneaza null; // Dacă nodul este obiectivul, returnați-l dacă (nextX == end.x && nextY == end.y) returnează un nou nod (nextX, nextY); // Cauza diagonală dacă (dX! = 0 && dY! = 0) if (/ * ... Verificați vecinul forțat diagonală ... * /) return Node.pooledNode (nextX, nextY); // Verificați direcțiile orizontale și verticale pentru vecinii forțați // Acesta este un caz special pentru direcția diagonală dacă (salt (nextX, nextY, dX, 0, start, sfârșit)! = Null || salt (nextX, nextY, 0) , dY, start, sfârșit)! = null) retur Node.pooledNode (nextX, nextY); altceva // Caz orizontal dacă (dX! = 0) if (/ * ... Verifică orizontală forțată Vecină ... * /) retur Node.pooledNode (nextX, nextY); /// Vertical case altceva if (/ * ... Vertical Forced Neighbor Check ... * /) retur Node.pooledNode (nextX, nextY); /// Dacă vecinul forțat nu a fost găsit, încercați saltul de întoarcere în saltul următor (nextX, nextY, dX, dY, start, end);
Am eliminat verificările vecinului forțat din instrucțiunile if, deoarece acestea sunt destul de mari. Ele constau, în principiu, din verificările care sunt similare cu cele când am selectat mai întâi vecinii pentru un nou nod (o mulțime de verificări pentru a vedea dacă celulele sunt blocate). Acestea servesc scopului de a detecta când ne este permis să avem presupunerile noastre privind simetria.
Cazul diagonal este special și trebuie să ne uităm nu doar pentru vecinii forțați pe direcțiile diagonale, ci și pe direcțiile orizontale și verticale, iar dacă oricare dintre aceștia nu reușește, trebuie să punem un nod forțat ca punct de salt. De asemenea, trebuie să luăm în considerare un caz special al nodului de țintă, unde metoda de salt se termină.
De fiecare dată când nu găsim un nod de căutare, apelăm recursiv funcția de salt în direcția specificată. În demo-ul pe care l-am derulat de fapt, acest apel recursiv, deoarece acest lucru va fi numit mult. (În testarea mea, această performanță a crescut cu un factor de două.)
Asta face JPS; rezultatul final este nodurile noi pentru A * pentru a verifica și vom continua cu algoritmul. Când se găsește nodul de țintă, reconstruim traseul și îl returnează.
JPS poate sări peste multe noduri atunci când caută, ceea ce poate da îmbunătățiri rapide ale vitezei (în proiectul meu este de aproximativ 30x peste A *), dar are un cost.
Ea funcționează cel mai bine pe o rețea uniformă, dar poate fi făcută pentru a lucra cu non-uniforme folosind o modificare suplimentară, marcând vecinii ca fiind forțată în cazul în care există o tranziție la un nod cu costuri diferite (cel mai bine să se utilizeze costuri discrete).
Într-un joc pe care lucrez, grila este uniformă, cu excepția drumurilor, care costă mult mai puțin decât mersul pe teren obișnuit. (Se pare mult mai bine atunci când personajul respectă acest lucru.) În cele din urmă am rezolvat acest lucru prin precompunerea unor valori ale pozițiilor rutiere. Atunci când se inițiază trasarea căutării, algoritmul caută posibile puncte mai apropiate de calea de la nodurile de start și de la goluri, apoi caută un grafic special de nivel al drumurilor (care este precompus) și apoi utilizează JPS pentru a căuta zone de teren.
O notă rapidă despre depanare. Depistarea acestor tipuri de algoritmi poate fi foarte dificilă și este aproape sigur că prima implementare va avea ceva greu de găsit. Puteți să vă faceți o favoare și să construiți un fel de vizualizare funcțional și să desenați ce se întâmplă atunci când rulează algoritmul.
Dacă primiți o eroare, ar trebui să reduceți domeniul (dimensiunea grilei) la minimum, ceea ce vă permite să reproduceți problema și să încercați de acolo. După cum probabil puteți ghici, prima mea implementare de JPS nu a funcționat imediat!
Accentsconagua