Qu'est-ce qu'un bon algorithme pour une disposition de ville procédurale basée sur les fractales?

19

Contexte

Je gère un serveur minecraft où je vais concevoir une ville de départ assez grande. J'ai une série de choses, comme des panneaux de règles et des cages de foule, je voudrais y installer des bâtiments. La ville elle-même sera extrêmement grande et étendue, de préférence jusqu'à 1000 par 1000 blocs de taille.

Les bâtiments eux-mêmes auront des empreintes cubiques ou rectangulaires basées sur un certain cube de base, comme tous les multiples de 3 blocs. Les rues et la distance entre les bâtiments auront de préférence une largeur de 5 à 11 blocs, selon l'importance de la rue.

Quand je commencerai le plan de la ville, je saurai exactement quelle taille je veux que les bâtiments soient et combien il y en aura.

Le problème

Le problème est de concevoir l'aménagement de la ville. Évidemment, avec quelque chose d'une telle envergure, et moi venant d'un milieu de programmation plutôt que d'un urbaniste, il est assez difficile de commencer même à envelopper ma tête autour du problème.

Le problème est précisément que je veux que la ville soit aussi naturelle que possible. Bien sûr, ce serait assez facile à construire sur un modèle de grille simple, mais je veux éviter autant que possible une grille, ou tout ce qui ressemble à une grille.

La question

Quels algorithmes pourrais-je poursuivre pour pouvoir m'aider à le concevoir à l'aide de code? Je pensais que cela aurait l'air le plus naturel si j'utilisais des fractales d'une manière ou d'une autre, car minecraft utilise déjà des fractales dans sa génération de terrain, et une ville semble se développer naturellement dans un modèle fractal.

Je pense qu'il est similaire à certains égards à un algorithme de jeu tetris, donc si quelqu'un a des solutions qui existent dans cette direction, cela aiderait aussi. J'imagine quelque chose où je serai en mesure de définir les formes que je veux utiliser, et le logiciel répète ensuite jusqu'à ce qu'il trouve la solution la plus "optimale" pour une distribution uniforme des bâtiments. Existe-t-il déjà quelque chose pour m'aider à résoudre ce problème en utilisant python, de préférence de manière visuelle en utilisant pygame?

Naturellement, cela a également des implications intéressantes pour la génération de villes en général dans la conception de jeux, donc je suis très heureux de voir quelle est la meilleure solution.

edit Pour être clair, je cherche juste la disposition à ce stade car les bâtiments seront conçus et construits dans le jeu.

python terrain-rendering pygame minecraft-modding fractal Ken
la source
3
Minecraft utilise des fractales? J'avais l'impression qu'il n'utilisait que des fonctions de bruit continu (Perlin ou Simplex, je crois).
Martin Sojka
Le bruit @Martin Sojka Perlin est en fait une fractale, donc là.
Nevermind
1
@Nevermind: La caractéristique qui définit une fractale est l' auto-similitude : si vous en choisissez une partie et la redimensionnez à la taille de l'original, elle sera "similaire" (aura la même structure). En particulier, le spectre de fréquence d'un signal fractal est invariant à l'échelle. Si vous faites cela avec du bruit Perlin, tout ce que vous obtiendrez sera une zone agrandie d'un bruit Perlin; le spectre de fréquences changera également.
Martin Sojka
@Nevermind Le bruit Perlin n'est en fait pas une fractale, mais le mouvement brownien (qui est une technique qui peut utiliser le bruit Perlin) est une fractale et est communément appelé bruit Perlin.
Elva
Ouais, désolé, je corrige toujours les gens quand ils confondent le bruit Perlin et le bruit rose, mais ici je fais la même erreur moi-même. Ma seule défense est que Minecraft utilise également le bruit rose (mouvement brownien), IIRC.
Nevermind

Réponses:

20

J'ai récemment implémenté un algorithme pour une disposition procédurale de la ville. C'est encore beaucoup de travail en cours, mais cela me semble prometteur. Regarde:

exemple de ville procédurale

L'algorithme utilisé pour créer cette disposition est vaguement basé sur L-Systems . J'ai une Elementclasse de base , qui a un rectangle marquant sa place sur la carte et une méthode Grow, qui en crée d'autres Elementsà l'intérieur du rectangle et / ou fait apparaître certains objets sur la carte. Ensuite , il y a des éléments réels, hérités de cette classe de base: City, Street, Buildingetc.

La génération commence avec un certain nombre d'objets "germes" (dans mon cas, juste un seul Cityélément placé au hasard sur la carte). Ensuite, le système effectue une itération sur tous les éléments, appelant Grow, jusqu'à ce que tous les éléments deviennent inactifs ( Growretours false), ou qu'un grand nombre d'itérations passe.

La ville dans l'image est construite en utilisant seulement quelques règles simples:

  • Citydevient un Streetélément divisant la zone quelque part.
  • Tous Streets développent 0-3 rues latérales, divisant davantage la zone.
  • De plus, Streetessayez continuellement d'adapter une taille aléatoire Buildingsur le côté.

Le résultat n'est pas terriblement intéressant, mais pas mal non plus. Le système peut être étendu facilement et est assez simple pour comprendre ce qui se passe (-8

Ça ne fait rien
la source
J'adore la simplicité. Les villes sont, je suppose, en fait organiques parce qu'elles sont contrôlées par une entité organique - qui cherche à créer la perfection comme le voit son esprit - faisant des L-Systems probablement la meilleure approximation de ce processus.
Jonathan Dickinson
Je l'aime. =) Maintenant à implémenter dans pygame ...
Ken
8

Il y a ce discours de GDC sur la génération de bâtiments procéduraux d'il y a quelques années. C'est pour créer des bâtiments individuels sur la base d'un ensemble de modèles, mais pas pour créer des villes entières (tracer des rues, etc.). Il n'y a malheureusement pas de code gratuit. Le système décrit dans l'exposé est implémenté dans Unreal bien que je ne sache pas s'il est dans la version gratuite d'UDK ou non. Dans tous les cas, vous pouvez utiliser certaines des mêmes idées pour créer votre propre système.

La recherche sur "bâtiments procéduraux" ou "ville procédurale" vous donnera également de nombreux autres articles et articles sur le sujet.

Nathan Reed
la source