Algorithme optimal de génération de labyrinthe multijoueur

Question

Je travaille sur un jeu multijoueur simple dans lequel 2 à 4 joueurs sont placés à différents points d’entrée 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 l'objectif avant tout le monde et je ne veux pas que l'algorithme de génération favorise radicalement un joueur par rapport à d'autres.

Je recherche donc un algorithme de génération de labyrinthe dans lequel le chemin optimal pour chaque joueur, du point de départ à l'objectif, ne dépasse pas 10% de plus que le chemin moyen. De cette façon, les joueurs sont sur un terrain plus ou moins égal. Quelqu'un peut-il imaginer un tel algorithme?

(J'ai une idée en l'état, mais elle n'est pas bien pensée et semble loin d'être optimale - je vais la publier en guise de réponse.)

Answer 1

Une alternative à la réponse de freespace serait de générer un labyrinthe aléatoire, puis d'attribuer à chaque cellule une valeur représentant le nombre de déplacements pour atteindre la fin du labyrinthe (vous pouvez faire les deux à la fois si vous décidez de commencer à la fin'). Ensuite, choisissez une distance (peut-être la plus haute avec n points à cette distance?) Et placez les joueurs sur les cases correspondant à cette valeur.

Answer 2

Qu'en est-il de sélectionner d'abord la position des joueurs et de l'objectif et un chemin de longueur égale, puis de construire un labyrinthe en respectant les chemins définis? Si les chemins ne se croisent pas, cela devrait facilement fonctionner, je suppose

Answer 3

Je voudrais aborder ceci en fixant l’objectif et le point d’entrée de chaque joueur, puis en générant des chemins de longueur similaire pour chacun d’eux vers l’objectif. Ensuite, je commencerais par ajouter de fausses branches le long de ces chemins, en veillant à ne pas créer de lien avec les chemins des autres joueurs, ou à ce qu’une branche ne soit reconnectée au chemin. Donc, chaque branche est essentiellement une impasse.

De cette façon, vous garantissez que les chemins sont de longueur similaire. Cependant, cela ne permettra pas aux joueurs d'interagir les uns avec les autres. Vous pouvez toutefois intégrer cela en créant des liens entre les branches de telle sorte que les points d’entrée de branche situés sur l’un des chemins soient à une distance similaire de l’objectif. Et sur cette branche, vous pouvez sortir de plus d'impasses pour le plaisir et le profit :-)

Answer 4

La solution la plus simple que je puisse trouver est de générer de manière aléatoire un labyrinthe complet comme d'habitude, puis de choisir au hasard le point de but et les points de départ des joueurs. Une fois cela fait, calculez le chemin le plus court de chaque point de départ à l'objectif. Recherchez la moyenne et commencez à lisser (supprimer / déplacer les obstacles - vous ne savez pas comment cela fonctionnera) les chemins qui sont nettement au-dessus, jusqu'à ce que tous les chemins se trouvent dans la marge appropriée. De plus, il pourrait être possible de prendre ceux qui sont nettement en dessous de la moyenne et d’insérer des barrières supplémentaires.

Answer 5

Choisissez votre point de sortie quelque part au milieu

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

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

Ajoutez des branches supplémentaires en dehors des lignes jusqu'à ce que le labyrinthe soit plein.