Share
Wat is de veiligste route om te nemen, waar liggen de meeste vijanden en waar is het dichtstbijzijnde gezondheidspakket? Deze gemeenschappelijke vragen over ruimtelijke relaties kunnen allemaal efficiënt worden opgelost met een wiskundige routine genaamd Voronoi. Tegen het einde van deze tutorial zul je de tools en kennis hebben om je kaarten te analyseren en informatie te produceren die essentieel is voor het realisme en succes van de KI.
gerelateerde berichtenAls u meer wilt weten over AI (kunstmatige intelligentie), moet u het volgende controleren:
Een ruimtelijke relatie is alles dat beschrijft hoe een object in een ruimte gerelateerd is aan een ander object. Bijvoorbeeld: de afstand tot elkaar, hoeveel gebied elk bedekt en of hun gebieden elkaar overlappen, of hoeveel van deze objecten zich in een gebied bevinden.
Deze relaties komen de hele tijd in videogames en kunnen zeer nuttige informatie aan de AI of zelfs aan de speler verstrekken.
EEN Voronoi-diagram beschrijft de ruimtelijke relatie tussen punten die dicht bij elkaar liggen of hun naaste buren. Het is een set verbindingspolygonen afgeleid van punten of locaties. Elke regel van een Voronoi "regio" ligt halverwege tussen twee punten.
Laten we hier eens naar een afbeelding kijken om een gevoel te krijgen:
Hier kun je zien dat elke lijn precies halverwege tussen twee punten ligt en dat ze allemaal in het midden samenkomen. Laten we wat meer punten toevoegen aan de scène en zien wat er gebeurt:
Dat wordt steeds interessanter! We beginnen echte regio's te krijgen.
Dus wat vertelt elke regio ons? We weten dat we in een regio zeker het dichtst bij het punt in de regio staan. Dit vertelt ons veel over wat ons nabij is en is de fundamentele ruimtelijke relatie in Voronoi-diagrammen.
Het omgekeerde van een Voronoi-diagram wordt de Delaunay-triangulatie genoemd. Dit diagram bestaat uit lijnen van elk punt naar de dichtstbijzijnde buren en elke lijn staat loodrecht op de Voronoi-rand die het kruist. Hier is hoe het eruit ziet:
De witte lijnen zijn de Delaunay-lijnen. Elke Delaunay-lijn komt overeen met één en slechts één Voronoi-rand. Hoewel het op het eerste gezicht lijkt op een overlapping van meerdere randen, laten we het eens van dichterbij bekijken en verduidelijken wat we zien.
Hier is de groene Delaunay-lijn gerelateerd aan de roze Voronoi-rand. Je moet je gewoon voorstellen dat de roze rand zich verder uitstrekt en dan zul je zien dat ze elkaar kruisen.
Met Delaunay kunt u zien dat we nu een reeks driehoeken hebben in plaats van veelpuntige polygonen. Dit is ongelooflijk handig omdat we nu een gebied hebben onderverdeeld in renderbare driehoeken. Deze techniek kan worden gebruikt voor tessellation of triangulatie van vormen. Super cool!
Het is ook een geweldige manier om de verzameling punten als een grafiek op te bouwen, voor het geval u van het ene punt naar het andere wilt gaan. Stel je voor dat de punten steden zijn.
Oké, we weten hoe Voronoi eruit ziet; laten we nu een kijkje nemen naar de datastructuur voor een Voronoi-diagram. Eerst moeten we de punten opslaan die de basis vormen van het Voronoi-diagram:
klasse VoronoiPoint float x float y VoronoiRegion * region
Elk VoronoiPoint heeft een locatie (x, y), en een verwijzing naar de regio waarin het zich bevindt.
Vervolgens moeten we het VoronoiRegion:
class VoronoiRegion VoronoiPoint * punt Rand * randen [] // onze lijst met randen
De regio slaat een verwijzing naar zijn op VoronoiPoint, evenals een lijst van de VoronoiEdges dat bond het.
Laten we nu kijken naar de VoronoiEdges:
class VoronoiEdge VoronoiPoint * pointA VoronoiPoint * pointB float distance // afstand tussen punt A en punt B float x1, z1, x2, z2 // om het begin en einde van de rand te visualiseren
Een rand kent de twee punten die deze definiëren, evenals de afstand ertussen. Voor visuele weergave of voor het opbouwen van de werkelijke vorm van het polygoongebied, moet u de begin- en eindpunten van de rand opslaan.
En daar hebben we het. Met die informatie kunnen we eenvoudig het diagram van Voronoi gebruiken. Verderop zullen we bekijken hoe we het Voronoi-diagram daadwerkelijk kunnen genereren. Maar laten we nu eens kijken naar enkele voorbeelden van hoe we de gegevens kunnen gebruiken.
Laten we nog een keer kijken naar het puntenoverzicht van Voronoi.
Als elk punt een gezondheidspakket was, kon je vrij snel achterhalen waar de dichtstbijzijnde was - maar eerst moet je de regio vinden waarin je je bevindt. Voronoi biedt geen efficiënte manier om dit uit de doos te vinden. U kunt echter een verwijzing naar elke regio in een kwadratuur of een R-structuur opslaan, zodat de opzoeksnelheid snel is. En als je eenmaal je regio hebt, kun je de buren en hun buren vinden.
Als het zorgpakket in uw regio bijvoorbeeld weg is, hebt u een manier nodig om het dichtstbijzijnde dichtstbijzijnde pakket te vinden. Als we verwijzen naar onze gegevensstructuur en de bovenstaande pseudocode, zien we dat we vanuit een regio de randen ervan kunnen achterhalen. En met die randen kunnen we dan de buren bereiken. Pak de dichtstbijzijnde buur en dan kunnen we zien of het een gezondheidspakket heeft.
De Delaunay-triangulatie kan hier ook worden gebruikt. Het bestaat uit lijnen tussen elk van de health packs. Dit kan dan worden doorlopen met A * -padvinden om het volgende dichtstbijzijnde pakket te vinden, als het gebeurt dat iemand alle packs bij jou in de buurt heeft gepakt.
Laten we ons in plaats van gezondheidspakketten elk punt voorstellen als een vijandige wachttoren. Je moet de veiligste manier om ze te vinden vinden zonder te worden betrapt. Een veelgebruikte methode voor het doorlopen van een grafiek in videogames is het gebruik van het A * -algoritme (http://en.wikipedia.org/wiki/A*_search_algorithm). Omdat het Voronoi-diagram een grafiek is, is dit eenvoudig in te stellen. U hoeft alleen maar een A * -algoritme te hebben dat generieke grafiestructuren ondersteunt; een beetje planning van tevoren kan hier zijn vruchten afwerpen.
Als de grafiek is ingesteld, moeten we elke rand wegen. De gewichtswaarde waarmee we ons bezighouden, is de afstand van deze wachttorens, en we kunnen dit rechtstreeks van onze gegevensstructuur halen: elk VoronoiEdge weet de afstand tussen de twee punten al. Normaal gesproken is een lagere waarde op een A * -rand beter, maar in dit geval willen we dat de grotere waarde idealer is, omdat deze de afstand tot de toren weergeeft.
Hier is hoe de startgrafiek eruit ziet als we van punt A naar punt B willen gaan:
Door het gewicht op elke rand toe te passen, gaan we kijken welke route het beste is om te nemen:
De rode randen vertegenwoordigen de dichtstbijzijnde ontmoetingen met de torens. De oranje minder; minder geel dan dat; en tenslotte is groen de veiligste. Het uitvoeren van A * met deze gewichten zou het volgende pad moeten opleveren:
Als u de gewichten op deze manier gebruikt, bent u niet verzekerd van de snelste pad, maar de veiligste, dat is wat je wilt. Het zou ook verstandig zijn als de AI dicht bij dat pad blijft en vermijden dwalen!
Een andere stap die u kunt nemen garantie veilige doorgang is het verwijderen van randen die onder een minimale veilige afstand vallen. Als elke bewakingskolom bijvoorbeeld een zichtbereik van 30 eenheden heeft, kunnen randen waarvan de afstand tot hun punten kleiner is dan die van de grafiek worden verwijderd en helemaal niet worden doorlopen.
Een ander gebruik hiervan is om de breedste route te vinden voor eenheden die groot zijn en niet door nauwe ruimtes passen. Omdat elke rand een afstand heeft tussen de twee punten, weten we of deze door die ruimte kan passen.
Omgekeerd, als we in plaats daarvan een Delaunay triangulatie van het diagram zouden gebruiken, zouden we lijnen krijgen vanaf elke bewakings toren. Een bewaker AI die op een toren is gestationeerd, kan snel achterhalen wat de andere torens in de buurt zijn, en mogelijk naar een van de nabijgelegen torens gaan om te helpen indien nodig.
Stel dat je een pak kattenkruid lucht wilt laten vallen voor een hele hoop schattige kittens in een veld. Wat is de beste locatie om het te laten vallen zodat de meeste kittens ervan kunnen genieten? Dit kan een zeer, zeer dure berekening worden. Maar gelukkig kunnen we een gefundeerde schatting maken door onze Delaunay-triangulatie te gebruiken.
Tip: Vergeet niet dat de Delaunay-triangulatie slechts het omgekeerde is van het Voronoi-diagram. Het wordt eenvoudigweg gevormd door het samenvoegen van elk Voronoi-punt met zijn buurpunten verkregen uit de lijst met randen.
Met deze verzameling driehoeken kunnen we het gebied onderzoeken dat elke driehoek bedekt. Als we de driehoek met het kleinste gebied vinden, hebben we de drie dichtstbijzijnde punten of kittens. Het is misschien niet het dichtste gemiddelde pakket van kittens in het veld, maar het is een goede inschatting. Als we meerdere catnip-pakketten kunnen laten vallen, kunnen we gewoon aangeven welke driehoeken we al hebben getarget en de volgende kleinste pakken.
De weergave van deze gebieden is ook bekend als de circum-kringen van de Delaunay-triangulatie. Elke cirkel is de grootste cirkel die past binnen de punten van de driehoeken. Hier is een afbeelding van de circum-cirkels voor een Voronoi-diagram:
U kunt het exacte midden van de cirkels gebruiken om het midden van het gebied te bepalen om het catnip-pakket te laten vallen. De straal van de cirkel is eigenlijk een betere methode om te bepalen wat de beste driehoek is die moet worden neergezet in plaats van het driehoeksgebied - vooral als twee punten van een driehoek erg dicht bij elkaar zijn en de ene is ver weg, waardoor een zeer scherpe driehoek ontstaat met een klein gebied, maar wel representatief punten die eigenlijk vrij ver uit elkaar liggen.
Er zijn verschillende manieren om Voronoi-diagrammen te genereren en het tijdstip waarop u de gegevens hebt, kan u helpen bepalen welke techniek u moet gebruiken.
De snelste methode wordt genoemd Fortune's Line-sweep algoritme. Het is O (n log (n)) en vereist dat alle punten die worden gebruikt om de grafiek te genereren, aanwezig zijn op het moment van genereren. Als je later nieuwe punten toevoegt, moet je de hele grafiek opnieuw genereren. Dit is misschien niet zo belangrijk met een paar punten, maar als je 100.000 hebt, kan het een tijdje duren!
Het implementeren van dit algoritme is niet triviaal. Je moet parabolen doorkruisen en een aantal speciale gevallen behandelen. Het is echter de snelste techniek. Gelukkig zijn er veel open source-implementaties van die je al kunt gebruiken en we hebben ze hier gekoppeld.
Laten we even kijken hoe het werkt.
Het algoritme bestaat uit het vegen van een lijn (verticaal of horizontaal) over het gebied van punten. Wanneer het een punt tegenkomt, begint het een parabool te tekenen die doorgaat met de zwaaiende lijn. Hier is een animatie van het proces:
(Afbeelding met dank aan Mnbayazit, vrijgegeven voor het publieke domein.) De kruisende parabolen produceren de Voronoi-randen. Waarom parabolen echter?
Om dat te begrijpen, stel je elk punt in dat een ballon bevat die uitzet totdat deze in contact komt met een andere ballon. U kunt dit idee uitpakken in cirkels die zich uitbreiden op een 2D-vlak. We gaan een stap verder en plaatsen een omgekeerde kegel op elk punt, een kegel met een helling van 45 graden en die gaat tot in het oneindige. We stellen ons dan de sweeplijn voor als een vlak, ook op 45 graden, dat doorloopt tot het in contact komt met de kegels. Omdat het vlak en de kegels dezelfde hoek maken, produceren ze parabolen wanneer ze elkaar snijden.
Naarmate de kegels verticaal groeien, zullen ze uiteindelijk een of meer andere kegels kruisen. Als we kijken naar waar de kegels of cirkels elkaar snijden, krijgen we de rechte lijnen van de Voronoi-randen. Hier kunt u de rode lijn zien van waar de kegels elkaar kruisen. Als de kegels iets groter werden (verticaal naar het oneindige), zou de rode lijn zich blijven uitbreiden.
Wanneer het vliegtuig naar voren veegt en voor het eerst contact maakt met een kegel, wordt een lijn als volgt geproduceerd:
Terwijl het vliegtuig door de kegels beweegt, zie je de parabolen vormen:
Het vliegtuig gaat door de scène. Voor elk punt dat het tegenkomt, onderzoekt het de buurpunten op de sweeplijn die al parabolen hebben en begint op dit punt een nieuwe parabool. Het blijft doorgaan en groeien totdat deze nieuwe parabool begint te overlappen met een andere dan voorheen. Die vorige parabool is dan afgesloten. Dit is een plaats waar drie punten 'Voronoi-lijnen' samenkomen.
Zoals eerder vermeld, is het een beetje ingewikkeld, dus hier zijn enkele open source-implementaties die u kunt gebruiken en onderzoeken:
Een andere methode is om stapsgewijs één punt per keer in te voegen, te beginnen met een basisdriehoek van drie punten buiten het mogelijke bereik van alle andere punten. Deze techniek is O (n ^ 2) en vereist niet dat alle punten aanwezig zijn op het moment van opwekking.
Wanneer een nieuw punt wordt ingevoegd, lokaliseert het een bestaande regio waarin het past. Die regio wordt vervolgens onderverdeeld en nieuwe regio's worden gemaakt.
Hier is een open source-voorbeeld dat u kunt gebruiken en onderzoeken:
Inmiddels zou je een idee moeten hebben van wat Voronoi-diagrammen kunnen bieden voor je game en zijn AI. Met een goed gestructureerde grafiek van knooppunten en randen kunt u belangrijke informatie opvragen om ervoor te zorgen dat de kittens de catnip krijgen die ze nodig hebben en dat u de veiligste route kunt nemen om bij hen te komen. En, voor het geval dat, kunt u ook vinden waar de dichtstbijzijnde Med-kit is.
Accentsconagua