Share
Qual è la via più sicura da percorrere, dove si trova il maggior numero di nemici e dove si trova il pacchetto sanitario più vicino? Queste comuni domande sulla relazione spaziale possono essere risolte in modo efficiente con una routine matematica chiamata Voronoi. Alla fine di questo tutorial avrai gli strumenti e le conoscenze per analizzare le tue mappe e produrre informazioni che saranno fondamentali per il realismo e il successo dell'IA.
Post correlatiSe sei interessato a leggere di più sull'intelligenza artificiale (intelligenza artificiale), assicurati di controllare:
Una relazione spaziale è qualcosa che descrive come un oggetto in uno spazio è correlato a un altro. Per esempio: la loro distanza l'una dall'altra, quanta area copre e se le loro aree si sovrappongono, o quanti di questi oggetti si trovano in un'area.
Queste relazioni saltano continuamente nei videogiochi e possono fornire informazioni molto utili all'IA o persino al giocatore.
UN Diagramma di Voronoi descrive la relazione spaziale tra i punti vicini l'uno all'altro o i loro vicini più vicini. È un insieme di poligoni di connessione derivati da punti o posizioni. Ogni linea di una "regione" Voronoi è a metà strada tra due punti.
Ecco, guardiamo un'immagine per farti un'idea:
Qui puoi vedere che ogni linea è esattamente a metà strada tra due punti e che tutti si incontrano nel mezzo. Aggiungiamo altri punti alla scena e vediamo cosa succede:
Ora sta diventando più interessante! Stiamo iniziando a ottenere regioni attuali.
Quindi cosa ci dice ogni regione? Sappiamo che mentre ci troviamo in una regione, siamo sicuri di essere più vicini al singolo punto che si trova anche all'interno della regione. Questo ci dice molto su ciò che ci sta vicino ed è la relazione spaziale fondamentale nei diagrammi di Voronoi.
L'inverso di un diagramma di Voronoi è chiamato Triangolazione di Delaunay. Questo diagramma consiste di linee da ogni punto ai suoi vicini più prossimi, e ogni linea è perpendicolare al bordo di Voronoi che attraversa. Ecco come appare:
Le linee bianche sono le linee Delaunay. Ogni linea Delaunay corrisponde a uno e solo un bordo Voronoi. Sebbene a prima vista sembrino dei bordi multipli sovrapposti, diamo un'occhiata più da vicino e chiariamo cosa stiamo vedendo.
Qui, la linea verde Delaunay è legata al bordo rosa di Voronoi. Devi solo immaginare il bordo rosa che si estende più lontano e poi vedrai che si incrociano.
Con Delaunay puoi vedere che ora abbiamo una serie di triangoli anziché poligoni a più punti. Questo è incredibilmente utile poiché ora abbiamo suddiviso un'area in triangoli renderizzabili. Questa tecnica può essere utilizzata per la tassellatura o la triangolazione di forme. Super cool!
È anche un ottimo modo per costruire il set di punti come un grafico, nel caso in cui si voglia avventurarsi da un punto a un altro. Immagina solo che i punti siano città.
Va bene, sappiamo come appare Voronoi; ora diamo uno sguardo alla struttura dati per un diagramma di Voronoi. Innanzitutto, dobbiamo memorizzare i punti che sono alla base del diagramma di Voronoi:
classe VoronoiPoint float x float y VoronoiRegion * region
Ogni VoronoiPoint ha una posizione (x, y), e un riferimento alla regione che è dentro.
Quindi, dobbiamo descrivere il VoronoiRegion:
class VoronoiRegion VoronoiPoint * point Edge * edges [] // our list of edges
La regione memorizza un riferimento al suo VoronoiPoint, così come un elenco di VoronoiEdges quello lo vincolava.
Ora diamo un'occhiata al VoronoiEdges:
class VoronoiEdge VoronoiPoint * pointA VoronoiPoint * pointB distanza float // distanza tra il punto A e il punto B float x1, z1, x2, z2 // per visualizzare inizio e fine del bordo
Un bordo conosce i due punti che lo definiscono, così come la distanza tra loro. Per la rappresentazione visiva o per costruire la forma reale della regione poligonale, è necessario memorizzare i punti iniziale e finale del bordo.
E lì ce l'abbiamo. Con questa informazione, possiamo facilmente usare il diagramma di Voronoi. Più in basso, vedremo come generare effettivamente il diagramma di Voronoi. Ma per ora, diamo un'occhiata ad alcuni esempi di come possiamo usare i dati.
Diamo un'occhiata di nuovo al diagramma di punti di Voronoi.
Se ogni punto rappresentasse un pacco salute, potresti scoprire abbastanza rapidamente dove si trovava il più vicino, ma prima devi individuare la regione in cui ti trovi. Voronoi non fornisce un modo efficace per scoprirlo immediatamente. Tuttavia, è possibile memorizzare un riferimento a ciascuna regione in un quadruplo o in un albero R, in modo che la ricerca sia rapida. E una volta che hai la tua regione, puoi trovare i suoi vicini e i loro vicini.
Ad esempio, se il pacchetto di salute nella tua regione è sparito, hai bisogno di un modo per trovare quello successivo più vicino. Se ci riferiamo alla nostra struttura dati e allo pseudocodice sopra, vediamo che da una regione possiamo scoprirne i bordi. E con quei bordi possiamo quindi ottenere i vicini. Afferra il vicino più vicino e poi possiamo vedere se ha un pacchetto di salute.
La triangolazione di Delaunay può essere utilizzata anche qui. Consiste di linee tra ciascuno dei pacchetti di salute. Questo può quindi essere attraversato con un path finder A * per trovare il prossimo pacchetto più vicino se accade che qualcuno abbia afferrato tutti i pacchetti vicino a te.
Invece di pacchetti salute, immaginiamo ogni punto come una torre di guardia nemica. È necessario trovare il modo più sicuro attraverso di loro senza essere catturati. Un metodo comune per attraversare un grafico nei videogiochi consiste nell'utilizzare l'algoritmo A * (http://en.wikipedia.org/wiki/A*_search_algorithm). Dato che il diagramma di Voronoi è un grafico, questo è facile da configurare. Hai solo bisogno di avere un algoritmo A * che supporti strutture grafiche generiche; un po 'di pianificazione in anticipo può ripagare qui.
Con il grafico impostato, dobbiamo pesare ogni spigolo. Il valore di ponderazione di cui ci occupiamo è la distanza da queste torri di guardia, e possiamo prenderle direttamente dalla nostra struttura dati: ciascuna VoronoiEdge conosce la sua distanza tra i suoi due punti già. Normalmente un valore inferiore su un margine A * è migliore, tuttavia in questo caso vogliamo che il valore più grande sia più ideale, poiché rappresenta la distanza dalla torre.
Ecco come appare il grafico iniziale se vogliamo passare dal punto A al punto B:
Applicando il peso a ciascun bordo, iniziamo a vedere quale percorso potrebbe essere meglio prendere:
I bordi rossi rappresentano gli incontri più vicini con le torri. L'arancia meno così; giallo meno di quello; e infine il verde è il più sicuro. L'esecuzione di A * con questi pesi dovrebbe produrre il seguente percorso:
L'uso dei pesi in questo modo non garantisce il più veloce percorso, ma il più sicuro, che è quello che vuoi Sarebbe anche saggio che l'IA si avvicinasse a quel sentiero ed evitasse di allontanarsi!
Un altro passo che puoi fare garanzia passaggio sicuro è quello di rimuovere eventuali bordi che cadono sotto una distanza minima di sicurezza. Ad esempio, se ciascuna torre di guardia aveva un raggio di visione di 30 unità, allora qualsiasi spigolo la cui distanza dai loro punti è inferiore a quella che potrebbe essere rimossa dal grafico e non attraversata affatto.
Un altro uso di questo è trovare il percorso più ampio per unità che sono grandi e non possono adattarsi attraverso spazi stretti. Poiché ogni spigolo ha una distanza tra i suoi due punti, sappiamo se può adattarsi attraverso quello spazio.
Viceversa, se invece usassimo una triangolazione di Delaunay del diagramma, otterremmo linee che vanno da ogni torre di guardia. Una IA di guardia situata in una torre potrebbe scoprire rapidamente quali sono le altre torri vicine e, se necessario, andare verso l'una per aiutarla.
Dì che vuoi far cadere un pacchetto di catnip per un intero gruppo di simpatici gattini in un campo. Qual è la posizione migliore per lasciarla in modo che la maggior parte dei gattini possa apprezzarla? Questo potrebbe finire per essere un calcolo molto, molto costoso. Ma fortunatamente possiamo fare un'ipotesi istruita usando la nostra triangolazione di Delaunay.
Mancia: Ricorda che la triangolazione di Delaunay è solo l'inverso del diagramma di Voronoi. Si forma semplicemente unendo ciascun punto Voronoi con i punti adiacenti ottenuti dalla sua lista di bordi.
Con questa raccolta di triangoli, possiamo esaminare l'area coperta da ciascun triangolo. Se troviamo il triangolo con l'area più piccola, allora abbiamo i tre punti più vicini, o gattini. Potrebbe non essere il pacchetto medio più denso di gattini sul campo, ma è una buona ipotesi. Se siamo in grado di rilasciare più pacchetti catnip, possiamo semplicemente contrassegnare quali triangoli abbiamo già preso di mira e ottenere quello successivo più piccolo.
La rappresentazione di queste aree è anche nota come circum-cerchi della triangolazione di Delaunay. Ogni cerchio è il cerchio più grande che può rientrare nei punti dei triangoli. Ecco un'immagine dei circonferenze per un diagramma di Voronoi:
È possibile utilizzare il centro esatto dei cerchi per determinare il centro dell'area in modo da eliminare il pacchetto catnip. Il raggio del cerchio è in realtà un metodo migliore per determinare il miglior triangolo da far cadere al posto dell'area triangolare - specialmente se due punti di un triangolo sono molto vicini e uno è lontano, producendo un triangolo molto nitido con una piccola area ma che rappresenta punti che sono in realtà abbastanza distanti.
Esistono diversi modi per generare diagrammi di Voronoi e il momento in cui si dispone dei dati può aiutare a determinare quale tecnica utilizzare.
Il metodo più veloce è chiamato Algoritmo di spazzata della linea di Fortune. È O (n log (n)) e richiede che tutti i punti utilizzati per generare il grafico siano presenti al momento della generazione. Se aggiungi nuovi punti in seguito, devi rigenerare l'intero grafico. Questo potrebbe non essere un grosso problema con pochi punti, ma se hai 100.000 o giù di lì, potrebbe volerci un po '!
L'implementazione di questo algoritmo non è banale. Devi intersecare le parabole e affrontare alcuni casi speciali. Comunque è la tecnica più veloce. Fortunatamente, ci sono già molte implementazioni open source che è già in uso per voi e le abbiamo collegate qui.
Diamo una rapida occhiata a come funziona.
L'algoritmo consiste nello spazzare una linea (verticale o orizzontale) attraverso l'area dei punti. Quando incontra un punto, inizia a disegnare una parabola che continua con la linea ampia. Ecco un'animazione del processo:
(Immagine per gentile concessione di Mnbayazit, rilasciata al pubblico dominio.) Le parabole intersecanti producono i bordi di Voronoi. Perchè parabole, comunque?
Per capirlo, immagina ogni punto contenente un fumetto che si espande fino a quando non entra in contatto con un altro fumetto. Puoi estrarre questa idea in cerchi che si espandono su un piano 2D. Facciamo un ulteriore passo avanti e posizioniamo un cono capovolto su ogni punto, un cono che ha una pendenza di 45 gradi e che sale all'infinito. Quindi immaginiamo la linea di scorrimento come un piano, anch'esso a 45 gradi, che procede lungo fino a quando non entra in contatto con i coni. Poiché l'aereo e i coni sono nella stessa angolazione, producono parabole quando si intersecano.
Mentre i coni crescono verticalmente, alla fine si intersecheranno con uno o più altri coni. Se guardiamo dove si incrociano i coni, o cerchi, otteniamo le linee rette dei bordi di Voronoi. Qui puoi vedere la linea rossa di dove si intersecano i coni. Se i coni si espandevano ancora (salivano verticalmente all'infinito), la linea rossa continuava ad estendersi.
Quando l'aereo attraversa e raggiunge il primo contatto con un cono, viene prodotta una linea in questo modo:
Mentre l'aereo si muove attraverso i coni, puoi vedere le parabole che si formano:
L'aereo continua attraverso la scena. Per ogni punto che incontra, esamina i punti vicini sulla linea di scorrimento che hanno già parabole e inizia una nuova parabola per questo punto. Continua a progredire e a crescere fino a quando questa nuova parabola inizia a sovrapporsi a una diversa rispetto a prima. Quella parabola precedente è quindi chiusa. Questo è un luogo in cui le linee di Voronoi di tre punti si incontrano.
Come detto prima, è un po 'complicato, quindi ecco alcune implementazioni open source che puoi usare ed esaminare:
Un altro metodo consiste nell'inserire in modo incrementale un punto alla volta, partendo da un triangolo di base di tre punti al di fuori dell'intervallo possibile di tutti gli altri punti. Questa tecnica è O (n ^ 2) e non richiede che tutti i punti siano presenti al momento della generazione.
Quando viene inserito un nuovo punto, individua un'area esistente in cui si inserisce. Questa regione viene quindi suddivisa e vengono create nuove regioni.
Ecco un esempio open source che puoi usare ed esaminare:
A questo punto dovresti avere un'idea di ciò che i diagrammi di Voronoi possono fornire per il tuo gioco e la sua IA. Con un grafico ben strutturato di nodi e spigoli è possibile richiedere informazioni importanti per garantire che i gattini ricevano la catnip di cui hanno bisogno e che sia possibile prendere la via più sicura per raggiungerli. E, nel caso, puoi trovare anche il kit medico più vicino.
Accentsconagua