O que é um bom algoritmo para o layout de cidade processual baseada em fractal?

19

fundo

Eu corro um servidor minecraft onde vou projetar uma cidade inicial de escala bastante grande. Eu tenho uma série de coisas, como placas de regras e gaiolas da multidão, eu gostaria de colocar em prédios lá. A cidade em si será extremamente grande e espalhada, de preferência entre 1000 e 1000 blocos.

Os próprios edifícios terão cubo ou pegadas retangulares baseadas em um determinado cubo base, como todos os múltiplos de 3 blocos. As ruas e a distância entre os prédios terão, de preferência, de 5 a 11 quarteirões de largura, dependendo da importância da rua.

Quando eu começar o plano da cidade, saberei exatamente o tamanho que quero que os edifícios tenham e quantos haverá.

O problema

O problema é projetar o layout da cidade. Obviamente, com algo dessa escala, e eu vindo de um background de programação e não de um planejador urbano, é bastante desafiador começar a entender o problema.

O problema especificamente é que eu quero que a cidade pareça o mais natural possível. É claro que isso seria bastante fácil de construir em um padrão de grade simples, mas eu quero evitar uma grade, ou qualquer coisa que pareça uma grade, o máximo possível.

A questão

Quais algoritmos posso buscar para me ajudar a projetá-lo usando código? Eu estava pensando que pareceria mais natural se eu usasse fractais de alguma forma, já que o minecraft usa fractais já em sua geração de terreno, e uma cidade parece crescer naturalmente em um padrão fractal.

Eu acho que, de certa forma, é semelhante a um algoritmo de execução de tetris, portanto, se alguém tiver soluções que existem nessa direção, também ajudaria. Estou imaginando algo em que poderei definir as formas que quero usar, e o software itera até encontrar a solução mais "ideal" para a distribuição uniforme dos edifícios. Já existe algo para me ajudar a resolver esse problema usando python, de preferência visualmente usando pygame?

Naturalmente, isso também tem implicações interessantes para a geração das cidades em geral no design de jogos, por isso estou muito animado para ver qual é a melhor solução.

edit Para ser claro, estou apenas procurando o layout neste momento, pois os prédios serão projetados e construídos no jogo.

python terrain-rendering pygame minecraft-modding fractal Ken
fonte
3
Minecraft usa fractais? Fiquei com a impressão de que apenas utiliza funções de ruído contínuas (Perlin ou Simplex, acredito).
Martin Sojka
@Martin Sojka Perlin o ruído é na verdade um fractal, então está aí.
Nevermind
1
@ Nevermind: A característica que define um fractal é a auto-similaridade : se você escolher uma parte dela e dimensioná-la para o tamanho do original, ela será "semelhante" (tem a mesma estrutura). Em particular, o espectro de frequência de um sinal fractal é invariante para a escala. Se você fizer isso com o ruído Perlin, tudo o que terá é uma área ampliada de um ruído Perlin; o espectro de frequências também mudará.
Martin Sojka
@Nevermind O ruído Perlin na verdade não é um fractal, no entanto, o movimento browniano (que é uma técnica que pode usar o ruído Perlin) é um fractal e é geralmente chamado de ruído Perlin.
Elva #
Sim, desculpe, eu sempre corrijo as pessoas quando elas confundem o ruído Perlin e o ruído rosa, mas aqui estou cometendo o mesmo erro. Minha única defesa é que o Minecraft também usa ruído rosa (movimento browniano) também, IIRC.
Nevermind

Respostas:

20

Eu recentemente implementei um algoritmo para um layout de cidade processual. Ainda é um trabalho em andamento, mas parece promissor para mim. Dê uma olhada:

exemplo de cidade processual

O algoritmo usado para criar esse layout é vagamente baseado em L-Systems . Eu tenho uma Elementclasse base , que tem um retângulo marcando seu lugar no mapa e um método Grow, que cria outro Elementsdentro do retângulo e / ou gera alguns objetos no mapa. Depois, há elementos reais, herdada esta classe base: City, Street, Buildingetc.

A geração começa com vários objetos "iniciais" (no meu caso, apenas um único Cityelemento colocado aleatoriamente no mapa). Em seguida, o sistema itera sobre todos os elementos, chamando Grow, até que todos os elementos se tornem inativos ( Growretornos false), ou algum grande número de iterações passa.

A cidade na imagem é construída usando apenas algumas regras simples:

  • Citytorna-se um Streetelemento que divide a área em algum lugar.
  • Todos Streetcrescem 0-3 ruas laterais, dividindo ainda mais a área.
  • Além disso, Streets tentam continuamente ajustar um tamanho aleatório Buildingao lado.

O resultado não é muito interessante, mas também não é ruim. O sistema pode ser estendido facilmente e é simples o suficiente para entender o que está acontecendo (-8

deixa pra lá
fonte
Ame a simplicidade. As cidades são, eu acho, realmente orgânicas porque são controladas por uma entidade orgânica - que busca criar perfeição como seus olhos pensam - tornando o L-Systems provavelmente a melhor aproximação desse processo.
Jonathan Dickinson
Eu gosto disso. =) Agora, para implementar em pygame ...
Ken
8

Há uma palestra do GDC sobre geração de edifícios processuais há alguns anos. É para criar edifícios individuais com base em um conjunto de modelos, mas não para criar cidades inteiras (definindo ruas e assim por diante). Infelizmente, não há código livre para acompanhá-lo. O sistema descrito na palestra é implementado no Unreal, embora não esteja claro se está na versão gratuita do UDK ou não. De qualquer forma, você pode usar algumas das mesmas idéias para criar seu próprio sistema.

A pesquisa em "edifícios processuais" ou "cidade processual" também fornecerá alguns outros artigos e artigos sobre o assunto.

Nathan Reed
fonte