Share
Une navigation décente des PNJ nécessite souvent la capacité d’éviter les obstacles. Ce tutoriel couvre les évitement de collision comportement de pilotage, qui permet aux personnages d'esquiver gracieusement un nombre quelconque d'obstacles dans l'environnement.
Remarque: Bien que ce tutoriel ait été écrit avec AS3 et Flash, vous devriez pouvoir utiliser les mêmes techniques et concepts dans presque tous les environnements de développement de jeux. Vous devez avoir une compréhension de base des vecteurs mathématiques.
L'idée de base de la prévention des collisions est de générer une force de direction permettant d'éviter les obstacles chaque fois que l'on est suffisamment proche pour bloquer le passage. Même si l'environnement présente plusieurs obstacles, ce comportement utilisera un à la fois pour calculer la force d'évitement..
Seuls les obstacles à venir du personnage sont analysés. le plus proche, considéré comme le plus menaçant, est sélectionné pour évaluation. En conséquence, le personnage est capable d'esquiver tous les obstacles de la zone et de passer de l'un à l'autre de manière élégante et transparente..
Le comportement d'évitement des collisions n'est pas un algorithme de recherche de chemin. Cela incitera les personnages à se déplacer dans l'environnement, en évitant les obstacles et en trouvant un chemin pour traverser les blocs - mais cela ne fonctionne pas très bien avec les obstacles en "L" ou "T", par exemple.
Pointe: Ce comportement d'évitement de collision peut sembler similaire au comportement de fuite, mais il existe une différence importante entre eux. Un personnage qui se déplace près d'un mur ne l'évitera que s'il bloque le passage, mais le comportement de fuite éloignera toujours le personnage du mur..La première étape pour éviter les obstacles dans l’environnement est de les percevoir. Les seuls obstacles que le personnage doit s'inquiéter sont ceux qui se trouvent devant et qui bloquent directement la route en cours..
Comme expliqué précédemment, le vecteur vitesse décrit la direction du caractère. Il sera utilisé pour produire un nouveau vecteur appelé devant, qui est une copie du vecteur vitesse, mais avec une longueur différente:
Accentsconagua
devant le vecteur est la ligne de mire du personnage. Ce vecteur est calculé comme suit:
ahead = position + normaliser (vélocité) * MAX_SEE_AHEAD
le devant longueur du vecteur (ajustée avec MAX_SEE_AHEAD) définit jusqu'où le personnage "verra".
Le meilleur MAX_SEE_AHEAD C'est-à-dire que plus tôt le personnage commencera à agir pour éviter un obstacle, car il le percevra comme une menace même s'il est éloigné:
Pour vérifier la collision, chaque obstacle (ou son cadre de sélection) doit être décrit comme une forme géométrique. L'utilisation d'une sphère (cercle en deux dimensions) donne les meilleurs résultats, ainsi chaque obstacle de l'environnement sera décrit comme tel..
Une solution possible pour vérifier la collision est l'intersection ligne-sphère - la ligne est la devant vecteur et la sphère est l'obstacle. Cette approche fonctionne, mais je vais utiliser une simplification de ce qui est plus facile à comprendre et a des résultats similaires (parfois même meilleurs)..
le devant vecteur sera utilisé pour produire un autre vecteur avec la moitié de sa longueur:
le à venir2 le vecteur est calculé exactement comme devant, mais sa longueur est coupée en deux:
ahead = position + normaliser (vitesse) * MAX_SEE_AHEAD ahead2 = position + normaliser (vitesse) * MAX_SEE_AHEAD * 0.5
Nous souhaitons effectuer une vérification de collision pour vérifier si l'un ou l'autre de ces deux vecteurs se trouve à l'intérieur de la sphère d'obstacle. Ceci est facilement accompli en comparant la distance entre l'extrémité du vecteur et le centre de la sphère.
Si la distance est inférieure ou égale au rayon de la sphère, le vecteur est à l'intérieur de la sphère et une collision a été détectée:
Si non plus des deux vecteurs en avant sont à l'intérieur de la sphère d'obstacle, alors cet obstacle bloque le chemin. La distance euclidienne entre deux points peut être utilisée:
fonction privée distance (a: objet, b: objet): nombre return Math.sqrt ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); fonction privée lineIntersectsCircle (ahead: Vector3D, ahead2: Vector3D, obstacle: Circle): Boolean // la propriété "centre" de l'obstacle est un Vector3D. distance de retour (obstacle.center, en avant) <= obstacle.radius || distance(obstacle.center, ahead2) <= obstacle.radius;
Si plus d'un obstacle bloque le passage, alors le plus proche ("le plus menaçant") est sélectionné pour le calcul:
La force d'évitement doit éloigner le personnage de l'obstacle, lui permettant d'esquiver la sphère. Cela peut être fait en utilisant un vecteur formé en utilisant le centre de la sphère (qui est un vecteur de position) et le devant vecteur. Nous calculons cette force d’évitement comme suit:
Avoidance_force = ahead - obstacle_center Avoidance_force = Normaliser (Avoidance_force) * MAX_AVOID_FORCE
Après force d'évitement est calculé, il est normalisé et mis à l'échelle par MAX_AVOID_FORCE, qui est un nombre utilisé pour définir la force d'évitement longueur. Le meilleur MAX_AVOID_FORCE le plus fort est la force d'évitement qui éloigne le personnage de l'obstacle.
La mise en œuvre finale pour le évitement de collision() La méthode qui renvoie la force d’évitement est la suivante:
fonction privée collisionAvoidance (): Vector3D ahead =…; // calcule le vecteur à venir ahead2 =…; // calcule le vecteur ahead2 var mostThreatening: Obstacle = findMostThreateningObstacle (); évitement var: Vector3D = nouveau Vector3D (0, 0, 0); if (mostThreatening! = null) Avoidance.x = ahead.x - MostThreatening.center.x; Avoidance.y = ahead.y - mostThreatening.center.y; evitement.normalise (); Avoidance.scaleBy (MAX_AVOID_FORCE); else Avoidance.scaleBy (0); // annule la force d'évitement return evitance; fonction privée findMostThreateningObstacle (): Obstacle var mostThreatening: Obstacle = null; pour (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;
La force d'évitement doit être ajoutée au vecteur vitesse du personnage. Comme expliqué précédemment, toutes les forces de direction peuvent être combinées en une seule, produisant une force qui représente tout comportement actif agissant sur le personnage..
En fonction de l'angle et de la direction de la force d'évitement, cela n'interrompra pas les autres forces de direction, telles que la recherche ou le dérapage. La force d’évitement s’ajoute à la vitesse du joueur comme d’habitude:
direction = rien (); // le vecteur nul, signifiant "magnitude zéro force" Steering = Steering + seek (); // en supposant que le personnage cherche quelque chose direction = direction + collisionAvoidance (); direction = troncature (direction, force max.) direction = direction / vitesse de la masse = troncature (vitesse + direction, vitesse maximale) position = position + vitesse
Puisque tous les comportements de direction sont recalculés à chaque mise à jour du jeu, la force d’évitement reste active tant que l’obstacle bloque le passage..
Dès que l'obstacle n'intercepte pas le devant ligne d’effet, la force d’évitement deviendra nulle (pas d’effet) ou sera recalculée pour éviter le nouvel obstacle menaçant. Le résultat est un personnage capable d'éviter les obstacles:
La mise en œuvre actuelle pose deux problèmes, tous deux liés à la détection de collision. Le premier arrive quand le devant les vecteurs sont en dehors de la sphère obstacle, mais le personnage est trop proche de (ou à l'intérieur) de l'obstacle.
Si cela se produit, le personnage touchera (ou entrera) l'obstacle en ignorant le processus d'évitement car aucune collision n'a été détectée:
devant les vecteurs sont en dehors de l'obstacle, mais le personnage est à l'intérieur. Ce problème peut être résolu en ajoutant un troisième vecteur à la vérification de collision: le vecteur de position du personnage. L’utilisation de trois vecteurs améliore considérablement la détection des collisions.
Le deuxième problème survient lorsque le personnage se trouve près de l'obstacle et s'en éloigne. Parfois, la manœuvre provoque une collision, même si le personnage tourne pour faire face à une autre direction:
Ce problème peut être résolu en mettant à l'échelle le devant les vecteurs en fonction de la vitesse actuelle du personnage. Le code pour calculer le devant le vecteur, par exemple, devient:
dynamic_length = longueur (vélocité) / MAX_VELOCITY ahead = position + normaliser (vélocité) * dynamic_length
La variable longueur_dynamique sera compris entre 0 et 1. Lorsque le personnage se déplace à toute vitesse, longueur_dynamique est 1; quand le personnage ralentit ou accélère, longueur_dynamique est égal à 0 ou supérieur (par exemple 0,5).
En conséquence, si le personnage est juste en train de manœuvrer sans bouger, longueur_dynamique tend à zéro, produisant un zéro devant vecteur, qui n'a pas de collisions.
Voici le résultat avec ces améliorations:
Afin de démontrer le comportement d'évitement des collisions en action, je pense qu'une horde de zombies est la solution idéale. Ci-dessous, une démo montrant plusieurs zombies (de vitesses différentes) cherchant le curseur de la souris. Art par SpicyPixel et Clint Bellanger, d'OpenGameArt.
Le comportement d'évitement des collisions permet à n'importe quel personnage d'esquiver les obstacles dans l'environnement. Toutes les forces de pilotage étant recalculées à chaque mise à jour du jeu, les personnages interagissent de manière transparente avec différents obstacles, en analysant toujours le plus menaçant (le plus proche)..
Bien que ce comportement ne soit pas un algorithme de recherche de chemin, les résultats obtenus sont assez convaincants pour les cartes encombrées.
