Procédure… maison avec générateur de pièces

J'ai examiné des algorithmes et des articles sur la génération procédurale d'un donjon. Le problème, c’est que j’essaie de créer une maison avec des pièces qui ne semblent pas correspondre à mes besoins.

D'une part, les cachots ont des couloirs, où les maisons ont des halls. Et même si, au départ, elles peuvent sembler identiques, une salle n’est rien de plus que la zone qui n’est pas une pièce, alors qu’un couloir est spécifiquement conçu pour relier une zone à une autre.

Une autre différence importante avec une maison est que vous avez une largeur et une hauteur spécifiques et que vous devez remplir le tout de pièces et de salles, tandis que dans un donjon, il y a un espace vide.

Je pense que les halls d'une maison sont quelque chose entre un couloir de donjon (vous amène à d'autres salles) et un espace vide dans le donjon (ce n'est pas explicitement défini dans le code).

Plus précisément, les exigences sont les suivantes:

• Il y a un ensemble de pièces prédéfinies que
  je ne peux pas créer de murs et de portes à la volée.
• Les pièces peuvent être pivotées mais pas redimensionnées.
  Encore une fois, comme je dispose d’un ensemble de pièces prédéfini, je ne peux que les faire pivoter, pas les redimensionner.
• Les dimensions de la maison sont définies et doivent être entièrement remplies de pièces (ou de salles),
  c'est-à-dire que je souhaite remplir une maison 14x20 avec les pièces disponibles en veillant à ce qu'il n'y ait pas d'espace vide.

Voici quelques images pour rendre cela un peu plus clair:

Comme vous pouvez le constater, dans la maison, "l’espace vide" est toujours praticable et vous permet de vous déplacer d’une pièce à l’autre.

Cela dit, une maison n’est peut-être qu’un donjon vraiment très serré avec des couloirs. Ou c'est quelque chose de plus facile qu'un donjon. Peut-être qu'il y a quelque chose dehors et je ne l'ai pas trouvé parce que je ne sais pas vraiment quoi rechercher.

C'est là que j'aimerais votre aide: pourriez-vous me donner des indications sur la façon de concevoir cet algorithme? Avez-vous des idées sur les étapes à suivre? Si vous avez créé un générateur de donjon, comment le modifieriez-vous pour l'adapter à mes besoins? Vous pouvez être aussi spécifique ou aussi générique que vous le souhaitez. Je cherche à choisir vos cerveaux, vraiment.

Je pense que c’est un bon exemple pour utiliser une partition d’espace binaire ou ternaire.

Lors du premier passage, divisez l’espace de la maison en halls et {blocs de chambres}. Obtenez le prochain gros morceau, divisez-le en {hall et morceau} ou {2 morceaux et hall entre eux}. À chaque étape, faites pivoter la direction de découpage de 90 degrés. Arrêtez-vous quand {il ne reste plus de gros morceaux} ou {la limite de la surface totale de la salle atteinte}.

Lors du second passage, divisez les morceaux restants en pièces. Obtenez le prochain gros morceau et divisez-le. Évitez de diviser au hasard des morceaux pas très gros pour avoir de grandes salles.

Si une salle fait face à une salle beaucoup plus ancienne, placez-y un mur (ou un mur avec une porte).

Reliez les salles avec les salles directement ou par l’intermédiaire de salles déjà connectées.

Par exemple, vous pouvez voir mon résultat fabriqué manuellement ou un pseudo-code identique à C ++ . Tir final:

Vous pouvez tirer parti du fait que la conception que vous souhaitez assemble les pièces dans des pièces rectangulaires entourées de couloirs. Dans cet esprit, je ferais ceci:

1. Concevoir les couloirs et les "grands espaces" pour les chambres
2. Remplissez chaque "grand espace" avec des chambres

Il est facile de remplir les grands espaces avec des chambres si vous commencez par les chambres situées aux frontières. Elles ont des contraintes spécifiques. Par exemple, les chambres donnant sur un couloir peuvent avoir une porte sur ce mur, mais les chambres donnant sur les "murs extérieurs". ne peut pas (ils pourraient avoir des fenêtres, peut-être). Les pièces "à l'intérieur" des grands blocs de pièces auront besoin d'au moins une entrée.

Alors, voici comment j'ai résolu ce problème. Mais tout d’abord, je voudrais remercier @Shadows In Rain et @egarcia pour leurs réponses. Ils m'ont donné une bonne direction qui m'a aidé à obtenir des résultats.

J'ai utilisé le partitionnement d'espace de Shadows In Rain pour créer une maison de base, puis j'ai suivi le conseil d'Egarcia de remplir la zone de pièces.

Le partitionnement de l'espace était assez simple puisque 90% du code a été créé par Shadows. La partie "Remplir les chambres" était un peu plus difficile. J'ai décidé d'utiliser un pseudo système de planification IA utilisant A * pour positionner correctement les salles. La bonne chose à propos de l'utilisation de la planification au lieu de simplement A * est que les conditions préalables permettent de réduire considérablement l'espace de recherche.

Voici quelques captures d'écran avec les résultats:

Phase de génération du plan d'étage

Phase de placement de la salle

Maintenant, avec des portes communicantes!

Dahl & Rinde ont une thèse sur la génération procédurale d'environnements intérieurs qui utilise une approche squelette et régions pour remplir les intérieurs de bâtiment avec des chambres et des couloirs. Le document comprend des diagrammes de classe pour leur prototype. Il y a aussi quelques bonnes références dans leur bibliographie, y compris le langage de modèle A mentionné ci-dessus .

Leur travail a été conçu autour des hypothèses simplificatrices suivantes:

• ne traite que des immeubles
• pas de niveaux séparés
• la limitation de la forme des bâtiments (enveloppe) doit être polygonale
• pas de trous dans l'enveloppe
• Epaisseur d'enveloppe similaire ou à changement linéaire (c'est-à-dire sans forme de sablier)
• ne traite que des bâtiments qui ont besoin de couloirs

Voici un bref aperçu de leur processus:

• Trouvez le squelette de l'enveloppe. Les corridors sont ensuite placés le long du squelette en fonction de la distance de l'enveloppe, de la proximité des portes ou des escaliers et de la proximité des corridors précédemment placés.
• Ensuite, l’espace restant hors couloir est divisé en zones connectées maximales, chacune avec une limite continue unique. Dans certains cas, cela nécessitera l'insertion d'un mur.
• Ces régions sont ensuite divisées en appartements essayant d'allouer au moins une fenêtre par appartement. Dans certains cas, des divisions plus petites fusionneront pour éviter des appartements trop petits. Les régions sans fenêtre sont simplement ignorées.

• Enfin, les appartements sont divisés en chambres sur la base suivante d’un diagramme pondéré de type Voronoï:

  • Le poids des graines est utilisé pour influencer la taille de la pièce. Des graines sont ajoutées aux portes et aux fenêtres. Des graines supplémentaires sont ajoutées, généralement une par pièce désirée; Bien que cela ne soit pas explicitement indiqué, il semble que les graines soient placées le long des murs extérieurs de l'appartement.
  • En commençant par le point le plus éloigné, une ligne entre la graine donnée et tous les autres points est calculée, puis divisée en deux par une distance par rapport aux poids respectifs des points finaux (par exemple, si A & B avait des poids de 1 & 4, le point de bissection serait 1/4 du chemin de A à B). La collection de lignes de bissection, avec le mur extérieur, forme alors la cellule pour la graine.
  • Ensuite, un squelette de paroi S-Space (selon Peponis et al, 1997) est créé en divisant la zone avec des lignes partant perpendiculairement des points médians entre des paires voisines d'éléments de paroi externes (fenêtres ou portes).
  • Enfin, les murs sont sélectionnés dans le squelette de l'espace S qui «correspond le mieux possible aux parois des cellules de Voronoï».