Algoritmos de generación de ciudades

En este RPG.SE se menciona una página perdida hace mucho tiempo con varios generadores en línea.

Tengo particular curiosidad por la forma en que se generaron los pueblos. Tome esta imagen por ejemplo:

Aunque muchas cosas podrían mejorarse en cuanto a gráficos, fue muy bueno teniendo en cuenta las herramientas disponibles en ese momento (mediados a finales de los 90):

• El diseño del camino parece bastante orgánico (incluso teniendo en cuenta que todos los caminos se colocan de manera ortogonal).
• No todas las carreteras están necesariamente conectadas, pero se siente bien .
• Los edificios se colocan en lugares creíbles .
• Incluso los árboles parecen estar ubicados en lugares lógicos .

Creo que sería divertido intentarlo y probarlo yo mismo. Sobre todo porque mis intentos anteriores han sido demasiado "bloqueados":

Notarás que estoy describiendo muchas de las cualidades con adjetivos no bastante medibles ( parece , se siente , es creíble , etc.), por lo que me resulta difícil traducirlos a instrucciones y, finalmente, a un algoritmo.

¿Hay algún algoritmo probado y verdadero para la generación de ciudades?

Entiendo que esto parece ser demasiado amplio, así que considere esto: si pidiera un algoritmo para generar mapas de masas de tierra continentales, obtendría referencias a Perlin y otros algoritmos de ruido de inmediato; seguido de cerca por Voronoi.

He visto preguntas como esta, pero parece que ya tienen en mente una idea más concreta (es decir: casas de 2x2, número fijo de casas, restricciones de ubicación de canales y carreteras).

Lo que me gustaría tener es algo menos limitado. Excepto quizás por el diseño de la cuadrícula, que debería ser mucho más fácil para un primer intento que, por ejemplo, el sistema L.

Introversion Software hizo un generador de ciudad realmente impresionante para su proyecto Subversion cancelado indefinidamente :

El algoritmo está diseñado para generar grandes metrópolis modernas. Pero se pueden usar las mismas técnicas para generar más asentamientos rurales.

Es un algoritmo de arriba hacia abajo que genera primero los contornos generales y luego genera más y más detalles para encajar en ellos (para el enfoque opuesto de abajo hacia arriba para la generación de procedimientos, verifique la respuesta por uliwitness). Aquí hay un video que visualiza el algoritmo en progreso .

El algoritmo parece funcionar de la siguiente manera (ligeramente simplificado):

1. Centros de ciudades: elija algunos puntos del mapa aún vacío como nodos de tráfico principales. Deben estar distribuidos uniformemente alrededor del mapa
2. Carreteras: conecte los principales nodos de tráfico a sus vecinos y al mundo exterior utilizando las carreteras principales.
3. Autopistas: subdivida las celdas generadas por las carreteras principales creando algunas carreteras secundarias.
4. Calles: repita el proceso de subdivisión de forma recursiva con caminos cada vez más pequeños hasta alcanzar el tamaño de bloque de construcción deseado
5. Bloques: decida el propósito de cada bloque de construcción (residencial, minorista, corporativo, industrial ...). Los factores relevantes son los tamaños de las carreteras vecinas y la distancia desde el centro.
6. Asignaciones: divida los bordes de todos los bloques de construcción en lotes (esto significa que cada lote tiene al menos un borde que está conectado a una carretera).
7. Edificios: genere un edificio apropiado para cada lote.

Con respecto a la ubicación de los árboles: mi primer enfoque sería integrarlos en el algoritmo de generación de edificios. Un edificio no necesita llenar su lote por completo. Puede llenar el espacio libre con los objetos decorativos apropiados.

El problema con el enfoque de arriba hacia abajo es que, si bien puede generar una ciudad plausible, es posible que no genere una ciudad plausible con todo lo que desea . Digamos que cada ciudad en tu juego necesita una tienda de armas, una tienda de armaduras, una tienda de pociones y una posada. El algoritmo anterior selecciona edificios en función de los requisitos del lote, por lo que puede terminar con 12 tiendas de armaduras, pero no una sola posada. Abordaría ese problema en la fase de generación del edificio. Antes de comenzar a generar edificios al azar, revise su lista de edificios imprescindibles y seleccione el lote más apropiado para cada uno de ellos. Luego llene los lotes restantes con edificios aleatorizados.

Tengo muchas ganas de explorar las ciudades generadas por procedimientos en tu juego.

Obtenga restricciones de la vida real

A menudo, la respuesta sobre cómo encontrar el algoritmo correcto comienza por observar cómo suceden estas cosas en la vida real. ¿Ha investigado eso? Fuera de mi cabeza, puedo pensar en lo siguiente:

• Hay caminos para conectar edificios y otros puntos de interés.
• Los edificios se colocan a lo largo de las carreteras existentes, si es posible
• Si no hay camino, se coloca un edificio en un lugar vacío y se conecta a un camino cercano a través de su propio camino
• Los edificios se colocan cerca de otros edificios que son de interés para sus habitantes: las personas se mudan para vivir cerca de sus lugares de trabajo, tiendas de comida y ropa, etc.
• Los edificios se colocan cerca de los recursos que son necesarios para su uso previsto. Por ejemplo, un aserradero se coloca cerca de los bosques, o incluso en un claro del bosque. la gente necesita agua y comida (plantas, animales) para vivir en algún lugar.
• Los edificios se colocan lejos de otros edificios que son perjudiciales para su uso previsto, o que serían perjudiciales para ellos. Por ejemplo, la tienda de un tintorero huele horrible, por lo que generalmente no se coloca en una zona residencial. Del mismo modo, las tabernas y los restaurantes son ruidosos, por lo que los residentes no quieren vivir encima de ellos, pero necesitan clientes, por lo que deben estar cerca de las áreas residenciales.
• Algunos países tienen leyes de zonificación que también influyen en la colocación de edificios. Por lo general, esta es una forma más formal de anticipar qué tipos de edificios pueden ser perjudiciales entre sí, o qué recursos son exclusivos del área (por ejemplo, el suelo de alta calidad es para campos, no para construir estacionamientos).
• Los edificios son para habitantes, y su estilo y preferencias personales se reflejan en ellos. Por ejemplo, si una población es pobre, es mucho más probable que compartan tierra (rascacielos, edificios de apartamentos), si están más acomodados, pueden obtener condones, si son ricos, obtienen una villa independiente. Si a ciertos grupos no les gustan otros grupos, serán menos propensos a convivir. Si hay una afinidad entre ciertos grupos, pueden mudarse a áreas similares.

Aplícalos a tu topografía

Una vez que tenga estas restricciones, puede intentar construir un algoritmo a su alrededor. Por ejemplo, genere su topografía y distribuya los recursos necesarios alrededor del mapa (tal vez vigilando la colocación de pequeños depósitos de los recursos más importantes en el área de inicio, luego depósitos más grandes más lejos y uno del otro). Aquí es donde entran en juego las necesidades y la mecánica de su juego, por supuesto, pero es probable que también agregue un elemento aleatorio.

Luego, construya negocios (y sus edificios residenciales) cerca de los recursos que los usan. Por ejemplo, una cantera junto a una gran montaña. Luego agregue la infraestructura que necesitan. Por ejemplo, un puesto comercial con oficina de correos y taberna donde pueden hacer negocios y vender sus productos, una herrería para proporcionar herramientas, etc.

Para decidir qué va a dónde, divida el mapa en mosaicos donde calcule un número para cada mosaico qué tan deseable es para un determinado propósito, utilizando una función de ponderación. Coloque los edificios en los mosaicos más deseables para ese tipo de edificio. Agregue reglas como "un puesto comercial puede manejar 50 negocios o 100 hogares", lo que aumenta la probabilidad de agregar otro puesto comercial si una ciudad alcanza cierto tamaño.

Una vez que tenga esto, debería obtener algunos mapas bastante decentes. Si observa que todos los mapas terminan como formas no naturales, agregue penalizaciones a sus funciones de ponderación para esas formas, como "si mi calle termina justo al lado de otra calle, -100 deseabilidad", o "si mi calle se cruza, -100 deseabilidad "etc. Siempre puede agregar un elemento aleatorio para permitir una sensación más peculiar, o agregar otras mecánicas como" si un cruce tiene más de N edificios conectados a sus carreteras, conviértalo en una rotonda ".

Incluso puede usar estas restricciones para dar a diferentes mapas una sensación diferente, como hacer que un determinado país tenga más montañas en su topografía, o que una determinada cultura construya más caminos sinuosos, y que otros prefieran caminos rectos, etc. Todo con solo modificar uno de sus funciones de ponderación.

Simplificar

Por supuesto, este enfoque es demasiado complejo para los juegos que no son simulaciones comerciales, pero resuélvelo de todos modos y observa qué tipos de edificios tienen sentido para tu juego y elimina los innecesarios. Luego, invente reglas simplificadas como "coloque ciudades cerca de un río, una montaña o un buen suelo. 1 edificio por cada 100 recursos, negocios basados ​​en el tipo de recurso, 10 edificios residenciales para cada conjunto completo de recursos de alimentos / artesanía ... o simplemente" 1 m de río / 1 m 2 de tierra puede soportar 10 edificios residenciales ... lo que tenga sentido para un juego. Aún así, una vez que sepa cuánta área tiene (por ejemplo, no hay edificios en las laderas de las montañas empinadas) y cuántos edificios puede soportar el área, simplemente coloque conjuntos de edificios en esa área hasta que esté llena (como, 1 edificio comercial, 10 residenciales , 3 infraestructura, o lo que sea) y conectarlos con carreteras.