Saturday, April 23, 2011

Escalabilidade de sistemas multiagentes em jogos digitais: herdando técnicas e componentes da computação gráfica 2

[18] atenta para o fato de que a paralelização funcional é complicada e a adaptação de algoritmos em si para novas arquiteturas de hardware é impraticável ou simplesmente não vale o esforço. Dessa maneira, a melhor solução é a paralelização dos agentes, fazendo com que uma mesma classe de algoritmo seja executada em paralelo com cada processo sendo responsável por uma das entidades da simulação. Pois, a GPU é bem adaptada para a classe de problemas conhecidas como computação paralela de dados, onde o mesmo programa, shader no caso da GPU, é executado em diversos elementos de dados diferentes ao mesmo tempo [20].
Seguindo essa linha, [20], propõe métodos para a implementação de algoritmos de path-finding na GPU. E todos os agentes podem ser simulados ao mesmo tempo. Algoritmos de path-finding na GPU possibilitam a simulação de diversos agentes ao mesmo tempo em paralelo. As técnicas de path-finding dinâmicos envolvem a simulação do comportamento dos personagens e análise do terreno para identificar caminhos válidos bons e ruins. E essas operações podem ser bem caras de serem feitas na CPU mesmo com múltiplos núcleos (multi-core).
[22] discute o problema da latência na operação de transferência de dados entre CPU e GPU. Apontando para a necessidade de implementação das técnicas de manipulação dos dados na GPU. Ou seja, quando jogabilidade e física são simuladas na CPU, existe um gargalo adicional que é a via PCI-E, para transferência da posição e estados do personagem entre CPU e GPU.
A implementação de geometry shaders em placas gráficas que suportam a especificação do DirectX 10 [23],  é explorada por [22] na implementação de uma simulação de multidão totalmente na GPU. São propostos algoritmos gráficos de remoção de superfícies escondidas, animação e até de nível de detalhe (LOD). No entanto a técnica de LOD implementada é bastante simples e não eficiente para a escolha de técnicas de inteligência artificial, somente operações gráficas.
[25] apresenta diversas possibilidades para nível de detalhe para inteligência artificial, mas, como de costume, utilizando sempre a CPU como arquitetura de execução. [25] reforça todas as complicações na simulação de um grande número de agentes em computadores tradicionais. E atenta para dois problemas principais resolvidos com algoritmos de LOD para a CPU:

  •          Facilidade de extensão do comportamento dos agentes, evitando a utilização de aprendizagem de máquina.
  •          A velocidade da simulação deve ser boa o suficiente mesmo em computadores com recursos limitados.


Para resolver os problemas um framework foi criado, o IVE. No entanto, o IVE foca na construção de técnicas de LOD voltadas para a execução em CPU. Como já mostrado anteriormente para hardware de futuras gerações esse não é um comportamento desejado. Para o nosso projeto será necessário que essas técnicas sejam adaptadas para a execução em arquiteturas multi-processadas.
[25] ainda afirma que não existe um trabalho, com artigos publicados, que combina todas as preocupações do IVE: affordance[13], practical reasoning[21], e LOD AI. Para este trabalho buscaremos resultados compatíveis com o IVE, mas, novamente, voltadas para arquiteturas de hardware multi-processadas especialmente a GPU. É preciso deixar claro que não estamos procurando implementar o IVE em GPU e sim criar uma alternativa viável em GPU para simulação de mundos virtuais.
Os criadores do IVE afirmam ainda que para ter uma simulação extensível seja necessário utilizar o método de affordances, pois utilizar algoritmos de aprendizagem de máquina seria como “utilizar um martelo para abrir uma noz”. No entanto, acreditamos que a complexidade a ser utilizada em jogos no futuro próximo é suficiente para utilizarmos aprendizagem de máquina[12]. Inclusive, a academia tem vários artigos nas áreas de balanceamento automático de jogos[11], modelagem da satisfação do usuário [10] entre outras áreas relacionadas a criação de inteligência artificial para jogos com resultados bastante promissores. Cabe então, também, adaptarmos os algoritmos de aprendizagem para utilizar melhor os novos hardware que estarão disponíveis com arquiteturas multi-processadas.
Por fim, o artigo ainda foca bastante na questão da mudança de foco no LOD de um paradigma “see – not see”, para um novo paradigma baseado em um LOD com três níveis de detalhe. Apesar de ser uma mudança significativa, a maneira como o LOD é feito deve ser tratado de acordo com o que já é feito na área de computação gráfica, como é proposto por nós, que já possui vasta literatura no assunto. A questão mais importante fica em como adaptar os algoritmos de IA para possuir diversos níveis de detalhe e ser fácilmente utilizado pelos algoritmos de LOD mais competentes.
Sendo assim, apesar de termos os mesmos objetivos do IVE, as arquiteturas de execução são bastante distintas o que requer uma abordagem diferente de ataque ao problema. De acordo com a própria Intel [9][20], a mudança de paradigma das arquiteturas para CPUs multi-processadas e GPUs forçar a repensar os problemas de maneira a utilizá-las da melhor forma possível. O consenso geral é que os algoritmos devem ser repensados e não adaptados.