Quel itinéraire sera le plus sûr, où sont les plus ennemis et où se trouve la trousse de premiers soins la plus proche? Tous ces problèmes fréquemment rencontrés de relations spatiales peuvent être résolus efficacement en utilisant des partitions mathématiques appelées «diagrammes de Voronoï». À partir de ce post, vous apprendrez à analyser les cartes de jeu et à recevoir des informations qui garantissent le réalisme et le succès de l'intelligence artificielle.
Relation spatiale
Une relation spatiale est toute information qui décrit comment un objet dans l'espace est lié à un autre. Exemples: la distance entre eux, la zone couverte par chacun d'eux espace et l'intersection de ces zones, le nombre de ces objets situés dans une zone.
De telles relations sont constamment utilisées dans les jeux vidéo et peuvent fournir des informations d'IA très utiles, ainsi qu'au joueur lui-même.
Voronoi a une réponse
Le diagramme de Voronoi décrit la relation spatiale entre des points étroitement espacés ou leurs voisins les plus proches. Il s'agit d'un ensemble de polygones connectés obtenus à partir de points ou d'emplacements. Chaque ligne de la «zone» de Voronoi est située au milieu entre deux points.
Pour comprendre, regardez la photo:
Comme vous pouvez le voir, chaque ligne est exactement au milieu entre deux points, et tous sont connectés au centre. Ajoutez quelques points supplémentaires à la scène et voyez ce qui se passe:
L'image est devenue plus intéressante! Nous avons déjà de vrais domaines.
Que nous dit chacun des domaines? Nous savons que le fait d'être dans la région est garanti d'être situé le plus près d'un point, qui est également dans la région. Cela nous en dit beaucoup sur ce qui se trouve à proximité; telle est la relation spatiale fondamentale dans les diagrammes de Voronoï.
Tournez Voronoi à l'envers: triangulation de Delaunay
Le système opposé au diagramme de Voronoi est appelé triangulation de Delaunay. Ce diagramme se compose de lignes de chaque point vers ses voisins les plus proches, et chaque ligne est perpendiculaire à l'arête de Voronoï qu'elle intersecte. Voici à quoi ça ressemble:
Le blanc marque la ligne Delaunay. Chaque ligne Delaunay correspond à un et un seul bord Voronoi. Au début, il semble que certains d'entre eux traversent plusieurs bords, mais en y regardant de plus près, vous vous rendrez compte que ce n'est pas le cas.
Sur la figure, la ligne verte Delaunay correspond à la côte rose de Voronoi. Imaginez simplement que la côte rose va plus loin et vous voyez qu'elles se croisent.
Grâce à la triangulation de Delaunay, nous voyons qu'au lieu des polygones, nous avons maintenant de nombreux triangles. C'est incroyablement utile car nous avons divisé la zone en triangles qui peuvent être rendus. Cette technique peut être utilisée pour la mosaïque ou la triangulation des figures. Super!
De plus, c'est un excellent moyen de créer un graphique à partir de plusieurs points au cas où nous souhaiterions passer d'un point à un autre. Par exemple, des points peuvent indiquer des villes.
Structure des données Voronoi
Nous savons déjà à quoi ressemble le diagramme de Voronoi; Voyons maintenant à quoi ressemblera sa structure de données. Nous devons d'abord enregistrer les points qui sont à la base du diagramme de Voronoi:
class VoronoiPoint { float x float y VoronoiRegion* region }
Chaque
VoronoiPoint a un emplacement
(x, y) et un lien vers la zone dans laquelle il se trouve.
Ensuite, nous devons décrire
VoronoiRegion :
class VoronoiRegion { VoronoiPoint* point Edge *edges[]
La zone stocke un lien vers son
VoronoiPoint , ainsi qu'une liste des arêtes
VoronoiEdges qui le
VoronoiEdges .
Voyons à quoi ressemble
VoronoiEdges :
class VoronoiEdge { VoronoiPoint* pointA VoronoiPoint* pointB float distance
Le bord connaît deux points qui le définissent, ainsi que la distance entre eux. Pour l'affichage visuel, ainsi que pour construire la forme de la région polygonale, nous devons stocker les points de début et de fin du bord.
Et c'est tout. Avec ces informations, nous pouvons facilement construire un diagramme de Voronoi. Ci-dessous, nous apprendrons comment le diagramme de Voronoi est généré. Mais pour l'instant, regardons quelques exemples de la façon dont ces données peuvent être utilisées.
Trouvez l'armoire à pharmacie la plus proche
Encore une fois, regardez le diagramme de Voronoi pour les points.
Si chaque point désigne une trousse de premiers soins, alors nous pouvons rapidement déterminer où se trouve le plus proche de nous, mais nous devons d'abord déterminer la zone dans laquelle nous nous trouvons. Les diagrammes de Voronoi ne fournissent pas un moyen efficace de définir une région, cependant, pour accélérer la recherche, nous pouvons stocker un lien vers chaque région dans l'
arborescence du
quadrant ou dans l'
arborescence R. Et après avoir appris la région, nous pourrons reconnaître ses voisins et les voisins de ses voisins.
Par exemple, s'il n'y a plus de trousse de premiers soins dans votre région, vous devez trouver un chemin vers un autre plus proche. De la structure des données et du pseudo-code ci-dessus, nous pouvons comprendre que connaissant la région, nous pouvons reconnaître ses bords. Et avec l'aide de ces côtes, nous pouvons avoir des voisins. Nous prendrons le voisin le plus proche et verrons s'il y a une trousse de premiers soins.
Vous pouvez également appliquer ici la triangulation de Delaunay. Il se compose de lignes entre les trousses de premiers soins. Ensuite, vous pouvez le contourner en utilisant l'algorithme de recherche de chemin A * pour trouver la trousse de premiers soins la plus proche.
Rechercher un itinéraire sûr
Remplacez toutes les trousses de premiers soins par des tours de guet ennemies. Vous devez trouver l'itinéraire le plus sûr entre eux pour ne pas être pris. La manière standard de parcourir les graphes dans les jeux vidéo est d'utiliser
l'algorithme A * . Le diagramme de Voronoi étant un graphe, il est très facile d'implémenter une recherche. Nous avons juste besoin de l'algorithme A *, qui prend en charge les structures graphiques générales; planifiez à l'avance et cela vous aidera à l'avenir.
Après avoir préparé le graphique, vous devez attribuer un poids à chaque bord. Pour nous, la valeur du poids sera la distance à ces tours de guet, et vous pouvez l'obtenir directement à partir de la structure des données: chaque
VoronoiEdge connaît déjà sa distance entre deux points. Habituellement, plus la valeur sur le bord A * est petite, mieux c'est, mais dans notre cas, plus la valeur est élevée, car elle indique la distance à la tour.
Voici à quoi ressemble le graphe initial si on veut passer du point A au point B:
En appliquant du poids à chaque bord, nous verrons quel itinéraire est préférable de choisir:
Les nervures rouges indiquent les contacts les plus proches avec les tours. Orange indique les plus longs; jaune encore plus éloigné, et enfin vert - le plus sûr. Après avoir exécuté A * avec ces poids, nous obtenons le chemin suivant:
Avec cette utilisation des balances, pas
la plus rapide , mais
la façon
la plus sûre sera choisie, c'est ce dont nous avons besoin. L'IA devrait adhérer à cette voie et ne pas s'en écarter!
Vous pouvez prendre une autre mesure pour
garantir un chemin sûr: éliminer tous les bords qui sont plus proches que la distance de sécurité minimale. Par exemple, si chaque tour de guet a un rayon de visibilité de 30 unités, tous les bords, la distance à laquelle les points sont inférieurs, peuvent être supprimés du graphique et ne pas être contournés.
Vous pouvez également utiliser cette méthode pour trouver l'itinéraire le plus large pour les grandes unités qui ne peuvent pas passer par des goulots d'étranglement. Chaque arête a une distance entre deux points, nous savons donc s'ils peuvent passer dans cet espace.
Vous pouvez également effectuer l'opération inverse - utilisez le diagramme de triangulation Delaunay et obtenez les lignes provenant de chaque tour de guet. L'IA des gardes pourra déterminer rapidement quelles autres tours se trouvent à proximité et, si nécessaire, leur venir en aide.
Rechercher un ensemble d'articles bien emballés
Supposons que nous devions laisser tomber un colis de cataire d'un avion pour un tas de phoques assis sur le sol. Quelle est la meilleure façon de l'abandonner pour que le plus grand nombre de chats puisse l'utiliser? Cela peut être extrêmement coûteux. Mais, heureusement, nous pouvons faire une hypothèse raisonnable en utilisant la triangulation de Delaunay.
Astuce: n'oubliez pas que la triangulation de Delaunay n'est que l'inverse du diagramme de Voronoi. Il est formé en reliant chaque point de Voronoi aux points voisins obtenus à partir de la liste des arêtes.
Avec cette collection de triangles, vous pouvez explorer la zone couverte par chacun des triangles. Si nous trouvons le triangle avec la plus petite surface, alors nous avons trois points les plus proches, ou chats. Ce n'est peut-être pas l'amas moyen le plus dense à la surface, mais ce sera une bonne hypothèse. Si nous pouvions jeter quelques parcelles à la menthe, nous marquerions simplement les triangles déjà sélectionnés et passerions aux suivants en augmentant de taille.
La désignation de ces zones est également appelée les
cercles circonscrits de la triangulation de Delaunay. Chaque cercle est le plus grand cercle pouvant tenir aux points du triangle. Voici une image des cercles circonscrits pour le diagramme de Voronoi:
Vous pouvez utiliser le centre exact des cercles pour déterminer le centre de la zone où l'herbe à chat est expédiée. En fait, le rayon du cercle est un moyen plus approprié pour déterminer le meilleur triangle à plier au lieu de l'aire du triangle, surtout si les deux points du triangle sont très proches l'un de l'autre et que le troisième est loin; nous obtenons ensuite un triangle très net avec une petite zone, mais les points qui le définissent sont en fait très éloignés.
Implémentation des diagrammes de Voronoi
Il existe plusieurs façons de générer des diagrammes de Voronoi, et le choix de la méthode utilisée dépend de l'heure à laquelle nous recevons les données.
Algorithme de fortune
Le moyen le plus rapide est appelé
l'algorithme de Fortune . Il s'exécute en
O(n log(n)) et nécessite que tous les points utilisés pour générer le graphe soient connus au début de la génération. Si vous ajoutez de nouveaux points plus tard, vous devrez régénérer le graphique entier. S'il y a peu de points, cela peut ne pas causer de problèmes, mais si vous en avez 100 000, cela peut prendre beaucoup de temps!
La mise en œuvre de cet algorithme n'est pas triviale. Paraboles croisées et cas spéciaux. Cependant, c'est la méthode la plus rapide. Heureusement, il existe de nombreuses implémentations de cet algorithme open source que vous pouvez utiliser, et je leur ai fourni des liens ci-dessous.
Voyons comment cela fonctionne.
L'algorithme consiste à faire glisser une ligne (verticale ou horizontale) sur une zone à points. Quand il rencontre un point, il commence à en tirer une parabole, qui continue avec une ligne de balayage. Voici l'animation de ce processus:
Les paraboles qui se croisent forment les côtes de Voronoi. Mais pourquoi des paraboles?
Pour comprendre cela, imaginez chaque point comme contenant un ballon gonflable qui gonfle jusqu'à ce qu'il entre en collision avec une autre balle. Vous pouvez transférer cette idée dans des cercles se développant sur un plan 2D. Nous allons faire avancer une autre balle et placer à chaque point un cône inversé avec un angle d'inclinaison de 45 degrés, augmentant à l'infini. Imaginez ensuite une ligne de balayage en forme de ligne, également à 45 degrés, qui glisse jusqu'à ce qu'elle entre en collision avec les cônes. Puisque l'avion et les cônes sont situés sous le même angle, lorsqu'ils se croisent, ils forment des paraboles.
En grandissant, les cônes se croisent tôt ou tard avec un ou plusieurs autres cônes. Si nous regardons l'intersection des cônes ou cercles, nous obtenons des lignes droites des bords de Voronoi. Sur la figure, la ligne rouge indique l'intersection des cônes. Si les cônes poussent encore plus loin (verticalement jusqu'à l'infini), la ligne rouge continuera de s'étirer.
Lorsque l'avion glisse et que le premier contact avec le cône se produit, la ligne résultante sera comme ceci:
Avec la poursuite du mouvement de l'avion le long des cônes, nous verrons comment se forment les paraboles:
L'avion continue de se déplacer sur la scène. Pour chaque point qu'il rencontre, il examine les points voisins sur la ligne de balayage qui ont déjà des paraboles et commence une nouvelle parabole à ce point. Elle continue d'avancer et de grandir jusqu'à ce que cette nouvelle parabole commence à ne pas chevaucher celle qui était précédemment superposée. Puis cette précédente parabole se ferme. C’est le point où les lignes de trois points de Voronoi se rencontrent.
Comme indiqué ci-dessus, cela est assez difficile à comprendre, alors voici des liens vers des implémentations open source que vous pouvez utiliser et apprendre:
Insertion incrémentale de triangle
Une autre méthode consiste à insérer progressivement un point à la fois, en commençant par un triangle de base de trois points en dehors de la zone possible de tous les autres points. Cette méthode fonctionne avec
O(n^2) et ne nécessite pas tous les points au moment de la génération.
Lorsque vous insérez un nouveau point, il définit la zone existante dans laquelle il se situe. Cette zone est ensuite subdivisée et de nouvelles zones sont créées.
Voici un exemple open source à utiliser et à apprendre:
Conclusion
Maintenant, vous devez imaginer ce que les diagrammes de Voronoi peuvent apporter à votre jeu et à son IA. Si vous avez un graphique correctement structuré des nœuds et des bords, vous pouvez demander des informations importantes pour que tout le monde reçoive ses trousses de premiers soins, son herbe à chat et passe les tours ennemies.