Dans un jeu tel que Warcraft 3 ou Age of Empires, la manière dont un adversaire AI peut se déplacer sur la carte semble presque illimité. Les cartes sont énormes et la position d'autres joueurs change constamment.
Comment est-ce que l'AI Chemin de recherche dans des jeux comme ces travaux? Les méthodes de recherche de graphique standard (telles que DFS, BFS ou A *) semblent impossibles dans une telle configuration.
4 Réponses :
Ceci est un peu un exemple simple, mais il montre que vous pouvez faire l'illusion de l'entrée d'accès AI / Indépendante à partir d'un ensemble non complexe de règles: PAC-MAN PATHFINDING
Essentiellement, il est possible que l'AI connaisse des informations locales (à proximité) et de prendre des décisions fondées sur ces connaissances.
a * est un algorithme de parcours commun. Ceci est un sujet de développement de jeux populaire - vous devriez être en mesure de trouver de nombreux livres et sites Web contenant des informations.
Prenez les éléments suivants avec un grain de sel, car je n'ai pas d'expérience de la première personne avec PathFinding.
Cela étant dit, il y a probablement des approches différentes, mais je pense que les méthodes de recherche graphique standard, notamment (variantes de) A * sont parfaitement raisonnables pour les jeux de stratégie. La plupart des jeux de stratégie que je connais semblent être basés sur un système de tuiles, où la carte est composée de petits carrés, qui sont facilement mappés sur un graphique. Un exemple serait StarCraft II ( Capture d'écran ), que je vais continuer à utiliser À titre d'exemple dans le reste de cette réponse, parce que je le connais le plus.
tandis que A * peut être utilisé pour des jeux de stratégie en temps réel, quelques inconvénients doivent être surmontés par des modifications à l'algorithme de base:
a * est trop lent
Étant donné qu'un RTS est par définition "temps réel", attendre que le calcul de la fin sera frustré le joueur, car les unités seront à la traîne. Cela peut être corrigé de plusieurs manières. On consiste à utiliser A * multi-niveaux, qui calcule un parcours approximatif avant de prendre plus petit obstacles en compte. Une autre optimisation évidente consiste à grouper des unités en direction de la même destination dans un peloton et ne calcule qu'un chemin pour tous.
Au lieu de l'approche naïve de la fabrication de chaque carreau d'un nœud dans le graphique, on pourrait également construire un NAVIGATION MESH , qui comporte moins de nœuds et pourrait être recherché plus rapidement - cela nécessite de modifier un peu l'algorithme de recherche, mais il serait toujours un * au cœur.
a * est statique
A * fonctionne sur un graphe statique, quoi faire quand le paysage change? Je ne sais pas comment cela se fait dans des jeux réels, mais j'imagine que le chemin est fait à plusieurs reprises pour faire face à de nouveaux obstacles ou supprimé des obstacles. Peut-être qu'ils utilisent un Version incrémentielle d'A * (PDF).
Pour voir une démonstration de StarCraft II faire face à cela, allez à 07h50 dans cette vidéo < / a>.
a * a des informations parfaites
Une partie de nombreux jeux RTS est un terrain inexploré. Puisque vous ne pouvez pas voir le terrain, vos unités ne doivent pas savoir où marcher non plus, mais souvent ils faire de toute façon. Une approche consiste à sanctionner la marche à travers des terrains inexplorés. Les unités sont donc plus réticentes à tirer parti de leur omniscience, une autre consiste à emporter l'omniscience et à assumer simplement un terrain inexploré est de la marche. Cela peut entraîner les unités trébuchant en morts, parfois des celles qui sont évidentes pour le joueur, jusqu'à ce qu'ils explorent enfin un chemin vers la cible.
Fog of War est un autre aspect. Par exemple, dans StarCraft 2, il y a des obstacles destructibles sur la carte. Il a été démontré que vous pouvez commander une unité pour passer à la base ennemie et commencera à un chemin différent si l'obstacle a déjà été détruit par votre adversaire, vous donnant ainsi des informations que vous ne devriez pas réellement avoir.
Pour résumer: Vous pouvez utiliser des algorithmes standard, mais vous devrez peut-être les utiliser intelligemment. Et en tant que dernier bonus: j'ai trouvé Informations sur la programmation du jeu d'Amit intéressant en ce qui concerne pathing. Il a également des liens vers une nouvelle discussion sur le problème.
Vérifiez les graphiques de visibilité. Je crois que c'est ce qu'ils utilisent pour la recherche de sentiers.
bonne question. Peut-être qu'il serait préférable de la publier sur gamedev.stackexchange.com