Algoritmos de geração de cidades

8

Em este post RPG.SE uma página há muito perdida com vários geradores on-line é mencionado.

Estou particularmente curioso sobre a maneira como as cidades foram geradas. Veja esta imagem, por exemplo:

Uma cidade PCG da extinta Irony Games

Embora muitas coisas pudessem ser melhoradas em termos de gráficos, foi muito bom, considerando as ferramentas disponíveis na época (meados dos anos 90):

  • O layout da estrada parece bastante orgânico (mesmo considerando todas as estradas serem colocadas de maneira ortogonal).
  • Nem todas as estradas estão necessariamente conectadas, mas parece certo .
  • Os edifícios são colocados em locais confiáveis .
  • Até as árvores parecem colocadas em pontos lógicos .

Eu acho que seria divertido tentar e tentar sozinho. Especialmente porque minhas tentativas anteriores foram muito "em blocos":

Minha última tentativa de geração de cidades

Você notará que estou descrevendo muitas das qualidades com adjetivos não muito mensuráveis ​​( parece , sensações , credíveis etc.), por isso estou tendo dificuldade em traduzi-las para instruções e, finalmente, para um algoritmo.

Existem algoritmos testados e comprovados para a geração de cidades?

Entendo que isso parece muito amplo, considere o seguinte: se eu pedisse um algoritmo para gerar mapas de massas continentais, obteria referências a Perlin e outros algoritmos de ruído imediatamente; seguido de perto por Voronoi.

Eu já vi perguntas como essa, mas elas parecem ter uma idéia mais concreta em mente (ou seja: casas 2x2, número fixo de casas, restrições de posicionamento de canais e estradas).

O que eu gostaria de ter é algo menos restrito. Exceto, talvez, o layout da grade, que deve ser muito mais fácil para uma primeira tentativa do que, digamos, o sistema L.

Roflo
fonte
Listar algoritmos para um amplo domínio de problemas geralmente acaba sendo amplo demais para responder bem em nosso formato de perguntas e respostas. Geralmente, temos mais sorte com "Como posso gerar conteúdo de jogos com essas características específicas " - onde você fornece vários critérios ou exemplos positivos / negativos que podemos usar para avaliar possíveis respostas e avaliar a melhor proposta. Você pode tentar editar sua pergunta para explicar com mais detalhes o que produz uma cidade adequada versus uma menos adequada?
DMGregory
muito amplo, especialmente porque esses geradores são provavelmente compostos (por exemplo, a etapa 1 gera estradas, a etapa 2 gera casas, a etapa 3 gera árvores). Se você puder restringir as coisas a um gerador específico, e que problemas específicos você está tendo com isso, isso seria menos amplo.
congusbongus
11
Também temos essa pergunta sobre a geração processual de cidades . Pode ajudar se você puder articular como suas necessidades diferem dessa questão.
Pikalek 03/08/1918
11
Nenhuma ótima resposta aqui, mas uma coisa que noto é que, no bom exemplo, todo prédio fica ao lado de uma estrada, enquanto no seu exemplo, não está.
user1118321
@ user1118321: Na verdade, as casas nem sempre estão próximas a uma estrada, mas as parcelas são (abordagem moderna) ou pelo menos existe um caminho para a próxima estrada (talvez abordagem mais antiga, não como uma casa no quintal). Portanto, os espaços não são tão antinaturais, como os mercados, por exemplo.
PSquall

Respostas:

9

Introversão Software fez um gerador cidade realmente impressionante para sua cancelado projeto indefinidamente suspenso Subversion :

Subversion City Generator

O algoritmo foi projetado para gerar metrópoles grandes e modernas. Mas as mesmas técnicas podem ser usadas para gerar mais assentamentos rurais.

É um algoritmo de cima para baixo que gera primeiro os contornos brutos e depois gera mais e mais detalhes para se encaixar neles (para a abordagem de baixo para cima da geração de procedimentos, verifique a resposta por uliwitness). Aqui está um vídeo que visualiza o algoritmo em andamento .

O algoritmo parece funcionar da seguinte maneira (ligeiramente simplificado):

  1. Centros da cidade: escolha alguns pontos do mapa ainda vazio como principais nós de tráfego. Eles devem ser distribuídos uniformemente pelo mapa
  2. Rodovias: conecte os principais nós de tráfego aos vizinhos e ao mundo exterior usando as principais estradas.
  3. Autoestradas: subdivide as células geradas pelas principais estradas criando algumas estradas menores.
  4. Ruas: repita o processo de subdivisão recursivamente com estradas cada vez menores até atingir o tamanho de bloco de construção desejado
  5. Blocos: decida a finalidade de cada bloco de construção (residencial, varejo, corporativo, industrial ...). Fatores relevantes são o tamanho das estradas vizinhas e a distância do centro.
  6. Atribuições: divida as arestas de todos os blocos de construção em lotes (isso significa que cada lote tem pelo menos uma aresta conectada a uma estrada).
  7. Edifícios: Gere um edifício adequado para cada lote.

Com relação à localização das árvores: Minha primeira abordagem seria integrar as do algoritmo de geração de edifícios. Um edifício não precisa preencher seu lote completamente. Você pode preencher o espaço livre com objetos decorativos apropriados.

O problema com a abordagem de cima para baixo é que, embora possa gerar uma cidade plausível, ela pode não gerar uma cidade plausível com tudo o que você deseja . Digamos que toda cidade do seu jogo precise de uma loja de armas, uma loja de armaduras, uma loja de poções e uma pousada. O algoritmo acima escolhe edifícios com base nos requisitos do lote, então você pode acabar com 12 oficinas de blindagem, mas não uma única pousada. Eu abordaria esse problema na fase de geração de edifícios. Antes de começar a gerar edifícios aleatoriamente, consulte sua lista de edifícios obrigatórios e selecione o lote mais apropriado para cada um deles. Em seguida, preencha os lotes restantes com edifícios aleatórios.

Estou ansioso para explorar as cidades geradas processualmente em seu jogo.

Philipp
fonte
Esqueci totalmente de mencionar ruas de vários tamanhos, bom ponto!
uliwitness
Obrigado! Não tenho certeza se vou tentar de cima para baixo ou de baixo para cima ... mas percebendo que tenho duas opções, meu cérebro deu um salto de novo. ;)
Roflo
5

Obtenha restrições da vida real

Muitas vezes, a resposta sobre como encontrar o algoritmo certo começa com a observação de como essas coisas acontecem na vida real. Você já olhou para isso? De cabeça para baixo, posso pensar no seguinte:

  • Existem estradas para conectar prédios e outros pontos de interesse
  • Os edifícios são colocados ao longo das estradas existentes, se possível
  • Se não houver estrada, um edifício é colocado em um local vazio e conectado a uma estrada próxima por sua própria estrada
  • Os edifícios são colocados perto de outros edifícios que são de interesse de seus habitantes: as pessoas se mudam para morar perto de seus locais de trabalho, lojas de alimentos e roupas etc.
  • Os edifícios são colocados perto de recursos necessários para o uso pretendido. Por exemplo, uma serraria é colocada perto de florestas, ou mesmo em uma clareira. as pessoas precisam de água e comida (plantas, animais) para morar em algum lugar.
  • Os edifícios são colocados longe de outros edifícios que são prejudiciais ao uso pretendido ou aos quais seriam prejudiciais. Por exemplo, uma loja de tintureira cheira horrivelmente, por isso geralmente não é colocada em uma área residencial. Da mesma forma, as tabernas e restaurantes são barulhentos, então os moradores não querem morar em cima deles, mas precisam de clientes, por isso precisam estar perto de áreas residenciais.
  • Alguns países têm leis de zoneamento que também influenciam a colocação de edifícios. Geralmente, essa é uma maneira mais formal de antecipar que tipos de edifícios podem ser prejudiciais um para o outro ou quais recursos são exclusivos da área (como solo de alta qualidade é para campos, não para a construção de estacionamentos).
  • Os edifícios são para habitantes e seu estilo e preferências pessoais são refletidos neles. Por exemplo, se uma população é pobre, é muito mais provável que compartilhe terreno (arranha-céus, prédios de apartamentos), se estiver mais bem, eles podem obter preservativos, se são ricos, ficam em uma vila independente. Se certos grupos não gostarem de outros, eles terão menos probabilidade de coabitar. Se houver uma afinidade entre certos grupos, eles podem se mover para áreas semelhantes.

Aplique-os à sua topografia

Depois de ter essas restrições, você pode tentar criar um algoritmo em torno dela. Por exemplo, gere sua topografia e distribua os recursos necessários ao redor do mapa (talvez esteja de olho em colocar pequenos depósitos dos recursos mais importantes na área inicial, depois depósitos maiores, mais afastados e afastados um do outro). É aqui que as necessidades e mecânicas do seu jogo entram em jogo, é claro, mas você provavelmente também adicionará um elemento aleatório.

Em seguida, construa empresas (e seus edifícios residenciais) perto dos recursos que as utilizam. Por exemplo, uma pedreira ao lado de uma grande montanha. Em seguida, adicione a infraestrutura necessária por eles. Por exemplo, um posto comercial com correios e tabernas, onde eles podem fazer negócios e vender seus produtos, uma ferraria para fornecer ferramentas etc.

Para decidir o que vai aonde, divida o mapa em blocos onde você calcula um número para cada bloco, quão desejável é para uma determinada finalidade, usando uma função de ponderação. Coloque os edifícios nos ladrilhos mais desejáveis ​​para esse tipo de edifício. Adicione regras como "um posto comercial pode lidar com 50 empresas ou 100 residências", o que aumenta a probabilidade de adicionar outro posto comercial se uma cidade atingir um determinado tamanho.

Depois de ter isso, você deve obter alguns mapas decentes. Se você notar que todos os mapas terminam em formas não naturais, adicione penalidades às suas funções de ponderação para essas formas, como "se minha rua acabar bem ao lado de outra rua, -100 desejabilidade" ou "se minha rua se cruzar, -100 desejabilidade "etc. Você sempre pode adicionar um elemento aleatório para permitir uma sensação mais peculiar ou adicionar outras mecânicas como" se um cruzamento tiver mais de N edifícios conectados às suas estradas, transformá-lo em uma rotatória ".

Você pode até usar essas restrições para dar a diferentes mapas uma sensação diferente, como fazer com que um determinado país tenha mais montanhas em sua topografia ou uma certa cultura construa mais estradas sinuosas e outra prefira estradas retas etc. Tudo apenas modificando uma de suas funções de ponderação.

Simplificar

Obviamente, essa abordagem é muito complexa para jogos que não são simulações de comércio, mas resolva isso de qualquer maneira e veja quais tipos de construções fazem sentido para o seu jogo e elimine os desnecessários. Em seguida, crie regras simplificadas como "coloque cidades próximas a um rio, uma montanha ou solo bom. 1 construção por 100 recursos, empresas baseadas no tipo de recurso, 10 edifícios residenciais para cada conjunto completo de recursos de alimentos / artesanato ... ou apenas" 1m de rio / 1sqm de solo pode suportar 10 edifícios residenciais ... o que fizer sentido para um jogo. Ainda assim, depois de saber quanta área você tem (por exemplo, sem prédios nas encostas íngremes das montanhas) e quantos prédios a área pode suportar, basta colocar conjuntos de prédios nessa área até ficarem cheios (como 1 prédio comercial, 10 residenciais). , 3 infraestrutura ou o que for) e conecte-os às estradas.

uliwitness
fonte
11
Esta resposta descreve a abordagem de baixo para cima para geração de procedimentos. Ele complementa muito bem a minha resposta, que descreve um exemplo da abordagem oposta de cima para baixo. Ambas as abordagens têm vantagens e desvantagens. A vantagem de baixo para cima é que você tem um controle muito bom sobre quais objetos você tem em sua cidade gerada. A desvantagem é que você precisa de um conjunto de regras muito mais complexo e frágil para gerar uma cidade que pareça realista como um todo.
Philipp
Sim. Também depende muito do tipo de jogo e do layout da cidade desejado. De baixo para cima funciona melhor em cidades menores, de estilo medieval e naturalmente cultivadas, enquanto de cima para baixo funciona melhor em cidades e metrópoles no estilo dos EUA. Da mesma forma, se você tem um jogo que envolve edifícios funcionais e gerenciamento de recursos, de baixo para cima pode fornecer um controle mais refinado, enquanto de cima para baixo é a melhor otimização para cidades em jogos de corrida etc. onde você realmente não se importa com a função dos edifícios .
uliwitness
Obrigado pela resposta. Have you looked into that?Eu tenho. Bem, mais ou menos (eu não conseguia pensar em muitas "regras da vida real"). Mas isso é bastante revelador em comparação com as minhas tentativas anteriores: eu estava falhando em reconhecer os recursos que não poderia desenhar (ou seja: há uma floresta ao leste ... independentemente de eu a desenhar ou não).
Roflo