Share
Goede NPC-navigatie vereist vaak het vermogen om obstakels te vermijden. Deze tutorial behandelt de het uit de weg gaan van botsingen stuurgedrag, waardoor personages gracieus allerlei obstakels in de omgeving kunnen ontwijken.
Notitie: Hoewel deze tutorial geschreven is met behulp van AS3 en Flash, zou je in bijna elke game-ontwikkelomgeving dezelfde technieken en concepten moeten kunnen gebruiken. Je moet een basiskennis hebben van wiskundige vectoren.
Het basisidee achter het vermijden van botsingen is om een stuurkracht te genereren om obstakels te ontwijken telkens als er een dichtbij genoeg is om de doorgang te blokkeren. Zelfs als de omgeving meerdere obstakels heeft, gebruikt dit gedrag een van hen tegelijkertijd om de ontwijkingskracht te berekenen.
Alleen de obstakels die voor het personage liggen, worden geanalyseerd; de dichtstbijzijnde, naar men zegt de meest bedreigende, wordt geselecteerd voor evaluatie. Het resultaat is dat het personage alle obstakels in het gebied kan ontwijken en elegant en naadloos van de ene naar de andere kan overschakelen.
Het botsingsvermijdingsgedrag is geen padzoekalgoritme. Het zorgt ervoor dat personages zich door de omgeving verplaatsen, obstakels vermijden en uiteindelijk een route vinden om door de blokken te gaan - maar het werkt niet echt goed met "L" of "T" obstakels, bijvoorbeeld.
Tip: Dit gedrag om botsingen te vermijden lijkt misschien op het vluchtgedrag, maar er is een belangrijk verschil tussen beide. Een personage dat in de buurt van een muur komt, vermijdt het alleen als het de weg blokkeert, maar het vlieggedrag zal het personage altijd van de muur duwen.De eerste stap om obstakels in de omgeving te vermijden, is ze waar te nemen. De enige obstakels waar het personage zich zorgen over moet maken, zijn degenen die ervoor staan en die de huidige route direct blokkeren.
Zoals eerder uitgelegd, beschrijft de snelheidsvector de richting van het personage. Het zal worden gebruikt om een nieuwe vector te produceren genaamd verder, wat een kopie is van de snelheidsvector, maar met een andere lengte:
Accentsconagua
verder vector is de gezichtslijn van het personage. Deze vector wordt als volgt berekend:
vooruit = positie + normaliseren (snelheid) * MAX_SEE_AHEAD
De verder vectorlengte (aangepast met MAX_SEE_AHEAD) definieert hoe ver het personage "ziet".
Hoe groter MAX_SEE_AHEAD is, hoe eerder het karakter begint te handelen om een obstakel te ontwijken, omdat het het als een bedreiging zal zien, zelfs als het ver weg is:
Om te controleren op een botsing, moet elk obstakel (of zijn begrenzingsvak) worden beschreven als een geometrische vorm. Het gebruik van een bol (cirkel in twee dimensies) geeft de beste resultaten, zodat elk obstakel in de omgeving als zodanig wordt beschreven.
Een mogelijke oplossing om te controleren op een botsing is het snijpunt van de lijnbol - de lijn is de verder vector en de bol is het obstakel. Die aanpak werkt, maar ik ga een vereenvoudiging gebruiken van dat wat makkelijker te begrijpen is en vergelijkbare resultaten heeft (soms zelfs betere).
De verder vector zal worden gebruikt om een andere vector te produceren met de helft van de lengte:
De ahead2 vector is precies zoals berekend verder, maar de lengte ervan wordt gehalveerd:
vooruit = positie + normaliseren (snelheid) * MAX_SEE_AHEAD vooruit2 = positie + normaliseren (snelheid) * MAX_SEE_AHEAD * 0,5
We willen een botsingcontrole uitvoeren om te testen of een van deze twee vectoren zich binnen de hindernisbol bevindt. Dat wordt eenvoudig bereikt door de afstand tussen het uiteinde van de vector en het midden van de bol te vergelijken.
Als de afstand kleiner is dan of gelijk is aan de bolstraal, bevindt de vector zich in de bol en is een botsing gevonden:
Als een van beide van de twee voorste vectoren bevinden zich binnen de hindernisbol, dan blokkeert dat obstakel de weg. De euclidische afstand tussen twee punten kan worden gebruikt:
persoonlijke functie afstand (a: Object, b: Object): Number return Math.sqrt ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); private function lineIntersectsCircle (ahead: Vector3D, ahead2: Vector3D, obstacle: Circle): Boolean // de eigenschap "center" van het obstakel is een Vector3D. terugkeer afstand (obstacle.center, vooruit) <= obstacle.radius || distance(obstacle.center, ahead2) <= obstacle.radius;
Als meer dan één obstakel de weg blokkeert, wordt de dichtstbijzijnde (de "meest bedreigende") geselecteerd voor berekening:
De ontwijkingskracht moet het karakter weg van het obstakel duwen, waardoor het de bol kan ontwijken. Het kan worden gedaan met behulp van een vector die wordt gevormd door het middelpunt van de bol te gebruiken (die een positievector is) en de verder vector. We berekenen deze ontwijkingskracht als volgt:
avoidance_force = ahead - obstacle_center avoidance_force = normalize (avoidance_force) * MAX_AVOID_FORCE
Na avoidance_force wordt berekend dat het wordt genormaliseerd en geschaald door MAX_AVOID_FORCE, dat is een nummer dat wordt gebruikt om het te definiëren avoidance_force lengte. Hoe groter MAX_AVOID_FORCE is, des te sterker is de ontwijkingskracht die het personage weg duwt van het obstakel.
De uiteindelijke implementatie voor de het uit de weg gaan van botsingen() methode, die de ontwijkingskracht teruggeeft, is:
persoonlijke functie collisionAvidance (): Vector3D ahead = ...; // bereken de toekomstige vector ahead2 = ...; // bereken de ahead2 vector var mostThreating: Obstacle = findMostThreateningObstacle (); var avoidance: Vector3D = new Vector3D (0, 0, 0); if (mostThreating! = null) avoidance.x = ahead.x - mostThreatening.center.x; avoidance.y = ahead.y - mostThreatening.center.y; avoidance.normalize (); avoidance.scaleBy (MAX_AVOID_FORCE); else avoidance.scaleBy (0); // vernietig de ontwijkingskracht terugkeervermijding; private function findMostThreateningObstacle (): Obstacle var mostThreating: Obstacle = null; for (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;
De ontwijkingskracht moet worden toegevoegd aan de snelheidsvector van het personage. Zoals eerder uitgelegd, kunnen alle stuurkrachten worden gecombineerd tot één, waardoor een kracht wordt geproduceerd die alle actieve gedrag weergeeft dat op het personage inwerkt.
Afhankelijk van de hoek en richting van de vermijdingskracht worden andere stuurkrachten, zoals zoeken of afdwalen, niet onderbroken. De ontwijkingskracht wordt zoals gebruikelijk aan de afspeelsnelheid toegevoegd:
besturing = niets (); // de nulvector, wat betekent "nulkrachtmagnitude" besturing = sturen + zoeken (); // ervan uitgaande dat het personage iets zoekt dat stuurt = sturen + botsingAvoidance (); sturen = afbreken (sturen, max_kracht) sturen = sturen / massasnelheid = afbreken (snelheid + sturen, max_snelheid) positie = positie + snelheid
Aangezien alle besturingsgedragingen elke game-update opnieuw berekenen, blijft de ontwijkingskracht actief zolang het obstakel de weg blokkeert.
Zodra het obstakel de verder vectorlijn, wordt de ontwijkingskracht nul (geen effect) of wordt deze herberekend om het nieuwe dreigende obstakel te vermijden. Het resultaat is een personage dat obstakels kan ontwijken:
De huidige implementatie heeft twee problemen, beide gerelateerd aan de botsingsdetectie. De eerste gebeurt wanneer het verder vectoren bevinden zich buiten de hindernisbol, maar het personage bevindt zich te dicht bij (of binnen) het obstakel.
Als dat gebeurt, zal het personage het obstakel raken (of binnengaan) en het vermijdingsproces overslaan omdat er geen botsing werd gedetecteerd:
verder vectoren bevinden zich buiten het obstakel, maar het personage bevindt zich binnenin. Dit probleem kan worden opgelost door een derde vector toe te voegen aan de collisioncheck: de positievector van het personage. Het gebruik van drie vectoren verbetert de botsingsdetectie aanzienlijk.
Het tweede probleem doet zich voor wanneer het personage zich dicht bij het obstakel bevindt en er vanaf weggaat. Soms leidt het manoeuvreren tot een botsing, hoewel het personage alleen maar draait om een andere richting op te gaan:
Dat probleem kan worden opgelost door de verder vectoren volgens de huidige snelheid van het personage. De code om het te berekenen verder vector, bijvoorbeeld, is veranderd in:
dynamic_length = lengte (velocity) / MAX_VELOCITY ahead = position + normalize (velocity) * dynamic_length
De variabele dynamic_length zal variëren van 0 tot 1. Wanneer het personage op volle snelheid beweegt, dynamic_length is 1; wanneer het personage vertraagt of versnelt, dynamic_length is 0 of groter (bijvoorbeeld 0,5).
Als gevolg hiervan, als het personage gewoon manoeuvreert zonder te bewegen, dynamic_length neigt naar nul, produceert een nul verder vector, die geen botsingen heeft.
Hieronder is het resultaat met deze verbeteringen:
Om het botsingsvermijdingsgedrag in actie te demonstreren, denk ik dat een horde zombies de perfecte pasvorm heeft. Hieronder is een demo met verschillende zombies (met verschillende snelheden) op zoek naar de muiscursor. Kunst van SpicyPixel en Clint Bellanger, van OpenGameArt.
Het botsingsvermijdingsgedrag laat elk personage obstakels in de omgeving ontwijken. Aangezien alle stuurkrachten elke game-update opnieuw berekenen, werken de personages naadloos op verschillende obstakels in, waarbij altijd de meest bedreigende (het dichtst) wordt geanalyseerd.
Hoewel dit gedrag geen padzoekalgoritme is, zijn de behaalde resultaten tamelijk overtuigend voor overvolle kaarten.
