Como o Dwarf Fortress controla tantas entidades sem perder o desempenho?

79

No Dwarf Fortress, você pode ter centenas de anões, animais, duendes etc. no jogo a qualquer momento, cada um com sua própria IA complexa e rotinas de busca de caminhos. Minha pergunta é como isso não produz uma desaceleração perceptível? Cada anão é executado em seu próprio segmento?

RSH1
fonte
6
Pergunta interessante. Embora eu não goste da forma como é formulada, uma vez que seria apenas especulação responder a essa pergunta como formulada. De qualquer forma, você pode ter visto este artigo conversando com Tarn Adams. Onde eles cobrem brevemente o caminho.
MichaelHouse
25
É absolutamente produz desaceleração perceptível uma vez que você tem uma topologia túnel complexo e 100+ anões.
Russell Borogove
3
Sim, o DF na minha experiência é incrivelmente lento no cenário que você descreve.
argentage 23/07/12
4
Destrua uma escada principal e observe sua taxa de quadros cair como uma pedra por um momento, enquanto todos os anões repentinamente repatram ao mesmo tempo.
Mooing Duck
2
Vou gritar e concordar que o DF não é o melhor exemplo; de fato, o DF é conhecido por sofrer problemas de desempenho.
Robert S.

Respostas:

110

Qualquer sistema que tivesse um encadeamento para cada um dos tantos caracteres ficaria sem recursos muito rapidamente. Os threads podem fornecer acesso a núcleos extras de processador, mas eles não tornam nada intrinsecamente mais eficiente e vêm com sobrecarga.

A resposta simples é apenas para ser eficiente no processamento de cada entidade no jogo.

  • Não processe todas as entidades em cada quadro.
  • Divida o processamento em coisas que precisam ser feitas com frequência e coisas que não precisam ser feitas com frequência.
  • Espalhe algoritmos de execução longa por vários quadros para que eles não bloqueiem o processamento em outros sistemas.
  • Garanta que algoritmos e estruturas de dados eficientes sejam usados.
  • Coloque em cache os resultados de cálculos caros, se é provável que sejam usados ​​novamente.
Kylotan
fonte
2
+1 por isso, por realmente explicar o que está acontecendo, em vez de ficar falando sobre gráficos como eu. :)
Matt Kemp
4
Para ser justo, também dei +1 a você porque esqueci esse aspecto, e é verdade - tire gfx da equação e é como tornar os computadores 2x ou 3x mais rápidos instantaneamente.
Kylotan
Ouvi dizer que o DF agora é multithread, mas, pelo menos até recentemente, tudo foi feito em um único thread. (Ainda pode ser, não tenho certeza) #
Mooing Duck
@MooingDuck Ainda não é.
Tharwen
63

O Dwarf Fortress não é de código aberto e, embora exista muita conjectura e engenharia reversa que possam ajudar no funcionamento de tudo isso, vou me concentrar em algumas técnicas básicas para otimizar um roguelike 3D (não gráficos 3D, mundo 3D) do mesmo tipo.

Como é o caso de todos os videogames, há muita fumaça e espelhos que estão criando a ilusão de complexidade a partir de regras e sistemas simples. Eles variam desde o uso de números aleatórios simples para movimentos sem objetivo até a pré-montagem de uma malha de alto nível de nós para busca de caminhos.

Movimento

Falando em busca de caminhos, esse pode ser um problema muito difícil de resolver para grandes espaços, como um mapa DF (até 768x768x64 IIRC). No entanto, o problema pode ser simplificado e acelerado das seguintes maneiras:

  • Rede de nós pré-cozidos: Quando o mapa é criado, o mundo pode ser dividido em partes, e cada parte pode ter suas saídas e entradas mapeadas. Quando um pedaço é atualizado, como quando um muro é construído, apenas a rede desse pedaço precisa ser atualizada.
  • Localização de caminho em etapas: a execução de um caminho em todo o mapa, célula por célula, levaria muito tempo; em vez disso, você encontraria a rede de chunk maior, que mapeia toda a conexão entre os chunks e, em seguida, executa apenas um caminho intra-chunk quando movendo-se de pedaço para pedaço. Isso faz duas coisas para você. Ele acelera a localização do caminho, dividindo-o em várias partes menores, e também permite que a unidade mude a direção parcialmente ao longo do caminho quando um pedaço é atualizado. Seria redirecionado pela rede grande se qualquer um dos nós necessários para a atualização cruzada.
  • Direção aleatória: quando não se move para uma meta, a unidade precisa apenas andar sem rumo. Muitos roguelikes apenas movem a unidade em uma direção aleatória, o que não é natural. Várias técnicas de direção podem ser usadas, as simples são favoráveis ​​ao movimento em linha reta e têm menos e menos chance de se mover nas direções que irradiam para trás, o que teria apenas cerca de 1% de chance. Portanto, a unidade algumas vezes revertia completamente a direção, mas apenas raramente.

Não abordarei o básico da busca de caminhos. A maioria dos roguelikes usa A *, mas existem outros métodos para esfolar o gato. Mmmm couro de gato ..

Tarefas pessoais

Uma das principais coisas que faz as unidades do DF aparecerem e se sentirem vivos é a sua lista de objetivos pessoais. Na verdade, muitos jogos roguelike têm isso em um nível básico. Essencialmente, cada unidade tem uma lista de desejos (e para os seus filhos, tarefas que eles podem escolher que você está pedindo que sejam feitas) e eles escolherão com base na personalidade deles (estatísticas).

Algumas tarefas têm requisitos. Para fazer uma saia de couro, o dorf deve estar em uma loja com itens X. Então, todos esses são verificados e adicionados como tarefas à sua lista. Simples assim.

Como na maioria das vezes uma unidade estará em trânsito, as verificações do que as unidades estão fazendo podem ser muito rápidas, apenas algumas unidades farão uma escolha a qualquer momento e, portanto, no geral, não há desaceleração nem para centenas ou milhares de unidades. E lembre-se, no DF, de abelhas a trogloditas e árvores, são unidades.


Ao fazer algumas pesquisas adicionais, fica claro que, hilariamente, o DF está fazendo um trabalho terrível de busca de caminhos em geral. Não está dividindo o mapa em partes, está dividindo o mapa em segmentos ou áreas conectadas (o que é melhor do que nada, com certeza); portanto, minha avaliação acima é ainda menos um exemplo de como o DF funciona do que eu pensava. :) O que não quer dizer que o DF seja nada menos que incrível por um milhão de outras razões.

Isso mostra que o que é importante em um jogo é o jogo. Nem gráficos, nem boa programação, nem boa escrita, nem boa música, nem mesmo a interface; nada mais é 1% tão importante quanto o próprio jogo.

DampeS8N
fonte
1
1024X1024X32? Vertical é 128 ou 256 eu acredito. Sua muito maior do que 32.
Lawton
@ Lawton Eu acredito que estou incorreto sobre o tamanho máximo, mas a altura não é tão incorreta. Eu estou corrigindo isso. Carreguei o jogo e o embarque em que estou tinha apenas 45 níveis de altura. Mais pode ser "simulado", mas não tenho acesso a eles para escavação ou construção.
24912 DampeS8N
@ DampeS8N Acabei de carregar um mapa médio e não modificado e consegui visualizar de +16 a -156, em torno de 180 níveis. Os mapas de 40 níveis são a exceção, não a regra. Mesmo que você possa cavar apenas 40 deles por ter sido bloqueado por um aqüífero ou lava, isso não é relevante, porque a área abaixo ainda é preenchida com diversão simulada.
Lawton
@ Lawton, meu mapa só me permite percorrer 45 níveis. Eles são absolutamente variáveis, mas eu não consegui facilmente encontrar números sobre quantos mapas cada um tem acesso. Também pode depender da versão do jogo que estamos usando. No final, não é tão importante para a minha resposta.
DampeS8N
É um posto antigo, mas as profundezas da fortaleza anã dependem de camadas sedimentares. Como a crosta terrestre é mais espessa em alguns lugares. DF não é completamente correto geologicamente, mas o homem estuda como profissional: D.
Madmenyo
50

A partir desta página :

Bem [o caminho] parece incrível do meu lado, já que há uma tonelada métrica de personagens todos fazendo isso de uma só vez.

TA: Os anões se movem principalmente com A *, com a heurística antiga e regular de rua. A parte complicada é que ele realmente não pode chamar A * se eles não sabem que podem chegar lá com antecedência ou isso acabará inundando o mapa e matando o processador.

Não sei se é definitivamente assim que ele evita "inundar o mapa" , mas a maneira usual de fazer isso nos jogos é usar uma alteração no A * chamada Hierarchical Path-Finding A * , ou HPA *. A idéia é dividir a grade em muitos pedaços menores, porém maiores, e use A * para encontrar o melhor caminho de cada pedaço para os pedaços vizinhos. Você pode usar isso para criar um gráfico muito menor sobre o qual executar A * para cada unidade.

Localização de caminho hierárquico

Você também pode agrupar esses pedaços em pedaços ainda maiores, e é daí que vem o "hierárquico".

Esse algoritmo encontra apenas caminhos quase ótimos, mas para jogos como o Dwarf-Fortress isso geralmente é bom. Ainda é garantido encontrar um caminho, se houver; e quando não houver caminho, ele preencherá apenas o gráfico menor, economizando uma quantidade enorme de tempo.

Há também uma abstração do HPA * que lida com unidades que podem percorrer alguns terrenos, mas não outros (como falésias, pelas quais as unidades aéreas podem atravessar, mas as unidades terrestres não podem) . Chama-se HAA * , e há um artigo muito acessível explicando aqui .

Você pode ler mais sobre vários algoritmos de busca de caminhos aqui .

BlueRaja - Danny Pflughoeft
fonte
3
Achei este vídeo do desenvolvedor do RimWorld muito esclarecedor. É um jogo semelhante, enquanto apenas em 2D. Ele explica o básico por trás da busca de caminhos e os benefícios de separar o mapa em regiões. youtube.com/watch?v=RMBQn_sg7DA
Pai
18

Se qualquer coisa, é o oposto - a coisa toda roda em um thread e agora está chegando ao ponto em que isso está se tornando o fator de bloqueio (da última vez que verifiquei!)

A razão pela qual é rápido é que não há gráficos sofisticados. É enganoso, mas a principal coisa que atrasa as coisas é desenhar coisas (pense em mais de dois terços de um quadro nos títulos AAA). Como a fortaleza dos anões é bastante básica, ela dedica o resto do tempo a fazer coisas interessantes.

Matt Kemp
fonte
8
Um dado a favor disso é a reescrita do OpenGL de um tempo atrás que, lembro-me, trouxe um aumento maciço na taxa de quadros. Assim, mesmo fazendo os gráficos simples de sprite que o DF causou um impacto eficiente.
Millimoose
3
+1 Faixa de gráficos = enorme quantidade de tempo livre para computação gameplay
Laurent Couvidou
2
Vale a pena notar que os gráficos do DF são tão exigentes quanto qualquer jogo 2D indie moderno. Existem muitas texturas, mesmo que pequenas e simples, e podem ser espalhadas por monitores full HD de imóveis. Não existem efeitos de partículas chamativos ou o que você tem, mas o trabalho bruto "pintar todos esses pixels" ainda está presente e, devido ao número de chamadas de desenho necessárias para os pequenos tamanhos de ladrilhos, é realmente um grande desafio para o desempenho.
DampeS8N
Pode parecer uma resposta tola no começo, mas isso está correto, imagine o que pode ser feito com 4-12GB de grama e 4-12tflops de GPU se você não precisar desenhar primitivas complexas, desembrulhar, texturas, transformar vetores 3D em uma matriz de pixels, 2d sombreamentos, etc
Felype
10

Não sei como o DF é codificado, mas a quantidade de AIs realmente não me impressiona, porque o que as pessoas geralmente supervisionam é que a IA não precisa de precisão . É perfeitamente viável fazer a maioria das coisas apenas a cada poucos segundos. Também é viável usar cálculos imprecisos. A imperfeição economiza muito desempenho . Você pode executar a rotina de tomada de decisões de 100 unidades a cada 100 ms ou executar por 1000 unidades a cada segundo; levará a mesma quantidade de tempo da CPU, mas bem ... você tem 10 vezes as unidades.

Aqui está um exemplo simples de como lidar com muitas unidades:

int curUnit;
Array<Unit> units;
[...]
while([...]) // Game Loop
{
  [...game logic...]
  // process 10 AIs per Frame
  for(int i=0; i++; i<10)
  {
    curUnit++
    if(curUnit == units.length()) curUnit=0;
    if(curUnit < units.length())
      units[curUnit].processAI();
  }

  // Update the position of all units, this should be as optimized as possible
  foreach(Unit& unit in units){ unit.move(); };

  [...graphics...]
}

A IA se tornará cada vez menos responsiva quanto mais houver, mas o jogador provavelmente só perceberá isso em casos extremos.

API-Beast
fonte
Há muito a ser dito para percorrer pilhas de tarefas que não são precisas no nível de quadros. Os jogos AAA geralmente cronometram explicitamente cada departamento individual em porcentagens de quadros, para que um departamento não possa pisar no pé de outros departamentos. Se o método para animar o balanço das árvores com base na velocidade e direção do vento for lento, menos árvores serão processadas em vez de consumir o orçamento de outras equipes.
DampeS8N