MAC 499 – Projeto de formatura supervisionado

MIP – Patto – Gannso

Instituto de Matemática Estatística da Universidade de São Paulo

Ricardo Skubs

Supervisão do Professor Marcus Dimas Gubitoso

Introdução

Durante todo o ano de 2000 desenvolveu-se no IME um projeto de construção de Jogos para Computador. Esse documento tenta relatar os objetivos desse projeto, as atividades realizadas e os novos projetos que o desenvolvimento desse trabalho gerou.

O grupo empenhado no desenvolvimento desse projeto é formado por:

Luiz Gustavo Marins (Gus)

Marcus Harada Pena (Meio)

Ricardo Bueno Cordeiro (Ricardo)

Ricardo Skubs (Skubs)

Roberto Augusto Giacomo da Motta (Guto)

Tiago Tagliari Martinez (Tiago)

Professor coordenador: Marcos Dimas Gubitoso (Gubi).

O desenvolvimento desse projeto buscou o exercício da programação de jogos de computadores e, principalmente, a criação de ferramentas que facilitassem esse trabalho e servissem de incentivo para que outras pessoas pudessem desenvolver seus próprios projetos baseados em nossas ferramentas.

O contato com jogos de computador se dá muito cedo em pessoas que se interessam por computadores. Quando alunos de ciência da computação entram na faculdade, imaginam poder participar do desenvolvimento de jogos do tipo que estão acostumados a jogar. Muitos deles já têm projetos em vista, mas não têm o conhecimento de programação necessário para pô-los em prática.

Infelizmente, ao se deparar com o mundo acadêmico, a realidade é um pouco diferente. Estudar vários anos de teoria pura sem qualquer aplicação faz com que os alunos percam boa parte da motivação original.

Temos, portanto, um grande dilema. Se ao entusiasta falta o conhecimento para desenvolver software de qualidade, ao programador mais experiente falta boa parte da iniciativa original.

Desenvolvendo uma ferramenta que possibilitasse aos ingressantes um bom contato inicial com a produção de jogos, estaríamos permitindo a eles a realização de suas ambições. Poderiam guiar seus estudos no IME buscando aprimorar o uso dessas ferramentas e até melhorar o software por nós produzido.

Criando essa base de software, e otimizando-a ao máximo, também facilitaríamos nosso próprio trabalho de criação de jogos. Esse reaproveitamento de código diminuiria sensivelmente o tempo de desenvolvimento de novos jogos.

A idéia começou a ganhar forma ao definirmos parte da estrutura do projeto. A organização das ferramentas em uma biblioteca gráfica, utilizada por sua vez na criação de um engine pareceu ser o formato correto.

Ganhando grande liberdade de atualização e permitindo o desenvolvimento distribuído, a organização em classes de cada um desses programas foi o passo definitivo rumo à orientação a objetos.

Alguns questionamentos quanto a performance se fizeram necessários, mas concluímos que não haveria grande perda de performance. Os ganhos de organização do código provindos da modularização certamente compensariam as poucas perdas.

Assim, programamos em C++. Essa linguagem traz a modularização inerente à orientação a objetos sem trazer grande perda de performance. Sempre pode-se escrever código inline em assembly ou mesmo trechos de programação em C, nos pontos críticos de performance.

Enfim, optamos por desenvolver ferramentas que facilitem a vida do programador de jogos, na esperança de que isso aumente o interesse das pessoas pela área e lance no mercado produtos de qualidade técnica, mas principalmente criativa.

O Projeto

Nosso projeto foi desenvolvido em algumas fases distintas. Podemos dizer que tivemos três grandes fases, são elas:

Desenvolvimento do MIP

O MIP já era uma idéia existente antes da criação desse projeto, já existiam algumas poucas funções desenvolvidas e apenas uma versão para Windows. Retomamos o projeto com força total e iniciamos a criação de diversas funções auxiliares. Além disso iniciamos a migração do MIP para linux assim que as funções foram ficando prontas.

Quando o MIP já possuía funcionalidades suficientes para ser usado na criação de um jogo completo resolvemos que era hora de testar suas funcionalidades e sua portabilidade.

Teste do MIP e Desenvolvimento do Patto

Para testar o MIP resolvemos retomar outro projeto parado, o Patto. O Patto nasceu no inicio de 2000 com uma versão para Windows desenvolvida pelo Tiago. Resolvemos tornar o Patto portável e usa-lo para testar toda a capacidade do MIP. Os trabalhos se iniciaram em meados de maio e terminaram no início de agosto. Foram encontrados diversos problemas no MIP, e algumas funções tiveram de ser retomadas e reprogramadas, outra precisaram ser otimizadas para funcionar com performance aceitável.

Após esses testes executamos o teste de portabilidade e descobrimos que realmente nosso principal objetivo tinha sido alcançado. O jogo foi portado em uma tarde.

Desenvolvimento da Engine (Gannso)

Nosso próximo passo foi desenvolver a engine de jogos. Definimos nossos objetivos e começamos a bolar um jogo que deveria servir de base para testar nossa engine. Esse trabalho começou em maio e só terminou às vésperas da entrega quando a primeira versão portável da engine ficou pronta e testada.

MIP - (MIP Is Portable)

Talvez uma das questões mais importantes na hora de efetivamente colocar a mão na massa e começar a codificar um jogo seja em qual plataforma ele irá rodar. Nesse momento vários parâmetros devem ser levados em consideração na escolha de determinado sistema operacional para o desenvolvimento. Entre eles podemos destacar a estabilidade do sistema, a disponibilidade de ferramentas de desenvolvimento, facilidade de acesso à documentação do sistema, facilidade de acesso aos recursos de hardware.

Existem diversos outros fatores que também devem ser levados em consideração, como facilidade de distribuição e aceitação do sistema operacional no mercado, já que seria bastante interessante que o maior número possível de pessoas entrassem em contato com o jogo e apreciasse nosso trabalho.

A discussão desses aspectos nos levou à idéia de desenvolver uma biblioteca gráfica que permitisse a migração do código de um sistema para o outro com o mínimo de esforço. Dessa forma poderíamos desenvolver os jogos num sistema e migrá-lo para outro conforme as necessidades.

Nesse contexto nasceu o MIP, cujos principais objetivos são:

Portabilidade

A idéia inicial é permitir a portabilidade de código pelo menos entre Windows/DirectX e Linux/X.

Performance

As tarefas usuais da biblioteca gráfica devem funcionar da melhor maneira possível.

Extensibilidade

Porque não permitir que cada vez mais recursos sejam desenvolvidos? As estruturas de dados foram projetadas para facilitar o trabalho de desenvolvimento futuro.

Leveza

A pretensão do MIP não é ser um novo DirectX, mas realizar as tarefas utilizando os recursos já existentes de hardware e software.

Funcionamento:

O MIP funciona como uma camada localizada entre o sistema operacional e o código do jogo. A idéia é fornecer uma série de funções importantes para o desenvolvimento de um jogo utilizando uma interface padrão, assim podemos programar boa parte do software utilizando as funções do MIP, que se encarrega de utilizar outras ferramentas disponíveis naquele sistema operacional e os recursos de hardware. Quando da necessidade de migração do jogo, tudo que se precisa fazer é trocar o MIP para aquele correspondente ao novo sistema operacional e trocar o restante do código incompatível, que dependendo do cuidado dos programadores durante o desenvolvimento pode ser quase inexistente.

Para citar um exemplo simples de como isso pode funcionar vamos imaginar que precisamos inserir uma imagem estática na tela, se estivermos trabalhando sobre o Microsoft Windows poderíamos utilizar as bibliotecas do DirectX para realizar essa tarefa. Isso seria bem fácil de fazer, basta conhecer a interface oferecida pelo DirectX e fazer a chamada da função. Agora vamos imaginar que precisamos portar o jogo para o Linux, nesse caso precisamos vasculhar um nosso código todas as chamadas para essa função e trocá-la por alguma outra função semelhante do Linux.

Podemos facilmente perceber o quão improdutivo isso é, pois além de possuir conhecimentos a respeito das duas plataformas e das bibliotecas gráficas pertencentes ao sistema teremos que adaptar nosso código de uma maneira muito radical, o que pode significar mais trabalho do que se tivéssemos que reescrever o jogo do início nesse novo sistema.

Ao invés disso podemos utilizar o MIP, que já possui versões para Linux e Windows e portanto cuida dessas diferenças entre os sistemas. A chamada da função que insere uma imagem na tela é a mesma tanto numa versão como em outra e não vamos precisar nos preocupar com esse aspecto na hora de migrar.

A utilização de uma biblioteca como o MIP nesse caso é fundamental para tornar o processo de migração viável, mais rápido e barato. Seria então interessante agregar no MIP diversas funções de uso comum na programação de jogos, como funções gráficas e sonoras. Foram justamente essas duas ferramentas que foram primeiramente implementadas no projeto.

ENGINE DE JOGO

Além de desenvolver essa biblioteca portável, nosso objetivo ia além, desenvolver uma engine de jogo, uma engine nada mais é que o programa responsável por realizar todas as tarefas de um jogo específico.

Nossos objetivos incluíam a programação de uma engine para jogos estilo covert action, ela seria responsável por realizar a maioria das funções de um jogo nesse estilo, como cuidar da movimentação do personagem do jogador (PC) e da movimentação dos outros personagens (NPC), além da interação desses personagens com objetos existentes. Também precisa cuidar da interface com o jogador, captando os comandos inseridos através do teclado e do mouse. A inteligência artificial dos personagens e a tomada de ação dos mesmos também devem estar estruturadas, permitindo aos programadores do jogo incluir de maneira fácil os algoritmos e regras para tomada de decisão.

O trabalho foi dividido em algumas áreas chave como Gráficos, Som, Inteligência Artificial, Interface com o Usuário e Controle Interno. Entrei na equipe responsável pela inteligência artificial da engine junto com o Gus.

Dividimos então nosso serviço em tarefas, que foram realizadas na seqüência:

Definição de interfaces

Definição:

Começamos nosso trabalho definindo algumas interfaces para nossas funções e levantando que tipos de informações iríamos precisar das outras áreas do jogo. Especificamos também como os programadores iriam nos acessar.

Dificuldades encontradas:

Nossa principal dificuldade nesse ponto do projeto foi levantar as informações que seriam necessárias para escrever os algoritmos de tomada de decisão e busca de caminhos. Para tanto fizemos um esboço de como seriam os NPCs e imaginamos como eles deveriam agir.

Acabamos por imaginar diversas tarefas que nossos personagens poderiam fazer, como escutar os passos dos outros personagens, encontrar estratégias para combater o PC de maneira mais eficiente, fugir e buscar reforços e coisas do tipo, que fariam que nossos personagens agissem de maneira mais próxima a realidade.

Conclusões:

Chegamos a conclusão que seria impossível desenvolver tantas funcionalidade de uma só vez e que esse tipo de funcionalidade poderia ser acrescentada ao código da engine ao longo do tempo. Nosso objetivo foi esquematizar o objeto de maneira a facilitar a inclusão de outras funções de tomada de decisão.

Encontrar caminhos:

Definição:

Todo jogo que se preze no estilo covert action deve possuir uma boa função para encontrar caminhos, isso evita que os NPCs fiquem perdidos no mapa ou que ainda travem em algum ponto ou então tentem encontrar o caminho e acabem entrando num ciclo infinito.

Dificuldades encontradas:

Pode-se imaginar que essa tarefa seja fácil, mas quando lembramos que devemos realizar uma busca numa matriz com quase dois milhões de posições possíveis de maneira eficiente e repetir esse processo para diversos personagens percebemos que essa tarefa não é nada fácil.

Conclusões:

Para resolver e esses problemas tomamos duas atitudes, primeiro reduzimos o tamanho da matriz de busca. O nosso objetivo foi diminuir drasticamente o número de comparações necessárias até que o personagem encontrasse o caminho. Para tanto utilizamos uma máscara que ficava escondida atrás da do mapa do jogo, essa máscara continha pontos que deveriam ser utilizados para que o personagem utilizasse na busca de caminhos. Essa máscara continha também informações úteis como a distância entre os pontos, dessa maneira evitávamos que o personagem procurasse percorrer distâncias maiores que utilizasse o mesmo número de pontos entre elas.

Tomada de decisões:

Definição:

Outro aspecto importante a ser levado em consideração é o algoritmo que possibilita ao personagem tomar algum tipo de decisão, como fugir quando está sendo atacado, se esconder ou ainda revidar ao ataque ou pedir reforços. Além disso definimos que teríamos no início dois tipos de personagem com características diferentes e elas deveriam ser levadas em consideração na hora de tomar determinada decisão.

Dificuldades encontradas:

O grande problema agora era definir que tipo de ação os personagens poderiam tomar e qual seria o efeito disso no jogo. Outro problema era que no momento propício os personagens devem também poder trocar estado e assim o jogo ganharia um pouco de dinamismo e os personagens pareceriam menos falsos.

Conclusões:

Para resolver o problema das ações possíveis definimos diversos estados de ação e obrigatoriamente os personagens deveriam estar em algum desses estados a todo o momento no jogo. Para cada estado de ação um conjunto de regras são definidas e o personagem age de acordo com aquelas regras.

Também identificamos algumas ocasiões especiais onde os personagens poderiam mudar de estado caso possuíssem determinadas características atribuídas em seus atributos.

Essas funções foram preparadas mas acabaram não entrando no código apresentado do Gannso pois não estavam completamente terminadas, já que a maior parte dos dados que precisávamos saber para executar tomadas de decisão não foram desenvolvidas a tempo. A estrutura de estados e foi definida e implementada mas esta ainda não realiza mudanças de comportamento nos personagens.

Definições de Atributos:

Definição:

Com o intuito de tornar nossos personagens únicos pensamos em criar algumas características individuais para os personagens, assim como classes de personagens que fossem diferentes entre si e pudessem agir de maneira distinta de acordo com as situações encontradas.

Dificuldades encontradas:

Primeiro foi preciso identificar que tipos de personagem iríamos criar e definir quais atributos seriam utilizados para representar um ser humano no jogo e como os valores desses atributos iriam interferir nas tomadas de decisão de todos os personagens.

Conclusões:

Para definir os atributos necessários criamos um sistema baseado em alguns RPGs famosos, onde valores numéricos são atribuídos a qualidades e definem de uma maneira geral o quanto o personagem foge da média da população. Para tanto definimos que os atributos poderiam ser força, destreza, inteligência e saúde, a média desses atributos para um cidadão normal seria 10, então um personagem com destreza 13 é alguém com coordenação fora do normal.

Passamos então a tentar definir como esses atributos deveriam influenciar nas decisões dos personagens e decidimos criar alguns atributos auxiliares como coragem, esses atributos seriam em testes para decidir se em determinada situação o personagem tomaria uma decisão ou outra.

O IME e os estudos realizados para a realização do projeto.

No que diz respeito a programação em si eu acredito ter aprendido bastante no IME, e isso com certeza ajudou muito no projeto. Aprendemos técnicas e algoritmos que nos possibilitam utilizar as linguagens da melhor maneira possível e no meu modo de entender, o mais importante, é conhecer que a computação a fundo e saber que sempre temos alternativas para resolver os problemas que nos são apresentados.

Fora isso treinamos durante todo o curso nossa capacidade de aprender coisas novas em pequeno espaço de tempo e de se adaptar as ferramentas que nos eram apresentadas para completar nossos projetos e Eps.

No que tange a inteligência artificial desde o início da graduação eu me interessava em aprender e conhecer os algoritmos e técnicas utilizadas em inteligência artificial. Essa área da computação é cercada de mistérios e lendas e eu fui descobrindo no decorrer do curso aspectos da IA que nunca havia imaginado antes. Infelizmente a maior parte daquilo que aprendi nesse campo foi conseguida com estudos particulares e longe do ambiente acadêmico. Acredito que isso foi um erro e que poderia ter aprendido muito mais se tivesse me envolvido em projetos acadêmicos, mas a sede por aprender cada vez mais coisas e por estar sempre conhecendo novas técnicas não me deixavam estudar matérias básicas para essa área como álgebra e estatística, assim como não me permitiram concentrar meus estudos num tema específico visando o aprofundamento do conhecimento.

Frustrações

Durante todo o projeto encontramos vários desafios e todos foram sendo vencidos graças ao esforço conjunto de todos e a nossa vontade de apresentar o resultado do nosso trabalho com a satisfação do dever cumprido.

Nesse sentido fico muito feliz por ter participado da elaboração do MIP, do Gannso e da programação do Patto, usado para testar o MIP. Mas também tenho que lamentar o verdadeiro fiasco da inteligência artificial apresentada nessa primeira versão do Gannso. Entre os vários problemas que enfrentamos, o maior de todos foi desenvolver nossa engine a tempo de poder ter à disposição as funções necessárias para implementar uma inteligência artificial um pouco complexa, com algoritmos de tomada de decisão já consagrados com nosso toque pessoal e nossas inovações. Também pretendíamos implementar funções de aprendizado, utilizando métodos conhecidos adaptados a realidade do nosso jogo.

Vontade não nos faltou, e nem idéias para tornar o jogo mais divertido e real mas infelizmente o tempo, ou a falta dele, foi nosso algoz, e não conseguimos implementar nem um décimo daquilo a que nos dispúnhamos no inicio do projeto.

Futuro

Não é intenção do grupo abandonar o projeto Gannso, mesmo porque ele ainda não está totalmente terminado. Vamos continuar a aperfeiçoar o MIP e já estão sendo projetadas um módulo com interfaces para uso de rede e um outro módulo com funções de input.

Também pretendemos transformar o Gannso num jogo de verdade, e para isso ainda temos que melhorar nosso enredo e trabalhar em cima principalmente da inteligência artificial, que de todas as áreas é aquela que ainda está menos desenvolvida.

Referências

Página pessoal sobre o projeto: http://www.linux.ime.usp.br/~rskubs/mac499/

Página oficial do projeto: http://www.linux.ime.usp.br/~tiagotm/mac499/

Página de John Funge: http://www.dgp.toronto.edu/~funge/

Gama Sutra: http://www.gamedeveloper.com/

GameDev.net: http://www.gamedev.net/

Game AI: http://www.gameai.com/games.html

Esses sites ajudaram bastante na hora de por a mão na massa na programação do jogo. Foram também de fundamental importância uma séria de papers que foram lidos durante o curso, sobre diversos assuntos, desde história da inteligência artificial passando por redes neurais e alguns métodos de “aprendizado”.

Além disso posso destacar a importância de alguns livros sobre a linguagem C++, que foi a linguagem base da nossa implementação.