Share
În acest tutorial vă voi explica vector fieldfinding și avantajele sale față de algoritmii de traducere mai tradiționali, cum ar fi Dijkstra. O înțelegere de bază a algoritmului lui Dijkstra și a câmpurilor potențiale vă va ajuta să înțelegeți acest articol, dar nu este necesar.
Pathfinding este o problemă cu multe soluții și fiecare are argumente pro și contra. Mulți algoritmi de trasare a traseului funcționează calculând o cale spre obiectiv pentru fiecare pathfinder, ceea ce înseamnă că trasarea pe traseu va dura de două ori mai mult pentru a calcula cu două ori mai mulți factori de căutare. Acest lucru este acceptabil în multe situații, dar atunci când lucrăm cu mii de pasionați, este posibilă o abordare mai eficientă.
Cunoscut ca vector fieldfinding, această abordare calculează calea de la obiectiv la fiecare nod din grafic. Pentru a consolida această explicație a traseului vectorial al câmpului, voi explica algoritmul folosind exemplul meu de implementare.
Notă: Vectorul de trasare a vectorilor poate fi abstracționat la noduri și grafice în general; tocmai pentru că eu explic acest lucru folosind gigantul meu și abordarea bazată pe grilă nu înseamnă că acest algoritm este limitat la lumini bazate pe dale!
Vectorul de trasare a câmpului vectorial este compus din trei etape.
Acest videoclip vă arată rezultatele finale și apoi vă oferă o prezentare generală a conceptelor prezentate în tutorialul complet de mai jos:
Diagrama termică stochează distanța parcursă de la țintă la fiecare țiglă de pe hartă. Distanța distanței este diferită de distanța euclidiană prin faptul că este un calcul al distanței dintre două puncte care trec numai prin terenul traversabil. Un GPS, de exemplu, calculează întotdeauna distanța parcursă, drumurile fiind singurul teren traversabil.
Mai jos, puteți vedea diferența dintre distanța parcursă și distanța liniară de la obiectiv (marcată cu roșu) la o piesă arbitrară (marcată în roz). Placile ne-traversabile sunt desenate in verde. După cum puteți vedea, distanța parcursă (afișată în galben) este 9, în timp ce distanța liniară (prezentată în albastru deschis) este aproximativ 4.12.
Numerele din partea stângă sus a fiecărei plăci indică distanța parcursă de obiectivul calculată de algoritmul de generare a căldurii. Rețineți că există mai mult de o posibilă distanță-cale între două puncte; în acest articol, suntem interesați doar de cea mai scurtă.
Algoritmul de generare a căldurii este a wavefront algoritm. Începe la țintă cu o valoare de 0, și apoi curge spre exterior pentru a umple întreaga regiune traversabilă. Există doi pași pentru algoritmul wavefront:
Accentsconagua
0.distanța parcursă de piesa precedentă + 1.Notă: Algoritmul wavefront rulează pur și simplu o primă căutare pe grilă și stocând câți pași au fost necesare pentru a ajunge la fiecare țiglă de-a lungul drumului. Acest algoritm este uneori numit și algoritmul brushfire.
Acum, că distanța parcursă de la fiecare țiglă până la obiectiv a fost calculată, putem determina cu ușurință calea care trebuie luată pentru a ajunge mai aproape de obiectiv. Este posibil să se facă acest lucru la timpul de execuție pentru fiecare pathfinder în fiecare cadru, dar este adesea mai bine să se calculeze un câmp vectorial odată și apoi toate căile de navigare să se refere la câmpul vectorial în timpul execuției.
Câmpul vectorial stochează pur și simplu un vector care indică în jos gradientul funcției de distanță (spre țintă) la fiecare țiglă. Iată o vizualizare a câmpului vectorial, vectorii îndreptându-se spre centrul țiglei de-a lungul celei mai scurte căi spre țintă (redenumită din nou în roșu).
Acest câmp vectorial este generat de câte o țiglă, privindu-se harta de căldură. Componentele x și y ale vectorului sunt calculate separat, după cum se arată în pseudocodul de mai jos:
Vector.x = left_tile.distance - right_tile.distance Vector.y = up_tile.distance - down_tile.distance
Notă: Variabilele de distanțe ale fiecărei plăci stochează distanța parcursă la țintă, calculată de algoritmul wavefront de mai sus.
Dacă oricare dintre plăcile la care se face referire (stânga / dreapta / sus / în jos) nu este traversabilă și, prin urmare, nu este stocată o distanță utilă, distanța asociată plăcii curente este folosită în locul valorii lipsă. Odată ce vectorul traseului a fost calculat aproximativ, este normalizat pentru a evita inconsecvențele mai târziu.
Acum că câmpul vectorial a fost calculat, este foarte ușor să se calculeze mișcarea pentru un traseu de cale. Presupunând că vector_field (x, y) returnează vectorul pe care l-am calculat anterior la țiglă (X y), și că dorit_velocitatea este un scalar, pseudocodul pentru a calcula viteza unei particule la țiglă (X y) arata asa:
velocity_vector = câmp vector_ (x, y) * dorit_velocitate
Particulele trebuie pur și simplu să înceapă în direcția indicată de vector. Acesta este cel mai simplu mod de a face acest lucru, dar sistemele de mișcare mai complicate pot fi implementate cu ușurință utilizând câmpurile de curgere.
De exemplu, tehnicile explicate în Comportamentul de înțelegere a direcției ar putea fi aplicate mișcării pathfinder. Într - o astfel de situație, velocity_vector calculat mai sus, ar fi folosit ca viteza dorită și comportamentele direcției ar fi folosite pentru a calcula mișcarea reală la fiecare pas de timp.
Când se calculează mișcarea, există o problemă care uneori poate apărea, cunoscută sub numele de local optima. Acest lucru se întâmplă atunci când există două căi optime (cele mai scurte) care trebuie luate pentru a ajunge la obiectivul dintr-o anumită țiglă.
Această problemă poate fi văzută în imaginea de mai jos. Plăcuța (afișată în roz) imediat în stânga centrului peretelui are un vector al cărui componente (x și y) sunt egale cu 0.
Oficiali locali care cauzează călătorii; acestea se vor referi la câmpul vectorial care nu va indica o direcție în care să intră. Când se întâmplă acest lucru, traseele vor rămâne în aceeași locație dacă nu este implementată o remediere.
Cea mai elegantă cale (am găsit) pentru a rezolva problema este de a subdiviza atât heatmap cât și câmpul vectorial o singură dată. Fiecare placă termică și placă de câmp vectorială au fost acum împărțite în patru plăci mai mici. Problema rămâne aceeași cu o rețea subdivizată; aceasta a fost doar puțin redusă.
Trucul real care rezolvă problema optimă locală este să adăugați inițial patru noduri de țintă, în loc de unul singur. Pentru aceasta trebuie pur și simplu să modificăm primul pas al algoritmului de generare a căldurii. Când am adăugat doar un singur gol, cu o distanță de cale de 0, adăugăm acum cele patru plăci care se află cel mai aproape de obiectiv.
Există mai multe modalități de alegere a celor patru plăci, dar modul în care acestea sunt alese este în mare măsură irelevant - atâta timp cât cele patru plăci sunt adiacente (și traversabile), această tehnică ar trebui să funcționeze.
Aici este pseudocodul modificat pentru generarea de căldură:
0.distanța parcursă de piesa precedentă + 1.Și acum, aici sunt rezultatele finale, arătând clar că problema optimă locală a fost eliminată:
Deși această soluție este elegantă, ea este departe de a fi ideală. Utilizarea acestuia înseamnă că calcularea câmpului de căldură și a vectorului durează de patru ori mai mult din cauza numărului crescut de plăci.
Alte soluții necesită efectuarea de controale și apoi determinarea în ce direcție să se procedeze de la caz la caz, ceea ce încetinește semnificativ calculele privind mișcarea particulelor. În cazul meu, subdivizarea hărților a fost cea mai bună opțiune.
Sperăm că acest tutorial te-a învățat cum să implementi pathfinding pe bază de țintă într-o lume bazată pe țiglă. Rețineți că acest tip de trasare este, în centrul său, simplu: particulele urmăresc gradientul funcției de distanță spre obiectiv.
Implementarea este mai complexă, dar poate fi împărțită în următorii trei pași simplificabili:
Sper să văd că oamenii se extind asupra ideilor prezentate aici. Ca întotdeauna, dacă aveți întrebări, nu ezitați să le întrebați în comentariile de mai jos!
