Génération de donjons procéduraux: existe-t-il un algorithme simple pour s'assurer que toutes ces salles sont connectées en utilisant des couloirs minimaux?

Est-il possible d'obtenir une structure en forme de ruche, reliant toutes les pièces sans avoir trop de couloirs? (Trop de 3-4 + couloirs venant d'une seule pièce)

Vous trouverez ci-dessous la sortie de l'apparence de mes pièces, essentiellement placées au hasard.

Ce que j'espère obtenir dans le couloir.

Eh bien, la façon la plus simple à laquelle je peux penser commence par s'assurer que toutes les pièces sont reliées par au moins 1 couloir:

1. Commencez par la dernière ou la première pièce.
2. Prenez une pièce au hasard à moins d'une distance, qui n'est pas déjà connectée à une pièce (toutes les pièces commencent à être déconnectées, vous en garderez la trace au fur et à mesure).
3. S'il n'y en a pas, allez à la distance +1. Si vous pouvez passer par-dessus / sous une autre pièce, c'est plus facile, en supposant que vous ne voulez pas de couloirs de connexion.
4. Parcourez votre pseudo-aléatoire jusqu'à ce que toutes les pièces soient connectées.

Nous savons maintenant que vous pouvez accéder à toutes les pièces, mais maintenant, si vous voulez plus que ce labyrinthe strictement linéaire, vous pouvez simplement parcourir vos pièces et créer au hasard un nouveau chemin pour connecter les pièces, jusqu'à une limite par pièce de 2-3, ou jusqu'à ce qu'un certain pourcentage de pièces atteigne le nombre maximal de connexions - etc.

Comme dernière étape, vous pouvez ajouter des règles qui modifieraient vos résultats pour s'adapter à diverses situations. Par exemple, vous pourriez observer que toute pièce avec seulement 1 couloir est, par définition, une impasse; Vous pourriez créer plus d'impasses ou les éliminer toutes en vous assurant que tout a au moins 2 connexions. Vous pourriez faire en sorte que les impasses aient un passage secret. Vous pouvez vous assurer qu'une salle de boss est une impasse. Vous pouvez vous assurer que votre salle de départ est une impasse, mais assurez-vous ensuite que la deuxième salle a un minimum de X connexions.À l'infini.

Chaque hypothèse et règle peut changer radicalement l'apparence de vos niveaux, mais cela fait partie du plaisir! Cela devrait au moins vous permettre de commencer par des pièces ressemblant à des ruches / grottes.

Construisez simplement vos pièces déjà connectées. Commencez avec une pièce, puis construisez 1 à 3 couloirs vers d'autres pièces. Puis récusez jusqu'à ce que vous ayez ajouté suffisamment de pièces.

Étant donné que ces pièces sont des sommets de graphes intégrés dans une plaine 2D, cela pourrait en théorie être fait en résolvant le problème du voyageur de commerce (ce qui serait bien avec seulement quelques pièces). De toute évidence, un simple heuristique serait très bien et permettrait une évolutivité raisonnable.

Vous calculez les bords (longueurs de couloir) entre toutes les pièces. Vous les triez par longueur. Vous ajoutez le couloir le plus court à moins qu'il ne crée un cycle ou n'augmente le degré du sommet (pièce) au-dessus de votre valeur maximale souhaitée (3-4) (Répéter). Pour vérifier les cycles, vous pouvez appliquer UnionFind ou effectuer un rapide BFS sur de petites données.