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?
ai
path-finding
multithreading
npc
RSH1
fonte
fonte
Respostas:
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.
fonte
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:
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.
fonte
A partir desta página :
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.
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 .
fonte
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.
fonte
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:
A IA se tornará cada vez menos responsiva quanto mais houver, mas o jogador provavelmente só perceberá isso em casos extremos.
fonte