Comment utiliser les diagrammes de Voronoï pour contrôler l'IA

Quel est le chemin le plus sûr à prendre, où se trouvent le plus grand nombre d’ennemis et où se trouve la trousse de soins la plus proche? Ces questions de relations spatiales communes peuvent toutes être résolues efficacement avec une routine mathématique appelée Voronoï. À la fin de ce didacticiel, vous disposerez des outils et des connaissances nécessaires pour analyser vos cartes et produire des informations essentielles au réalisme et au succès de l'IA..

Articles Similaires

Si vous souhaitez en savoir plus sur l'IA (intelligence artificielle), assurez-vous de consulter:

  • Comment accélérer une recherche de * avec l'algorithme de recherche de points de saut
  • Les trois règles simples des comportements de flocage: alignement, cohésion et séparation
  • Comprendre la série sur les comportements de conduite
  • Structure de données de la liste d'actions: bonne pour l'interface utilisateur, l'IA, les animations et autres
  • Comprendre la recherche de champs de vecteurs basés sur des objectifs

Relations spatiales

Une relation spatiale est tout ce qui décrit comment un objet dans un espace est lié à un autre. Par exemple: leur distance les uns par rapport aux autres, la superficie qu'ils couvrent et le chevauchement de leurs zones, ou le nombre d'objets situés dans une zone..

Ces relations apparaissent constamment dans les jeux vidéo et peuvent fournir des informations très utiles à l'IA, voire au joueur..


Voronoi a la réponse

UNE Diagramme de Voronoï décrit la relation spatiale entre des points proches les uns des autres ou leurs voisins les plus proches. C'est un ensemble de polygones de connexion dérivés de points ou d'emplacements. Chaque ligne d'une "région" de Voronoï est à mi-chemin entre deux points.

Ici, regardons une image pour en avoir une idée:


Ici, vous pouvez voir que chaque ligne est exactement à mi-chemin entre deux points et qu’elles se rejoignent toutes au milieu. Ajoutons quelques points supplémentaires à la scène et voyons ce qui se passe:


Maintenant, ça devient plus intéressant! Nous commençons à avoir des régions réelles.

Alors, que nous dit chaque région? Nous savons que lorsque nous sommes dans une région, nous sommes assurés d'être au plus près du seul point qui se trouve également dans la région. Cela nous en dit long sur ce qui est près de nous et constitue la relation spatiale fondamentale dans les diagrammes de Voronoï..


Voronoï à l'envers: la triangulation de Delaunay

L'inverse d'un diagramme de Voronoï s'appelle la Triangulation de Delaunay. Ce diagramme est constitué de lignes allant de chaque point à ses voisins les plus proches, et chaque ligne est perpendiculaire au bord de Voronoï qu’elle croise. Voici à quoi cela ressemble:


Les lignes blanches sont les lignes de Delaunay. Chaque ligne de Delaunay correspond à un et un seul bord de Voronoï. Bien qu'à première vue, il semble que certains bords se chevauchent, examinons de plus près et clarifions ce que nous voyons..


Ici, la ligne verte de Delaunay est liée au bord rose de Voronoï. Il suffit d’imaginer le bord rose qui s’étend plus loin et vous verrez alors qu’ils se croisent.

Avec Delaunay, vous pouvez voir que nous avons maintenant un ensemble de triangles au lieu de polygones à plusieurs points. Ceci est extrêmement utile car nous venons de subdiviser une zone en triangles à rendre. Cette technique peut être utilisée pour le pavage ou la triangulation de formes. super cool!

C'est également un excellent moyen de constituer l'ensemble des points sous forme de graphique, au cas où vous souhaiteriez vous aventurer d'un point à un autre. Imaginez juste que les points sont des villes.


Structure de données de Voronoï

Très bien, nous savons à quoi ressemble Voronoï; Regardons maintenant la structure de données pour un diagramme de Voronoï. Premièrement, nous devons stocker les points qui constituent la base du diagramme de Voronoï:

 classe VoronoiPoint float x float y VoronoiRegion * region

Chaque VoronoiPoint a un emplacement (x, y), et une référence à la région, il est à l'intérieur.

Ensuite, nous devons décrire le VoronoiRegion:

 class VoronoiRegion VoronoiPoint * point Bord * bords [] // notre liste de bords

La région stocke une référence à ses VoronoiPoint, ainsi qu'une liste des VoronoiEdges qui l'a lié.

Maintenant regardons le VoronoiEdges:

 class VoronoiEdge VoronoiPoint * pointA VoronoiPoint * pointB distance float // distance entre le point A et le point B float x1, z1, x2, z2 // pour visualiser le début et la fin de l'arête

Un bord connaît les deux points qui le définissent, ainsi que la distance qui les sépare. Pour une représentation visuelle ou pour construire la forme réelle de la région de polygone, vous devez stocker les points de début et de fin du bord..

Et là nous l'avons. Avec cette information, nous pouvons facilement utiliser le diagramme de Voronoï. Plus bas, nous verrons comment générer le diagramme de Voronoï. Mais pour l'instant, regardons quelques exemples de la façon dont nous pouvons utiliser les données.


Trouver le pack santé le plus proche

Reprenons le diagramme de Voronoï.


Si chaque point représente un pack de santé, vous pouvez trouver assez rapidement où se trouve le plus proche, mais vous devez d’abord localiser la région dans laquelle vous vous trouvez. Voronoi ne fournit pas un moyen efficace de le trouver immédiatement. Cependant, vous pouvez stocker une référence à chaque région dans un arbre sur quatre, ou un arbre R, afin que la recherche soit rapide. Et une fois que vous avez votre région, vous pouvez trouver ses voisins et ses voisins.

Par exemple, si le dossier de santé de votre région est parti, vous avez besoin d'un moyen de trouver le prochain plus proche. Si nous nous référons à notre structure de données et au pseudocode ci-dessus, nous voyons que nous pouvons découvrir ses limites à partir d'une région. Et avec ces bords, nous pouvons alors avoir les voisins. Attrapez le voisin le plus proche et ensuite nous pourrons voir s'il a un pack de santé.

La triangulation de Delaunay peut également être utilisée ici. Il se compose de lignes entre chacun des packs de santé. Ceci peut ensuite être parcouru avec A * pathfinding pour trouver le prochain pack le plus proche s'il s'avère que quelqu'un a saisi tous les packs près de chez vous..


Trouver la route la plus sûre

Au lieu de trousses de santé, imaginons chaque point comme une tour de garde ennemie. Vous devez trouver le moyen le plus sûr de les traverser sans vous faire prendre. Une méthode courante pour parcourir un graphique dans les jeux vidéo consiste à utiliser l'algorithme A * (http://en.wikipedia.org/wiki/algorithme_A_recherche_A*). Le diagramme de Voronoï étant un graphique, il est facile à configurer. Vous devez juste avoir un algorithme A * qui supporte les structures de graphes génériques; un peu de planification à l'avance peut porter ses fruits ici.

Avec le graphique mis en place, nous devons peser chaque bord. La valeur de poids qui nous intéresse est la distance qui sépare ces tours de garde, et nous pouvons la saisir directement dans notre structure de données: VoronoiEdge connaît déjà sa distance entre ses deux points. Normalement, une valeur inférieure sur un bord A * est préférable, mais dans ce cas, nous souhaitons que la valeur supérieure soit plus idéale, car elle représente la distance à la tour..

Voici à quoi ressemble le graphe de départ si nous voulons passer d'un point A à un point B:


En appliquant le poids à chaque bord, nous commençons à voir quel itinéraire serait le mieux à prendre:


Les bords rouges représentent les rencontres les plus proches avec les tours. L'orange l'est moins; jaune moins que cela; et enfin le vert étant le plus sûr. Exécuter A * avec ces poids devrait produire le chemin suivant:


Utiliser les poids de cette manière ne garantit pas la le plus rapide chemin, mais le le plus sûr, c'est ce que tu veux. Il serait également sage que l’intelligence artificielle reste proche de ce chemin et évite de s’égarer.!

Une autre mesure à prendre pour garantie Le passage en toute sécurité consiste à éliminer les bords se trouvant en dessous d’une distance de sécurité minimale. Par exemple, si chaque tour de garde avait une plage de vision de 30 unités, les arêtes dont la distance par rapport à leurs points est inférieure à celle-ci pourraient être supprimées du graphique et ne pas être parcourues du tout..

Une autre utilisation consiste à trouver le chemin le plus large pour les unités de grande taille qui ne peuvent pas traverser des espaces étroits. Puisque chaque arête a une distance entre ses deux points, nous savons si elle peut passer à travers cet espace.

Inversement, si nous utilisions plutôt une triangulation de Delaunay du diagramme, nous aurions des lignes partant de chaque tour de garde. Un garde IA en poste dans une tour pourrait savoir rapidement quelles sont les autres tours à proximité et éventuellement se rendre à l'une d'elles pour l'assister si nécessaire..


Trouver une collection d'objets dense

Supposons que vous souhaitiez déposer un paquet d’airoil-chat dans l’air pour un tas de chatons mignons dans un champ. Quel est le meilleur endroit pour le déposer afin que la plupart des chatons puissent en profiter? Cela pourrait finir par être un calcul très, très coûteux. Mais heureusement, nous pouvons faire une supposition éclairée en utilisant notre triangulation de Delaunay.

Pointe: Rappelez-vous que la triangulation de Delaunay n’est que l’inverse du diagramme de Voronoï. Il est simplement formé en joignant chaque point de Voronoï avec ses points voisins obtenus à partir de sa liste d'arêtes..

Avec cette collection de triangles, nous pouvons examiner la zone couverte par chaque triangle. Si nous trouvons le triangle avec la plus petite surface, alors nous avons les trois points les plus proches, ou chatons. Ce n'est peut-être pas le groupe de chatons le plus dense en moyenne sur le terrain, mais c'est une bonne idée. Si nous sommes en mesure de supprimer plusieurs paquets d’herbe à chat, nous pouvons simplement marquer les triangles que nous avons déjà ciblés et obtenir le prochain plus petit..

La représentation de ces zones est également connue sous le nom de cercles de la triangulation de Delaunay. Chaque cercle est le plus grand cercle pouvant tenir dans les points des triangles. Voici une image des circum-cercles pour un diagramme de Voronoï:


Vous pouvez utiliser le centre exact des cercles pour déterminer le centre de la zone où déposer le paquet d’herbe à chat. Le rayon du cercle est en fait une meilleure méthode pour déterminer le meilleur triangle à remplacer plutôt que son triangle - en particulier si deux points d’un triangle sont très proches et l’un est éloigné, produisant un triangle très net avec une surface réduite points qui sont en fait assez éloignés.


Mise en œuvre de Voronoï

Il existe plusieurs façons de générer des diagrammes de Voronoï et l’heure à laquelle vous disposez des données peut aider à déterminer la technique à utiliser..

Algorithme de balayage de ligne de Fortune

La méthode la plus rapide s'appelle Algorithme de balayage linéaire de Fortune. Il est O (n log (n)) et exige que tous les points utilisés pour générer le graphique soient présents au moment de la génération. Si vous ajoutez de nouveaux points ultérieurement, vous devez générer à nouveau le graphique entier. Ce n'est peut-être pas un gros problème avec quelques points, mais si vous en avez environ 100 000, cela peut prendre un certain temps!

La mise en œuvre de cet algorithme n'est pas triviale. Vous devez intersecter des paraboles et traiter certains cas particuliers. Cependant c'est la technique la plus rapide. Heureusement, il existe déjà de nombreuses implémentations open source que vous pouvez utiliser et nous les avons liées ici..

Permet de jeter un coup d'œil sur son fonctionnement.

L'algorithme consiste à balayer une ligne (verticale ou horizontale) sur l'aire des points. Quand il rencontre un point, il commence à en tirer une parabole qui continue avec la ligne de balayage. Voici une animation du processus:

(Courtoisie d'image de Mnbayazit, rendue publique.)

Les paraboles qui se croisent produisent les arêtes de Voronoï. Pourquoi les paraboles?

Pour comprendre cela, imaginez chaque point contenant un ballon en expansion jusqu'à ce qu'il entre en contact avec un autre ballon. Vous pouvez extraire cette idée dans des cercles en expansion sur un plan 2D. Nous allons plus loin et plaçons sur chaque point un cône inversé, un cône qui a une pente de 45 degrés et qui monte à l'infini. Nous imaginons ensuite la ligne de balayage comme un avion, également à 45 degrés, qui balaie jusqu’au contact avec les cônes. Puisque le plan et les cônes sont au même angle, ils produisent des paraboles quand ils se croisent.


Lorsque les cônes grandissent verticalement, ils vont éventuellement se croiser avec un ou plusieurs autres cônes. Si nous regardons où les cônes, ou cercles, se croisent, nous obtenons les lignes droites des arêtes de Voronoï. Ici, vous pouvez voir la ligne rouge de l’intersection des cônes. Si les cônes s’étendaient davantage (montaient verticalement à l’infini), la ligne rouge continuerait de s’étendre.


Lorsque l'avion survole et établit le premier contact avec un cône, une ligne est créée comme suit:


Pendant que l'avion se déplace à travers les cônes, vous pouvez voir les paraboles se former:


L'avion continue à travers la scène. Pour chaque point rencontré, il examine les points voisins de la ligne de balayage qui ont déjà une parabole et commence une nouvelle parabole pour ce point. Elle continue d'évoluer et de grandir jusqu'à ce que cette nouvelle parabole commence à se chevaucher avec une parabole différente de celle d'avant. Cette parabole précédente est alors fermée. C’est un endroit où les lignes de Voronoï se rencontrent en trois points.

Comme indiqué précédemment, c'est un peu compliqué, voici donc quelques implémentations open source que vous pouvez utiliser et examiner:

  • Java sur GitHub. Auteurs: Benny Kjær Nielsen et Allan Odgaard https://github.com/sorbits/visual-fortune-algorithm/tree/master
  • Python sur GitHub: https://github.com/MikkoJo/Voronoi. Auteur: Mikko Johansson
  • Implémentation détaillée de l'algorithme de Fortune: http://blog.ivank.net/fortunes-algorithm-and-implementation.html

Insertion incrémentielle d'un triangle

Une autre méthode consiste à insérer progressivement un point à la fois, en commençant par un triangle de base de trois points situé en dehors de la plage possible de tous les autres points. Cette technique est O (n ^ 2) et n'exige pas que tous les points soient présents au moment de la génération.

Lorsqu'un nouveau point est inséré, il localise une région existante dans laquelle il s'inscrit. Cette région est ensuite subdivisée et de nouvelles régions sont créées..

Voici un exemple open source que vous pouvez utiliser et examiner:

  • Source Java. Auteur: Paul Chew. Gratuit pour utiliser. Téléchargez le fichier ZIP. Source: http://www.cs.cornell.edu/home/chew/Delaunay.html

Conclusion

Vous devriez maintenant avoir une idée de ce que les diagrammes de Voronoï peuvent fournir à votre jeu et à son intelligence artificielle. Avec un graphe bien structuré de nœuds et d'arêtes, vous pouvez interroger des informations importantes pour vous assurer que les chatons reçoivent l'herbe à chat dont ils ont besoin et que vous pouvez choisir la route la plus sûre pour les atteindre. Et, juste au cas où, vous pouvez trouver où se trouve également le kit médical le plus proche..