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

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.

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):

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

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:

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.

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.

É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.

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.