Comment fonctionne la recherche de trajectoire dans les jeux RTS?

42

[crossposted de stackoverflow]

Dans un jeu tel que Warcraft 3 ou Age of Empires, la manière dont un adversaire IA peut se déplacer sur la carte semble presque illimitée. Les cartes sont énormes et la position des autres joueurs change constamment.

Comment fonctionne le repérage de l'IA dans des jeux comme ceux-ci? Les méthodes standard de recherche de graphes (telles que DFS, BFS ou A *) semblent impossibles dans une telle configuration.

des couvertures
la source
2
Pourquoi A * ne fonctionnerait-il pas dans ce graphique?
user712092
Blog associé
dix heures le
1
@tenfour, le lien est cassé maintenant.
Montréal

Réponses:

29

Dans la plupart des cas, l'utilisation de A * sur un maillage de navigation (communément appelé "navmesh") est la solution de recherche de cheminement commerciale utilisée par les RTS. Il existe une explication détaillée du fonctionnement de navmeshes, pourquoi ils constituent une meilleure solution que les systèmes de points de cheminement, ainsi que des liens vers des ressources de mise en œuvre, ici .

Si vous envisagez de développer des modes de jeu spéciaux (capture de points / nœuds) ou des unités qui patrouillent, se mettent à l’abri, etc., vous voudrez probablement mettre en place une couche de points de cheminement au-dessus de votre navmesh, pour contrôler le comportement de l’intelligence artificielle (et non la recherche de trajectoire ).

Ari Patrick
la source
17

Découvrez l' algorithme Flowfield utilisé dans Supreme Commander 2. Il fait beaucoup mieux que la plupart des systèmes de recherche de chemins RTS (passez à 0:50 pour quelques exemples).

ZorbaTHut
la source
4
c'est une démo vraiment cool mais qui ne me dit rien sur la mise en oeuvre elle
MetaGuru
4
Ils ont mentionné dans une phrase - il est basé sur la recherche de flux de foule de UW, que vous pouvez trouver à grail.cs.washington.edu/projects/crowd-flows .
L'algorithme flowfield semble assez intéressant, et semble certainement faire un travail de cheminement bien meilleur que la plupart des algorithmes, mais j'aimerais qu'il existe une documentation publique sur le fonctionnement du système lui-même, et pas seulement sur son fonctionnement. Naturellement, les développeurs devraient poser de nombreuses questions avant de mettre en œuvre un système de base tel que celui-ci, mais dans ce cas, la seule façon de répondre à ces questions est de commencer par mettre en œuvre le système. :(
Ari Patrick
2
@ Kragen: Vous n'avez vraiment besoin que de deux unités avant qu'un simple A * (en particulier un point de repère) les fasse se croiser encore et encore, et vous avez besoin d'une sorte de système pour le contourner.
5
D'après la vidéo, l'orientation de Starcraft 2 ressemble à ceci. Est-ce que SC2 utilise flowfield?
Chris Bui
7

Beaucoup de jeux plus anciens utilisent A *. Le Starcraft original utilisait A *; ce qui a conduit à des problèmes dans le traitement de la collision. Starcraft 2 gère très bien les collisions, utilisant un comportement de swaming / flock pour maintenir le contrôle fluide des grands groupes. Cet article de gamedev explique comment cela pourrait être réalisé.

phillipwei
la source
2

Je suis d’accord sur l’autre réponse déjà, mais essayez aussi de penser à WoW / Warcraft3 comme à des mondes 2D réels. Ils ne sont pas si différents des tuiles, c'est juste les tuiles.

Vous pouvez également penser à la manière dont un GPS trouve le meilleur chemin? il y a une foule d'algortimns pour parcourir les cartes liées.

Je pense que certains des premiers scripts "Quake bots" pourraient également vous aider, car ils ont été développés pour fonctionner dans des "zones inconnues", car nous pouvions concevoir nos propres niveaux à partir de zéro.

Globalement, ma façon personnelle de gérer une telle carte serait de la considérer comme le guide A *. Mais tout d’abord, je calculais à l'avance chaque "point de mosaïque" et les indexais avec "le plus proche voisin", etc. toucher au but.

Selon le type de jeu et le paysage / scénario, différentes tactiques de pré-analyse peuvent également être utiles. Certains jeux ont très peu d'obstacles et ceux-ci peuvent être des mouvements "streight line" + quelques "comment je me déplace" pour les objets.

J'espère que cela a un sens et que vous avez peut-être réfléchi.

BerggreenDK
la source
1

La plupart des jeux utilisent une sorte d'algorithme de recherche ou A * pour trouver des chemins sur une carte. L'intelligence artificielle a été légèrement modifiée à certains égards pour des raisons de performances.

Vous remarquerez cela dans Starcraft 2, où Zerglings n’a manifestement pas la moindre trajectoire, ce serait un cauchemar pour le processeur de le faire pour Zerglings. Ils font juste le mieux pour aller de A à B et ne tentent même pas de trouver le meilleur chemin. Ils s'approcheront le plus près possible du goulot d'étranglement ou des rampes.

Bryan Harrington
la source
1

La carte est une grille. La grille est un graphique. A * fonctionne sur un graphe, c'est un algorithme de recherche de graphes. Un * devrait chercher quelques nœuds de graphe.

Comme il a été mentionné, ils peuvent utiliser le maillage de navigation. Mais le A * (ou quelque chose de similaire) sera quand même au dessus de ce maillage, car les polygones de ce maillage ne sont que des nœuds d'un graphe; A * cherchera alors le chemin d'un polygone à un autre.

Pas sûr de Warcraft ou des jeux commerciaux, mais il y a aussi une technique appelée Diffusion Collaborative et c'est très simple; cela se fait habituellement sur une grille. Il existe également une technique appelée Champs potentiels , qui est très similaire à la précédente sinon identique.

Vous pourriez aussi essayer:

  • si certains de ces jeux ont du code source disponible
  • si certains des clones de ces jeux ont une source disponible
  • si le SDK ou les éditeurs ne suggèrent rien
  • demander aux employeurs des entreprises qui fabriquent ces jeux, certains d’entre eux pourraient être disposés à partager
utilisateur712092
la source
0

Je ne suis absolument pas expérimenté, mais je pense qu'une bonne solution repose sur des méthodes heuristiques et non sur une vérification complète de la carte connue. Les heuristiques auxquelles je peux penser sont locales et basées sur l'expérience. Les commandes locales peuvent être basées sur la vérification du terrain et les obstacles, en continuant de progresser dans la direction requise. Je pense que la plupart des cartes ne nécessitent pas de mouvements complexes ressemblant à des labyrinthes, mais sont plutôt connectées. Une autre heuristique consiste à utiliser les chemins connus précédents (explorés par d'autres unités ou explicitement par l'utilisateur) pour déplacer des unités vers des positions connues ou presque connues. Mais je parle de passer sur de grandes cartes, pas vraiment dans des espaces fermés comme l’a dit ZorbaTHut. Dans les cas surpeuplés, l'algorithme peut être plus complexe, nécessitant des sortes de "prédiction", une coordination entre les unités d'une même équipe ou simplement des stratégies d'attente ressemblant à des sémaphores. Également,

Je pense que les algorithmes heuristiques sont bons car ils fournissent généralement une bonne solution sur les grands espaces avec un temps de calcul raisonnable (ce qui est important lorsque vous déplacez plusieurs unités).

Désolé si cette réponse est générique: j'ai travaillé avec des foules, mais l'espace était assez particulier et je ne peux pas expliquer exactement le fonctionnement de l'algorithme (basé sur les agents, de toute façon, non défini globalement). J'espère que ma réponse vous donnera des idées utiles.

AkiRoss
la source
Mmmh, je me demande ce qui n'allait pas dans ce que j'ai dit ... Était-ce trop difficile de poser un commentaire?
AkiRoss
BTW, je voudrais souligner que A * utilise l'approche heuristique. Merci pour le -2.
AkiRoss
Votre réponse équivaut à: "Ditch A * et ses semblables et roulez les vôtres". Cela peut être le début d’une réponse raisonnable, mais vous fournissez très peu d’informations autres que la suggestion. Il pense que la raison du vote négatif est que vous ne précisez pas à quel point votre solution serait difficile à mettre en œuvre. Je ne doute pas qu'un super génie disposant d'un temps illimité puisse coder / accorder un algorithme de cheminement pour un RTS donné qui serait supérieur à A * sur un navmesh. Mais "génie" et "illimité" sont très difficiles à trouver.
deft_code
Oh ... d'accord. Je pensais que le gars voulait une réponse générique, puisqu'il ne demandait pas comment en faire une, mais comment fonctionnaient-ils en général. En tout cas, je ne suis pas un expert comme je le disais: je ne faisais que donner des informations sur les solutions que je connais pour explorer de grands espaces dans une application IA générale. Merci pour votre commentaire.
AkiRoss