Share
Anständig NPC-navigering kräver ofta förmåga att undvika hinder. Denna handledning täcker kollisionsundvikande styrning beteende, vilket gör att tecken graciöst undviker några hinder i miljön.
Notera: Även om denna handledning skrivs med AS3 och Flash, borde du kunna använda samma tekniker och begrepp i nästan vilken spelutvecklingsmiljö som helst. Du måste ha en grundläggande förståelse för matematiska vektorer.
Grundidén bakom kollisionsundvikande är att skapa en styrkraft för att undvika hinder varje gång man är tillräckligt nära för att blockera passagen. Även om miljön har flera hinder, kommer detta beteende att använda en av dem i taget för att beräkna undvikningskraften.
Endast hindren framför karaktären analyseras; Den närmaste, som sägs vara den mest hotande, är vald för utvärdering. Som ett resultat kan karaktären undvika alla hinder i området, övergången från en till en annan graciöst och sömlöst.
Kollisionsundviklingsbeteendet är inte en sökfelsalgoritm. Det kommer att göra tecken rör sig genom miljön, undvika hinder, så småningom hitta en väg att gå igenom blocken - men det fungerar inte riktigt bra med "L" eller "T" hinder, till exempel.
Tips: Detta kollisionsundvikande beteende kan låta likna flygningsbeteendet, men det finns en viktig skillnad mellan dem. Ett tecken som rör sig nära en vägg kommer att undvika det bara om det blockerar vägen, men flyktsättet kommer alltid att trycka tecknet bort från väggen.Det första steget att undvika hinder i miljön är att uppfatta dem. De enda hinder som karaktären måste oroa är de som står framför den och direkt blockerar den nuvarande vägen.
Som tidigare förklarat beskriver hastighetsvektorn karaktärens riktning. Det kommer att användas för att producera en ny vektor som heter ett huvud, vilken är en kopia av hastighetsvektorn men med en annan längd:
Accentsconagua
ett huvud vektorn är karaktärens synfält. Denna vektor beräknas enligt följande:
framåt = position + normalisera (hastighet) * MAX_SEE_AHEAD
De ett huvud vektorlängd (justerad med MAX_SEE_AHEAD) definierar hur långt tecknet kommer att "se".
Ju större MAX_SEE_AHEAD ju desto tidigare börjar karaktären att agera för att undvika ett hinder, för att det uppfattar det som ett hot även om det är långt ifrån:
För att kontrollera efter kollision måste varje hinder (eller dess avgränsningsbox) beskrivas som en geometrisk form. Att använda en sfär (cirkel i två dimensioner) ger de bästa resultaten, så alla hinder i miljön kommer att beskrivas som sådana.
En möjlig lösning för att kontrollera om kollisionen är linjär korsning - linjen är ett huvud vektor och sfären är hindret. Det här tillvägagångssättet fungerar, men jag kommer att använda en förenkling av det som är lättare att förstå och har liknande resultat (ännu bättre ibland).
De ett huvud vektor kommer att användas för att producera en annan vektor med hälften av dess längd:
De ahead2 vektorn beräknas exakt som ett huvud, men dess längd är skuren i halva:
framåt = position + normalisera (hastighet) * MAX_SEE_AHEAD ahead2 = position + normalisera (hastighet) * MAX_SEE_AHEAD * 0,5
Vi vill utföra en kollisionskontroll för att testa om någon av de två vektorerna är inuti hinderzonen. Det uppnås lätt genom att jämföra avståndet mellan vektorns ände och sfärens centrum.
Om avståndet är mindre än eller lika med sfärraden är vektorn inuti sfären och en kollision hittades:
Om antingen av de två framåtriktade vektorerna är inuti hinder sfären, då hindrar detta hinder vägen. Det euklidiska avståndet mellan två punkter kan användas:
privata funktionsavstånd (a: Objekt, b: Objekt): Nummer returnera Math.sqrt ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); privat funktionslinjeIntersectsCircle (framåt: Vector3D, ahead2: Vector3D, hinder: Circle): Booleska // egenskapen "center" av hinderet är en Vector3D. returavstånd (hinder.center, framåt) <= obstacle.radius || distance(obstacle.center, ahead2) <= obstacle.radius;
Om mer än ett hinder blockerar vägen väljs den närmaste ("mest hotande") för beräkning:
Undvikningskraften måste trycka karaktären bort från hinderet, så att den kan undvika sfären. Det kan göras med hjälp av en vektor som bildas genom att använda sfärens mitt (vilket är en positionsvektor) och ett huvud vektor. Vi beräknar denna undvikande kraft enligt följande:
avoidance_force = ahead - obstacle_center avoidance_force = normalisera (avoidance_force) * MAX_AVOID_FORCE
Efter avoidance_force beräknas det är normaliserat och skalas av MAX_AVOID_FORCE, vilket är ett tal som används för att definiera avoidance_force längd. Ju större MAX_AVOID_FORCE desto starkare är undvikningskraften som skjuter karaktären bort från hinderet.
Den slutliga genomförandet för kollisionsundvikande() metod som returnerar undvikningskraften är:
privat funktionskollisionAvoidance (): Vector3D ahead = ...; // beräkna framåtriktad vektor ahead2 = ...; // beräkna framåt2 vektorn var mostThreatening: Obstacle = findMostThreateningObstacle (); var undvikande: Vector3D = ny Vector3D (0, 0, 0); om (mostThreatening! = null) avoidance.x = ahead.x - mostThreatening.center.x; avoance.y = ahead.y - mostThreatening.center.y; avoidance.normalize (); avoidance.scaleBy (MAX_AVOID_FORCE); annars avoidance.scaleBy (0); // nullify the avoidance force privat funktion findMostThreateningObstacle (): Hindring var mostThreatening: Hindring = null; för (var i: int = 0; i < Game.instance.obstacles.length; i++) var obstacle :Obstacle = Game.instance.obstacles[i]; var collision :Boolean = lineIntersecsCircle(ahead, ahead2, obstacle); // "position" is the character's current position if (collision && (mostThreatening == null || distance(position, obstacle) < distance(position, mostThreatening))) mostThreatening = obstacle; return mostThreatening;
Undvikningskraften måste läggas till karaktärens hastighetsvektor. Som tidigare förklarats kan alla styrkor sammanföras i ett, vilket ger en kraft som representerar allt aktivt beteende som verkar på karaktären.
Beroende på undvikningskraftens vinkel och riktning kommer det inte att avbryta andra styrkor, som att söka eller vandra. Undvikningskraften läggs till spelarens hastighet som vanligt:
styrning = inget (); // nollvektorn, som betyder "nollstyrka" styrning = styrning + sök (); // förutsatt att tecknet söker något styrning = styrning + kollisionAvoidance (); styrning = stympa (styrning, max_force) styrning = styrning / masshastighet = trunkera (hastighet + styrning, max_hastighet) position = läge + hastighet
Eftersom alla styrningsbeteenden omräknas varje speluppdatering kommer undvikningskraften att förbli aktiv så länge hinderet blockerar vägen.
Så snart hindret inte avlyssnar ett huvud vektorlinjen kommer undvikningskraften att bli null (ingen effekt) eller det kommer att beräknas för att undvika det nya hotande hinderet. Resultatet är ett tecken som kan undvika hinder:
Det aktuella genomförandet har två problem, både relaterade till kollisionsdetektering. Den första sker när ett huvud vektorer ligger utanför hinder sfären, men karaktären är för nära (eller inuti) hindret.
Om det händer kommer tecknet att röra (eller ange) hindret och hoppa över undvikande processen eftersom ingen kollision upptäcktes:
ett huvud vektorer ligger utanför hindret, men karaktären är inuti. Detta problem kan lösas genom att lägga till en tredje vektor till kollisionskontrollen: karaktärens positionsvektor. Användningen av tre vektorer förbättrar kollisionsdetektering.
Det andra problemet händer när karaktären ligger nära hindret, styrning bort från det. Ibland kommer manövreringen att orsaka kollision, även om karaktären bara roterar för att möta en annan riktning:
Det problemet kan lösas genom att skala ett huvud vektorer enligt karaktärens aktuella hastighet. Koden för att beräkna ett huvud vektor, till exempel, ändras till:
dynamic_length = längd (hastighet) / MAX_VELOCITY framåt = position + normalisera (hastighet) * dynamic_length
Variabeln dynamic_length kommer att sträcka sig från 0 till 1. När tecknet rör sig i full hastighet, dynamic_length är 1; när tecknet saktar eller accelererar, dynamic_length är O eller större (t ex 0,5).
Som en konsekvens, om karaktären bara manövrerar utan att flytta, dynamic_length tenderar att nollställa en nullställning ett huvud vektor, som inte har några kollisioner.
Nedan är resultatet med dessa förbättringar:
För att demonstrera kollisionen undvikande beteende i åtgärd, tror jag att en horde av zombies är den perfekta passformen. Nedan är en demonstration som visar flera zombier (med olika hastigheter) som söker muspekaren. Konst av SpicyPixel och Clint Bellanger, från OpenGameArt.
Kollisionsundviklingsbeteendet gör att alla tecken kan undvika hinder i miljön. Eftersom alla styrkrafter omräknas varje speluppdatering, samverkar karaktärerna sömlöst med olika hinder och analyserar alltid den mest hotande (den närmaste).
Även om detta beteende inte är en sökningsalgoritm, är de uppnådda resultaten ganska övertygande för trånga kartor.
