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

74

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:

Générateur de donjon typique Donjon sans couloir Résultat générateur de maison

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.

pek
la source
2
Une recommandation étrange: je recommande vivement de consulter les livres de Christopher Alexander, The Timeless Way , un langage de modèle , les livres d'architecture qui ont jeté les bases de la notion de modèle (logiciel); ils décrivent essentiellement un langage explicite pour les bâtiments et les espaces de vie qui peut être transformé en une méthode de construction procédurale descendante.
Steven Stadnicki
Personnellement, j'essaierais de créer un algorithme comme celui de egarcias. Commencez par générer des espaces réservés pour les pièces (de grandes zones pouvant être remplies avec un nombre variable de pièces. Chaque espace réservé pour une pièce doit avoir un intervalle de taille spécifique (ou aléatoire comportant une limite inférieure) entre eux. Cet espace est ce qui serait Considéré comme un couloir, c'est-à-dire un espace qui se trouve dans la maison mais pas dans une pièce, les remplaçants seraient remplis par des pièces de taille aléatoire semblables à celles de votre exemple de "cachot sans couloirs"
Benjamin Danger Johnson -
@pek S'il vous plaît créer une réponse pour votre solution, ne le mettez pas dans la question.
MichaelHouse
@ Byte56 Fait. Soyons clairs, je l’ai fait parce que je ne voulais pas obtenir de crédit, car je n’avais fait que ce que les autres avaient suggéré. Je comprends cependant pourquoi cela n’est pas idéal pour le format du site, alors j’ai ajouté ma réponse.
Pek
Merci @pek. Ne vous inquiétez pas pour obtenir un crédit, il est mérité et utile aux personnes qui visitent le site pour voir la solution (et voir où il est prévu est le meilleur).
MichaelHouse

Réponses:

50

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:

tir final

Ombres sous la pluie
la source
C'est là que mes recherches ont abouti, au partitionnement de l'espace. Votre exemple avec le code m'a donné un très très bon début. Je suis en train de lire sur des algorithmes. Une question cependant: une de mes exigences est que les pièces soient prédéfinies (par exemple, il y a 2x2 pièces avec une porte, 1x1 avec deux portes, mais pas 2x2 avec trois portes), donc je ne peux pas commencer à cloisonner puis décider de l'endroit où je vais placer les portes. . Je pense que je dois garder à l'esprit mes limites lorsque je partitionne. Avez-vous une suggestion quant à la façon dont je procéderais? En tout cas, merci beaucoup pour votre réponse et vos efforts!
Pek
@pek Je ne suis pas sûr que le simple mortel puisse trouver une solution théorique à ce problème. Vous pouvez essayer de définir des conditions supplémentaires pour le fractionneur de blocs et le diviseur de boîtes, puis de générer et de supprimer des niveaux jusqu'à ce que vous en trouviez un où toutes les conditions peuvent être remplies.
Shadows In Rain
oui, j'espérais avoir manqué quelque chose. Ma première approche consistait à utiliser A * pour comprendre comment adapter les salles à un espace donné, mais la logique manquait pour les salles. Maintenant, je pense que je peux utiliser BSP pour placer des salles, puis utiliser A * pour les blocs. Ce qui m'inquiète surtout, c'est que cela risque d'être trop coûteux et de ne pas toujours produire un résultat. Mais je vais devoir tester ceci en premier. Peut-être que ce ne sera pas aussi grave?
Pek
2
@pek j'ai trouvé quelque chose d'utile, si vous êtes toujours intéressé. Regardez ça aussi, google L-system.
Shadows In Rain
24

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

2 étapes

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.

egarcia
la source
15

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 génération du plan d'étage

Phase de placement de la salle Phase de placement de la salle

Maintenant, avec des portes communicantes!
Maintenant, avec des portes communicantes!

pek
la source
11

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ï».
Pikalek
la source
3
Pouvez-vous inclure des images? Ce serait génial. J'ai écrémé le papier et les salles qu'ils ont générées avaient l'air bien d'un POV architectural.
congusbongus
Méthode très intéressante, je devrai l'examiner de plus près moi-même pour toutes les idées que je pourrais pouvoir en retirer.
Draco18s
Je suis venu ici pour me détendre du travail ... Mon sujet de recherche est surpris. Je suis trop paresseux pour écrire une réponse basée sur mes propres recherches (je n'ai encore conçu que les bases de l'algoirthm, donc ça ne vaut pas la peine de toute façon) ou décrire les approches de Danil Nagy face au problème, alors je vais laisser ça ici autodeskresearch.com/publications/…
Felipe Gutierrez