Utilisation de L-Systems pour générer des villes de manière procédurale

Je fais actuellement une application qui se concentre beaucoup sur le contenu généré de manière procédurale. Jusqu'à présent, j'ai réussi à implémenter la génération procédurale du terrain et de la forme d'une carte en utilisant le bruit simplex. Je suis vraiment content de son apparence. Maintenant j'essaye de faire la même chose pour les villes. J'ai juste besoin de générer une disposition 2D des rues et des bâtiments. Je l'ai étudié et il semble que la plupart des gens suggèrent d'utiliser L-Systems. Cependant, je n'arrive pas à envelopper ma tête autour d'eux. J'obtiens le concept, mais pas l'implémentation dans le code. Quelqu'un a-t-il des exemples de code de L-Systems pour les villes générées de manière procédurale, ou des suggestions sur d'autres façons de gérer les villes?

Les L-Systems , d'après ce que je peux dire *, sont un ensemble de règles de substitution de type grammatical que vous pouvez appliquer récursivement pour obtenir des résultats «organiques» intéressants.

Les plantes sont les endroits où les L-Systems sont souvent utilisés, car ils montrent beaucoup de croissance récursive (c'est-à-dire que les branches se divisent en plusieurs branches). Pour un exemple simple, je vais montrer un arbre "sucette" généré à l'aide d'un L-System:

variables : | o              (these are the things that will grow)
start  : o
         |                   (this is what we start with)
rules  : (o → o   o)         (these are the substitution rules that we apply
               \ /            one step at a time)

Donc à la génération 1, nous avons juste le début:

o
|

À la génération 2, nous suivons chacune des règles et substituons les parties existantes selon les règles. Nous remplaçons les «balles» par «deux bâtons et balles»:

o   o
 \ /
  |

Génération 3:

o o   o o
 \|   |/
   \ /
    |

Bientôt, nous aurons un joli grand arbre (merde)!

Pour ce faire dans le code, vous pouvez le faire récursivement (c'est-à-dire DFS), en appliquant continuellement les règles sur les mêmes parties jusqu'à ce que vous atteigniez une fin arbitraire, ou vous pouvez le faire de manière itérative (c'est-à-dire BFS) comme nous l'avons fait dans cet exemple , en exécutant une règle "passer" sur tous les éléments et en répétant un certain nombre d'étapes. C'est:

Récursivement:

tree = start
grow(tree, start)

func grow(tree, part)
    if this part of the tree is big enough
        stop
    if part is 'o'
        replace part with 'o\/o'
        grow(tree, the left 'o')
        grow(tree, the right 'o')

Itérativement:

tree = start
for a number of iterations
    for each part in tree
        if part is 'o':
            replace with 'o\/o'

Un grand nombre d'utilisations des L-Systems effectuent l'étape de «croissance» en utilisant la subdivision - c'est-à-dire que les pièces deviennent de plus en plus petites au fur et à mesure qu'elles sont «cultivées», les plus grosses pièces sont simplement divisées. Sinon, votre système en croissance peut commencer à se chevaucher sur lui-même. Vous verrez dans mon exemple d'arbre à sucettes, j'ai magiquement veillé à ce que les deux branches ne se chevauchent pas au milieu en changeant la forme des nouvelles branches. Faisons l' exemple de la ville en utilisant la subdivision:

variables: block_vertical block_horizontal road_vertical road_horizontal
start: block_vertical
rules: (block_vertical → block_horizontal road_vertical block_horizontal)
       (block_horizontal → block_vertical road_horizontal block_vertical)

Cela aura du sens dans une minute.

Génération 1:

+--------------------+
|                    |
|                    |
|                    |
|        V           |
|                    |
|                    |
|                    |
+--------------------+

Un seul bloc vertical ennuyeux. (Le V signifie vertical.)

Génération 2: nous remplaçons le bloc vertical par des blocs horizontaux avec une route verticale au milieu

+--------------------+
|       r            |
|       r            |
|       r            |
|   H   r      H     |
|       r            |
|       r            |
|       r            |
+--------------------+

Le r signifie route! J'ai espacé aléatoirement la séparation, nous ne voulons pas de parties régulières ennuyeuses dans PCG.

Génération 3: nous remplaçons les blocs horizontaux par des blocs verticaux séparés par des routes horizontales. Les routes existantes restent; il n'y a pas de règles pour eux.

+--------------------+
|   V   r            |
|       r            |
|rrrrrrrr            |
|       r      V     |
|   V   r            |
|       rrrrrrrrrrrrr|
|       r      V     |
+--------------------+

Remarquez comment les routes se connectent entre elles, ce qui est bien. Répétez cela suffisamment de fois et vous vous retrouverez avec quelque chose comme ça (arraché ouvertement une réponse connexe ):

Notez qu'il y a beaucoup de détails que je n'ai pas couverts, et que ce résultat semble généré "évidemment" - les vraies villes semblent quelque peu différentes. C'est ce qui rend PCG amusant / difficile. Il y a d'innombrables choses que vous pouvez faire pour modifier et améliorer vos résultats, mais n'étant pas lié aux L-Systems, je laisse cette réponse ici; j'espère que cela vous aidera à démarrer.

_{* - Je n'ai pas étudié les L-Systems de manière formelle, bien que j'aie rencontré des types spécifiques comme les grammaires et la végétation PCG; veuillez me corriger si je me trompe de définitions ou de concepts}

La réponse @congusbongus est excellente, permettez-moi d'ajouter quelques éléments.

Les blocs doivent être divisés en zones de construction en fonction de toutes les routes qui les bordent. Lorsque vous avez une route tout autour, le motif global est un anneau. Voir ce lien par exemple: http://oldurbanist.blogspot.fr/2012/01/city-blocks-spaces-in-between.html

(Selon la densité, il peut ne pas y avoir d'espace au centre de l'anneau, voir kowloon).

Une fois que vous avez fait les blocs, vous devez générer les bâtiments. Ils sont un peu délicats et nécessitent une génération en deux passes. Ils sont partiellement interdépendants: votre génératrice ne doit pas créer de fenêtre devant le mur latéral du bâtiment suivant.

Et pour ajouter de la vie à cela, vous voudrez peut-être influencer la génération avec des environnements comme le terrain ou une carte économique: les routes (sauf à San Francisco) ont tendance à contourner les grandes collines, au lieu d'aller tout droit et les types de maisons sont fortement influencé par la partie de la ville où ils se trouvent.

s'amuser.