Algorithme de cheminement dynamique pour le jeu de tower defense

16

Je fais un Tower Defense et j'ai besoin d'un bon algorithme de cheminement pour cela.

J'ai pensé à Dijkstra mais j'en ai besoin d'un qui peut être dynamique; il doit pouvoir se mettre à jour automatiquement lorsqu'un bord est supprimé ou ajouté sans recalcul complet.

Je code en C # si cela aide.

Dani
la source

Réponses:

8

Vous voudrez généralement utiliser A *, sauf si vous recherchez quelque chose d'important différent.

John Haugeland
la source
Si je ne connais pas très bien A *, comment pourrais-je aborder des environnements en évolution dynamique? Recalculer à chaque image? Lors de collisions?
Justin L.
1
En général, vous devez rediriger chaque image dans un jeu simple comme celui-ci. La grille de la carte sera probablement très petite et le nombre d'agents au maximum par centaines. Si cela finissait par être un énorme problème de performances, vous pouvez l'optimiser plus tard en ne reconstruisant pas l'arborescence, sauf en cas de besoin.
coderanger
6
S'il est lent, mes recommandations: ne calculez pas le chemin pour chaque mob. Probablement, ils empruntent tous le même chemin. Je recalcule uniquement sur le placement de la nouvelle tour, et la tour est dans le chemin actuel . Même dans ce cas, ne recalculez que les monstres aux points du chemin avant la case du bloc, pas les monstres qui le dépassent et ne s'en soucient donc pas. Et puis, pour raccourcir la recherche de chemin, vous pouvez le limiter pour trouver le chemin vers le carré après le carré bloqué, car vous connaissez déjà le chemin à partir de là.
seanmonstar
4
En fait, "mob" est le jargon de l'industrie (et du joueur MMO / MUD) pour "objet mobile".
3
Quoi qu'il en soit, il existe depuis longtemps, remonte à MUD1, et suffisamment standard pour avoir paru dans de nombreuses publications. en.wikipedia.org/wiki/Mob_%28computer_gaming%29
19

J'avais besoin de résoudre un problème similaire: trouver la voie sur une grande grille semblable à un labyrinthe avec des «coûts» et des obstacles en constante évolution.

Le fait est que, dans le jeu de tower defense, le nombre d'entités qui ont besoin que le chemin soit résolu pour elles est généralement beaucoup plus grand que le nombre de nœuds dans le graphique. Un * n'est pas l'algorithme le plus approprié pour gérer cela, car vous devrez le résoudre à nouveau chaque fois que quelque chose est modifié. Eh bien, c'est approprié si vous devez trouver un seul chemin, mais dans mon cas, je devais être capable de gérer des entités qui peuvent apparaître à différents endroits et chacune a son propre chemin.

L' algorithme Floyd-Warshall est beaucoup plus approprié, mais pour mon cas, j'ai écrit un algorithme personnalisé qui chaque fois qu'un nœud change, il recalcule le coût pour ce nœud à partir de tous ses voisins, puis si les voisins ont été modifiés, il est invoqué récursivement sur eux.

Donc, au début du jeu, je lance simplement cet algorithme sur tous mes nœuds "objectif". Ensuite, chaque fois qu'un seul nœud change (par exemple, devient impossible à passer), je le lance simplement sur ce nœud et le changement est propagé à tous les nœuds qui seront affectés, puis arrêté. Donc, pas besoin de recalcul global, et l'algorithme est complètement indépendant du nombre d'entités qui nécessiteront la recherche de chemin.

Mon algorithme était essentiellement quelque chose comme (pseudo-code):

update_node method in Node class:
    $old <- $my_score
    find $neighbor node among all neighbors such that
        $neighbor.score + distance_to($neighbor) is minimal
    $my_score <- $neighbor.score + distance_to($neighbor)
    $next_node <- $neighbor
    if ($my_score != $old)
        for each $neighbor
            $neighbor.update_node()

Avec le score initial selon que le nœud est une cible ou une sorte de barrière.

Chêne
la source
1
Il serait également facile de répartir dynamiquement cela sur les trames à mesure que la charge du processeur change.
tenpn
+1 pour A * n'étant pas le bon algorithme à utiliser.
Ricket
5

L'algorithme de route que j'ai utilisé sur mon TD était à l'envers du chemin A * normal en raison du nombre d'entités que j'avais dans le jeu. Au lieu de passer du but aux méchants, j'ai routé du but vers chaque case vide du plateau.

Cela ne prend pas très longtemps, vous continuez simplement à itérer le tableau jusqu'à ce que vous ayez trouvé vos «coûts», et cela fournit de bons commentaires pour les itinéraires bloqués (si vous les faites). L'utilisation de l'algorithme de Floyd est rapide et compatible avec le cache par rapport à A * car il ne fait pas de recherches dépendantes des données, il se contente de charger et d'opérer sur les données dans les flux.

Commencez avec votre tableau défini sur un coût infini, puis définissez le carré de l'objectif sur zéro, puis parcourez le tableau en vérifiant si une cellule voisine coûte moins cher que le coût actuel plus le coût du voyage. Le coût du voyage est l'endroit où vous mettez votre heuristique (dans mon cas, le coût du voyage en diagonale était infini, mais le coût du voyage à travers une tour était élevé, donc ils étaient autorisés à manger à travers les tours, mais pas à moins qu'ils n'aient pas choix)

Une fois que vous avez votre grille de coûts, vous pouvez rapidement créer une grille de "flux" à partir de celle-ci en testant le gradient de coût le plus raide sur les cellules. Cela fonctionne vraiment bien pour des quantités massives de méchants car aucun d'entre eux n'a jamais à trouver de chemin, ils suivent simplement les panneaux virtuels.

Un autre avantage est que de cette façon, vous n'avez qu'à exécuter cette tâche à chaque fois que vous ajustez les obstructions (ou dans mon jeu, lorsqu'un fluage mange dans l'une de vos tours). Pas à chaque fois qu'un creep / mob arrive sur le terrain (ce qui avec des milliers de mobs et des dizaines par seconde aurait été un vrai casse-tête).

Richard Fabian
la source
4

La recherche de chemin est rapide, et sur quelque chose de la taille d'un jeu de tower defense normal, vous n'aurez aucun mal à exécuter une passe A * ou Dijkstra complète chaque fois que quelque chose change. Nous parlons bien en moins d'une milliseconde pour un rafraîchissement complet. Tout type de guidage adaptatif finit par être terriblement compliqué. Faites-le simplement, à moins que vous ne fabriquiez le plus grand réseau de tower defense au monde.

ZorbaTHut
la source
1
Il convient de noter que Tower Defense est populaire sur les téléphones mobiles, où la recherche de chemin n'est pas rapide. Surtout sur les appareils légèrement plus anciens, comme le Sidekick ou les appareils Android 1.6.
seanmonstar
1
Les développeurs utilisent des algorithmes de recherche de chemin comme A * et Dijkstra sur du matériel beaucoup moins puissant depuis des décennies (pensez à Game Boy). Tout téléphone suffisamment récent pour avoir un écran adéquat pour les jeux ne devrait pas avoir de problème, à condition bien sûr que la mise en œuvre soit raisonnablement efficace. Il y a quelques optimisations astucieuses discutées ici: harablog.files.wordpress.com/2009/06/beyondastar.pdf
Mike Strobel
+1. Je suis arrivé à la même conclusion lorsque je développais mon propre clone DTD. J'ai essayé de mettre à jour les chemins de façon incrémentielle mais l'algorithme est devenu trop complexe. Après y avoir passé une journée, je suis passé à un recalcul complet à chaque changement. Cela a fonctionné, et avec quelques ajustements, j'ai pu le faire assez rapidement.
finnw
2

Cela peut être exagéré pour votre solution, mais pensez au routage vers l'arrière plutôt que vers l'avant.

Dans un jeu TD, les ennemis tentent généralement d'atteindre un objectif spécifique. Parcourez ce but vers le premier ennemi, puis cachez ce chemin. Lors de la génération de chemin pour les ennemis suivants, utilisez le premier chemin comme point de départ, etc. Si vous avez plusieurs points d'entrées ennemis ou plusieurs objectifs, disposez d'une gamme de chemins pré-mis en cache pour commencer.

tenpn
la source
1

La recherche de points de cheminement serait probablement la meilleure pour un jeu td, car généralement basée sur le niveau, l'IA suit un chemin direct. Fondamentalement, vous définissez vos nœuds ou points de cheminement, puis vous avez le point "ai" vers le point de cheminement et vous vous y dirigez, une fois qu'il est assez proche de celui-ci, passez au point de cheminement suivant, faites-lui face et avancez vers lui.

Loktar
la source
Cela ne fonctionne que pour les jeux TD où vous ne pouvez placer que des tourelles sur le côté du chemin - pas des jeux qui permettent le placement de tours n'importe où sur le plateau.
Iain
ouais au départ l'auteur n'a pas précisé quel type il voulait donc j'ai supposé non dynamique.
Loktar
1

Depuis que quelqu'un a posé la question, vous vous adressez à des environnements à changement dynamique en recalculant le chemin à chaque fois que le joueur place ou supprime une tour, et vous stockez simplement ce chemin en mémoire entre-temps. L'environnement ne change pas sur chaque image.

Notez que certains jeux TD ont un chemin défini et ne vous permettent pas de placer des tours dessus, ils résolvent donc les chemins facilement: en codant en dur un chemin et en ne vous laissant pas le bloquer :)

Ian Schreiber
la source
1

Une solution simple est de tricher.

Concevez la carte à l'avance pour vous assurer qu'il n'y a pas d'impasse. Ensuite, à chaque intersection, ajoutez un déclencheur qui permet au personnage de choisir un itinéraire (exemple: toujours tourner à gauche, toujours à droite ou au hasard).

MrValdez
la source
1
Vraisemblablement, il parle de quelque chose comme Desktop TD où l'utilisateur crée la carte à la volée. Toujours pour les ennemis "stupides", cela pourrait être une bonne solution pour que vous puissiez vous faire des ennemis avec une meilleure IA un peu plus difficile.
coderanger