Como gerar uma rede de ruas da cidade?

Eu gostaria de criar um gerador de cidade para um jogo, mas estou enfrentando um problema no início da geração: o sistema rodoviário.

Como é um mundo medieval, não quero um plano de grade como muitas cidades modernas. Idealmente, eu preferiria uma geração pseudo-aleatória de grandes avenidas e ruas menores, onde seria possível se perder, mas com ainda alguma lógica - não um labirinto completo.
Algo que se pareceria com uma cidade naturalmente crescida.

Para simplificar, digamos que minhas cidades estariam em terrenos planos e estáveis, sem problemas de travessia ou alívio de rios. Eu poderia tentar integrá-lo a uma solução depois.

Eu não decidi um tamanho ou disposição precisa para minhas cidades; portanto, se você tiver uma solução que funcione apenas com cidades de uma forma precisa (quadrado, círculo, retângulo etc.), eu a aceitaria.

Um bom ponto de partida para a geração processual de cidades é a Paróquia e a Modelagem Processual de Cidades de Müller . Seu artigo apresenta um sistema L no qual as regras relativas à densidade populacional e padrões de estradas (grade retangular, radial e menor alteração de elevação) são combinadas e depois fixadas para acomodar restrições locais, como frentes de água e estética de estradas. Embora os resultados desse sistema sejam impressionantes, ele foi criticado por ser desnecessariamente complicado . A solução alternativa de Barrett é reapresentada no blog de desenvolvimento de Rudzicz Spare Parts , da seguinte maneira:

• manter uma lista de estradas "propostas"
• avaliá-los em alguma ordem
• se eles são aceitáveis ​​(com ou sem algumas pequenas modificações)
• armazene cada estrada aceita enquanto "propõe" mais algumas ramificações dela

Essa abordagem remove a maior parte da reescrita de tarefas domésticas herdada no Parish e no L-System de Müller. Você pode ver uma demonstração dessa abordagem aqui .

Um benefício dessa abordagem é que ela é independente da forma da cidade - você pode adicionar restrições de estrutura de tópicos conforme necessário, para que a forma da sua cidade possa ser determinada pelas necessidades do design do jogo e não pelo algoritmo. Dependendo do tamanho da sua cidade, isso pode ser bom o suficiente. Aqui está um resultado da demonstração acima com um limite de segmento de 100: mas se você precisar de algo grande, poderá ter problemas; aqui está um resultado com um limite de segmento de 500:

Em parte, você pode ajustar isso alterando as regras de ramificação da estrada, evitando ângulos de 90 graus, etc. Se seu layout ainda for muito regular, aqui está minha correção:

Transforme sua grade da cidade em um gráfico onde cada rua é uma aresta e cada interseção é um nó. Em seguida, use o algoritmo que você preferir para converter o gráfico em um labirinto . Aqui está o último exemplo transformado em labirinto:

Agora a saída tem o problema oposto, é muito labirinto. Mas agora podemos aplicar algumas técnicas dos Trabalhos Secretos do Dungeon Generator, de Jamis Buck . Primeiro, aumente a escassez removendo alguns corredores sem saída. Em seguida, aumente a conectividade adicionando estradas que criam loops (ou seja, introduza ciclos no gráfico). Aqui está um exemplo de resultado:

Nota: é possível obter o mesmo resultado final diretamente do estágio de layout orientado à grade anterior (antes de gerar o labirinto), aplicando apenas remoções de arestas na grade da cidade. O problema dessa abordagem é que você deve garantir que a remoção de uma borda não particione a cidade, tornando partes inacessíveis.

Se você procurar planos de cidades medievais / antigas no Google, encontrará muitas variações diferentes, principalmente com base nas origens da cidade (por exemplo, assentamento aleatório versus posição militar organizada).

Suponho que você esteja procurando um assentamento mais caótico / cultivado naturalmente.

Para estes, eu tentaria uma abordagem como esta:

• Comece com uma estrada principal que vai de uma extremidade à outra (e, idealmente, conecte alguns outros assentamentos. Se desejar, crie uma terceira estrada para obter uma junção na qual iniciar seu assentamento.
• Coloque algumas casas ao longo da estrada (apenas de um lado).
• Agora amplie a estrada pelas casas e adicione um ponto de referência importante do outro lado (normalmente uma igreja, mas isso também pode ser um moinho ou algo parecido). Este será o seu centro / mercado.
• Agora escolha duas posições fora da área com as casas e crie uma nova estrada que encerre as casas.
• Opcionalmente, crie aliados menores entre as casas que conectam a estrada antiga e a nova.
• Agora repita até ficar satisfeito com o seu "núcleo":
  • Adicione mais algumas casas.
  • Adicione outra estrada que os rodeia.
  • Adicione becos que conectam as estradas.
• Quando estiver satisfeito com isso, estará pronto. Se é para ser uma cidade, envolva-a com muros e repita os últimos passos mais algumas vezes, adicionando casas adicionais fora dos muros.

Primeiro de tudo, existem muitas maneiras de gerar geração procedural e nenhuma delas é fácil, farei um tipo de abordagem de como você pode fazê-lo funcionar, depende de você aceitá-lo, modificá-lo ou descartá-lo.

Será pseudo-código em JS, pois é mais fácil de entender.

1º defina um ponto de entrada, como você quer construir uma cidade medieval, vamos começar com um quadrado, então digamos que sua cidade terá 300 unidades quadradas e a praça estará no meio dela (representada por um X).

       300
________________
|               |
|               |
|               | 300
|       X       |
|               |
|               |
|_______________|

const square = [ 150, 150 ];

2º agora vamos às avenidas, haverá um número aleatório delas, serão retas e começarão da praça do meio ou de outras avenidas

let avenues = [] // will contain start and end [[sx,sy],[ex,ey]]
const n_avenues = RANDOM(4, 8); // number of avenues
const n_av_from_square = RANDOM(0, avenues); // starting in the square

for av in av_from_square
  avenues.push(square, [RANDOM(0, 200) + 100, RANDOM(0, 200) + 100])
  // we want avenues to have, at least 100 units length, thats why we randomize just te last 200 units of the whole town size

Isso deve lhe dar uma praça e algumas ruas principais

       300
________________
|   \\          |
|    \\         |
|     \\        | 300
|       X=====  |
|               |
|               |
|_______________|

Agora temos que definir as avenidas que não começam na praça principal, elas cruzarão as outras avenidas

for av in (n_avenues - av_from_square){
  const av_to_intersect = avenues[RANDOM(0,avenues.length)];

  //check av_to... and get a perpendicular vector (explained bellow)
  av[0] = [ av_to_intersect[0][1], - av_to_intersect[0][0] ];
  av[1] = [ av_to_intersect[1][1], - av_to_intersect[1][0] ];

}

Para obter vetores perpendiculares, você deve trocar os cabos x, y e negar o novo y:

swiped == x: noswiped.y, y: -1 * (noswiped.x)

Agora você deve ter algo parecido com isso, não parece uma cidade? : P

       300
________________
|   \\  //      |
|    \\//  ||   |
|     \\   ||   | 300
|    //\X=====  |
|   //     ||   |
|          ||   |
|_______________|

3º agora você só precisa interconectar as avenidas com ruas curtas, além disso, você pode gerar quadrados aleatórios por toda a cidade e fazer o mesmo que acima para todos eles, ou apenas gerar pequenas ruas de algumas praças secundárias, depende de você.

Lembre-se, quanto mais curtas forem as ruas, mais caótica será a cidade.