Share
Vad är den säkraste vägen att ta, var ligger de flesta fiender och var ligger närmaste hälso-pack? Dessa gemensamma frågor om rymdrelaterade frågor kan alla lösas effektivt med en matematisk rutin som heter Voronoi. I slutet av denna handledning kommer du att ha verktyg och kunskaper för att analysera dina kartor och producera information som kommer att vara nyckeln till AI: s realism och framgång.
relaterade inläggOm du är intresserad av att läsa mer om AI (artificiell intelligens), se till att kolla in:
Ett rumsligt förhållande är något som beskriver hur ett objekt i ett utrymme är relaterat till en annan. Till exempel: deras avstånd från varandra, hur mycket område varje täcker och huruvida deras områden överlappar varandra, eller hur många av dessa objekt ligger i ett område.
Dessa relationer dyker upp i videospel hela tiden och kan ge mycket användbar information till AI, eller till och med spelaren.
en Voronoi diagram beskriver det rumsliga förhållandet mellan punkter som ligger nära varandra, eller närmaste grannar. Det är en uppsättning anslutningspolygoner som härrör från punkter eller platser. Varje linje i en Voronoi "region" är halvvägs mellan två punkter.
Här, låt oss titta på en bild för att få en känsla för det:
Här kan du se att varje linje är exakt halvvägs mellan två punkter, och att de alla möts tillsammans i mitten. Låt oss lägga till några fler poäng till scenen och se vad som händer:
Nu blir det mer intressant! Vi börjar att få faktiska regioner.
Så vad berättar varje region för oss? Vi vet att när vi är inom en region, är vi garanterade att vara närmast den enda punkt som också ligger inom regionen. Detta berättar mycket om vad som ligger nära oss och är det grundläggande rumsliga förhållandet i Voronoi-diagram.
Den inverse av ett Voronoi diagram kallas Delaunay Triangulation. Detta diagram består av linjer från varje punkt till närmaste grannar, och varje linje är vinkelrätt mot Voronoi-kanten som korsar. Så här ser det ut:
De vita linjerna är Delaunay-linjerna. Varje Delaunay-linje motsvarar en och endast en Voronoi-kant. Även om det vid första anblicken ser ut som om de överlappar flera kanter, låt oss ta en närmare titt och klargöra vad vi ser.
Här är den gröna Delaunay-linjen relaterad till den rosa Voronoi-kanten. Du måste bara tänka dig att den rosa kanten sträcker sig längre och då ser du att de passerar.
Med Delaunay kan vi se att vi har en uppsättning trianglar nu istället för polygoner med många punkter. Detta är oerhört användbart eftersom vi nu bara har indelat ett område i renderbara trianglar. Denna teknik kan användas för tessellering eller triangulering av former. supercool!
Det är också ett bra sätt att bygga upp uppsättningen poäng som ett diagram, om du vill satsa från en punkt till en annan. Tänk dig att poängen är städer.
Okej, vi vet vad Voronoi ser ut; Låt oss nu ta en titt på datastrukturen för ett Voronoi-diagram. Först måste vi lagra punkterna som ligger till grund för Voronoi-diagrammet:
klass VoronoiPoint float x float y VoronoiRegion * region
Varje VoronoiPoint har en plats (x, y), och en referens till regionen det är inuti.
Därefter måste vi beskriva VoronoiRegion:
klass VoronoiRegion VoronoiPoint * Point Edge * kanter [] // vår lista över kanter
Regionen lagrar en hänvisning till dess VoronoiPoint, samt en lista över VoronoiEdges som bundet det.
Nu ska vi titta på VoronoiEdges:
klass VoronoiEdge VoronoiPoint * punktA VoronoiPoint * punktB float distance // avstånd mellan punkt A och punkt B float x1, z1, x2, z2 // för att visualisera start och slut på kanten
En kant känner till de två punkterna som definierar den, liksom avståndet mellan dem. För visuell representation, eller för att bygga upp den egentliga formen av polygonregionen, bör du lagra start- och ändpunkterna på kanten.
Och där har vi det. Med den informationen kan vi enkelt använda Voronoi-diagrammet. Längre ner ser vi på hur man faktiskt skapar Voronoi-diagrammet. Men för nu, låt oss titta på några exempel på hur vi kan använda data.
Låt oss ta en titt igen på Voronoi diagram över punkter.
Om varje punkt representerade ett hälsopaket, kunde du ta reda på hur snabbt det närmaste var - men först måste du hitta den region du befinner dig i. Voronoi ger inte ett effektivt sätt att hitta det här direkt ut ur rutan. Du kan dock lagra en referens till varje region i en quadtree eller ett R-träd så att uppslaget blir snabbt. Och när du har din region, kan du hitta sina grannar och deras grannar.
Om till exempel hälsopaketet i din region är borta behöver du ett sätt att hitta nästa närmaste. Om vi hänvisar till vår datastruktur och pseudokoden ovan ser vi att från en region kan vi ta reda på dess kanter. Och med dessa kanter kan vi sedan få grannarna. Ta tag i närmaste granne och sedan kan vi se om det har ett hälsopaket.
Delaunay Triangulation kan också användas här. Den består av linjer mellan var och en av hälsopaket. Detta kan sedan korsas med A * pathfinding för att hitta nästa närmaste pack om det så händer att någon har tagit alla förpackningarna nära dig.
Istället för hälsopaket, låt oss bilda varje punkt som ett fiendens vaktorn. Du måste hitta det säkraste sättet genom dem utan att bli fångad. En vanlig metod för att korsa en graf i videospel är att använda A * -algoritmen (http://en.wikipedia.org/wiki/A*_search_algorithm). Eftersom Voronoi-diagrammet är ett diagram är det enkelt att ställa in det. Du behöver bara ha en A * -algoritm som stöder generiska grafstrukturer. lite planering i förväg kan löna sig här.
När grafen ställs in måste vi väga varje kant. Det viktvärde vi berör är avståndet från dessa vaktornor, och vi kan ta tag i detta direkt från vår datastruktur: var och en VoronoiEdge vet dess avstånd mellan dess två punkter redan. Normalt är ett lägre värde på A * -kanten bättre, men i det här fallet vill vi att det större värdet är mer idealiskt eftersom det representerar avståndet till tornet.
Här är vad startgrafen ser ut om vi vill flytta från punkt A till punkt B:
Med hjälp av vikten på varje kant börjar vi se vilken väg som är bäst att ta:
De röda kanterna representerar närmaste möten med tornen. Apelsinen mindre så; gul mindre än det; och äntligen grönt är det säkraste. Att köra A * med dessa vikter ska producera följande väg:
Med hjälp av vikterna garanterar inte detta snabbaste väg, men säkraste, vilket är vad du vill ha. Det skulle också vara klokt för AI att hålla sig nära den vägen och undvika att avvika!
Ett annat steg du kan ta till garanti säker passage är att ta bort eventuella kanter som faller under ett minimalt säkert avstånd. Till exempel om varje vakttårn hade ett visionsintervall på 30 enheter, så kan alla kanter vars avstånd till deras punkter är mindre än det som skulle kunna avlägsnas från grafen och inte överskridas alls.
En annan användning av detta är att hitta den bredaste vägen för enheter som är stora och inte kan passa genom smala utrymmen. Eftersom varje kant har ett avstånd mellan sina två punkter, vet vi huruvida det kan passa genom det här utrymmet.
Omvänt, om vi istället använde en Delaunay triangulering av diagrammet, skulle vi få linjer som går från varje vakttorn. En väktare AI stationerad vid ett torn kunde snabbt ta reda på vad de andra närliggande tornen är och eventuellt gå över till en för att hjälpa till om det behövs.
Säg att du vill släppa ett paket kattnip för en hel massa söta kattungar i ett fält. Vad är det bästa stället att släppa så att de flesta kattungarna kan njuta av det? Detta kan sluta bli en mycket, mycket dyr beräkning. Men lyckligtvis kan vi göra en utbildad gissning genom att använda vår Delaunay triangulering.
Tips: Kom ihåg att Delaunay trianguleringen är bara den inverse av Voronoi diagrammet. Det bildas helt enkelt genom att ansluta sig till varje Voronoi-punkt med sina grannpunkter erhållna från dess lista av kanter.
Med denna samling av trianglar kan vi undersöka det område som varje triangel täcker. Om vi hittar triangeln med det minsta området, så har vi de tre närmaste punkterna, eller kattungarna. Det kan inte vara den tätaste genomsnittliga packningen av kattungar i fältet, men det är en bra gissning. Om vi kan släppa flera catnip-paket så kan vi bara markera vilka trianglar vi redan riktade och få den näst minsta.
Representationen av dessa områden är också känd som omstän-cirklar av Delaunay trianguleringen. Varje cirkel är den största cirkeln som kan passa in i trianglarna. Här är en bild av omkretsen för ett Voronoi diagram:
Du kan använda exakt centrum av cirklarna för att bestämma mitten av området för att släppa kattipaketet. Radiets radie är faktiskt en bättre metod för att bestämma den bästa triangeln att släppa i stället för triangelområdet - speciellt om två punkter i en triangel är mycket nära varandra och en är långt bort och producerar en mycket skarp triangel med lite område men som representerar poäng som faktiskt är ganska långt ifrån varandra.
Det finns flera sätt att generera Voronoi diagram, och den tid då du har data kan hjälpa till att bestämma vilken teknik som ska användas.
Den snabbaste metoden heter Fortunes Line-Sweep Algorithm. Det är O (n log (n)) och kräver att alla punkter som används för att generera grafen är närvarande vid genereringstillfället. Om du lägger till nya poäng senare måste du generera hela grafen igen. Det här kanske inte är en stor sak med några punkter, men om du har 100 000 eller så kan det ta ett tag!
Genomförandet av denna algoritm är inte trivial. Du måste korsa paraboler och hantera några speciella fall. Det är dock den snabbaste tekniken. Lyckligtvis finns det många open source-implementeringar av det där ute som du redan kan använda och vi har länkat till dem här.
Låt oss ta en snabb titt på hur det fungerar.
Algoritmen består av att svepa en linje (antingen vertikal eller horisontell) över punktens område. När det möter en punkt börjar det att dra en parabola från den som fortsätter med soplinjen. Här är en animering av processen:
(Bild med tillstånd av Mnbayazit, släppt till allmänheten.) De skärande parabolerna producerar Voronoi kanterna. Varför paraboler, dock?
För att förstå det, bild varje punkt som innehåller en ballong som expanderar tills den kommer i kontakt med en annan ballong. Du kan extrahera denna idé till cirklar som expanderar på ett 2D-plan. Vi tar det ett steg längre och lägger en upp och ner kegel på varje punkt, en kotte som har en lutning på 45 grader och det går upp till oändligheten. Vi föreställer oss sålunda linjen som ett plan, även vid 45 grader, som sveper fram tills det kommer i kontakt med konerna. Eftersom planet och konerna ligger i samma vinkel producerar de paraboler när de skär.
När kottarna växer vertikalt kommer de så småningom att korsa med en eller flera andra koner. Om vi tittar på var konerna eller cirklarna skär varandra får vi de raka linjerna i Voronoi kanterna. Här kan du se den röda linjen där kottarna skärs. Om kottarna utvidgades lite mer (gick upp vertikalt till oändligheten) fortsatte den röda linjen att förlängas.
När planet sveper över och gör första kontakten med en kon, produceras en linje som sådan:
När planet flyter genom konerna, kan du se att parabolerna bildar:
Planet fortsätter genom scenen. För varje punkt som den möter undersöker den grannpunkterna på soplinjen som redan har paraboler och börjar en ny parabola för denna punkt. Det fortsätter att fortsätta och växa tills denna nya parabola börjar överlappa med en annan än tidigare. Den tidigare parabolen stängs sedan av. Det här är en plats där tre punkter "Voronoi-linjer möts.
Som sagt tidigare är det lite komplicerat, så här är några open source-implementeringar som du kan använda och undersöka:
En annan metod är att stegvis infoga en punkt i taget, med en basstriangel på tre punkter utanför det möjliga området för alla andra punkter. Denna teknik är O (n ^ 2) och kräver inte att alla punkter är närvarande vid generationens gång.
När en ny punkt läggs in, lokaliserar den en befintlig region som den passar in i. Den regionen delas sedan in och nya regioner skapas.
Här är ett open source-exempel för att du ska kunna använda och undersöka:
Nu borde du ha en känsla för vad Voronoi diagram kan ge för ditt spel och dess AI. Med en välstrukturerad graf av noder och kanter kan du fråga viktig information för att säkerställa att killarna får den kattnota de behöver och att du kan ta den säkraste vägen för att komma till dem. Och bara i fallet kan du hitta var närmaste med-kit är också.
Accentsconagua