Share
Hva er den sikreste ruten å ta, hvor er de fleste fiender, og hvor er nærmeste helsepakke? Disse vanlige spørsmålene om romlige forhold kan alle løses effektivt med en matematisk rutine som heter Voronoi. Ved slutten av denne opplæringen vil du ha verktøy og kunnskap for å analysere kartene dine og produsere informasjon som vil være nøkkelen til AIs realisme og suksess.
Relaterte innleggHvis du er interessert i å lese mer om AI (kunstig intelligens), sørg for å sjekke ut:
Et romlig forhold er noe som beskriver hvordan et objekt i et rom er relatert til en annen. For eksempel: deres avstand fra hverandre, hvor mye område dekker hver, og om områdene deres overlapper, eller hvor mange av disse objektene er plassert i ett område.
Disse forholdene dukker opp i videospill hele tiden, og kan gi svært nyttig informasjon til AI, eller til og med spilleren.
EN Voronoi diagram beskriver romforholdet mellom punkter som er nær hverandre, eller deres nærmeste naboer. Det er et sett av forbindelsespolygoner avledet fra poeng eller steder. Hver linje i en Voronoi "region" er halvveis mellom to punkter.
Her, la oss se på et bilde for å få en følelse for det:
Her kan du se at hver linje er nøyaktig halvveis mellom to punkter, og at de alle møtes sammen i midten. La oss legge til flere poeng til scenen og se hva som skjer:
Nå blir det mer interessant! Vi begynner å få faktiske regioner.
Så hva forteller hver region oss? Vi vet at mens du er innenfor en region, er vi garantert å være nærmest det eneste punktet som også ligger i regionen. Dette forteller oss mye om hva som er nær oss og er det grunnleggende romlige forholdet i Voronoi-diagrammer.
Den inverse av et Voronoi diagram kalles Delaunay Triangulasjon. Dette diagrammet består av linjer fra hvert punkt til nærmeste naboer, og hver linje er vinkelrett på Voronoi-kanten som krysser. Slik ser det ut:
De hvite linjene er Delaunay linjene. Hver Delaunay-linje tilsvarer en og en eneste Voronoi-kant. Selv om det ved første øyekast ser ut som noen overlapper flere kanter, la oss ta en nærmere titt og avklare hva vi ser.
Her er den grønne Delaunay-linjen knyttet til den rosa Voronoi-kanten. Du må bare forestille seg at den rosa kanten strekker seg lenger og da vil du se at de krysser.
Med Delaunay kan du se at vi har et sett med trekanter nå i stedet for mangepunkts polygoner. Dette er utrolig nyttig ettersom vi nå bare har delt inn et område i gjengivne trekanter. Denne teknikken kan brukes til tessellasjon eller triangulering av former. kjempekul!
Det er også en fin måte å bygge opp settet av poeng som en graf, i tilfelle du ønsker å våge fra ett punkt til et annet. Tenk deg at poengene er byer.
Ok, vi vet hva Voronoi ser ut; La oss nå ta en titt på datastrukturen for et Voronoi-diagram. Først må vi lagre poengene som ligger til grunn for Voronoi-diagrammet:
klasse VoronoiPoint float x float y VoronoiRegion * region
Hver VoronoiPoint har en plassering (x, y), og en referanse til regionen den er inne.
Deretter må vi beskrive VoronoiRegion:
klasse VoronoiRegion VoronoiPoint * Point Edge * kanter [] // vår liste over kanter
Regionen lagrer en referanse til sin VoronoiPoint, samt en liste over VoronoiEdges som bundet det.
La oss nå se på VoronoiEdges:
klasse VoronoiEdge VoronoiPoint * punktA VoronoiPoint * punktB flyteavstand // avstand mellom punkt A og punkt B float x1, z1, x2, z2 // for å visualisere start og slutt på kanten
En kant kjenner de to punktene som definerer den, så vel som avstanden mellom dem. For visuell representasjon, eller for å bygge opp den faktiske formen på polygonområdet, bør du lagre start- og sluttpunktene til kanten.
Og der har vi det. Med den informasjonen kan vi enkelt bruke Voronoi-diagrammet. Lenger ned, vil vi se på hvordan man faktisk lager Voronoi-diagrammet. Men for nå, la oss se på noen eksempler på hvordan vi kan bruke dataene.
La oss ta en titt igjen på Voronoi diagrammet av poeng.
Hvis hvert punkt representerte en helsepakke, kan du finne ut hvor raskt det nærmeste var - men først må du finne regionen du befinner deg i. Voronoi gir ikke en effektiv måte å finne ut dette rett ut av boksen. Du kan imidlertid lagre en referanse til hver region i en quadtree eller et R-tre, slik at oppslaget blir raskt. Og når du har din region, kan du finne sine naboer, og deres naboer.
For eksempel, hvis helsepakken i din region er borte, trenger du en måte å finne den nærmeste nærmeste. Hvis vi refererer til vår datastruktur og pseudokoden ovenfor, ser vi at fra en region kan vi finne ut kantene. Og med disse kantene kan vi da få naboene. Ta tak i nærmeste nabo, og så kan vi se om det har en helsepakke.
Delaunay Triangulasjonen kan også brukes her. Den består av linjer mellom hver av helsepakker. Dette kan da krysse med A * -opplæring for å finne neste nærmeste pakke hvis det skjer slik at noen har tatt alle pakkene nær deg.
I stedet for helsepakker la vi bilde hvert punkt som et fiendtlig vaktårn. Du må finne den tryggeste veien gjennom dem uten å bli fanget. En vanlig metode for å krysse en graf i videospill er å bruke A * -algoritmen (http://en.wikipedia.org/wiki/A*_search_algorithm). Siden Voronoi diagrammet er en graf, er dette enkelt å sette opp. Du trenger bare å ha en A * -algoritme som støtter generiske grafstrukturer; en liten planlegging på forhånd kan betale seg her.
Med grafen satt opp, må vi veie hver kant. Vektverdien vi er opptatt av er avstanden fra disse vaktårnene, og vi kan gripe dette direkte fra vår datastruktur: hver VoronoiEdge kjenner avstanden mellom sine to punkter allerede. Normalt er en lavere verdi på en A * kant bedre, men i dette tilfellet ønsker vi at den større verdien skal være mer ideell, siden den representerer avstanden til tårnet.
Slik ser startgrafen ut om vi vil flytte fra punkt A til punkt B:
Ved å bruke vekten til hver kant begynner vi å se hvilken rute som er best å ta:
De røde kantene representerer nærmeste møter med tårnene. Den oransje mindre; gult mindre enn det; og til slutt grønn er den sikreste. Kjører A * med disse vekter bør produsere følgende sti:
Ved å bruke vekter vil denne veien ikke sikre raskeste bane, men den sikreste, som er hva du vil. Det ville også være klokt for AI å holde seg nær den banen og unngå å svikte!
Et annet skritt du kan ta til garanti sikker passasje er å fjerne eventuelle kanter som faller under en minimum sikker avstand. For eksempel hvis hvert vakttårn hadde et visningsområde på 30 enheter, så kan alle kanter hvis avstand til deres poeng er mindre enn det som kunne fjernes fra grafen og ikke krysses i det hele tatt.
En annen bruk av dette er å finne den bredeste ruten for enheter som er store og ikke kan passe gjennom smale mellomrom. Siden hver kant har en avstand mellom sine to punkter, vet vi om den kan passe gjennom dette rommet.
Omvendt, hvis vi i stedet brukte en Delaunay triangulering av diagrammet, ville vi få linjer som går fra hvert vakttårn. En vakt AI som er stasjonert ved et tårn, kan raskt finne ut hva de andre tårnene i nærheten er, og muligens gå over til en for å hjelpe det hvis det trengs.
Si at du vil slippe en pakke med kattemynte for en hel haug med søte kattunger i et felt. Hva er det beste stedet å slippe det, så de fleste kattunger kan nyte det? Dette kan ende med å bli en veldig, veldig dyr beregning. Men heldigvis kan vi lage et utdannet gjetning ved å bruke vår Delaunay triangulering.
Tips: Husk at Delaunay triangulasjonen er bare den inverse av Voronoi diagrammet. Det er ganske enkelt dannet ved å bli med i hvert Voronoi-punkt med sine nabopunkter hentet fra sin liste over kanter.
Med denne samlingen av trekanter kan vi undersøke området som hver trekant dekker. Hvis vi finner trekanten med det minste området, så har vi de tre nærmeste punktene, eller kattunger. Det kan ikke være den tetteste gjennomsnittlige pakken med kattunger i feltet, men det er et godt gjetning. Hvis vi er i stand til å slippe flere catnip-pakker, så kan vi bare merke hvilke trekanter vi allerede målrettet og få den nest minste.
Representasjonen av disse områdene er også kjent som stendigsirkler av Delaunay triangulasjonen. Hver sirkel er den største sirkelen som passer inn i trepunktene. Her er et bilde av omkretsene for et Voronoi diagram:
Du kan bruke det nøyaktige senterets sirkler for å bestemme midten av området for å slippe kattepakken. Radius av sirkelen er faktisk en bedre metode for å bestemme den beste trekanten for å slippe i stedet for trekantsområdet - spesielt hvis to punkter i en trekant er svært tett sammen og en er langt unna, og produserer en veldig skarp trekant med lite område, men representerer poeng som faktisk er ganske langt fra hverandre.
Det finnes flere måter å generere Voronoi diagrammer på, og tiden du har dataene på, kan hjelpe deg med å bestemme hvilken teknikk du skal bruke.
Den raskeste metoden heter Fortune's Line-Sweep Algorithm. Det er O (n log (n)) og krever at alle poeng som brukes til å generere grafen er tilstede på generasjonstidspunktet. Hvis du legger til nye poeng senere, må du generere hele grafen på nytt. Dette kan ikke være en stor avtale med få poeng, men hvis du har 100.000 eller så, kan det ta en stund!
Implementering av denne algoritmen er ikke trivial. Du må krysse paraboler og håndtere noen spesielle tilfeller. Men det er den raskeste teknikken. Heldigvis finnes det mange åpen kildekode-implementeringer der ute der du allerede kan bruke og vi har koblet til dem her.
La oss se på hvordan det fungerer.
Algoritmen består av å feie en linje (enten vertikal eller horisontal) over poengområdet. Når det møter et punkt begynner det å tegne en parabol fra det som fortsetter videre med feieringen. Her er en animasjon av prosessen:
(Bilde av Mnbayazit, utgitt til det offentlige området.) Kryssende paraboler produserer Voronoi kantene. Hvorfor paraboler, skjønt?
For å forstå det, bilde hvert punkt som inneholder en ballong som ekspanderer til den kommer i kontakt med en annen ballong. Du kan trekke denne ideen ut i sirkler som utvider seg på et 2D-plan. Vi tar det ett skritt videre og legger en oppadgående kjegle på hvert punkt, en kjegle som har en skråning på 45 grader, og det går opp til uendelig. Vi forestiller oss så feiebanen som et fly, også ved 45 grader, som feier sammen til det kommer i kontakt med kjeglene. Siden flyet og kjeglene er i samme vinkel, produserer de paraboler når de krysser.
Når kjeglene vokser vertikalt, vil de til slutt krysse med en eller flere andre kjegler. Hvis vi ser på hvor keglene, eller sirkelene skjærer, får vi de rette linjene i Voronoi kantene. Her kan du se den røde linjen der keglene krysser. Hvis keglene utvidet noe mer (gikk opp vertikalt til uendelig), ville den røde linjen fortsette å strekke seg.
Når flyet feier over og gjør første kontakt med en kjegle, produseres en linje som sådan:
Når flyet beveger seg gjennom kjeglene, kan du se at parabolene dannes:
Flyet fortsetter gjennom scenen. For hvert punkt det møter, undersøker det nabopunktene på søppelinjen som allerede har paraboler og begynner en ny parabola for dette punktet. Det fortsetter å fortsette og vokse til denne nye parabolen begynner å overlappe seg med en annen enn før. Den forrige parabolen er så stengt. Dette er et sted hvor tre punkter 'Voronoi linjer møtes.
Som nevnt tidligere er det litt komplisert, så her er noen åpen kildekode implementeringer du kan bruke og undersøke:
En annen metode er å inkrementivt sette inn ett punkt om gangen, og begynner med en trekant på tre punkter utenfor det mulige spekteret av alle andre punkter. Denne teknikken er O (n ^ 2) og krever ikke at alle poengene skal være til stede på generasjonstidspunktet.
Når et nytt punkt er satt inn, lokaliserer det en eksisterende region som den passer inn i. Den regionen deles da og nye regioner blir opprettet.
Her er et åpen kildekode-eksempel for deg å bruke og undersøke:
Nå skal du ha en følelse av hva Voronoi diagrammer kan gi for spillet og dets AI. Med en godt strukturert graf av noder og kanter kan du spørre viktig informasjon for å sikre at kattungen får den kattemuren de trenger, og at du kan ta den sikreste ruten for å komme til dem. Og bare i tilfelle, kan du finne hvor nærmeste med kit er også.
Accentsconagua