Exploration avec plusieurs chemins aléatoires dans un jeu Tower Defense

J'ai pensé à trouver un chemin aléatoire pour mon jeu Tower Defense. A * ne fonctionnerait pas pour mes besoins, car j'ai spécifiquement besoin d' un guidage aléatoire .

Imaginez une carte avec des itinéraires, un point de départ et une destination. J'ai plusieurs itinéraires, qui mènent tous du point de départ à la destination, d'une manière ou d'une autre. Cela pourrait ressembler à ceci:

Description de la couleur: rouge - point de départ; noir - destination; gris - route; blanc - espace libre
(les nombres sont utilisés dans le texte comme référence à certaines tuiles)

J'ai d'abord pensé à calculer le prochain waypoint au hasard, lorsqu'une entité passe une tuile. Mais cela ne fonctionnerait pas. Lorsqu'une entité passe la tuile 1, elle peut monter ou descendre. Quand il s'agit de 2, il peut descendre / monter (par rapport à sa position) ou à droite.
Si elle descend / monte, elle ira à la tuile 1, ce qui signifie qu'elle remonte. Mauvais...

Je voudrais vraiment le rendre dynamique , mais je ne sais pas ce que je peux faire maintenant. Quelqu'un avec des idées ou de l'expérience dans ce domaine?

Au lieu d'avoir tous les carrés adjacents comme prochains points de cheminement possibles, n'incluez que les carrés qui ne reviennent pas au début et les choisissent au hasard. Si vous faisiez cela, il serait impossible de revenir en arrière car revenir en arrière n'est pas une option.

Il s'agit d'un problème de graphe orienté avec chaque point de cheminement comme sommet et chaque chemin comme bord. Vous avez juste besoin de limiter le nombre de cycles, peut-être de les supprimer entièrement.

Vous dites aléatoire, mais combien de caractère aléatoire voulez-vous? Est-ce correct si les ennemis choisissent un chemin 10 fois plus long que le plus court? Est-ce correct si les ennemis entrent dans une impasse et doivent faire marche arrière? Autrement dit, aléatoire sur quel ensemble de chemins et avec quelle distribution de probabilité?

En supposant que vous vouliez que les ennemis préfèrent les chemins courts, vous pouvez utiliser A *, mais varier au hasard les poids des bords qui y sont alimentés. Ensuite, les ennemis choisiront toujours un chemin aléatoire qui visite chaque nœud au plus une fois, avec un biais vers des chemins plus courts. En particulier, si sans randomisation il y aurait plusieurs chemins de même longueur, chacun de ces chemins serait choisi avec une probabilité égale.

Alternativement, dans A *, vous pouvez parcourir les voisins dans un ordre aléatoire. Dans votre exemple, lorsque la recherche de chemin atteint le nœud 1, elle mettrait en file d'attente aléatoire le haut du voisin inférieur en premier, ce qui fera que le chemin du haut ou du bas sera considéré en premier. Cette solution obligerait les ennemis à choisir parmi tous les chemins les plus courts au hasard. Dans votre exemple simple, les deux chemins les plus courts seraient également probables, mais dans une situation comme:

start -+--------+
       |        |
       +--------+
       |        |
       +--------+- end

le chemin du haut serait choisi à la probabilité 1/2, tandis que ceux du bas seraient choisis à la probabilité 1/4 chacun.

Juste une preuve de concept:

1. Choisissez une direction aléatoire.
2. Si cela devait nous amener à aller quelque part où nous sommes déjà allés, choisissez une autre direction.
3. Si nous avons manqué de directions, revenons au dernier carré avec une direction inexplorée.