Como funcionam os algoritmos de geração de histórico?

19

Ouvi falar do jogo Dwarf Fortress, mas só agora uma das pessoas que eu sigo no Youtube fez um comentário ... Fiquei mais do que surpreso quando notei como o Dwarf Fortress realmente gera uma história para o mundo!

Agora, como esses algoritmos funcionam? O que eles geralmente usam como entrada, exceto a duração da simulação? Quão específicos eles podem ser?

E o mais importante; eles podem ser feitos em Javascript ou o Javascript é muito lento? (Acho que isso depende da profundidade da simulação, mas tome o Dwarf Fortress como exemplo.)

jcora
fonte
3
"Eles podem ser feitos em Javascript?" A resposta é obviamente sim, mas depende da rapidez com que você deseja que os resultados e da complexidade que deseja que sejam. A Fortaleza dos Anões também demora um pouco - e diminui à medida que o mundo envelhece! Contanto que você queira um histórico superficial, sim, você pode fazê-lo em Javascript, portanto depende de quão complexo você deseja que o histórico seja.
doppelgreener
2
Ele quer dizer "no nível da Fortaleza dos Anões", como em escala.
MichaelHouse
2
@Bane Sim, quero dizer que você pode alterar a quantidade de histórico que haverá no DF. Quando você inicia um mundo, ele primeiro gera aleatoriamente o terreno e depois começa a envelhecer o mundo diante de seus olhos e a gerar história à medida que avança. Você vê como os impérios se expandem e encolhem, como o terreno muda, as florestas crescem e recuam, as áreas se tornam assombradas (ou não são mais assombradas) e assim por diante. Ele progride ano a ano (ou vários anos de cada vez) diante de seus olhos. Isso continua até você pedir para parar. Quanto mais você fica mais lento, mais a geração (devido ao uso da CPU, não à mecânica do jogo).
doppelgreener
1
Para ser bem claro: quanto mais velho o mundo, mais lento a cada ano é calculado. Em um mundo jovem, ele se apressará nos primeiros anos, em um mundo com centenas de anos, o próximo ano poderá levar um segundo ou alguns segundos para gerar.
doppelgreener
1
Ah, eu sei disso. Por "profundidade", não quis dizer a quantidade de anos, a quantidade de eventos que acontecem e a precisão da simulação. Você pode apenas manter o número de pessoas que um império tem, ou você pode realmente ter uma classe chamada Person, que faz tarefas, vai para o exército, etc. profundo seria ter cada soldado lutando por si próprio.
jcora

Respostas:

27

Primeiro, existem algumas dicas para a geração da história sobre o Dwarf Fortress. Alguém perguntou nos fóruns do Bay12 há um tempo, e uma transcrição foi compartilhada e você pode descobrir onde a discussão começa pesquisando: "nosso tópico hoje é geração mundial e geração de história".


Não sei exatamente como o Dwarf Fortress faz isso, mas vou explicar como planejo implementar um primeiro rascunho muito básico no meu jogo. Vou usar um autômato celular simples . Se você observar esses protótipos do Spore , como a cultura de células e o bioma.

insira a descrição da imagem aqui

Estes são exemplos de automações celulares e o que elas podem produzir. Essencialmente, vou criar regras para diferentes raças. Alguns exemplos de regras seriam:

  • Sua hostilidade em relação a outras raças
  • Suas preferências climáticas
  • Seus requisitos de recursos
  • Suas taxas de natalidade e vida útil
  • Seus desejos (pesquisa tecnológica, comércio, existência pacífica, dominação do mundo)
  • Suas capacidades (construção de estrutura, coleta de recursos, criação de guerra etc.)
  • E assim por diante...

Portanto, a entrada mais crítica para que tudo isso funcione é um mundo para colocar essas raças. O terreno determinará suas preferências e expansão. Então, depois de gerar um mundo, escolha locais aleatórios no mundo onde essas raças viveriam adequadamente e as soltariam. Agora as coisas interessantes começam a acontecer. Agora que você tem terra e raças com desejos e capacidades, pode começar a construir uma história. Essas raças reúnem recursos e as estruturas são construídas:

  • Cidades em áreas de alto recurso e alta habitabilidade.
  • Estradas conectam as cidades maiores.
  • Pontes através dos rios.
  • Túneis através das montanhas.
  • Fortaleza perto da linha de frente da expansão em resposta a batalhas.

Qualquer estrutura pode ser invadida / conquistada por outras raças. Quanto mais uma estrutura (como uma cidade ou fortaleza) existe na história, mais defensável é, mais difícil é assumir. E o mais desejável é para raças que desejam controle. As batalhas são travadas onde as raças se encontram (pelo menos uma é hostil). As batalhas são nomeadas após marcos ou estruturas próximas, ou se a batalha for significativa ou se os marcos não tiverem nome, os marcos serão nomeados após a batalha.

Estradas, pontes e túneis são expandidos através do comércio e transporte de recursos. Cada um tem uma taxa de transferência máxima que pode aumentar com o gasto de recursos. Construindo uma fortaleza de pedra no meio de pastagens? Essas estradas vão ficar pesadas transportando a pedra necessária. Eles ficarão maiores e receberão um nome.

Desastres naturais ocorrem, afetando populações e o curso da história. Terremotos podem reduzir uma cidade a ruínas ou desmoronar um túnel. Uma inundação pode varrer uma estrada ou ponte.


Não é tão profundo quanto o Dwarf Fortress, mas é um começo. Agora, como você pode imaginar (e como Johnathan Hobbs mencionou), quanto mais essas raças se expandem, mais células estão sendo simuladas. Não apenas mais células estão sendo simuladas, mas as simulações são mais complexas, pois agora existem estruturas para construir / manter, batalhas salariais, comércio para ... comércio e assim por diante. Isso fica pesado para qualquer idioma. Javascript pode abrandar mais cedo. No entanto, você sempre pode sacrificar a complexidade para aumentar a velocidade.

É tudo uma simulação (embora complexa), você está apenas registrando os eventos importantes ao longo do caminho e chamando isso de história.

Eu também acabei de encontrar um post no fórum Bay12 para pessoas discutindo como tornar a geração mundial da Fortaleza dos Anões mais rápida. Não o li, mas pode fornecer algumas dicas se você tiver problemas com a implementação muito lenta.

MichaelHouse
fonte
Ótimo e informativo como sempre, @ Byte56. :)
jcora
1
Obrigado Bane. Talvez nem sempre, acontece que as pessoas fazem perguntas sobre as quais acho que sei alguma coisa. Obrigado por me dar a oportunidade de pensar mais sobre isso e escrever algo :) :)
MichaelHouse
4

Apenas como um ponto lateral, o JavaScript não é tão lento quanto você imagina .

Os desenvolvedores de navegadores gastaram muito tempo e energia na otimização de seus mecanismos JavaScript . O benchmark ao qual vinculei mostra que, nas tarefas comparadas, na mediana, o JavaScript era apenas 5 vezes mais lento que C , o que não pode ser dito para outras linguagens interpretadas. E o limite inferior é ainda mais impressionante: a par com C .

Obviamente, os benchmarks de idiomas não significam muito - provavelmente você pode encontrar contra-exemplos usando um benchmark diferente. Mas o ponto é que o JavaScript é bem rápido . Não, não é C ou C ++, e não tenta ser. Mas é bom não ficar preso à mentalidade "linguagem interpretada == lenta", porque para qualquer tarefa de complexidade não trivial, o desempenho será mais importante no design do algoritmo e menos na escolha do idioma.

Na verdade, eu ia escrever tudo isso em um comentário, mas fiquei sem espaço.

voithos
fonte
1

Sim, ele pode ser construído em javascript, verifique projetos como o ASM.js, que obtêm uma velocidade quase duas vezes mais lenta que o C. Se você cuida de vários núcleos (usando trabalhadores da web), pode ser ainda mais rápido que o DF (em termos de recursos) , que é monocore agora.

user29687
fonte