Trajectoire optimale (par longueur)

Question

En supposant un espace de jeu de N par N carrés, avec des tours et des ennemis occupant une zone de 1x1, quelle est la configuration optimale du labyrinthe pour obliger les ennemis à parcourir la plus grande distance globale dans le labyrinthe de N par N carrés ?

Answer 1

En supposant que l'on commence dans le coin supérieur gauche et que l'on termine dans le coin inférieur droit, le chemin le plus long possible sera un chemin qui zigzague sur toute la carte du nord au sud ou de l'est à l'ouest. Pour m'amuser, j'ai écrit le programme récursif suivant pour trouver le chemin le plus long et produire un résultat. Il aboutit à cette solution, quelle que soit la taille, le poids et la hauteur que vous entrez :

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

# = wall
. = path
N = start
O = end

Width = 10, Height = 5
N#...#....
.#.#.#.##.
.#.#.#.#..
.#.#.#.#.#
...#...#.O

Width = 10, Height = 10
N#...#....
.#.#.#.##.
.#.#.#.#..
.#.#.#.#.#
.#.#.#.#..
.#.#.#.##.
.#.#.#.#..
.#.#.#.#.#
.#.#.#.#.#
...#...#.O

@Raven Dreamer

Oui, je réalise ce dernier cas limite, 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 centrale :

...#...#...#...##...
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
.#.#.#.#.#.#.#.##.#.
N#.#.#.#.#.#.#.##.#O
#..#.#.#.#.#.#.##.##
..#..#.#.#.#.#.##.## <---
.#..#..#.#.#.#.##.## <---
.#.#..#..#.#.#.##.## <---
.#.#.#..#..#.#.##.## <--- need optimization here
.#.#.#.#..#..#.##.## <---
.#.#.#.#.#..##..#.## <---
.#.#.#.#.#.####.#.## <---
...#...#...####...## <---

J'ai supprimé mon programme depuis que j'ai trouvé la source de l'erreur, je mettrai une version fonctionnelle plus tard, mais cela va demander un peu de 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.

Answer 2

N = 10
Path Length = 61
Towers = 30
N#...#....
...#.#.#..
..#..#..#.
.#..#..#..
#..#..#..#
..#..#..#.
.#..#..#..
.#.#..#...
.#.#.#..#.
...#...#.O

Cette conception diagonale utilise moins de tours que la conception verticale traditionnelle et donne une longueur de chemin légèrement supérieure pour N = 10. Pour N = 9, je n'ai pas été en mesure de 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 pense que pour N = 1 + 4x, où x est un nombre entier > 0, l'approche verticale donnera la longueur de chemin maximale, mais pas nécessairement le nombre de tours le plus bas.

Plus d'enquête :

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

Answer 3

C'est ma construction préférée. C'est une construction en spirale. Il est 190x. et 156x# Sa principale force est que les creeps tournent autour du milieu, donc vous pouvez investir tout votre argent dans quelques tours fortes et les mettre au milieu de votre labyrinthe.

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

Answer 4

Sur des jeux comme le tower defense de bureau où il y a une entrée en haut et à gauche, une ligne diagonale du haut à gauche vers le 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 rampants passent devant chaque tour, et en améliorant le peu de centre tous les rampants volants passeront devant les meilleures tours.

Answer 5

Est-ce que l'on suppose que les murs/tours/obstacles sont placés de façon permanente ? Si non, vous pouvez essayer jonglerie .