Algorithme de cheminement dynamique pour le jeu de tower defense

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.

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

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.

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).

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.

Comment fonctionne A * pathfinding? pourrait être un bon point de départ :-)

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.

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.

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 :)

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).