Génération procédurale d'un bâtiment d'une zone spécifique

15

Moi-même et une équipe travaillons sur un jeu de construction d'usine qui donne au joueur une usine aléatoire au début du jeu. Pour essayer de faire en sorte qu'il y ait un sentiment d '«équité», l'idéal serait que l'usine générée de façon aléatoire ait une superficie de quelques unités de (valeur d'espace réservé) 30.

Il est relativement simple d'écrire un générateur de rectangle aléatoire de base pour répondre à ces spécifications, mais notre objectif est que l'usine soit plus complexe, peut-être composée de 2, 3 ou même 4 rectangles qui se croisent, produisant des formes plus complexes (pensez à L, Bâtiments en forme de U et O).

J'ai essayé de générer un rectangle aléatoire, puis d'utiliser l'algèbre de base pour remplir un deuxième rectangle, mais jusqu'à présent, je n'ai eu aucune chance d'implémenter plus de 2 rectangles, et même dans ce cas, je ne suis pas satisfait des résultats pour un design à 2 rectangles seulement .

Quelques informations plus pertinentes: 2D de haut en bas Certaines des mécaniques sont de style factorio, donc les pièces devraient avoir une longueur et une largeur raisonnables pour laisser de la place aux machines Actuellement à Java et à Lua (peuvent utiliser des bibliothèques intégrées à partir de l'une ou l'autre si nécessaire)

Merci d'avance!

EDIT: Quand je dis «bonnes» ou «mauvaises» sorties, une mauvaise sortie serait toute sortie dont l'espace est inutilisable par le lecteur. La forme d'usine limite l'endroit où le joueur peut placer des machines d'usine telles que des bandes transporteuses. Idéalement, l'usine ne devrait pas avoir de zones de 1 à 2 blocs de large, la forme ne devrait pas être un ou deux grands rectangles avec une ligne de 1 à 2 blocs "suspendus" d'un côté. Une bonne sortie serait là où tout l'espace au sol est "réalisable", donc toutes les zones ont au moins 3 à 4 blocs de largeur. Une bonne sortie ne doit pas toujours être complexe (1 ou 2 rectangles est correct), mais elle devrait avoir une bonne chance si elle est composée de plus de 1-2 rectangles.

user2129189
la source

Réponses:

7

Vous pouvez utiliser des polyominos pré-générés comme méta-formes pour construire un assortiment de bâtiments.

Disons que votre distance minimale acceptable est de 3 blocs. Ensuite, la plus petite unité de construction acceptable que nous considérerons est 3x3. Pour plus de commodité, je vais appeler cela une cellule et cela donne une superficie de 9 blocs. Ensuite, prenez votre zone de départ cible et divisez-la par la zone de cellule. En utilisant la valeur de départ que vous avez donnée, nous obtenons 3,333; donc 3 cellules vous donneraient un peu moins que vous voulez et 4 cellules vous en donneraient plus.

De là, vous avez deux options. Si vous êtes flexible sur votre zone de départ, utilisez la méthode qui vous convient le mieux pour choisir le nombre de cellules qui vous donne une quantité acceptable (c'est-à-dire arrondir à la valeur la plus proche, arrondir, etc.). Je vais appeler cela le nombre de cellules.

Ensuite, sélectionnez au hasard le polyomino avec le nombre de cellules souhaité. Remplacez chaque carré du polyomino par une cellule de construction et vous avez votre forme finale.

Pour illustrer, disons que nous choisissons d'arrondir. Voici tous les polyominos de taille 3 (hors rotations / flips):

entrez la description de l'image ici

Supposons que nous choisissions au hasard la forme en L et appliquons une rotation aléatoire, votre bâtiment aurait la disposition suivante:

entrez la description de l'image ici

Quelques problèmes. Tout d'abord, le nombre de cellules que vous pouvez utiliser est limité. Wikipedia vous donnera tous les polyominos jusqu'à la taille 8 ( octomino ). Il comprend des données récapitulatives jusqu'à la taille 12, mais je ne sais pas s'il existe une liste en ligne pour tous. Deuxièmement, la solution ci-dessus ne fonctionne exactement que pour des tailles de bâtiment qui sont des multiples de 9. Il existe plusieurs façons de contourner certains de ces problèmes:

1) Utilisez une taille de cellule différente. Par exemple 3x4, 4x4, etc.

2) Ajoutez des cellules supplémentaires à un polyomino de départ. Cela peut être délicat si vous devez vous assurer que toutes les formes sont également probables, mais pour la plupart des applications de développement de jeu, vous n'avez pas besoin d'une distribution vraiment uniforme des formes de construction.

3) Remplissez un bâtiment pour l'agrandir. Pour revenir à l'exemple, si vous avez utilisé 3 cellules, votre bâtiment aurait une superficie de 27 carrés vous laissant court par 3. Vous pouvez ensuite scanner le périmètre pour trouver un emplacement pour coller un groupe de carrés de taille 1x3. Tant que votre groupe de maquillage est au moins AxB où A est au moins votre distance minimale acceptable, votre résultat ne violera pas votre contrainte de distance minimale acceptable. À partir de l'exemple ci-dessus, voici une illustration d'un résultat possible:

entrez la description de l'image ici

4) Au lieu de garnir un bâtiment trop petit, vous pouvez réduire un bâtiment trop grand. S'assurer que votre contrainte de distance minimale acceptable est respectée est plus complexe que l'option de remplissage, mais vous donnerait plus d'alternatives à envisager.

Quelques autres commentaires:

Ce n'est pas parce que vous pouvez utiliser tous les polyominos possibles d'une taille donnée. Si certains d'entre eux ne sont pas amusants, brisez votre thème, offensent votre public (modèles à croix gammée) ou causent un autre problème, supprimez-les. En outre, vous pouvez pondérer votre routine de sélection si certains modèles sont intéressants, mais trop bizarres pour apparaître régulièrement. Enfin, vous pouvez utiliser cette solution en combinaison avec votre stratégie actuelle. Peut-être que 70% du temps vous générez des bâtiments rectangulaires et 30% du temps vous utilisez l'approche polyomino. Ou peut-être que vous commencez avec un bâtiment rectangulaire et collez un petit polyomino à l'extérieur.

Pikalek
la source
16

Un moyen simple de créer un générateur procédural est:

  1. Construire des choses au hasard
  2. Exécutez une fonction qui vérifie si la sortie est bonne
  3. Si la sortie n'est pas bonne, passez à l'étape 1

Même si cela prend des milliers d'exécutions, la plupart des générateurs simples se débrouillent très bien avec cette approche. L'avantage est qu'il n'y a pas beaucoup d'intelligence requise dans le générateur, et puisque vérifier si quelque chose de bien est beaucoup plus facile que de construire quelque chose de bon 100% du temps, cette approche est très facile.

Vous avez énuméré quelques mesures objectives pour savoir si une sortie est bonne; cela devrait vous suffire pour créer un générateur rapide et sale. Placez des rectangles au hasard dans une zone et rejetez la sortie si, par exemple, il existe des zones qui ne font que 1 à 2 blocs de large.

Commencez par cela, améliorez et optimisez ensuite.

congusbongus
la source
Je vous remercie! Je me souviens d'avoir pensé à cela, mais l'idée qu'il y ait une chance pour un temps de chargement de plusieurs secondes m'a arrêté. Je réalise maintenant à quel point cette chance est incroyablement petite. Je vais devoir essayer cela, mais je vais peut-être attendre de voir si quelqu'un a une solution plus directe en premier.
user2129189
@ user2129189 Lorsque vous avez fait fonctionner votre générateur, vous pouvez toujours modifier ses plages de nombres aléatoires pour éviter de générer des dispositions qui ne réussiront probablement pas le test. Il est également possible de paralléliser cet algorithme de génération d'essais et d'erreurs sur plusieurs cœurs en faisant en sorte que chaque cœur génère une disposition à la fois.
Philipp
3
Moi-même, je ne suis pas un fan des méthodes de génération de rejet et de nouvelle tentative. Ils sont assez rapides lorsque votre générateur ne fait qu'une chose simple, mais pour les niveaux de jeu, nous commençons généralement à superposer davantage de fonctionnalités et d'étapes de génération pour enrichir les cartes. À ce stade, la probabilité de toucher une carte viable est le produit de la probabilité de réussite de chaque étape, qui peut diminuer rapidement. Ce n'est pas seulement une préoccupation académique - j'ai parlé avec des développeurs qui devaient implémenter un bon / mauvais système de mise en cache des semences pour éviter des temps de génération excessifs, alors qu'un générateur à passage unique correct aurait été plus facile.
DMGregory
@DMGregory ouais je peux certainement le voir. Un générateur aléatoire de base fonctionnerait 99% du temps en quelques passes pour mon cas, mais si je veux ajouter plus de complexité plus tard, il pourrait ralentir considérablement. Quelqu'un connaît-il des applications de programmation / jeu réelles du modèle de supposition et de vérification?
user2129189
Il peut peut-être y avoir des niveaux de fonctions et de vérifications de générations, en prenant soin de faire correspondre la formulation des conditions au niveau de génération actuel. De cette façon, le niveau entier n'a pas besoin d'être re-généré entier juste à partir de l'erreur trouvée en plaçant un élément légèrement incorrectement.
Pysis
7

Étant donné une restriction de "toutes les zones sont à au moins 3-4 blocs de large" la première idée qui me vient à l'esprit est quelque chose comme ceci:

  1. choisissez l'un des 3x3, 3x4, 4x3 ou 4x4
  2. placer un bloc de cette taille au centre de la grille
  3. choisissez une direction (haut, gauche, droite, bas)
  4. essayez de placer un bloc 3x3 à côté des blocs précédemment placés dans cette direction
  5. en cas de succès, avec une certaine probabilité, essayez d'étendre le bloc à un bloc 4x3 dans l'une des directions que vous n'avez pas choisies
  6. avec une certaine probabilité, déplacez un vers un bord aléatoire des blocs remplis
  7. répétez les étapes 3 à 6 jusqu'à ce que la zone soit suffisamment grande

L'idée de base est, étant donné que vous voulez que toutes les zones aient au moins une taille donnée, ne travaillez que dans des zones de cette taille. Plus généralement, si vous voulez que quelque chose soit vrai pour toutes les sorties générées, voyez si cela peut être rendu vrai pour toutes les sorties partiellement générées.

Ryan1729
la source
4
Je simplifierais les choses en commençant toujours par un bloc 3x3, puis en ajoutant des blocs 3x1 dans des positions aléatoires où chaque carré est adjacent à un bloc existant. Ajoutant à un bloc 3x3, il y a quatre positions possibles. Tous vous donnent un bloc 3x4, avec six positions possibles pour le suivant. De là, ça devient plus compliqué, mais pas si mal.
JollyJoker
0

Pensez à utiliser les booléens NOT et UNION et à choisir entre eux au hasard.

  1. Placez un rectangle aléatoire.
  2. Placez un deuxième rectangle aléatoire.
  3. Choisissez aléatoirement de les UNIR ou de soustraire le second du premier.
  4. Répétez l'opération pour un certain nombre de rectangles. Cependant, seulement deux ou trois pourraient donner des résultats suffisamment raisonnables.

Ensuite, je calculerais la zone et la ferais monter ou descendre pour correspondre plus étroitement à la taille approximative que vous recherchez, puis tester qu'il n'y a pas de dimensions inférieures à un montant minimum requis.

Poulpe
la source
Votre idée de mise à l'échelle pour obtenir la zone souhaitée est en fait silencieuse et intelligente. Je pourrais implémenter quelque chose de calme un peu comme ça.
user2129189