¿Cuál es un buen algoritmo para el diseño de ciudad procesal basado en fractales?

19

Antecedentes

Ejecuto un servidor de Minecraft donde voy a diseñar una ciudad de inicio de escala bastante grande. Tengo una serie de cosas, como signos de reglas y jaulas de la mafia, me gustaría poner en edificios allí. La ciudad en sí será extremadamente grande y extendida, preferiblemente de hasta 1000 por 1000 cuadras de tamaño.

Los edificios mismos tendrán huellas de cubo o rectangulares que se basan en un cierto cubo base, como todos los múltiplos de 3 bloques. Las calles y la distancia entre los edificios serán preferiblemente de 5 a 11 cuadras de ancho, dependiendo de la importancia de la calle.

Cuando comience el plan para la ciudad, sabré exactamente qué tan grande quiero que sean los edificios y cuántos habrá.

El problema

El problema es diseñar el diseño de la ciudad. Obviamente, con algo de tal escala, y yo viniendo de un fondo de programación en lugar de un fondo de planificador urbano, es bastante difícil incluso comenzar a entender el problema.

El problema específicamente es que quiero que la ciudad se vea lo más natural posible. Por supuesto, esto sería bastante fácil de construir en un patrón de cuadrícula simple, pero quiero evitar una cuadrícula, o cualquier cosa que parezca una cuadrícula, tanto como sea posible.

La pregunta

¿Qué algoritmos podría seguir para ayudarme a diseñarlo usando código? Estaba pensando que se vería más natural si usara fractales de alguna manera, ya que Minecraft ya usa fractales en su generación de terreno, y una ciudad parece crecer en un patrón fractal naturalmente.

Creo que es similar en algunos aspectos a un algoritmo de juego de tetris, por lo que si alguien tiene soluciones que existan en esa dirección, también ayudaría. Me estoy imaginando algo donde podré definir las formas que quiero usar, y el software iterará hasta que encuentre la solución más "óptima" para una distribución uniforme de los edificios. ¿Ya existe algo para ayudarme a resolver este problema usando Python, preferiblemente de manera visual usando Pygame?

Naturalmente, esto también tiene implicaciones interesantes para la generación de ciudades en general en el diseño de juegos, por lo que estoy muy emocionado de ver cuál es la mejor solución.

editar Para ser claros, solo estoy buscando el diseño en este punto, ya que los edificios se diseñarán y construirán en el juego.

python terrain-rendering pygame minecraft-modding fractal Conocer
fuente
3
¿Minecraft usa fractales? Tenía la impresión de que solo usa funciones de ruido continuo (Perlin o Simplex, creo).
Martin Sojka
@Martin Sojka El ruido de Perlin es en realidad un fractal, así que ahí.
importa
1
@Nevermind: La característica definitoria de un fractal es la autosimilitud : si eliges una parte y la escalas al tamaño del original, será "similar" (tendrá la misma estructura). En particular, el espectro de frecuencia de una señal fractal es invariable para la escala. Si hace eso con el ruido Perlin, todo lo que obtendrá es un área ampliada de un ruido Perlin; el espectro de frecuencia también cambiará.
Martin Sojka
@Nevermind El ruido de Perlin en realidad no es un fractal, sin embargo, el movimiento browniano (que es una técnica que puede usar el ruido de Perlin) es un fractal y se conoce comúnmente como ruido de Perlin.
Elva
Sí, lo siento, siempre corrijo a las personas cuando confunden el ruido de Perlin y el ruido rosa, pero aquí estoy cometiendo el mismo error. Mi única defensa es que Minecraft también usa ruido rosa (movimiento browniano), IIRC.
importa

Respuestas:

20

Recientemente he implementado un algoritmo para un diseño de ciudad procesal. Todavía es un trabajo en progreso, pero me parece prometedor. Echar un vistazo:

ejemplo de ciudad procesal

El algoritmo utilizado para crear este diseño se basa libremente en L-Systems . Tengo una Elementclase base , que tiene un rectángulo que marca su lugar en el mapa y un método Grow, que crea otro Elementsdentro del rectángulo y / o genera algunos objetos en el mapa. Luego hay elementos reales, heredadas de esta clase base: City, Street, Buildingetc.

La generación comienza con una serie de objetos "semilla" (en mi caso, solo un único Cityelemento colocado aleatoriamente en el mapa). Luego, el sistema itera sobre todos los elementos, invocando Grow, hasta que todos los elementos se vuelven inactivos ( Growretornos false), o pasa un gran número de iteraciones.

La ciudad en la imagen se construye usando solo unas pocas reglas simples:

  • Cityse convierte en un Streetelemento que divide el área en algún lugar.
  • Todos Streets crecen 0-3 calles laterales, dividiendo aún más el área.
  • Además, Streetcontinuamente intentamos colocar un tamaño aleatorio Buildinga un lado.

El resultado no es terriblemente interesante, pero tampoco está mal. El sistema se puede ampliar fácilmente y es lo suficientemente simple como para comprender lo que está sucediendo (-8

No importa
fuente
Amo la simplicidad. Supongo que las ciudades son realmente orgánicas porque están controladas por una entidad orgánica, que busca crear la perfección como lo ve su mente, lo que hace que L-Systems sea probablemente la mejor aproximación de este proceso.
Jonathan Dickinson
Me gusta. =) Ahora para implementar en pygame ...
Ken
8

Existe esta charla de GDC sobre la generación de edificios procesales de hace un par de años. Es para crear edificios individuales basados ​​en un conjunto de plantillas, pero no para crear ciudades enteras (diseño de calles, etc.). No hay ningún código gratuito que lo acompañe, desafortunadamente. El sistema descrito en la charla se implementa en Unreal, aunque no estoy claro si está en la versión gratuita de UDK o no. En cualquier caso, podría usar algunas de las mismas ideas para construir su propio sistema.

Buscar en Google "edificios procesales" o "ciudad procesal" también le proporcionará muchos otros documentos y artículos sobre el tema.

Nathan Reed
fuente