Localisez le chemin le plus court à travers les obstacles lorsque tous les chemins normaux sont bloqués

10

Je fais un Tower Defense et j'ai des fonctions de recherche de cheminement de base, mais j'ai un problème.

Je veux rendre le chemin bloquable, et quand un bloc se produit, les coureurs attaqueront les tours de blocage.

J'ai donc besoin d'un moyen de trouver le chemin le plus court qui, plus important encore, a le plus petit nombre de tours sur le chemin.

Comment je fais ça?

algorithm path-finding tower-defense Dani
la source
1
ne serait-ce pas une détection de collision sur votre chemin piétonnier?
Prix
Comme les tours de blocage sont destructibles, il y a en fait un chemin. Juste le coût de se déplacer à travers eux est bien plus élevé que de se déplacer le long d'un chemin dégagé. (Voir la réponse du coderanger ci-dessous)
bummzack

Réponses:

21

Sur votre chemin, il suffit de faire en sorte que passer par une tour coûte le même prix que de passer par un grand nombre de tuiles. En général, il essaiera de les contourner, mais s'il n'y a pas un tel chemin, la sortie passera toujours par le moins d'obstacles. Vous pouvez régler la pénalité de manière à ce que parfois ils passent simplement au lieu de faire le tour de la carte si vous le souhaitez.

coderanger
la source
aimerait voir un exemple de code de cette implémentation, simple et robuste
DFectuoso
3
L'algorithme A * ( en.wikipedia.org/wiki/A * _search_algorithm) fonctionne avec les coûts de chemin. Augmentez simplement le coût des segments qui traversent une tour. Vos agents tenteront alors d'éviter les tours, ou s'il est «moins cher» d'attaquer une tour, ils l'attaqueront. L'idée de l'algorithme A * est de minimiser le coût, vous devriez donc être en mesure d'atteindre ce que vous voulez en ajustant simplement les coûts du chemin ...
bummzack
C'est une excellente solution à laquelle je n'aurais pas pensé, merci!
jhocking le
Juste une note: Donner aux nœuds de la tour un coût de mouvement énorme sans augmenter également l'estimation utilisée pour l'algorithme A * lorsque le chemin est évidemment bloqué signifie que vos agents vérifieront chaque nœud de leur part de l'obstacle avant de décider d'une rupture- par le point. Selon la quantité de nœuds et d'agents, cela peut ralentir considérablement l'algorithme.
Martin Sojka