Eh bien, en supposant que vous commenciez dans le coin supérieur gauche et que vous finissiez dans le coin inférieur droit, le chemin le plus long possible sera celui qui zig / zague sur toute la carte du nord au sud ou d'est en ouest. J'ai écrit le programme récursif suivant pour le plaisir de trouver le chemin le plus long et de produire une sortie et il sort avec cette solution, peu importe la taille pour la taille, le poids que vous entrez:

Notez cependant que cela ne signifie pas le Le plus long chemin est en fait une stratégie optimale dans les jeux de type tourelle de défense, car vous devez prendre en compte des éléments tels que les coûts et les mises à niveau des tours. Le plus souvent, la meilleure situation est simplement de forcer les unités à se rassembler autant que possible dans une zone de mise à mort. Cela devient encore plus compliqué lorsque vous prenez en compte des choses comme le ralentissement des tours. Voici quelques exemples de sortie:

  # = wall. = cheminN = startO = endWidth = 10, Hauteur = 5N # ... # ..... #. #. #. ## .. #. #. #. # ... #. #. #. #. # ... # ... #. OWidth = 10, Hauteur = 10N # ... # ..... #. #. #. ## .. #. #. #. # ... #. # . #. #. #. #. #. #. # ... #. #. #. ## .. #. #. #. # ... #. #. #. #. #. #. # . #. #. # ... # ... #. O  

@Raven Dreamer

Oui, je réalise ce dernier cas, je ne sais pas pourquoi il ne fait pas encore cette dernière optimisation, mais j'ai modifié mon code pour inclure une entrée / sortie mobile. Voici un exemple de génération d'une entrée du milieu:

  ... # ... # ... # ... ## .... #. #. #. #. # . #. #. ##. # .. #. #. #. #. #. #. #. ##. # .. #. #. #. #. #. #. #. ##. #. . #. #. #. #. #. #. #. ##. # .. #. #. #. #. #. #. #. ##. # .. #. #. #. #. # . #. #. ##. # .. #. #. #. #. #. #. #. ##. # .. #. #. #. #. #. #. #. ##. #. .#.#.#.#.#.#.#.##.#.NON#..#.#.#.# . #. #. ##. ## .. # .. #. #. #. #. #. ##. ## < ---. # .. # .. #. #. #. #. # #. ## < ---. #. # .. # .. #. #. #. ##. ## < ---. #. #. # .. # .. #. #. ##. ## < --- besoin d'optimisation ici. #. #. #. # .. # .. #. ##. ## < ---. #. #. #. #. # .. ## .. # . ## < ---. #. #. #. #. #. ####. #. ## < ---... # ... # ... #### ... # # < ---  

J'ai supprimé mon programme depuis que j'ai découvert la source de l'erreur, je mettrai en place une version fonctionnelle plus tard, mais cela va nécessiter une réécriture. La réponse reste cependant inchangée, le chemin le plus long n'est pas si intéressant, mais c'était un exercice de programmation amusant.

  N = 10 Longueur du chemin = 61Towers = 30N # ... # ....... #. #. # .... # .. # .. # .. # .. # .. # .. # .. # .. # .. # .. # .. # .. # .. # .. # .. # ... #. # .. # .... #. #. #. . # .... # ... #. O  

Cette conception diagonale utilise moins de tours que la conception verticale traditionnelle et donne une longueur de chemin légèrement plus longue pour N = 10. Pour N = 9, je n'ai pas pu produire un chemin plus long que l'approche verticale.

Je n'ai pas testé d'autres cas que N = 9, 10 et 12, mais je soupçonne que pour N = 1 + 4x , où x est un entier> 0, l'approche verticale donnera la longueur maximale du chemin, mais pas nécessairement le plus petit numéro de tour.

Plus d'investigation:

• Entrée / sortie au milieu
• Quelles valeurs de N est cette approche diagonale plus efficace
• Identification de stratégies combinatoires
  • L'approche ci-dessus utilise des murs diagonaux avec des segments verticaux dans les coins NE et SW.

C'est ma version préférée. C'est une construction en spirale, c'est 190x. et 156x # Le principal point fort de ceci est que les creeps tournent autour du milieu afin que vous puissiez investir tout votre argent dans quelques tours fortes et les mettre au milieu de votre labyrinthe.

  ..... ............. # O. ################. # .. # ............. . #. # .. #. ############. #. # .. #. # .......... #. #. # .. #. #. ########. #. #. # .. #. #. # ...... #. #. #. # .. #. #. #. ####. #. # . #. # .. #. #. #. # .... #. #. #. # .. #. #. #. #. ####. #. #. # .. #. #. #. # ...... #. #. # .. #. #. #. ########. #. # .. #. #. # ......... . #. # .. #. #. ############. # .. #. # .............. # .. #. ## ##############. N # ..................  

Sur des jeux comme la défense de tour de bureau où il y a une entrée en haut et à gauche, une ligne diagonale de haut à gauche en bas à droite avec un espace en bas à droite, avec des lignes de chaque côté parallèles avec un espace en haut à gauche répété est le meilleur, car tous les monstres passent devant chaque tour, et en améliorant le centre, peu de tous les monstres volants dépasseront les meilleures tours.

Est-il supposé que les murs / tours / obstacles sont placés en permanence? Sinon, vous pouvez essayer de jongler.