Geração processual de rios ou estradas para terrenos infinitos

28

Devo dizer caminhos, não estradas, pois penso mais como medieval. Além disso, não procurando realismo. A resposta que estou procurando será se encaixar no molde que descrevo e não no realismo.

Estou procurando um método para gerar estradas / rios procedimentais de uma forma curvilínea, mas estou desejando fazer isso para um sistema de tipos de terrenos infinitos. Assim como o ruído perlin gera blobs, estou querendo gerar segmentos de linhas de comprimento aleatórios (possivelmente comprimento infinito).

Estou ciente de estratégias como a resposta sugerida encontrada aqui , no entanto, ela depende de um ponto inicial e final especificado para funcionar. Não tenho um ponto inicial e final especificado. Eu gostaria de poder simplesmente chamar uma função usando coordenadas arbitrárias e retornar se as coordenadas específicas fazem parte do rio / estrada.

Não quero exigir que o terreno seja gerado com antecedência. Isso inclui um mapa de altura (como usado para simulações de chuva ou similares). Eu também não gostaria de exigir um ponto de início / fim.

Existe um algoritmo desse tipo ou um ajuste em um algoritmo de ruído que alguém possa conhecer para realizar o que estou tentando explicar?

O mais próximo que cheguei até agora são os fractais com várias sulcos, se estiver usando o nome corretamente. Estou apenas pegando o valor absoluto do ruído de valor (supondo que ele seja dimensionado para -1 a +1) e definindo um limite. Meu principal problema com isso é que as linhas se sobrepõem com muita frequência, são principalmente circulares, às vezes convergem para formar grandes lagos, que são limpos, porém indesejados, e muitas vezes a espessura das linhas varia muito.

Aqui está uma imagem do que tenho até agora em 2D, mas com uma frequência muito alta para mostrar mais detalhes:

insira a descrição da imagem aqui

Mythics
fonte
como os rios "fluem", pode ser fácil determinar rios usando simplesmente o ruído para determinar o ponto de origem; depois, basta usar os dados brutos do mapa de altura para determinar o caminho.
War
As estradas podem ser um pouco mais desafiadoras, considerei construir estradas com base no uso, se um jogador / todos os jogadores andasse regularmente sobre algum terreno, ele se tornaria caminho.
War
11
@ user19142 OK, não é uma duplicata então. Você também pode encontrar alguma utilidade nesta pergunta / resposta: gamedev.stackexchange.com/questions/53400/… E incluirei os links anteriores novamente como gamedev.stackexchange.com/questions/45403/… gamedev "relacionados" . stackexchange.com/questions/29044/... gamedev.stackexchange.com/questions/31263/...
Michaelhouse
4
Eu acho que as estradas não serão muito confiáveis ​​se geradas com ruído. As estradas são criadas pela inteligência, e não pela física e pelo tempo. Embora possam parecer um com o outro às vezes, eles são diferentes o suficiente para que você provavelmente não possa usar o mesmo algoritmo para ambos.
MichaelHouse
11
As estradas nesse projeto eram linhas de contorno que seguiam alturas específicas, para que você pudesse gerá-las localmente. Ele trabalhou lá, mas os mapas de altura não foram gerados com o ruído Perlin.
Amitp

Respostas:

11

Apenas minha ideia de arquivar isso o que você deseja sem (muita) pré-computação e a possibilidade de um mundo infinito.

A primeira parte do algoritmo é o uso dos diagramas de Voronoi . Você divide seu mundo em grades, cada grade possui um endereço no formato (xgrid, ygrid). Para cada célula na qual você precisa criar estradas, você coloca as variáveis ​​xgrid e ygrid em uma função hash que retorna um número CellSeed . Você usa o CellSeed como a semente de um gerador de números aleatórios que gera as coordenadas dos pontos para o diagrama de Voronoi.

Agora você precisa pesquisar as arestas do diagrama e os nós em que várias arestas colidem. Você também pode armazenar as informações em um gráfico para facilitar o acesso.

Após esta etapa, você pode pesquisar caminhos válidos na rede.

Para caminhos válidos, agora você pode criar as estradas (elas possuem arestas de sharph).

Nota : Você também precisa gerar as coordenadas do diagrama de Voronio para todas as células do neightbor, para não ter bordas nas bordas da célula.

Se você não deseja arestas de sharph, pode calcular o ponto médio de cada conexão e usar a direção como uma tangente para uma interpolação de bezier entre duas arestas no gráfico.

Sobre o uso dos diagramas Voronoi

Para arquivar estruturas de cidades como estradas, os pontos da função pseudo-aleatória podem ser alinhados em uma grade, para que as formas sejam retangulares.

Para mais estradas do tipo condado, os pontos precisam ser mais desordenados.

diagrama da wikipedia

Sobre a função pseudo-aleatória para gerar as posições dos pontos para os diagramas de Voronoi

Pode ser uma função aleatória normal ou um conjunto de Hammersley para uma distribuição não uniforme e desajeitada dos pontos.

Quonux
fonte
Você tem algum exemplo de função hash? Eu tenho o mesmo objetivo (mundo infinito que usa voronoi para estradas), mas não consigo entender como isso deve ser feito. Toda lib liboronoi que posso encontrar espera coordenadas de uma caixa delimitadora que imediatamente anulam o objetivo.
BotskoNet
Não, a função hash é apenas para atribuir uma alimentação inicial à célula. Pode ser algo tão trivial quanto x * prime1 + y * prime2 + z * prime3. Onde os números primos são desiguais entre si e idealmente grandes, você deve calcular aqui com números inteiros de 64 bits / sem sinal. Não é um problema se a biblioteca usar uma caixa delimitadora, porque para cada célula você só precisa conserar todos os pontos da célula mais todos os pontos das células vizinhas (que são 8 células vizinhas).
Quonux 01/10/19
Você provavelmente terá problemas de precisão com precisão única se a biblioteca usar precisão única ou se você usar precsão única. Para contornar o problema se a lib usar apenas precisão única e você não fizer o seguinte: Antes de converter as posições em precisão única, subtraia a posição global da célula central a partir delas, coloque-a como flutua na lib e depois transforme o resultados de volta.
Quonux 01/10/19
Na verdade, nunca implementei esse algoritmo, mas a função hash pode ser de fato trivial.
Quonux 01/10/19
8

Para a criação de estradas (e cidades), o melhor artigo que encontrei é este:

Modelagem processual de cidades por Y Parish e P Müller

Ele usa o sistema L e pode gerar padrões de estradas nos EUA e na UE. Se você não quiser gerar estradas para uma cidade inteira, basta gerar as estradas principais. Pode ser usado um mapa de altura, um mapa da água e um mapa de densidade populacional.

Rak
fonte
+1 só porque gostei do artigo. Realmente não se encaixou com o modo como estou tentando gerar as estradas / caminhos / rios, enquanto gera dinamicamente o terreno.
Mythics
6

http://vterrain.org/Culture/Roads/ section "Gerando estradas 3D" tem algumas informações sobre geração de estradas .

O problema com as estradas é que eles conectam pontos de referência (embora muitas vezes sigam o terreno em vez de ir direto de A para B).

Pessoalmente, eu geraria o terreno, depois colocaria rios (talvez usando erosão, consulte http://vterrain.org/Water/ section "hydrogeology"), depois colocaria cidades em locais onde isso fizesse sentido (por exemplo, perto de um rio ou outro fonte de água ou em um local onde a água possa ser transportada para o uso de aquedutos ou torres e tubulações de água) e, finalmente, gerar estradas entre as cidades.

Para tornar isso mais fácil de usar em um mundo processual, você pode criar pontos intermediários no terreno para onde as estradas provavelmente aparecerão quando geradas nesse local e conectar os pontos intermediários se uma estrada for realmente criada naquele local.

Exilyth
fonte
4

Primeiro, rios e estradas são muito diferentes. As estradas tendem a seguir isolinhas (elevação igual / similar) - o motivo é que é muito mais fácil viajar em estradas que não sobem nem caem muito. Os rios, por outro lado, viajam perpendicularmente a isolinhas / isoclinas (descendo). Os rios se formam em bacias (coleções de montanhas que fluem para baixo até um determinado vale) e tendem a formar estruturas semelhantes a árvores. Além disso, as estradas costumam viajar perpendicularmente aos rios, para formar pontes lógicas. A melhor idéia é primeiro gerar rios e depois criar estradas lógicas (ou seja, estradas entre cidades). Infelizmente, não tenho tempo para entrar em mais detalhes, mas espero que isso o leve ao caminho certo.

Pode parecer óbvio, mas veja os mapas do Google em vários tipos de terreno e estradas; você terá uma noção melhor de como elas devem ser.

Gavan Woolery
fonte
11
Modifiquei a pergunta novamente para entender melhor que não estou interessado em realismo nem de perto nem na maneira como o algoritmo precisaria funcionar. No entanto, aprecio a resposta, embora principalmente para alguns dos termos usados. Tente pensar no meu desejo mais como rabiscos de tamanho aleatório infinito, capazes de serem gerados com o mínimo de dados necessários (como mapa de altura).
Mitos