Share
Care este cea mai sigură cale de urmat, unde sunt cei mai mulți inamici aflați și unde este cel mai apropiat pachet de sănătate? Aceste întrebări comune privind relațiile spațiale pot fi rezolvate eficient cu o rutină matematică numită Voronoi. Până la sfârșitul acestui tutorial veți avea instrumentele și cunoștințele necesare pentru a vă analiza hărțile și pentru a produce informații care vor fi esențiale pentru realismul și succesul AI.
postări asemănatoareDacă sunteți interesat să citiți mai multe despre AI (inteligență artificială), asigurați-vă că verificați:
O relație spațială este orice descrie modul în care un obiect dintr-un spațiu este legat de altul. De exemplu: distanța dintre ele, cât spațiu acoperă fiecare și dacă zonele se suprapun sau câte obiecte se află într-o zonă.
Aceste relații apar în jocuri video tot timpul și pot oferi informații foarte utile AI sau chiar jucătorului.
A Diagrama Voronoi descrie relația spațială dintre punctele care se află aproape unul de celălalt sau de cei mai apropiați vecini. Este un set de poligoane de conexiune derivate din puncte sau locații. Fiecare linie a unei "regiuni" Voronoi se află la jumătatea distanței dintre două puncte.
Aici, să examinăm o imagine pentru a vă simți:
Aici puteți vedea că fiecare linie este exact la jumătatea distanței dintre două puncte și că toți se întâlnesc împreună în mijloc. Să adăugăm mai multe puncte la scenă și să vedem ce se întâmplă:
Acum, asta devine tot mai interesant! Începem să obținem regiuni reale.
Deci ce ne spune fiecare regiune? Știm că, în timp ce suntem în interiorul unei regiuni, suntem siguri că suntem mai aproape de punctul unic care se află și în interiorul regiunii. Acest lucru ne spune foarte multe despre ceea ce este aproape de noi și este relația spațială fundamentală în diagramele Voronoi.
Inversa unei diagrame Voronoi se numește Triangulația Delaunay. Această diagramă constă din linii de la fiecare punct la cei mai apropiați vecini și fiecare linie este perpendiculară pe marginea Voronoi pe care o traversează. Iată cum arată:
Liniile albe sunt liniile Delaunay. Fiecare linie Delaunay corespunde unei singure margini Voronoi. Deși la prima vedere se pare că se suprapun mai multe margini, să aruncăm o privire mai atentă și să clarificăm ceea ce vedem.
Aici linia verde Delaunay este legată de marginea rozului Voronoi. Trebuie doar să vă imaginați marginea roz care se extinde mai departe și apoi veți vedea că ei trec.
Cu Delaunay puteți vedea că acum avem un set de triunghiuri în loc de poligoane de multe puncte. Acest lucru este incredibil de util, deoarece acum am subdivided o zonă în triunghiuri renderable. Această tehnică poate fi utilizată pentru tessellation sau triangulation of shapes. super-misto!
Este, de asemenea, o modalitate foarte bună de a construi setul de puncte ca un grafic, în cazul în care doriți să vă aventurați de la un punct la altul. Imaginați-vă că punctele sunt orașe.
Bine, știm ce arată Voronoi; acum să aruncăm o privire asupra structurii datelor pentru o diagramă Voronoi. În primul rând, trebuie să stocăm punctele care stau la baza diagramei Voronoi:
clasa VoronoiPoint float x float y VoronoiRegion * regiune
Fiecare VoronoiPoint are o locație (X y), și o referință la regiunea în care se află.
Apoi, trebuie să descriem VoronoiRegion:
clasa VoronoiRegion VoronoiPoint * punct Edge * marginile [] // lista noastră de margini
Regiunea înregistrează o referință la ea VoronoiPoint, precum și o listă cu VoronoiEdges care le-a legat.
Acum, să ne uităm la VoronoiEdges:
clasa VoronoiEdge VoronoiPoint * punctA VoronoiPoint * punctB distanța plutitoare // distanța dintre punctul A și punctul B float x1, z1, x2, z2 // pentru a vizualiza începutul și sfârșitul marginii
O margine cunoaște cele două puncte care o definesc, precum și distanța dintre ele. Pentru reprezentarea vizuală sau pentru construirea formei reale a regiunii poligonale, ar trebui să păstrați punctele de început și sfârșit ale muchiei.
Și acolo o avem. Cu aceste informații putem folosi cu ușurință diagrama Voronoi. Mai departe, vom analiza modul de generare a diagramei Voronoi. Dar, pentru moment, să examinăm câteva exemple despre modul în care putem folosi datele.
Să aruncăm o privire din nou la diagrama Voronoi a punctelor.
Dacă fiecare punct ar reprezenta un pachet de sănătate, ați putea afla destul de repede unde a fost cea mai apropiată - dar mai întâi trebuie să localizați regiunea în care vă aflați. Voronoi nu oferă o modalitate eficientă de a găsi acest lucru direct din cutie. Cu toate acestea, puteți stoca o referință pentru fiecare regiune într-un quadtree sau un arbore R, astfel încât căutarea să fie rapidă. Iar odată ce ai regiunea ta, îți poți găsi vecinii și vecinii.
De exemplu, dacă pachetul de sănătate din regiunea dvs. a dispărut, aveți nevoie de o modalitate de a găsi cel mai apropiat cel mai apropiat. Dacă ne referim la structura noastră de date și la pseudocodul de mai sus, vedem că dintr-o regiune găsim marginile sale. Iar cu aceste margini putem obține vecinii. Luați cel mai apropiat vecin și apoi vedem dacă are un pachet de sănătate.
Triangulația Delaunay poate fi folosită și aici. Se compune din linii între fiecare pachet de sănătate. Acest lucru poate fi apoi traversat cu A * pathfinding pentru a găsi următorul pachet următor dacă se întâmplă astfel încât cineva a luat toate pachetele de lângă tine.
În loc de pachete de sănătate, să imaginăm fiecare punct ca un turn de gardă inamic. Trebuie să găsiți calea cea mai sigură prin ele fără a fi prins. O metodă obișnuită pentru traversarea unui grafic în jocurile video este de a folosi algoritmul A * (http://en.wikipedia.org/wiki/A*_search_algorithm). Deoarece diagrama Voronoi este un grafic, acest lucru este ușor de configurat. Trebuie doar să aveți un algoritm A * care să susțină structuri grafice generice; un pic de planificare înainte de timp poate plăti aici.
Odată cu configurarea graficului, trebuie să cântărim fiecare margine. Valoarea de greutate cu care ne ocupăm este distanța de la aceste turnuri de pază și putem să le luăm direct din structura noastră de date: fiecare VoronoiEdge își cunoaște deja distanța între cele două puncte. În mod normal, o valoare mai mică pe o margine A * este mai bună, însă în acest caz vrem ca valoarea mai mare să fie mai ideală, deoarece reprezintă distanța față de turn.
Iată cum arată arcul de pornire dacă vrem să trecem de la punctul A la punctul B:
Aplicând greutatea la fiecare margine, începem să vedem care este cel mai bun traseu:
Marginile roșii reprezintă cele mai apropiate întâlniri cu turnurile. Portocaliu mai puțin; galben mai puțin de atât; și în cele din urmă verde fiind cel mai sigur. Rularea A * cu aceste greutăți ar trebui să producă următoarea cale:
Utilizarea greutăților în acest fel nu va asigura cel mai rapid cale, dar Cel mai sigur, ceea ce este ceea ce doriți. De asemenea, ar fi înțelept ca AI să rămână aproape de această cale și să evite slăbirea!
Un alt pas pe care îl puteți lua garanție trecerea sigură este de a elimina marginile care se află la o distanță minimă sigură. De exemplu, dacă fiecare turn de protecție avea o viziune de 30 de unități, atunci orice margini a căror distanță față de punctele lor este mai mică decât cea care ar putea fi îndepărtată din grafic și nu ar fi traversată deloc.
O altă utilizare a acestui lucru este de a găsi cea mai largă cale pentru unitățile care sunt mari și nu se pot încadra în spații înguste. Deoarece fiecare margine are o distanță între cele două puncte, știm dacă se poate potrivi prin acel spațiu.
În schimb, dacă am folosi o triangulare Delaunay a diagramei, vom obține linii care merg de la fiecare turn de pază. Un gardian AI staționat la un turn putea să afle repede ce sunt celelalte turnuri din apropiere și, eventual, să se îndrepte spre unul pentru al asista dacă este necesar.
Spuneți că doriți să lăsați un pachet de catnip pentru o grămadă de pisoi drăguți într-un câmp. Care este cea mai bună locație pentru ao lăsa, astfel încât cele mai multe pisoi să se poată bucura de ea? Acest lucru ar putea deveni un calcul foarte, foarte scump. Dar din fericire putem face o presupunere educată prin folosirea triangulării noastre Delaunay.
Bacsis: Amintiți-vă că triunghiul Delaunay este doar inversul diagramei Voronoi. Se formează pur și simplu prin aderarea fiecărui punct Voronoi la punctele de vecinătate obținute din lista sa de margini.
Cu această colecție de triunghiuri, putem examina zona pe care o acoperă fiecare triunghi. Dacă găsim triunghiul cu cea mai mică zonă, atunci avem cele trei puncte cele mai apropiate sau pisoii. Este posibil să nu fie cel mai dens pachet mediu de pisoi pe câmp, dar este o presupunere bună. Dacă suntem capabili să renunțăm la mai multe pachete de catnip atunci putem doar să marchem ce triunghiuri ne-am vizat deja și să obținem următoarea cea mai mică.
Reprezentarea acestor zone este, de asemenea, cunoscută sub numele de circum-cercuri din triangularea Delaunay. Fiecare cerc este cel mai mare cerc care se poate potrivi în punctele triunghiulare. Iată o imagine a circumcizilor pentru o diagramă Voronoi:
Puteți utiliza centrul exact al cercurilor pentru a determina mijlocul zonei pentru a renunța la pachetul de catnip. Raza cercului este de fapt o metodă mai bună de a determina cel mai bun triunghi să renunțe în loc de zona triunghiului - mai ales dacă două puncte ale unui triunghi sunt foarte aproape împreună și unul este departe, producând un triunghi foarte ascuțit, puncte care sunt de fapt destul de îndepărtate.
Există mai multe moduri de a genera diagrame Voronoi, iar momentul în care aveți datele vă poate ajuta să determinați ce tehnică să utilizați.
Cea mai rapidă metodă este numită Algoritmul Fortune's Sweep Line. Este O (n log (n)) și cere ca toate punctele folosite pentru generarea graficului să fie prezente la momentul generării. Dacă adăugați noi puncte mai târziu, trebuie să generați din nou întregul grafic. Aceasta ar putea să nu fie o problemă importantă cu câteva puncte, dar dacă aveți 100 000, ar putea dura ceva timp!
Implementarea acestui algoritm nu este banală. Trebuie să intersectezi parabolele și să rezolvi cazuri speciale. Cu toate acestea, este cea mai rapidă tehnică. Din fericire, există multe implementări cu sursă deschisă pe care deja le puteți utiliza și le-am conectat aici.
Să ne uităm rapid la modul în care funcționează.
Algoritmul constă în măturarea unei linii (fie verticală sau orizontală) în zona punctelor. Când întâlnește un punct, începe să deseneze o parabolă care continuă cu linia de măturat. Iată o animație a procesului:
(Imagine de la curtea lui Mnbayazit, lansată în domeniul public.) Parabolele intersectante produc marginile Voronoi. De ce parabolele, totuși?
Pentru a înțelege acest lucru, imaginați fiecare punct care conține un balon care se extinde până când ajunge în contact cu un alt balon. Puteți extrage această idee în cercuri care se extind pe un plan 2D. Mergem cu un pas mai departe și punem câte un con în fiecare punct, un con, care are o pantă de 45 de grade și care merge până la infinit. Atunci ne imaginăm linia de măturări ca un avion, de asemenea la 45 de grade, care mătură până când vine în contact cu conurile. Având în vedere că planul și conurile sunt în același unghi, ele produc parabole atunci când se intersectează.
Pe măsură ce conurile cresc vertical, eventual se vor intersecta cu unul sau mai mulți conuri. Dacă ne uităm unde se intersectează conurile sau cercurile, obținem liniile drepte ale muchiilor Voronoi. Aici puteți vedea linia roșie a locului în care se intersectează conurile. Dacă conurile s-au extins mai mult (s-au extins vertical până la infinit), linia roșie ar continua să se extindă.
Atunci când avionul trece peste și face primul contact cu un con, se produce o linie ca atare:
Când avionul se deplasează prin conuri, puteți vedea parabolele care formează:
Avionul continuă prin scenă. Pentru fiecare punct pe care îl întâlnește, el examinează punctele de vecinătate de pe linia de curățare care au deja parabole și începe o nouă parabolă pentru acest punct. Aceasta continuă să meargă și să crească până când această nouă parabolă începe să se suprapună cu una diferită decât înainte. Parabola anterioară este apoi închisă. Acesta este un loc în care se întâlnesc trei linii Voronoi.
Așa cum am spus mai devreme, este un pic cam complicat, deci iată câteva implementări open source pe care le puteți utiliza și examina:
O altă metodă este de a introduce incremental un punct la un moment dat, începând cu un triunghi de bază de trei puncte în afara intervalului posibil al tuturor celorlalte puncte. Această tehnică este O (n ^ 2) și nu necesită ca toate punctele să fie prezente în momentul generării.
Atunci când se introduce un nou punct, el localizează o regiune existentă în care se încadrează. Această regiune este subdivizată și se creează noi regiuni.
Iată un exemplu open source pentru a utiliza și a examina:
Până acum ar trebui să aveți un sentiment pentru ceea ce pot oferi diagramele Voronoi pentru jocul dvs. și pentru AI. Cu un grafic bine structurat de noduri și muchii, puteți interoga informații importante pentru a vă asigura că pisoii primesc catnipul de care au nevoie și că puteți lua cea mai sigură cale pentru a ajunge la ele. Și, doar în cazul în care, puteți găsi unde este cel mai apropiat kit med.
Accentsconagua