Share
A * pathfinding bazat pe grilă funcționează bine pentru jocuri în care personajele se pot mișca liber atât de-a lungul axelor x cât și y. Problema aplicării acestui fapt la platformeri este aceea că mișcarea pe axa y este puternic restricționată, datorită forțelor gravitaționale simulate.
În acest tutorial, voi oferi o privire de ansamblu asupra modului de modificare a unui algoritm standard A * pentru a lucra pentru platformeri prin simularea acestor restricții gravitaționale. (În următoarea parte, voi trece prin codarea algoritmului.) Algoritmul adaptat ar putea fi folosit pentru a crea un caracter AI care urmează playerului sau pentru a arăta jucătorului o rută spre obiectivul lor, de exemplu.
Presupun ca aici sunteti deja familiarizat cu A * pathfinding, dar daca aveti nevoie de o introducere, A * Pathfinding for Beginners de la Patrick Lester este excelent.
Puteți reda demonstrația Unity sau versiunea WebGL (64MB) pentru a vedea rezultatul final în acțiune. Utilizare WASD pentru a muta caracterul, stânga-clic pe un loc pentru a găsi o cale pe care să o puteți urma pentru a ajunge acolo și Click dreapta o celulă pentru a comuta la sol în acel punct.
Până la sfârșitul acestei serii, am adăugat și platforme unidirecționale, am extins codul pentru a trata diferite dimensiuni de caracter și am codificat un bot care poate urma automat calea! Check out demo-ul Unity aici (sau versiunea de 100MB + WebGL).
Înainte de a putea adapta algoritmul de urmărire a traseului, trebuie să definim în mod clar care sunt formele pe care se pot obține căile.
Să spunem că personajul nostru se ocupă o celulă, și poate sări trei celule înalt.
Nu vom permite ca personajul nostru să se miște în diagonală prin celule, pentru că nu vrem să treacă printr-un teren solid. (Adică nu vom permite să se miște prin colțul unei celule, numai prin partea de sus, de jos, stânga sau dreapta). Pentru a vă deplasa într-o celulă învecinată în diagonală, caracterul trebuie să deplaseze o celulă în sus sau în jos , și o celulă la stânga sau la dreapta.
Deoarece înălțimea saltului caracterului este de trei celule, atunci ori de câte ori sare, după ce sa mutat de trei ori, nu ar trebui să se poată muta sus mai multe celule, dar ar trebui să poată trece în continuare la latură.
Pe baza acestor reguli, iată un exemplu al traseului pe care personajul îl va lua în timpul saltului maxim al distanței:
Desigur, caracterul poate sări direct în sus sau cu orice combinație de mișcări stânga și dreaptă, dar acest exemplu arată tipul de aproximare pe care trebuie să-l îmbrățișăm atunci când calculam calea utilizând grila.
Fiecare dintre celule din cale va trebui să păstreze date despre înălțimea de salt, astfel încât algoritmul nostru să poată detecta că jucătorul nu poate sări mai sus și trebuie să înceapă să cadă.
Să începem prin atribuirea valorii de salt a fiecărei celule prin creșterea acesteia cu câte una, fiecare celulă, atâta timp cât saltul continuă. Desigur, atunci când caracterul este la sol, valoarea saltului ar trebui să fie 0.
Iată regula aplicată aceleiași căi de salt de la distanță maximă:
Celula care conține a 6 marchează cel mai înalt punct din cale. Acest lucru are sens, deoarece aceasta este de două ori valoarea înălțimii maxime a saltului personajului, iar caracterul se substituie mutând o celulă în sus și o celulă laterală, în acest exemplu.
Rețineți că, dacă caracterul sare direct în sus și vom continua să creștem valoarea saltului cu câte o celulă, atunci aceasta nu mai funcționează, deoarece în acest caz cea mai mare celulă ar avea o valoare de salt 3.
Să ne modificăm regula pentru a mări valoarea saltului la următorul număr par ori de câte ori caracterul se mișcă în sus. Apoi, dacă valoarea saltului este uniformă, caracterul se poate deplasa în stânga, în dreapta sau în jos (sau în sus, dacă nu a atins o valoare salt 6 totuși) și dacă valoarea saltului este ciudată, caracterul se mișcă numai în sus sau în jos (în funcție de faptul dacă au atins încă vârful saltului).
Iată ce arată pentru un salt în sus:
Iată un caz mai complicat:
Iată cum se calculează valorile saltului:
După cum puteți vedea, cu acest tip de numerotare, știm exact când caracterul atinge înălțimea maximă de salt: este celula cu valoarea saltului egală cu de două ori înălțimea maximă de salt a caracterelor. Dacă valoarea saltului este mai mică decât aceasta, caracterul se poate mișca în continuare; în caz contrar, trebuie să ignorăm nodul direct deasupra.
Acum, că suntem conștienți de tipul de mișcări pe care personajul îl poate face pe grila, să luăm în considerare următoarele configurații:
Celula verde în poziție (3, 1) este caracterul; celula albastră în poziție (2, 5) este obiectivul. Să desenați un traseu pe care algoritmul A * ar putea alege mai întâi să încerce să atingă obiectivul @
Numărul galben din colțul din dreapta sus al unei celule reprezintă valoarea saltului celulei. După cum puteți vedea, cu un salt direct în sus, personajul poate sări trei plăci în sus, dar nu mai departe. Nu e bine.
S-ar putea să găsim mai mult noroc pe un alt traseu, așa că haideți să ne derulam căutările și să reluăm din nou nodul (3, 2).
După cum puteți vedea, săriți pe blocul din dreapta personajului l-ați permis să sară destul de înalt pentru a ajunge la țintă! Cu toate acestea, există o mare problemă aici ...
Probabil că prima cale pe care o va lua algoritmul este prima pe care am analizat-o. După ce a luat-o, algoritmul nu va ajunge prea departe și va ajunge înapoi la nod (3, 2). Apoi poate căuta prin noduri (4, 2), (4, 3), (3, 3) (din nou), (3, 4) (din nou), (3, 5), și, în final, celula țintă, (2, 5).
Într-o versiune de bază a algoritmului A *, dacă un nod a fost deja vizitat, atunci nu trebuie să îl procesăm din nou. În această versiune, totuși, o facem. Acest lucru se datorează faptului că nodurile nu se disting numai prin coordonatele x și y, ci și prin valorile saltului.
În prima noastră încercare de a găsi o cale, valoarea saltului la nod (3, 3) a fost 4; în a doua încercare, a fost 3. Deoarece în a doua încercare valoarea de salt la acea celulă a fost mai mică, aceasta însemna că am putea obține potențial mai mare de acolo decât am putea în timpul primei încercări.
Înseamnă practic acest nod (3, 3) cu o valoare de salt 4 este a nod diferit decât nodul la (3, 3) cu o valoare de salt 3. Grila trebuie, în esență, să devină tridimensională la unele coordonate pentru a se potrivi pentru aceste diferențe, cum ar fi:
Nu putem schimba pur și simplu valoarea saltului nodului la (3, 3) din 4 la 3, deoarece unele căi utilizează același nod de mai multe ori; dacă am fi făcut asta, vom suprascrie practic nodul anterior și asta ar corupe, bineînțeles, rezultatul final.
Am avea aceeași problemă dacă prima cale ar fi atins obiectivul in ciuda valorile saltului mai mare; dacă am fi înlocuit unul dintre noduri cu unul mai promițător, atunci nu am avea nici o modalitate de a recupera calea inițială.
Amintiți-vă, este algoritmul care folosește o abordare bazată pe rețea; în teorie, jocul și nivelurile sale nu trebuie să.
Este important ca personajul să aibă macar la fel de multă libertate de mișcare pe care algoritmul o așteaptă - și de preferință un pic mai mult decât atât.
Dacă mișcarea caracterului corespunde exact constrângerilor algoritmului, nu este o abordare viabilă, datorită naturii discrete a rețelei și a dimensiunii celulei rețelei. Este posibil să codificați fizica în așa fel încât algoritmul să o facă mereu găsiți o cale dacă există una, dar care vă cere să construiți fizica în acest scop.
Abordarea pe care o iau în acest tutorial este să potrivesc algoritmul fizicii jocului, nu invers.
Principalele probleme apar în cazurile de margine atunci când libertatea de libertate a libertății așteptate a algoritmului nu se potrivește cu adevărata libertate de mișcare a personajului în joc.
Să presupunem că AI permite sărituri de sase celule lungi, dar fizica jocului permite o sari de sapte celule. Dacă există o cale care necesită un salt mai lung pentru a ajunge la obiectiv în cel mai scurt timp, atunci botul va ignora acea cale și va alege unul mai conservator, crezând că saltul mai lung este imposibil.
Dacă există o cale care necesită un salt mai lung și nu există altă modalitate de a atinge obiectivul, atunci pathfinder-ul va ajunge la concluzia că obiectivul nu poate fi atins.
Dacă, dimpotrivă, algoritmul crede că este posibil să sară șapte celule distanță, dar fizica jocului permite, de fapt, doar un salt cu șase celule, atunci botul poate fie să urmeze calea greșită și să cadă într-un loc din care nu poate obține sau încercați din nou să găsiți o cale și să primiți același rezultat incorect, cauzând o buclă.
(Din aceste două probleme, este preferabil să lăsăm fizica jocului să permită mai multă libertate de mișcare decât așteaptă algoritmul.)
Primul mod de a vă asigura că algoritmul este întotdeauna corect este să aveți niște niveluri pe care jucătorii nu le pot modifica. În acest caz, trebuie doar să vă asigurați că orice teren pe care îl proiectați sau generați funcționează bine cu AI de călătorie.
A doua soluție la aceste probleme este de a optimiza algoritmul, fizica sau ambele, pentru a vă asigura că se potrivesc. După cum am menționat mai devreme, acest lucru nu înseamnă că trebuie să se potrivească exact; de exemplu, dacă algoritmul crede că personajul poate sări cinci celule în sus, este bine să setați saltul real maxim la 5.5 celule mari. (Spre deosebire de algoritm, fizica jocului poate folosi valori fractionale.)
În funcție de joc, ar putea fi, de asemenea, adevărat că botul AI care nu găsește o cale existentă nu este o afacere uriașă; acesta va renunța pur și simplu și va reveni la postul său, sau doar sta și așteptați pentru jucător.
În acest moment, ar trebui să aveți o înțelegere conceptuală decentă cu privire la modul în care poate fi adaptat modul de trasare A * unui platformer. În următorul tutorial, vom face acest lucru concret, adaptând de fapt un algoritm A * pathfinding existent pentru a implementa acest lucru într-un joc!
Accentsconagua