Algorithme de génération de labyrinthe multijoueur optimal

Question

Je travaille sur un jeu multijoueur simple dans lequel 2-4 joueurs sont placés à des entrypoints séparés dans un labyrinthe et doivent atteindre un point de but. Générer un labyrinthe en général est très facile, mais dans ce cas le but du jeu est d'atteindre le but avant tout le monde et je ne veux pas que l'algorithme de génération favorise radicalement un joueur par rapport aux autres. Donc, je cherche un algorithme de génération de labyrinthe où le chemin optimal pour chaque joueur du point de départ au but n'est pas plus de 10% plus de pas que le chemin moyen. De cette façon, les joueurs sont plus ou moins sur un terrain de jeu égal. Quelqu'un peut-il imaginer un tel algorithme?

(j'ai une idée telle qu'elle est, mais il est pas bien pensé et semble beaucoup moins que optimale -. Je vais le poster comme une réponse)

Answer 1

Une alternative à la réponse de freespace serait de générer un labyrinthe aléatoire, puis affecter à chaque cellule une valeur représentant le nombre de coups pour atteindre la fin du labyrinthe (vous pouvez faire les deux à la fois si vous décidez que vous commencez à la 'fin'). Puis choisissez une distance (peut-être la plus élevée avec n points à cette distance?) Et placez les joueurs aux carrés avec cette valeur.

Answer 2

La solution la plus simple que je peux trouver avec est de générer aléatoirement un labyrinthe entier comme d'habitude, puis choisissez au hasard le point de but et les points de départ du joueur. Une fois cela fait, calculer le chemin le plus court entre chaque point de départ et le but. Trouver la moyenne et commencer à «lisser» (supprimer/déplacer les barrières - ne sais pas comment cela va fonctionner) les chemins qui sont significativement au-dessus, jusqu'à ce que tous les chemins sont dans la marge appropriée. En outre, il pourrait être possible de prendre ceux qui sont nettement inférieurs à la moyenne et d'insérer des barrières supplémentaires.

Answer 3

Que diriez-vous d'abord de sélectionner la position des joueurs et le but et un chemin de longueur égale et ensuite construire un labyrinthe en respectant les chemins définis? Si les chemins ne se croisent pas, cela devrait fonctionner facilement, je suppose

Answer 4

Je m'approche de cela en fixant le but et le point d'entrée de chaque joueur, puis en générant des chemins de longueur similaire pour chacun d'eux vers le but. Ensuite, je commencerais à ajouter de fausses branches le long de ces chemins, en prenant soin d'éviter de se lier aux chemins d'un autre joueur, ou d'avoir une branche qui se reconnecte au chemin. Donc, essentiellement, chaque branche est une impasse.

De cette façon, vous garantissez que les chemins sont similaires en longueur. Cependant, il ne permettra pas aux joueurs d'interagir entre eux. Vous pouvez cependant mettre ceci dedans, en créant des liens entre les branches telles que les points d'entrée de branche sur n'importe quel chemin sont à une distance semblable loin de l'objectif. Et sur cette branche, vous pouvez brancher plus d'impasses pour le plaisir et le profit :-)

Answer 5

Choisissez le votre point de sortie quelque part au milieu

Commencez vos chemins de N à partir de là, en ajoutant 1 à chaque chemin par boucle, jusqu'à ce qu'ils soient aussi longtemps que vous voulez qu'ils soient.

Il y a vos N points de départ, et ils ont tous la même longueur.

Ajouter des branches supplémentaires hors des lignes, jusqu'à ce que le labyrinthe soit plein.