IME - USP

Trabalho de conclusão de cursoAluno:

RAFAEL PARENTE

Orientador:

FLÁVIO SOARES

CORRÊA DA SILVA

Disciplina:

MAC0499 - TRABALHO DE

FORMATURA SUPERVISIONADO

São Paulo11 de fevereiro de 2013

Sumário

1 Introdução 31.1 Elementos do jogo . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Computador e sistema operacional . . . . . . . . . . . . . . . . . 4

2 Conceitos e tecnologias usadas 52.1 C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Ogre3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 CEGUI e OIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.4 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.4.1 Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . 82.5 Bounding box . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.6 Billboarding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.7 Câmera virtual . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.8 Singleton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3 Atividades realizadas 123.1 Definição da parte gráfica . . . . . . . . . . . . . . . . . . . . . . 123.2 As classes principais . . . . . . . . . . . . . . . . . . . . . . . . 133.3 Criação do mundo . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.3.1 Janelas do mundo . . . . . . . . . . . . . . . . . . . . . . 233.3.2 Grupos . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.3.3 Jogada dos inimigos . . . . . . . . . . . . . . . . . . . . 30

3.4 Criação do gerenciador da nação . . . . . . . . . . . . . . . . . . 313.5 Criação da batalha . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.5.1 Antes da batalha . . . . . . . . . . . . . . . . . . . . . . 353.5.2 A batalha . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4 Resultados 40

5 Conclusões 44

6 Desafios e frustrações 44

1

7 Disciplinas importantes para o trabalho 45

8 Melhoramento do projeto 46

9 Futuro 48

Referências 48

2

1 Introdução

Este trabalho de formatura é sobre a criação de um jogo de estratégia e RPG,baseado no jogo Dragon Force1, em que o jogador joga contra o computador.O jogador deverá escolher uma nação, que possui um território, e o objetivo dojogador será conquistar todos os demais territórios.

O jogo pode ser dividido em três partes principais:

• O mundo: onde o jogador decide algumas ações com relação a seus exérci-tos, como para onde enviar os generais, repor tropas em castelos, etc;

• Os assuntos internos (ou o gerenciador da nação): onde o jogador poderámelhorar as condições de cada general ou castelo, além de conseguir salvaro jogo para voltar a jogar em outro momento;

• A batalha: Onde ocorre o combate entre os generais de duas nações distin-tas, sendo que cada general possui uma tropa;

1.1 Elementos do jogo

Foram criados alguns elementos para modelar os objetos do jogo. Eles são:

• General: São como personagens controlados pelo jogador em jogos de RPGpara videogames, usando rótulos comuns nesses jogos para definir a vida(HP), pontos para usar em técnicas especiais (MP), ataque, inteligência,etc. Para este tipo de jogo foi também criado a condição de "comando",que serve para indicar a habilidade do general em comandar suas tropas,refletindo na probabilidade de acerto das tropas no combate;

• Castelo: Um local onde os generais se recuperam e podem recuperar suastropas. Dominar um castelo oferece vantagem em um combate, tambémmelhorando a probabilidade de acerto das tropas;

• Vilarejos e cavernas: São pontos no mapa assim como os castelos;

1[4]

3

• Grupos: Um grupo é uma coleção de, no máximo, 5 generais e 5 pri-sioneiros. Os grupos são a forma dos generais vagarem pelo mundo e atacarcastelos ou outros grupos;

• Prisioneiros: Generais capturados pelo inimigo;

• Tropas: As tropas que o general pode comandar. Existem 6 tipos de tropas,e cada tropa tem vantagens em relação a alguma outra tropa;

• Semana: Uma semana começa nos assuntos internos e termina quando voltapara os assuntos internos. O jogo sempre começa nos assuntos internos, vaipara o mundo, onde ocorrem batalhas e conquistas de território, e volta paraos assuntos internos;

1.2 Computador e sistema operacional

O sistema operacional usado foi o Ubuntu 11.04 - the Natty Narwhal2.Alguns dados do computador usado:

• Usando o comando cat /proc/cpuinfo obtemos os seguintes dados sobre oprocessador:

– model name: Intel(R) Pentium(R) Dual CPU E2220 @ 2.40GHz

– cpu MHz : 2403.000

– cache size : 1024 KB

• A placa de vídeo:

– Intel Corporation 82G33/G31 Express Integrated Graphics Controller;

Esta informação é importante como um pré-requisito para o jogo ser com-pilado, como também a justificativa para o desempenho do jogo.

2Ubuntu é um sistema operacional de código aberto baseado na distribuição Debian[18]

4

2 Conceitos e tecnologias usadas

2.1 C++

C++ é uma linguagem de programação multi-paradigma3 e de uso geral. A lin-guagem é considerada de médio nível, pois combina características de linguagensde alto e baixo níveis.4

É possível usar herança múltipla, que pode gerar aumento na complexidade eambiguidade em algumas situações.

C++ foi a linguagem usada para a criação do jogo.

2.2 Ogre3D

Ogre 5 é um motor gráfico 63D escrito em C++. Foi projetado para ser mais in-tuitivo para desenvolvedores produzirem aplicações utilizando gráficos 3D, comaceleração por hardware, abstraindo os detalhes de usar bibliotecas como Di-rect3D e OpenGL. É completamente multiplataforma.

Sendo somente um motor gráfico, Ogre valoriza a modularidade. É especia-lizado apenas na parte gráfica e, por isso, são necessárias outras bibliotecas paratratar de outras questões como a entrada, som e física, o que normalmente ummotor de jogo já oferece.

É possível usar scripts para definir alguns recursos, como texturas, o quediminui o código em C++ e torna mais fácil criar modificações, afinal não é pre-ciso recompilar o programa.

Ogre usa um grafo para o gerenciamento das cenas. Assim, é necessário criarum nó para exibir um objeto da cena. Além de objetos, é possível adicionar ou-tros recursos, como a câmera, o que torna mais simples a sua manipulação. Por

3Um paradigma de programação fornece e determina a visão que o programador possui so-bre a estruturação e execução do programa. Por exemplo, em programação orientada a objetos,programadores podem abstrair um programa como uma coleção de objetos que interagem entre si,enquanto em programação funcional os programadores abstraem o programa como uma sequênciade funções executadas de modo empilhado.[9]

4[8]5Ogre significa Object-Oriented Graphics Rendering Engine.[1]6Graphic engine ou rendering engine[2], um tipo de motor de jogo[3] especializado em ren-

derização de cenas 2D e/ou 3D.

5

exemplo, se um jogo tem a opção de usar a visão em primeira pessoa de um dadopersonagem, pode-se adicionar a câmera em algum olho do personagem, assimela mudaria de acordo com o seu movimento. O que se faz em um nó é propagadopara seus filhos, mas o que se faz nos filhos não afeta os pais.

Os nós podem ter nomes, que servem para recuperar um nó através do geren-ciador de cena, o que é útil quando não há um ponteiro para determinado nó.

Cada cena do jogo terá um gerenciador de cena, que é uma classe do Ogreque serve para criar os objetos da cena, incluindo a câmera. Quando uma cena étrocada, o gerenciador de cena, assim como todos os objetos que foram criadospor ele, continuam existindo, mas não são vistos por causa da troca de câmeraassociado a cada gerenciador de cena.

Para este trabalho foi usado Ogre 1.7, mas a versão mais atual é a 1.8, lançadaem 2 de setembro de 2012 (durante a realização deste trabalho).

Ogre3D é distribuído com licença MIT.7

2.3 CEGUI e OIS

CEGUI8 é uma biblioteca para criação de interfaces gráficas para o usuário escritaem C++. Foi criada para ser usada em jogos, mas é possível utilizá-la em outrastarefas. Pode ser personalizado através de imagens, XML9 e ferramentas de ediçãode código.

Para usar imagens, por exemplo, pode-se criar um arquivo em XML com ex-tensão ".imageset"que define um nome, que será usado para identificar a imagem,e a posição da imagem no arquivo de imagem. Assim, é possível construir váriasimagens para se usar no programa a partir de um único arquivo de imagem.

CEGUI é distribuído com licença MIT.7OIS 10 é uma biblioteca multiplataforma11 que constrói a interação entre o

7A licença MIT é uma licença de software livre permissiva, o que significa que possui ex-igências mínimas com relação à como o software é redistribuído. Pode-se usar um software comlicença MIT em um software proprietário ou em um software livre.[7]

8Crazy Eddie’s GUI[5].9O XML é um formato para a criação de documentos com dados organizados de forma hi-

erárquica, como se vê, frequentemente, em documentos de texto formatados, imagens vetoriais oubancos de dados.[25]

10OIS significa Object Oriented Input System. Mais informações em [11].11OIS tem suporte para GNU/Linux e Windows, sendo que OS X e FreeBSD são apenas par-

6

homem e máquina através de dispositivos de entrada, como mouse, teclado e con-troles de jogos, como joysticks e o Wii Remote.

Tudo o que foi usado sobre OIS foi aprendido através dos tutoriais do Ogre.OIS é distribuído com licença zlib.12

2.4 Grafos

Em matemática e ciência da computação, grafo é o objeto básico de estudo dateoria dos grafos. Tipicamente, um grafo é representado como um conjunto depontos (vértices) ligados por retas (as arestas). Um grafo é um tipo especial dedigrafo, também conhecido como grafo não dirigido e grafo não orientado.

Um digrafo consiste em dois conjuntos: um conjunto de vértices (ou nós) e umconjunto de arcos. Cada arco é um par ordenado de vértices. O primeiro vérticedo par é a ponta inicial do arco e o segundo é a ponta final.13

A ponta final de todo arco é diferente de sua ponta inicial. Um arco com pontainicial v e ponta final w será denotado por v-w. A presença de um arco v-w éindependente da presença do arco w-v: o digrafo pode ter os arcos v-w e w-v,pode ter apenas um deles, ou pode não ter nenhum deles.

Dizemos que um vértice w é vizinho de um vértice v se v-w é um arco dodigrafo. Dizemos também, nessa circunstância, que w é adjacente a v.

Um caminho num digrafo é uma sequência de vértices com a seguinte pro-priedade: se v e w são vértices consecutivos na sequência então v-w é um arco.Em geral, os vértices de um caminho não são todos distintos.

A origem de um caminho é o primeiro vértice do caminho. O término é oúltimo vértice. Diz-se que um caminho com origem s e término t vai de s a t.

Dizemos que um arco v-w pertence a um caminho se o vértice w é o sucessorde v no caminho. Todos os arcos de um caminho apontam no mesmo sentido, deum vértice para o seu sucessor.

O comprimento de um caminho é o número de termos da sequência menos

cialmente suportados.12A licença zlib é uma licença de software livre permissiva.[17]13A palavra digrafo não consta dos dicionários, mas é cômoda e corresponde bem ao termo

digraph em inglês, que já está bastante arraigado. Alguns autores descuidados escrevem "dígrafo",com acento; isso não faz sentido algum e deve ser evitado a todo custo.[10]

7

um. Em outras palavras, o comprimento de um caminho é o número de arcos docaminho.

Em grafos, a existência de caminhos é uma propriedade simétrica: para quais-quer dois vértices s e t, existe caminho de s a t se e somente se existe caminho det a s.

Uma arborescência é um digrafo em que:

• Não existem vértices com grau de entrada14 maior que 1;

• Existe exatamente um vértice com grau de entrada 0;

• Cada um dos vértices é término de um caminho com origem no único vérticeque tem grau de entrada nulo.

Os grafos são muito úteis na representação de problemas da vida real, emvários campos profissionais. Por exemplo, pode-se representar um mapa de estradasatravés dos grafos e usar algoritmos específicos para determinar o caminho maiscurto entre dois pontos, ou o caminho mais econômico. Assim, os grafos podempossuir também pesos (ou custo), quer nas arestas quer nos vértices, e o custo totalem estudo será calculado a partir destes pesos.

2.4.1 Algoritmo de Dijkstra

Seja o problema do caminho mínimo:

• Problema do Caminho Mínimo com Origem e Término Fixos: Dados vér-tices s e t de um digrafo com custos não negativos nos arcos, encontrar umcaminho mínimo simples de s a t.

• Problema dos Caminhos Mínimos com Origem Fixa: Dado um vértice s deum digrafo com custos não negativos nos arcos, encontrar, para cada vérticet que pode ser alcançado a partir de s, um caminho mínimo simples de s a t.

14O grau de saída de um vértice v num digrafo é o número de arcos que têm ponta inicial v. Ograu de entrada de um vértice w num digrafo é o número de arcos que têm ponta final w.[13]

8

O algoritmo de Dijkstra resolve eficientemente o problema do caminho mín-imo se os custos dos arcos não forem negativos.

No início de cada iteração, temos uma arborescência T com raiz s. Para qual-quer vértice w fora de T, o custo de w em relação a T é, por definição, a distânciade s a w no digrafo T+F, sendo F a franja de T. Aqui, a franja de T é o conjuntode todos os arcos que saem de T. Em outras palavras, o custo de um vértice w queestá fora de T é o custo de um caminho mínimo dentre os que começam em s,terminam em w, e só têm um arco — o último — fora de T. Diremos que o últimoarco de um tal caminho mínimo é o arco-pai de w.

Cada iteração do algoritmo de Dijkstra consiste no seguinte:

se a franja de T não é vazia

então

seja w um vértice fora de T que tem custo mínimo

seja e o arco-pai de w

comece nova iteração com T+e no papel de T

senão

pare

2.5 Bounding box

Em softwares de ilustração e paginação, bounding box15 é uma caixa retangularque surge sobre um objeto selecionado; é formada por quatro ou oito pontos decontrole que são manipulados para distorcer, mover, girar etc. Alguns problemasem arquivos fechados (rotação e corte irregular) podem ser resolvidos alterando-seos valores numéricos associados a esses pontos de controle.

2.6 Billboarding

Billboarding16 é uma técnica que ajusta a orientação do objeto para encarar umalvo, o qual pode ser a câmera. É uma técnica muito popular em jogos e aplicaçõesque precisam de um grande número de polígonos.

15Bounding box significa caixa de contorno.[23]16Billboard também é conhecido como sprite.

9

Billboarding pode ser usado para diminuir o número de polígonos necessáriospara modelar uma cena, trocando geometria por uma textura. Um exemplo clás-sico é uma árvore. Considere quantos polígonos seriam necessários para uma rep-resentação decente de uma árvore. Billboarding permite-nos trocar a geometriacom uma única textura aplicada em um quadrilátero (ou dois triângulos). Assim,é possível criar uma árvore ilusória, apesar de ser possível perceber o que foiusado navegando ao redor da árvore.

No Ogre3D[1] existem estruturas para criação e manipulação de billboard.

2.7 Câmera virtual

A câmera virtual possui os seguintes parâmetros:

• Definimos seis parâmetros extrínsecos:

– C = (Cx, Cy, Cz) - centro de projeção (posição);

– u, v, n - referencial (orientação);

A posição da câmera virtual é dada pelo centro de projeção C quecorresponde ao centro ótico. Para especificar a orientação precisamosdefinir um referencial. Inicialmente definimos o eixo ótico (direçãolongitudinal) da câmera especificando um vetor N chamado vetor do

eixo ótico. Esse vetor juntamente com o centro de projeção C definemum raio r chamado de eixo ótico da câmera.

O plano de projeção Π da câmera virtual é o plano perpendicular aoeixo ótico, situado a uma distancia d do centro de projeção. Portantoo vetor normal do plano de projeção é o vetor do eixo ótico N. Adistância d é chamada de distância focal.

Escolhemos agora um vetor V, não colinear com o vetor do eixo óticoN. Esse vetor é chamado de vetor de inclinação. Os vetores N e Vdeterminam o plano vertical-longitudinal da câmera. (Em termos in-tuitivos, a rotação desse plano em torno do eixo ótico determina ainclinação da câmera em relação ao espaço da cena.)

Usamos agora o vetor do eixo ótico N e o vetor de inclinação V paraconstruir o referencial da câmera virtual. Para isso, normalizamos o

10

vetor do eixo ótico N, obtendo o vetor n = N/||N||. Em seguida obtemosa partir do vetor de inclinação V um vetor unitário v, normal ao vetorn, utilizando o processo usual de orto normalização de vetores (Gram-Schmidt): projetamos V sobre n, subtraímos essa projeção do vetor Ve em seguida normalizamos o vetor obtido. Ou seja:

v = V−<V,n>n|V−<V,n>n|

O vetor v é chamado de vetor vertical do referencial. O último vetoru do referencial da câmera é obtido tomando o produto vetorial17 dovetor do eixo ótico com o vetor vertical:

u = n ⊗ v.

O referencial C, u,v,n define as coordenadas no espaço da câmeravirtual.

• Definimos sete parâmetros intrínsecos:

– d - distância focal;

– Q = (umin, vmin), S = (umax, vmax) − Telavirtual;

– n - distância do plano anterior;

– f - distância do plano posterior;

2.8 Singleton

Singleton18 é um padrão de projeto de software19. Este padrão garante a existênciade apenas uma instância de uma classe, mantendo um ponto global de acesso a seuobjeto.

17Produto vetorial: a⊗ b =

∣∣∣∣∣∣i j k

a1 a2 a3b1 b2 b3

∣∣∣∣∣∣ = [a2 ∗ b3 − a3 ∗ b2, a3 ∗ b1 − a1 ∗ b3, a1 ∗ b2 −

a2 ∗ b1].[24]18O termo vem do significado em inglês quando se resta apenas uma carta nas mãos, num jogo

de baralho. [22]19Do inglês Design Pattern.

11

Muitos projetos necessitam que algumas classes tenham apenas uma instância.Por exemplo, em uma aplicação que precisa de uma infraestrutura de log de dados,pode-se implementar uma classe no padrão singleton. Desta forma existe apenasum objeto responsável pelo log em toda a aplicação que é acessível unicamenteatravés da classe singleton.

Em C++:20

class MyClass

{

private:

// atributo estático da "instância única".

static MyClass *instance = 0;

//construtor privado.

MyClass() {}

public:

// Função-membro que retorna sempre a

//mesma instância do objeto.

static MyClass& getInstance()

{

if (!instance) instance = new MyClass();

return *instance;

}

};

3 Atividades realizadas

3.1 Definição da parte gráfica

A parte gráfica poderia ser implementada através de Ogre3D, que é um motor grá-fico para C++, ou Panda3D, que é um motor de jogo para Python. Usando apenas

20Retirado da wikipedia.[22]

12

os exemplos que vieram junto com cada biblioteca foi possível notar a diferençade desempenho entre as duas. Ogre3D, mesmo usando melhores efeitos, comosombra e mais iluminação, com objetos mais complexos, conseguia manter a taxade quadros por segundo mais estável que o Panda3D. Além disso, os exemplos doOgre3D também produziam melhores imagens.

Os códigos fonte dos exemplos do Panda3D eram muito mais simples e maiscurtos em relação aos do Ogre3D.

Para a escolha pesou mais a utilidade a longo prazo e o desempenho. O jogocriado neste trabalho poderia ser criado em Panda3D com menos trabalho, masOgre3D parecia ser mais útil e claramente era mais rápido.

Outras bibliotecas existentes que poderiam ser utilizadas são Irrlicht e Unity.Unity não possui versão para GNU/Linux.21

3.2 As classes principais

Foi decidido isolar os recursos importantes em classes separadas, mas que se co-municavam. Como era necessário apenas uma instância de algumas classes, edeveria ser possível acessar essa instância de diferentes pontos do programa, foidecidido usar singleton. Assim, o programa tem algumas classes importantes, quepodem ser acessadas de diferentes pontos do programa:

• O sistema gráfico, onde é tratado a inicialização do Ogre (conforme ostutoriais, ainda que seja possível modificar a forma como Ogre é iniciado) eCEGUI, além de dar informações com relação a exibição de gráficos (comoa taxa de quadros por segundo), o que é conseguido através de funções doOgre.

• O gerenciador de telas, que é o local onde ficam todas as cenas. Ogrechama as funções membro dessa classe para atualizar a cena sendo usada.Também é possível acessar uma cena através dele. Para cada quadro, ogerenciador de telas chama o sistema de entrada para atualizar os eventos

21Unity 4.0 foi confirmado ter suporte nativo para GNU/Linux, mas ainda não foi lançado. Noperíodo da criação deste trabalho Unity estava na versão 3.5.[6]

13

do mouse e teclado, testa se o evento atual é o mesmo da cena e modificaquando for necessário, e executada a função que atualiza a cena atual.

Quando há uma mudança de cena ocorrem os seguintes eventos:

– A câmera da cena antiga é retirada da viewport22 e substituída pelacâmera da nova cena;

– É chamado o sistema de entrada para a mudança de objetos que tratarãoos eventos de mouse e teclado;

– É chamada a função de desativação da cena antiga;

– É chamada a função de ativação da cena nova;

– O ponteiro para o objeto da cena antiga é mudado para apontar para anova cena;

O gerenciador de telas também cria as cenas e as destrói quando o jogotermina.

• O sistema de entrada, que serve para gerenciar os eventos de teclado emouse, guardando também os tipos de mouse e teclado de cada cena. Re-cupera alguma cena através do gerenciador de telas quando é necessário,e normalmente usa o gerenciador de eventos para voltar a tela de título aopressionar ESC.

Cada cena tem um mouse e teclado, que são objetos que ficam armazenadosno sistema de entrada. Usa-se o sistema gráfico (ou seja, o Ogre) e o OISpara associar a janela ao mouse e teclado.

Existem funções de retorno de chamada23 para cada evento do mouse eteclado:

– No caso do mouse, existe uma função para quando o mouse se move,quando um botão é pressionado e quando o botão é solto;

22Viewport é um retângulo 2D usado para projetar uma cena 3D para a posição da câmeravirtual.[26]

23Funções de retorno de chamada são pedaços de código executável que são passado como ar-gumento para outro código, que é esperado executar o argumento em algum momento conveniente(por exemplo, quando o botão esquerdo do mouse for pressionado.[27]

14

– No caso do teclado, existe uma função para quando um botão é pres-sionado ou solto;

O sistema de entrada recebe os eventos de mouse e teclado e passa paraos objetos que implementam as funções do mouse e teclado para o eventoatual.

• O gerenciador de eventos (ou eventos de jogo), que guarda o evento atuale muda quando é requisitado. Além disso, guarda informações para as fasesdo jogo, como a batalha (quem irá lutar), o que fazer com relação a quemperde ou ganha, a batalha do computador contra computador e a vantagemdo terreno.

As informações sobre quem irá lutar, seja um grupo, um castelo ou general,são implementadas através de ponteiros. Para isso, um grupo ou um castelosão times de batalha, ou seja, herdam a classe abstrata de time de batalha.Quando o evento de batalha acontece, os ponteiros apontam para os times

de batalha que irão lutar, e dentro do combate são decididos os generais decada luta.

O tipo de luta é decidido perguntando se algum dos dois times de batalha

pertencem ao jogador. Se algum deles pertencer ao jogador, o evento debatalha acontece, dando aos ponteiros os valores dos times de batalha rela-cionados. Caso contrário, ocorrerá a luta contra o computador.

A luta de computador contra o computador acontece apenas comparandoum valor dado para cada time, que depende do número de generais, otamanho da tropa de cada general, o HP (a vida do general) e MP (os pon-tos para usar algumas habilidades especiais). Um valor alto é dado para otime que tiver o líder da nação, para que uma nação nunca seja derrotadapelo computador. Cada time de batalha possui uma função com relaçãoao resultado (vitória ou derrota), que são chamadas com relação ao resul-tado obtido. Além disso, é decidido os generais do time perdedor que sãocapturados pelo time vencedor:

– Se há espaço para prisioneiros para o time vencedor, adiciona os pri-sioneiros do time perdedor;

15

– Após adicionar os prisioneiros do time perdedor, e se ainda existirespaço, adiciona os generais do time perdedor até ficar sem espaço ouo time perdedor ficar vazio;

O espaço para prisioneiros em grupos é 5 e em castelos 10.

Os generais do time vencedor que lutaram (o que significa que se o timevencedor tiver mais generais, apenas o número de generais do time perdedorterá lutado no time vencedor, portanto o restante não ganha nada) ganhamexperiência24, tem o HP diminuído aleatoriamente e o MP e tamanho datropa ficam iguais a zero.

A vantagem do terreno, nesta versão do jogo, influencia somente se um dostimes for um castelo. Essa vantagem é um número inteiro, e influencia ataxa de acerto das tropas do general do time.

Os resultados de uma batalha do jogador contra o computador dependem doevento de batalha, então tudo que é feito é chamar as funções membro dostimes de batalha para a vitória ou derrota. No caso de empate (os generaisdos dois times são derrotados) é chamada a função membro de derrota paragrupos, pois o grupo deve recuar em caso de empate.

• A classe de dados, que serve para armazenar e dar fácil acesso a todasas informações dos elementos do jogo, como generais, castelos e grupos.Além disso, dá informações sobre o jogador, como quantas vitórias foramatingidas ou em qual semana o jogo está.

Os generais, os itens e os lugares são lidos de arquivos de entrada de umformato já estabelecido, armazenados em vetores e recuperados através deseus índices. Armazena também a quantidade de cada item, inicialmentesendo 0.

A forma como os vizinhos dos lugares são visto é feita através de um grafocom listas de adjacência. O algoritmo de Dijkstra é executado para cadalugar, armazenando cada resultado relacionado a um lugar em uma linha

24Experiência é a forma que um general evolui. Depois de ganhar uma certa quantidade depontos de experiência, seu nível aumenta e suas características melhoram.

16

de uma matriz de caminhos mínimos. Quando é necessário conhecer umcaminho para um lugar, é criada uma lista do lugar de origem até o lugar dedestino.

Os grupos ficam em uma matriz de ponteiros para lista de grupos. Uma listade caminhos ativos existe para mostrar quais posições da matriz existemgrupos, ou seja, se um grupo entrar em um caminho vazio, o caminho éadicionado na lista de caminhos ativos, e se um grupo deixar um caminho,e não existir mais grupos neste caminho, o caminho é retirado da lista decaminhos ativos.

O ponteiro que percorre a lista de caminhos ativos e a lista de grupos daposição da matriz permanecem onde pararam quando ocorre o evento debatalha.

Cada cena terá algumas funções membro:

• Criar: Inicializa todos os recursos da cena, como as janelas do CEGUI e nósdo Ogre;

• Atualizar: A função membro que, a cada quadro, será executada pelo geren-ciador de janelas;

• Gerenciador de cena: Acesso ao gerenciador de cena criado pelo Ogre;

• Desativar: A última ação que a cena fará antes de ser trocada por outra;

• Ativar: Prepara a cena para voltar a ser executada;

• Destruir: Para destruir tudo que foi criado na cena. É usado quando o jogoé encerrado e pela cena do mundo quando um novo jogo é iniciado;

• Câmera: Usada somente para a troca de cena, em que a câmera na novacena será a câmera sendo usada, ou seja, associada a viewport;

17

3.3 Criação do mundo

O mundo é onde o jogo progride. Aqui, os generais sempre estão em grupos oudentro de um castelo. Se um grupo de generais encontrar outro grupo ou castelode uma nação diferente da sua, um combate acontece.

Os lugares do mundo foram implementados como um grafo2.4, onde os nóssão os lugares (castelos, vilarejos e cavernas) e os caminhos são suas arestas. Paraisso foram criados arquivos de texto onde estão definidos os lugares, condiçõesimportantes e suas localizações. Como o castelo pode aumentar de nível, é impor-tante ter uma estrutura fora do programa para facilitar o sistema de salvar/carregarjogo.

Os castelos inicialmente foram desenvolvidos usando o Blender25, mas o plug-in para exportar os arquivos gerados para o formato que o Ogre aceita (mesh)não funcionou adequadamente. Então foi decidido criar as estruturas dentro doprograma usando o ManualObject26, que tornou esta parte do trabalho mais fácil.ManualObject foi usado para criar todas as estruturas do jogo, com exceção dopiso.

Usar a classe de ManualObject é relativamente simples, pois basta criar cadaponto e ligá-los para formar arestas e faces. É necessário indicar em cada pontoqual coordenada da textura será usada, além de definir uma normal para a ilumi-nação.

Usando senos e cossenos é possível criar pontos com igual distância de umcentro.

Talvez por limitação de hardware, não foi possível usar o sistema de terrenosdo Ogre. O motivo de se cogitar "limitação de hardware"foi que mesmo os exem-plos dos tutoriais do Ogre não funcionaram completamente (aparecia algo quetalvez fosse parte do terreno, mas mudava a cor depois de pouco tempo, além deproduzir exceções no relatório do Ogre). Assim, foram usados planos para definiro terreno, sendo que Ogre possui uma classe justamente para a criação de planos.

25Blender, também conhecido como blender3d, é um programa de computador de código aberto,desenvolvido pela Blender Foundation, para modelagem, animação, texturização, composição,renderização, edição de vídeo e criação de aplicações interativas em 3D, tais como jogos, apresen-tações e outros, através de seu motor de jogo integrado, o Blender Game Engine.

26ManualObject é uma classe do Ogre que possui uma interface simplificada para a criação deobjetos manualmente.

18

O objetivo com relação à câmera era que ela pudesse ver todos os lugares comfacilidade, mas que não ultrapassasse uma certa distância e nem invadisse o chão.Usando os nós do Ogre isso foi alcançado com certa facilidade, mas a câmeraapresentava uma distorção caso a direção para onde ela olha era paralela à vertical.Isso acontece possivelmente porque o vetor vertical da câmera fica paralelo ao seuvetor de eixo ótico. Para corrigir esse problema foi necessário, inicialmente, fazercom que a câmera não olhasse para cima ou para baixo, adicionar a câmera emnós do Ogre e, através deles, girá-la. Isso faz com que toda a estrutura da câmeragire também.

Quando uma determinada quantia de tempo passa, a lista de lugares é percor-rida (através dos Dados) e, se for um castelo, é atualizado. Isso é feito usando afunção membro do mundo que é executada a cada quadro.

Os castelos possuem recrutas, que são soldados usados para recuperar os exérci-tos de cada general. Quando um castelo é atualizado, o seu número de recrutasaumenta um pouco, sem ultrapassar a quantia máxima permitida, além de recu-perar o HP e MP dos generais do castelo da mesma forma.

A seleção de objetos foi feita através de ray querys27, que captam os objetosque os atravessam. Os objetos podem ser encontrados pelo raio através de duasformas diferentes:

• Faces do objeto: Pode-se testar cada triângulo da malha do objeto e verse o raio passou por ele. É um método custoso e mais complicado (maiscódigo). Para o jogo, não teria um custo grande pois uma consulta é feitasempre após um clique do mouse, o que paralisa o jogo e chama as janelasdo CEGUI;

• Bounding box2.5: A outra forma é através de bounding box. É rápido e Ogreusa esse tipo de consulta por padrão, além do próprio Ogre gerar bounding

box automaticamente para cada objeto da cena. O problema deste métodoé quando a caixa gerada é exageradamente grande, como é o caso quandoé criado billboards (que é grande possivelmente para garantir que qualquerrotação do plano do billboard continue dentro do bounding box).

27Ray query é como uma reta, que retorna os objetos que atravessa, na cena dada.

19

Figura 1: Um bounding box de um billboard. O billboard é o retângulo branco eo bounding box são as retas brancas que formam uma caixa ao redor do billboard.Este bounding box foi diminuído.

Foi escolhido o bounding box pela facilidade e velocidade, mas foi necessáriolimitar seu bounding box, o que era necessário pois, quando era criado um ob-jeto da cena que usava um billboard, ficava praticamente impossível selecionarqualquer coisa ao seu redor.

Ogre disponibiliza algumas estruturas para a manipulação de bounding box

com facilidade.É possível dar máscaras para os objetos da cena, o que é um valor que permite

selecionar apenas um certo tipo de estrutura. Assim, os ray query apenas retornana sua lista de resultados os objetos necessários.

As máscaras são definidas através da posição de bit 1, então se uma montanhaé 001, um castelo é 010 e vilarejo é 100, se for necessário apenas selecionar ovilarejo e o castelo, basta passar para o ray query "010 | 100"(ou 110), sendo que"é o operador de bits OR.

Para melhorar o desempenho foi decidido não usar "dynamic_cast"quandofosse necessário converter ponteiros, e em seu lugar usar "static_cast"com algum

20

identificador.

Tabela 1: Comparações entre static_cast e dynamic_cast

Número de ponteiros static_cast dynamic_cast10 0 0

100 0 01000 0 010000 0 0

100000 0 0.0041000000 0 0.028

10000000 0 0.232100000000 0 2.228

As comparações foram feitas usando o comando time no seguinte programaescrito em C++:

using namespace std;

class Base

{

public:

virtual int Val() = 0;

virtual string Classe(){return "base";}

};

class D1 : public Base

{

public:

virtual int Val() {return 1;}

virtual string Classe() {return "D1";}

};

class D2 : public Base

{

21

public:

virtual int Val() {return 2;}

virtual string CLasse() {return "D2";}

};

class D3 : public D1

{

public:

virtual int Val() {return 3;}

virtual string Classe() {return "D3";}

};

volatile D3* d3;

void DynamicCastTest (int n)

{

Base* base = new (D3);

for (int i = 0; i < n; i++)

{

d3 = dynamic_cast <D3*> (base);

}

delete base;

}

void StaticCastTest (int n)

{

Base* base = new (D3);

for (int i = 0; i < n; i++)

{

d3 = static_cast <D3*> (base);

22

}

delete base;

}

int main (int argc, char* argv[])

{

if (argc < 3)

return 0;

switch (argv[1][0])

{

case ’d’:

DynamicCastTest(atoi(argv[2]));

break;

case ’s’:

StaticCastTest(atoi(argv[2]));

break;

default:

break;

}

cout << "Terminado" << endl;

return 0;

}

3.3.1 Janelas do mundo

As janelas são a forma como o jogador pode interagir com o mundo. Quandoalguma janela está ativa, o mundo fica paralisado. Isto é feito apenas testando se

23

alguma janela está ativa através do CEGUI.Um menu é uma lista de comandos ou opções que fazem parte das janelas

criadas pelo CEGUI. Com os menus são também exibidas informações sobre osseus elementos.

Basicamente as janelas possuem uma função de criação, de atualização e umapara cada botão. Os botões de troca de janelas são implementados da seguinteforma:

• Recupera o ponteiro para a janela atual e da janela de destino, o que é feitofacilmente caso tenha-se armazenado os ponteiros em alguma estrutura ousabendo o nome da janela, que está presente no arquivo .layout;

• Esconde a janela atual e mostra a janela de destino. Isto é feito usandoas funções de classe hide e show da classe Window do CEGUI, usando oobjeto da janela atual e de destino;

As janelas foram criadas em XML usando um editor de texto comum (gedit).Há programas para a criação dos arquivos de layouts de forma visual, mas nãofuncionaram corretamente. São exibidas no jogo através do CEGUI2.3.

Foram produzidas as faces dos generais usando o Gimp28, que possui umscript29 que facilita a criação de imagens e imagesets para o CEGUI. O scriptproduz o arquivo de imagem e o arquivo .xml para as faces baseado nas camadasda imagem original.

As janelas desta parte são as seguintes:

• A janela principal dá acesso as outras janelas do mundo.

A seleção de um grupo ou lugar da cena produz um identificador. Se for umgrupo, este identificador será o identificador do general. Se for um lugar,será um identificador de um lugar. Um general sabe onde está, então épossível descobrir o grupo através dele.

A classe de dados é usada para obter o ponteiro para um general ou para umlugar.

28Gimp é uma ferramenta de criação e edição de imagens, além de permitir a criação de an-imações através de plug-ins. Possui diversos recursos úteis, como o uso de scripts (Script-Fu,Python, Perl e Tcl).

29O script pode ser encontrado neste endereço: http://registry.gimp.org/node/6128

24

• A janela dos generais dá acesso as informações sobre os generais, sejado grupo ou de um castelo. Há uma lista de generais, onde cada um podeser selecionado e, assim, mudar suas tropas e ver suas características. Épossível ver o nível do castelo também, assim como quantos recrutas elepossui.

O que é feito é basicamente usar as informações que a classe de generaispermite ver e, através do CEGUI, exibi-las. Quando um general é sele-cionado na lista de generais, é possível encontrá-lo usando a posição que eleestá na lista (que é a mesma do vetor de generais do castelo e do grupo) ouassociar um identificador na linha onde o general está, permitindo encontrá-lo usando a classe de dados.

O botão de recrutar adiciona os recrutas do castelo para o exército do gene-ral, apenas não ultrapassando a quantia máxima. Assim, subtrai-se a quantiaque o general conseguiu obter da quantia do castelo e atualiza a janela.

O botão de liberar faz o oposto de recrutar: adiciona os soldados do generalno castelo, se existir espaço disponível.

O botão para mudar a tropa atual do general permite selecionar um novotipo de tropa, se for possível. É aberta uma nova janela para a escolha datropa atual. Generais podem usar outras tropas através de itens, conseguidose usados na fase de assuntos internos.

Cada linha do menu de seleção de tropas possui um identificador, que é aforma como cada uma das 6 tropas do jogo são reconhecidas. Quando umgeneral não pode selecionar uma tropa, ela fica escura no menu de seleção,o que é facilmente usando as funções do CEGUI para cores de texto.

• A janela de criar grupos permite escolher os generais e prisioneiros paraa criação de um grupo. Existe apenas em um castelo.

Uma lista de generais é exibida na parte inferior da tela. Ao selecionar umgeneral e apertar o botão selecionar, o general é adicionado ao grupo, se forpossível.

São usados uma cópia do castelo e um grupo vazio temporário. Isso é feitopara não alterar os objetos existentes no caso em que a criação do grupo

25

for cancelada. Em C++ é possível copiar um objeto com o "=". O grupotemporário é usado para a criação do novo grupo após o botão de enviarfor pressionado. O novo grupo é criado com a ação "Esperar do lado defora"(mais informações em 3.3.2).

Um último teste é feito antes de realmente criar um grupo: é testado seexiste algum prisioneiro no castelo caso o castelo seja abandonado. Casoexista algum, o botão de enviar não funciona.

Após a criação do grupo, é necessário ganhar uma forma vista pelo jogador,que deve ser dado pelo gerenciador de cena do mundo. A classe de dadospossui uma lista para novos grupos, e ela é vista pelo objeto do mundoquando a cena for atualizada no quadro atual. Quando isso ocorre, o grupoé adicionado no lado de fora do castelo onde ele foi criado.

É possível também adicionar prisioneiros no grupo, da mesma forma queé possível adicionar generais. Porém, não é possível criar um grupo semgenerais.

• A janela de prisioneiros é como a janela de generais, porém somente como botão de selecionar o general. Funciona exatamente da mesma forma quea janela de generais, porém usando os prisioneiros do castelo.

• O botão de entrar existe apenas em um grupo, e é apenas ativo quando ogrupo está executando a ação de esperar do lado de fora. Muda a ação atualdo grupo para entrar e executa esta ação. Os efeitos são como descritos em3.3.2.

3.3.2 Grupos

Os lugares do mundo são posições fixas, então basta carregá-los no início de cadajogo. Castelos podem aumentar ou diminuir o nível, mas tudo que é feito é trocarsua forma. Ao contrário dos lugares, os grupos não são objetos fixos e são cria-dos através de ações do jogador, além de possuir ações como andar e entrar emcastelos.

Cada grupo possui uma lista de ações, sendo que a primeira ação é executadaaté ser finalizada. Depois é destruída e vai para a próxima ação. As ações do

26

grupo são:

• Entrar no castelo: Os generais entram no castelo se há espaço para todosos prisioneiros do grupo no castelo. Caso não exista espaço para todos osgenerais, apenas alguns entram no castelo e o restante permanece no grupo.

A classe da ação de entrar apenas guarda o identificador do lugar que ogrupo tentará entrar. Quando é executada, acontece o seguinte:

– Testa se é um castelo, pois um grupo pode entrar apenas em castelos.Se não for um castelo, o grupo faz a ação de esperar do lado de forado lugar;

– Adiciona todos os prisioneiros do grupo no castelo. Se conseguir, adi-ciona todos os generais. Se conseguir, o grupo é removido da lista degrupos esperando do lado de fora do castelo se estiver nela;

– Caso não seja possível adicionar os prisioneiros ou generais do grupono castelo, o grupo entra na lista de grupos do castelo, esperando dolado de fora;

Não é possível entrar em um castelo inimigo, pois antes de encontrá-loatravés da ação de andar, ocorre uma batalha.

• Parar: Se um grupo ganhar uma luta, ele ficará parado por um tempo.

A classe da ação de parar apenas possui um inteiro sem sinal que indicaquantos quadros o grupo não se moverá.

Toda vez que o grupo faz esta ação, o número de quadros diminui em 1, atéalcançar zero. Quando o número de quadros de espera for zero, irá para apróxima ação.

Esta ação sempre é colocada como a primeira ação da lista de ações, nãomodificando o restante da lista.

• Andar: É selecionado um destino e o grupo anda até ele, com a possibilidadede encontrar um grupo ou castelo de uma nação adversária.

27

A classe de andar possui o identificador do lugar de origem, de destino e umvetor para indicar a velocidade vetorial. A velocidade vetorial é obtida sub-traindo a posição de destino pela de origem, normalizando e multiplicandopor um valor constante.

O tratamento da ação de andar ocorre da seguinte forma:

– O grupo recebe, se existir, um grupo que está a frente e um grupo atrásno caminho;

– É realizado o teste de colisão com um dos grupos recebidos, depen-dendo do destino da ação de andar;

– Se há colisão com algo que seja de uma nação diferente, ocorre umabatalha, que pode ser computador contra computador ou jogador con-tra computador. No caso de ser jogador contra computador, o eventoatual muda para o evento de batalha;

– Se há colisão com um grupo da mesma nação, então há uma troca deposições na lista de grupos do caminho;

– Se atingiu o destino, então o grupo vai para sua próxima ação. Se fornovamente uma ação de andar, o grupo é removido do caminho atuale adicionado em um novo caminho;

• Esperar do lado de fora: Grupos que esperam do lado de fora de um castelo,sem entrar nele, são os primeiros a lutar quando um castelo é invadido.

A classe que representa esta ação apenas possui o identificador do localonde o grupo está esperando.

Quando um grupo é visto em um caminho com esta ação, é adicionado nalista de grupos do local e removido do caminho.

As ações são colocadas em uma lista de ações de cada grupo. Assim, quandouma ação acaba, basta ir para a próximo, destruindo a antiga.

Para a ação de andar é necessário conhecer um caminho para o destino. Oalgoritmo de Dijkstra2.4.1 fornece uma forma de encontrar o caminho mais curto

28

para um digrafo, se não existirem arestas com custo negativo. No caso do mundo,o custo é a distância entre dois lugares, então sempre será positivo.

Dijkstra é usado no início do jogo, encontrando os caminhos mais curtos earmazenando em uma matriz, consultada toda vez que um grupo for andar paraalgum lugar. Assim, se um grupo deseja ir para um lugar x, ele consultará a matrizcom o resultado de Dijkstra, armazenará em uma lista de ações e andará seguindoo caminho.

Os grupos são representados por billboards2.6, sendo que mantem a coorde-nada y constante, mas as demais são modificadas de modo que sempre encaram acâmera (há uma opção para isso no Ogre).

Para andar, a cada quadro uma lista de caminhos ativos, que são caminhos quepossuem pelo menos um grupo, é percorrida. Cada um desse caminhos ativos, queé uma lista de grupos, também é percorrido, de modo que os grupos do caminhofaçam suas ações.

Os caminhos são dados em uma matriz, sendo que metade dela não é usada.Por exemplo, se existe um caminho do lugar 0 para o 3 ou do 3 para 0, existeuma lista de grupos na posição da matriz (3,0), mas na posição (0,3) não há nada.Grupos são adicionados no fim ou no começo da lista de grupos do caminho, eexecutam suas ações. Quando há uma colisão, o grupo anda somente até a posiçãode impacto. Se a colisão for entre dois objetos de nações diferentes, começa umabatalha, caso contrário, os grupos apenas trocam de lugar na lista caso estejamandando em sentidos contrários.

Grupos que estão "esperando do lado de fora"não estão em um caminho. Nestecaso, fazem parte de uma lista de grupos de um lugar e não são atualizados a cadaquadro.

Grupos que entram em um castelo e ficam vazios são destruídos quando forematualizados, assim como grupos que estão esperando do lado de fora e recebem aordem de entrar.

Quando há uma batalha, os seguintes eventos podem ocorrer:

• O grupo vence a batalha contra um castelo: Alguns generais inimigos queforem enfraquecidos na batalha se tornarão prisioneiros do grupo e o restantedos generais inimigos formarão um grupo e irão para outro lugar vizinho ao

29

atual. O grupo entrará no castelo vazio;

• O grupo vence a batalha contra um outro grupo: O grupo vencedor ficaráparado por algum tempo, ou seja, a próxima ação de sua lista de ações serápara ficar parado;

• O grupo perde a batalha: Ele passa a percorrer o caminho no sentido con-trário, caso ainda exista algum general no grupo. Se não existir nenhumgeneral, nada é feito e quando este grupo for se mover, será destruído (oobjeto, que contém o billboard e será destruído pelo gerenciador de cena);

3.3.3 Jogada dos inimigos

A jogada do computador precisava:

• Ser rápida: O jogo não poderia ficar mais lento por causa que o oponenteestava pensando;

• Razoavelmente correta: O inimigo tem que fazer jogadas que pelo menosfazem algum sentido. Por exemplo, não enviar grupos para algum lugarquando não há chance de vitória;

A primeira ideia foi usar uma thread para cada nação e uma para aqueles quenão fazem parte de uma. Ao usar threads, os inimigos poderiam pensar enquantoo jogo ocorre.

Um problema ao usar threads é com relação às regiões críticas. Uma threadnão poderia, por exemplo, bloquear o acesso a um castelo e seus generais pormuito tempo, pois talvez outra nação precise consultá-lo. Outro problema é queo jogo muda constantemente, então uma estratégia sendo desenvolvida pode serinvalidada a qualquer momento.

A jogada do computador usada foi a seguinte:

• Baseada em castelos, e não em nações: Os castelos que possuem generaisinimigos olham para seus vizinhos, e decidem suas ações baseado em umvalor dado para cada vizinho. Este valor tem relação com as característicasdo lugar (como o número de generais de um lugar);

30

• Não usa threads: Não existe risco de bloquear o acesso a algo importantepor muito tempo;

• Grupos tentam ir para um castelo aliado ou vão para algum castelo quetenham alguma chance de vitória;

• Às vezes joga aleatoriamente;

O inimigo joga rapidamente e melhor do que se fosse completamente aleatório,mas ainda não joga bem. É possível ver que os inimigos podem, às vezes, ficarindo e voltando para o mesmo castelo, pois ao formar um grupo o castelo antigoacaba sendo um bom lugar para voltar. A jogada aleatória evita que isso sempreocorra.

O inimigo joga em um intervalo de tempo constante, não afetado quando seestá vendo as janelas do mundo. Isso é feito usando a função membro que atua-liza o mundo a cada quadro, permitindo que o inimigo jogue apenas quando umcontador de tempo tenha alcançado um valor constante.

3.4 Criação do gerenciador da nação

O gerenciador da nação aparece depois de um tempo enquanto no evento domundo. No gerenciador (conhecido no jogo como assuntos internos), pode-sefazer buscas nos castelos, recrutar generais capturados, equipar itens e salvar ojogo.

Para realizar as ações foram usados menus implementados usando CEGUI.As ações do jogador nesta parte são:

• Equipar ou usar itens: Um jogador pode selecionar um item e, caso a classedo general permita, ele pode ser equipado ou usado. Um item usado desa-parece, e um item equipado é adicionado ao general, substituindo um itemantigo, se existir. A classe de dados tem a quantidade de itens não usadosque a nação do jogador possui.

Itens podem ser equipáveis e não equipáveis:

31

– Os generais possuem um ponteiro para itens equipáveis, e eles sãousados para definir as características do general. Por exemplo, umaespada pode aumentar seu valor de ataque, então quando for consul-tado o valor de ataque de um general equipado com essa espada, serádado como o ataque do general mais o valor dado pelo item. Essaespada também teria 0 nos outros atributos, aumentando somente oataque;

– Itens não equipáveis mudam permanentemente os atributos do general,então bastaria modificar o valor para determinado atributo do generalque o item modifica;

Cada general possui um ponteiro para um item equipável. Quando um itemequipável é usado em um general, o ponteiro para o item do general apontapara o novo item e devolve o item antigo. Se havia um item antigo (o pon-teiro não era 0), é somado mais um na posição do item no vetor de quanti-dade de itens dos dados.

Para mostrar os itens da nação, basta consultar, nos dados, os itens nãopossuem zero unidades.

As classes de generais são apenas valores numéricos, e são usados paramelhorar os atributos de um general quando seu nível é aumentado. Porexemplo, a classe espadachim aumentaria mais HP quando o nível do gene-ral aumentasse, e o nível do general aumenta após atingir uma determinadaquantia de experiência, ganha como resultado de uma batalha entre gene-rais. Então, para saber se um item pode ser equipado em um general, bastafazer uma comparação entre dois números (as classes).

• Buscas em um castelo: Um general pode fazer buscas em um castelo de-pendendo de sua inteligência do general e, assim, obter itens.

Cada item possui uma probabilidade de ser encontrado em um lugar, que édado no arquivo de entrada.

Para evitar que um general faça buscas mais de uma vez, existe uma variávelbooleana em cada general que diz se ele já fez algum busca ou fortaleceu

32

algum castelo. Essa variável tem o seu valor original recuperado quando épressionado o botão para ir para o evento do mundo.

A janela de busca mostra os castelos do jogador, que são encontrados per-correndo o vetor de lugares nos dados e adicionando apenas os castelos dojogador. Castelos que possuem generais com inteligência o suficiente ficamcom uma cor mais clara no menu, o que é facilmente encontrado apenasverificando os generais de cada castelo do jogador.

As buscas são realizadas da seguinte forma:

– Encontra o castelo onde está o general selecionado (apenas generaisem castelos e com inteligência alta o suficiente podem fazer buscasem castelos);

– É gerado um número aleatório entre 0 e 100;

– Se o número aleatório for menor que a probabilidade de encontrar oitem, então o general encontra o item. Os dados são atualizados (éadicionado 1 item do tipo dado no vetor de quantidade de cada itemdos dados). A busca termina e não é mais possível realizar outra busca;

– Caso não tenha encontrado o item por causa da probabilidade, procuranos vizinhos do castelo em que está o general;

– Se não encontrar nenhum item, a busca termina e não é possível fazeruma nova busca antes de passar pelo evento do mundo novamente;

• Fortalecer castelos: Um castelo possui um nível, que pode diminuir quandoé invadido. O nível do castelo define a quantidade de recrutas que ele temdisponível, e estes recrutas são usados para recuperar as tropas dos generais.Como na busca no castelo, um general que fortalece um castelo não podefazer buscas ou fortalecer novamente, pois usa a mesma variável booleanada busca.

Usa a mesma janela de busca, sendo que fortalecer é só mais um botão dela.

Acontece da seguinte forma:

– É gerado um número aleatório de 0 a 100;

33

– Se o número aleatório for menor do que (inteligência-20)/2, então ocastelo aumenta em 2 níveis;

– Caso contrário, se o número aleatório for menor do que (inteligência-20), então o castelo aumenta em 1 nível;

– Caso contrário, nada acontece, mas não é possível fazer buscas oufortalecer castelos sem passar pelo evento do mundo novamente;

• Recrutar prisioneiros: É possível recrutar generais para sua nação. Um testeé feito usando a lealdade, que é uma característica do general, e um númeroaleatório. Quanto menor a lealdade, mais fácil é recrutá-lo.

A mesma variável booleana usada na busca e no fortalecimento de castelosé usada nos prisioneiros, evitando que a tentativa de recrutá-los ocorra maisde uma vez.

Ocorre o seguinte:

– Se o general pode ser recrutado, continua. Caso contrário, falha. Umgeneral pode ser recrutado se ele não é um general com lealdade -1, que são recrutados apenas quando a nação a qual ele pertence étotalmente derrotada. Isto é feito apenas testando se a lealdade dogeneral é diferente de -1;

– É gerado um número aleatório de 0 a 100;

– Se este número for maior que a lealdade do prisioneiro, ele se unirá anação do jogador;

– Caso contrário, só é possível tentar novamente após passar pelo eventodo mundo novamente;

• Aumentar as tropas: É possível aumentar as tropas do general caso existaalguma medalha, que podem ser obtidas ao derrotar um general inimigo.Qualquer general da nação pode ter suas tropas aumentadas, a não ser queelas já estejam em seu nível máximo ou o general não tenha o controle datropa dada.

O que é feito é apenas permitir que tropas de tamanho maior que 0 possamser aumentadas.

34

3.5 Criação da batalha

O combate entre dois grupos de generais acontece no evento de batalha. Os gene-rais lutam um de cada vez contra um outro general do grupo oponente.

A batalha acontece da seguinte forma:

• Duelo entre duas tropas: os generais ficam parados, distantes um do outro,e quem anda pelo cenário são suas tropas. As tropas lutam entre si e tentamalcançar o outro general. O jogador dá instruções para sua tropa sobre comodevem se comportar (avançar, recuar, parar, etc);

• Duelo entre dois generais: não há mais tropas, então um general deve lutarum contra o outro diretamente;

Além do combate em si, existe o menu de seleção de generais ou da ação dogrupo (fugir, lutar, etc).

A batalha entre duas nações controladas pelo computador acontece baseadanas características dos generais dos grupos ou castelos envolvidos. Somam-se ascaracterísticas que podem dar a vitória, e quem ficou com uma pontuação maiorganha. Pertencer a uma nação também é um fator positivo para a vitória.

3.5.1 Antes da batalha

Como no gerenciador da nação, o recurso mais usado foi o CEGUI, para sele-cionar generais e as ações do grupo.

Generais selecionados para a batalha são enviados para o gerenciador de even-

tos, onde a cena de batalha os recupera e produz suas informações para o eventode batalha.

Existem as opções:

• Lutar: Vai para onde os generais podem ser escolhidos, e assim começar abatalha.

Basicamente o que acontece é permitir que as janelas de escolhas de ge-nerais seja vista, usando funções do CEGUI. Cada face de general e suascaracterísticas que aparecem no fundo e no topo da tela são botões. Foram

35

feitos em XML como um conjunto de janelas, com um botão, com umacerta transparência, em cima.

Clicar nos botões de generais define quem irá lutar, pois cada botão estáassociado a posição do general em cada grupo. Os ponteiros dos generaisescolhidos são enviados para os eventos de jogo, onde são recuperados nacena da batalha.

• Falar: O inimigo avalia o grupo do jogador. Se ele tem chance de vencer,o evento de batalha continua. Caso contrário, a luta acaba em empate(ninguém perde nada).

O que é feito, nesta versão do jogo, é comparar o número de generais decada grupo. Se o jogador tiver mais generais e usar o botão "falar", a batalhaterminará empatada, ou seja, os grupos inverterão seus caminhos (o destinoe a origem são trocados) e nada ocorrerá com castelos.

• Fugir: O jogador perde a batalha, podendo perder parte de sua tropa e pri-sioneiros. Se o jogador estiver em um castelo, o castelo é conquistado peloinimigo e grupos do jogador são formados, indo para algum vizinho docastelo.

O que é feito é usar a função membro de derrota para o time do jogador (ouseja, um castelo ou um grupo do jogador) e diminuir para zero o tamanhoda tropa dos generais do jogador.

Quando esta cena é ativada, é feito um teste sobre quais generais ainda podemlutar. Se um grupo não possui mais um general que possa lutar, então ele perdeua luta. Isto é feito através de um vetor booleano para cada grupo, em que cadaposição indica se o general pode lutar.

O resultado da batalha entre os times será dada nesta fase, chamando os even-

tos de jogo para tratar o resultado. Quem perder tem suas tropas reduzidas parazero.

3.5.2 A batalha

Os elementos da batalha são:

36

• O campo de batalha: Tem o propósito de mostrar para todos no campo ondeestão os outros elementos do campo. Implementado como uma matriz deponteiros para "elementos do campo de batalha", que podem ser soldados,generais, projéteis e ataques especiais;

• Os soldados: Soldados são as unidades da tropa de um general. Cada tipo detropa possui soldados com alguma vantagem ou desvantagem com relaçãoa outra tropa;

• Os generais: Existem dois generais no campo de batalha: o general inimigoe o general do jogador. Suas barras de vida (HP) ficam no topo da tela, equando alguma delas fica vazia um general é derrotado;

• Os projéteis: Criados por alguns soldados. Atravessam o campo e, caso sechoquem com algum inimigo, o eliminam se as condições de acerto foremcumpridas. Os projéteis não foram implementados, mas seria algo similaraos soldados, com a diferença que apenas seguiriam um caminho fixo;

• Ataques especiais: Percorrem o campo, destruindo o que esta em seu cami-nho e/ou afetando o general adversário. Também não foram implementados,assim como os projéteis;

Quando a cena de batalha é ativada, os generais ganham formas, que são bill-

boards. São dados alguns billboards para cada general, representando cada uma desuas ações, como parado, preparando para atacar, atacando e morrendo. As suasformas são carregadas no início do combate, tendo um ponteiro que mostra qualestá atualmente sendo executado, o que depende da ação do general. O mesmoocorre com os soldados, que são a tropa do general.

Os soldados são separados em 4 listas: 2 listas (uma para o jogador e outra parao computador) com soldados que irão seguir instruções dadas pelo jogador/computador,e 2 com soldados que ficarão na defesa. Estes soldados da defesa não aceitarão or-dens e apenas ficarão rodeando o general, de modo a defendê-lo de outras tropas.

Os soldados são colocados no campo a frente ou atrás do general, criandofilas de soldados. As formações indicam a porcentagem da tropa que ficará afrente, sendo que o restante ficará atrás (ou seja, é definido quais soldados ficarão

37

nas listas de soldados que seguirão instruções e listas de soldados que ficaramrodeando o general). As filas de soldados são criadas apenas preenchendo ascolunas a frente ou atrás do general, até que acabem os soldados disponíveis.

As listas de soldados são percorridas a cada quadro, fazendo com que cadasoldado produza uma ação. Se um soldado passa a fazer a ação de morrer, ele éretirado da sua lista e colocado na lista de soldados mortos.

A cada quadro os soldados olham o campo de batalha e decidem suas ações,que podem ser atacar algum soldado inimigo ou seguir alguma instrução. Asinstruções são dadas pelo computador ou jogador.

Algumas instruções são:

• Avançar: Ir até o general inimigo. É comparado onde o general inimigoestá com o lugar onde o soldado está, na matriz, para decidir se ele irá paraa direita ou esquerda;

• Recuar: Ir no sentido oposto do general inimigo;

• Reagrupar: Soldados para o centro (em relação a profundidade, ou a coor-denada z) do campo de batalha;

• Dispersar: O contrário de reagrupar - ir para os cantos do campo de batalha,em relação à coordenada z;

• Esperar: Os soldados ficam parados;

No início de uma batalha, o soldado estará executando a ação de esperar.Ocorre o seguinte:

• O soldado testa se há um inimigo a sua frente ou atrás, o que é uma infor-mação dada pelo campo de batalha;

• Se existir um inimigo, vai para a ação de "começar ataque". Depois dealguns quadros nesta ação (o que é implementado através de um contador),o ataque é feito, fazendo com que o que estiver na posição em que o inimigoestava execute a ação de morrer, caso for inimigo. O soldado permanecemais alguns quadros nesta ação e volta para a ação de esperar;

38

• Se não existir inimigo, o soldado seguirá uma instrução, a qual, caso nãofor uma instrução para esperar, produzirá uma ação para andar;

Para andar, o soldado testa posições próximas ao seu destino. Por exemplo,se ele estiver seguindo a instrução de avançar, ele irá ver a posição que está a suafrente (a posição a frente na matriz do campo de batalha) está livre. Se não estiverlivre, ele tentará a posição um pouco mais acima ou abaixo de forma aleatória. Senão existir posição livre, ele não fará nada no momento.

Se existir um lugar vago, uma velocidade vetorial é produzida de acordo coma direção e sentido produzidos após o soldado ver as instruções, além de colocaro valor 0 na posição antiga (ponteiro nulo) e colocar o soldado na nova posição(mesmo que ele ainda esteja caminhando para ela). A cada quadro é usada essa ve-locidade no nó do Ogre que está o billboard para movimentar o soldado. Quandoalcançar o objetivo, volta para a ação de esperar, seguindo uma próxima instrução(que pode ser a mesma) ou atacando um inimigo, como já foi mencionado.

O ataque de um soldado acerta dependendo do "comando"30 do general, alémdo terreno (se a luta ocorre em um castelo ou em um campo) e tipo de tropa.

Um castelo pode ser um time de batalha, então basta ver se o time de batalhade algum dos dois jogadores é um castelo para modificar a taxa de acerto.

Cada tropa tem suas fraquezas com relação a outras tropas, e isto afeta a prob-abilidade de acerto. Os valores como cada tropa age com relação a outra tropa édado por uma tabela, consultada através da classe de tropas.

É gerado um número aleatório que é comparado com a probabilidade de acerto,para assim definir se ele acertou ou não o soldado inimigo.

Generais agem de forma similar aos soldados, porém não aceitam instruçõese não se movem, ou seja, estão esperando, começando um ataque, atacando oumortos. Diferente dos soldados, quando são atacados e acertados, uma quantia ésubtraída de seu HP. Todo quadro é testado se algum general teve seu HP igual azero, o que define quem perdeu a luta.

Quando não há mais tropas, os generais são movidos um ficar na frente dooutro. Assim, quando eles procurarem na matriz se há um inimigo próximo, sem-pre encontrarão e certamente um dos dois terá seu HP reduzido a zero.

30Comando é uma das características do general, que define parte da probabilidade de acerto desuas tropas.

39

A batalha possui duração de no máximo 100 segundos. Se um resultado nãofor alcançado neste tempo (ou ir para o duelo), a luta termina em empate. OOgre disponibiliza o tempo entre o último quadro e o atual, então basta usar umavariável de tempo que será atualizada a cada quadro.

Sobre os resultados de uma batalha, um general que é derrotado fica sem suaface na seleção de generais, em 3.5.1. Os resultados comunicados através dogerenciador de eventos, que são visto quando 3.5.1 é ativado, mudando assim ovalor do vetor booleano que indica se um general pode lutar.

4 Resultados

A forma básica do jogo está pronta. Alguns recursos, como salvar o jogo, acabaramnão sendo implementados e faltaram alguns gráficos para representar alguns ob-jetos (como alguns itens e tropas).

O computador no mundo tenta expandir seu território e, na maioria das vezes,de forma segura. Porém, o computador da batalha apenas faz com que suas tropasataquem, o que os tornam oponentes fáceis de serem derrotados.

O jogador pode escolher sua nação no início do jogo, organizar grupos, con-quistar castelos e recrutar novos generais para sua nação. Na batalha, o jogadorpode dar ordens para suas tropas e, caso não exista mais tropas, pode optar porperder o combate ou ir para o duelo. Nos assuntos internos, é possível equiparitens, aumentar tropas caso o jogador tenha ganho alguma batalha, fazer buscasem castelos e melhorar castelos.

Nos combates, todas as tropas apenas atacam inimigos que estão a sua frente.A ideia é que arqueiros, por exemplo, pudessem atacar inimigos a longa distância.

O jogo não possui uma história, ainda que fosse fácil adicioná-la no jogo. Nãofoi adicionada por falta de tempo. Basicamente a história andaria quando um líderinimigo fosse capturado, e no fim haveria um único inimigo que, se derrotado,levaria ao final do jogo.

O jogo é jogável, tem suas principais funções que foram definidas na proposta,mas faltam os recursos mencionados.

O jogo roda em torno de 60 quadros por segundo (normalmente variando entre55 a 60).

40

Figura 2: O mundo.

Figura 3: O mundo, em outra posição.

41

Figura 4: O mundo, em outra posição.

Figura 5: A janela de seleção de generais no mundo.

42

Figura 6: Assuntos internos.

Figura 7: A batalha. Na parte de cima, a barra de HP de cada general e suas faces,a tropa que ainda resta para cada general e o tempo para o fim da luta. Na parte debaixo temos uma barra de "poder", que quando preenchida permitiria ao generalusar habilidades especiais, se tiver MP, que são os números em branco.

43

5 Conclusões

O planejamento de cada fase foi importante para o desenvolvimento do jogo, poispermitiu facilmente adicionar e testar novas funcionalidades.

Como este jogo foi baseado em um jogo existente31, alguns recursos forammais fáceis de definir, como a forma dos menus e onde eles apareceriam.

O uso de um motor gráfico permitiu, após aprender a utilizá-lo, criar recursoscom maior facilidade. Além disso, Ogre é rápido. CEGUI possui alguns proble-mas que estão sendo corrigidos a cada nova versão, mas é muito útil e produz bonsresultados.

Apesar dos pontos que faltaram na implementação, o jogo é jogável.

6 Desafios e frustrações

Durante o curso de ciências da computação eu sempre pensei sobre o tema de meutrabalho de formatura, mas não cheguei em alguma conclusão sobre o que queriafazer. Eu havia gostado de várias disciplinas que fiz e por isso não encontravauma área em especial para produzir um trabalho, e também não consegui pensarem um projeto.

O tempo passou e fui obrigado a escolher. Pensei sobre o que eu queria fazernaquele momento (no início de 2012) e a resposta foi processamento de imagens.Gostaria de usar algoritmos que havia aprendido em outras disciplinas (como emgeometria computacional ou programação linear) para fazer algum tratamento ouclassificação de imagens, ou pelo menos estudar outros algoritmos para esse fim.

Fui atrás dos professores que havia tido aula e que falaram algo sobre o as-sunto, mas eles estavam ocupados com alunos da pós-graduação. Um professorme disse que alguns outros colegas já o haviam procurado e imaginei que talvezessa área estivesse cheia. Pensei em computação gráfica mas, pelo que vi, eramos mesmo professores.

Alguns colegas me disseram sobre a possibilidade de fazer um jogo, que eraalgo que não sabia que era possível. Durante as férias eu sempre começava afazer um jogo, mas sempre parava em algum ponto. Pensei que seria uma boa

31Dragon Force. [4]

44

oportunidade de tentar fazer um até o fim e também ter a experiência de usar ummotor de jogo ou gráfico. Assim procurei o professor Flávio e ele aceitou a minhaproposta para o jogo.

O jogo foi muito mais trabalhoso do que eu havia pensado. No início Ogrenão foi algo muito trivial de se usar e tive alguns problemas com CEGUI, porqueapesar de ser fácil criar um layout em XML, é também fácil errar algo e váriasvezes não havia indicação sobre onde havia ocorrido o problema. Além disso,existe muita informação errada sobre Ogre e CEGUI pela internet.

Algumas ferramentas, como aquelas indicadas para se criar layouts dos menus,não funcionaram. Ao buscar alguma solução, vi que outras pessoas tambémtiveram os mesmos problemas. No caso do criador de layouts/imagesets do CEGUI,a resposta foi que o criador havia abandonado o projeto e uma nova ferramentafoi desenvolvida, que também possuía erros e, assim, não foi utilizada.

Imagens são um problema, porque muitas vezes os seus donos não deixammuito claro onde você pode usá-las. Eu acabei usando imagens que diziam quepoderiam ser usadas em qualquer lugar, imagens que vieram com o Ogre e CEGUIe imagens que eu mesmo criei.

Por fim, eu não fiz a disciplina de orientação a objetos. Acabei lendo sobreela, mas acredito que o projeto do jogo teria sido melhor se a tivesse feito.

7 Disciplinas importantes para o trabalho

• Introdução à Computação, Princípios de Desenvolvimento de Algoritmos,

Estruturas de Dados;

Disciplinas importantes para aprender o básico sobre programação, além deestruturas de dados muito importantes que são usadas durante todo o cursoe neste trabalho.

• Laboratório de Programação;

Onde temos as primeiras ideias sobre organização de código, além de desen-volvermos um projeto maior (quando comparados a um exercício-programa).Também temos uma introdução a linguagens de script.

45

• Laboratório de Programação II;

As primeiras ideias sobre orientação a objetos e mais sobre linguagens descripts.

• Algoritmos em Grafos;

Onde é aprendido a criação de grafos e algoritmos que os usam. Importantepara a criação do mundo (com relação as vizinhanças e castelos) e o algo-ritmo de Dijkstra resolve o problema de encontrar um caminho entre doiscastelos.

• Programação Orientada a Objetos;

Ogre e CEGUI usam orientação a objetos, assim como o jogo desenvolvido.Também importante com relação aos padrões de projeto.

• Engenharia de Software;

Importante para a criação do projeto do jogo.

• Direito e Software Livre;

Onde aprendi sobre algumas licenças e sobre leis com relação a software.

• Computação Gráfica;

Ogre abstrai boa parte do que é aprendido nesta disciplina, mas graças a elaque é possível realmente entender como tudo acontece, além de facilitar oentendimento de alguns conceitos. Além disso, foi graças a esta disciplinaque eu consegui corrigir alguns erros.

8 Melhoramento do projeto

• Som: Gostaria de ter adicionado som ao projeto e sei o que é necessário;

• Terreno: Não há rios no mundo. Também o chão é apenas um plano;

• Melhores modelos 3D e imagens: Foi evitado usar recursos disponíveispela internet e, por isso, acabei fazendo algumas imagens e modelos 3D.Gostaria de substituí-los no futuro;

46

• Algumas otimizações e melhor codificações de algumas partes;

• Jogada do computador no mundo: o problema é que o jogador teria quejogar bem, porém rápido. Esta parte do trabalho acabou ficando fraca porfalta de tempo;

• Jogada do computador na batalha: o computador acabou apenas enviandosuas tropas em direção ao inimigo. O ideal seria que cada tropa tivesse umaestratégia, seja na formação ou nas instruções, dependendo das condiçõesdo general;

• Ataques especiais: a barra inferior da luta e o "MP"acabaram ficando inú-teis. Alguns ataques especiais deveriam destruir a tropa do oponente queestá em alguma parte do campo, como o centro, e outros atacar diretamenteo general inimigo;

• Soldados com ataque de longa distância: Todos os soldados atacam apenasquem está a sua frente. Gostaria de adicionar disparos e flechas;

• Salvar o jogo;

• História no jogo: acabou não sendo colocada no jogo. De modo geral, ahistória para esse tipo de jogo é mais uma desculpa para fazer as ações, eacabei deixando de lado por causa que havia outras partes mais importantesdo trabalho a serem feitas. Basicamente seria colocar uma janela do CEGUIpara textos e ler um texto de um arquivo de texto, e atualizar cada vez queo botão esquerdo do mouse fosse pressionado. A história seria contadasempre na fase de "assuntos internos", em especial quando algum líder deoutra nação fosse capturado.

• Criar um executável em outros sistemas operacionais;

O jogo pode ser expandido, seja adicionando novas tropas ou nações, comotambém adicionar novas funções, como explorar as cidades e cavernas.

47

9 Futuro

Ainda existe no jogo algumas possibilidades de expansão. Gostaria de melhoraro código em algumas partes e adicionar o que é dito em 8, em especial a história,ataques especiais e salvar o jogo, já que eu gostaria de ter adicionado no jogoantes da entrega deste trabalho.

Sobre a jogada do computador, penso em criar alguma linguagem simples paraque um usuário possa criar um inimigo mais inteligente. Porém, preciso estudarmais sobre o assunto.

De qualquer forma, a criação do jogo me permitiu aprender vários recursospara a criação de um jogo, como o Ogre e CEGUI, além de outros que não foramusados no projeto, como um motor para física. Durante o desenvolvimento doprojeto tive várias ideias que gostaria de tentar e alguns recursos que gostaria deexplorar.

Referências

[1] Ogre3D. About. Disponível em: http://www.ogre3d.org/about. Acesso em:27 de agosto de 2012.

[2] Wikipédia. Motor gráfico. Disponível em:http://pt.wikipedia.org/wiki/Motor_gráfico. Acesso em: 27 de agostode 2012.

[3] Wikipedia. Game engine. Disponível em:http://en.wikipedia.org/wiki/Game_engine Acesso em: 27 de agostode 2012.

[4] Wikipedia. Dragon Force. Disponível em:http://en.wikipedia.org/wiki/Dragon_Force Acesso em: 27 de agostode 2012.

[5] Wikipedia. CEGUI. Disponível em: http://en.wikipedia.org/wiki/CEGUIAcesso em: 02 de setembro de 2012.

48

[6] Wikipedia. Unity (game engine). Disponível em:http://en.wikipedia.org/wiki/Unity_(game_engine). Acesso em: 15 desetembro de 2012.

[7] Wikipedia. MIT License. Disponível em:http://en.wikipedia.org/wiki/MIT_License. Acesso em: 15 de setembro de2012.

[8] Wikipedia. C++. Disponível em: http://pt.wikipedia.org/wiki/C++. Acessoem: 15 de setembro de 2012.

[9] Wikipedia. Paradigma de programação. Disponível em:http://pt.wikipedia.org/wiki/Paradigma_de_programação. Acesso em:15 de setembro de 2012.

[10] Paulo Feofiloff. Grafos. Disponível em:http://www.ime.usp.br/∼pf/algoritmos_para_grafos/aulas/graphs.html.Acesso em: 15 de setembro de 2012.

[11] Wikipedia. Object Oriented Input System. Disponível em:http://en.wikipedia.org/wiki/Object_Oriented_Input_System. Acessoem: 17 de setembro de 2012.

[12] Wikipedia. Grafos. Disponível em: http://pt.wikipedia.org/wiki/Grafo.Acesso em: 12 de novembro de 2012.

[13] Paulo Feofiloff. Digrafos. Disponível em:http://www.ime.usp.br/∼pf/algoritmos_para_grafos/aulas/digraphs.html.Acesso em: 12 de novembro de 2012.

[14] Paulo Feofiloff. Dijkstra. Disponível em:http://www.ime.usp.br/∼pf/algoritmos_para_grafos/aulas/dijkstra.html.Acesso em: 12 de novembro de 2012.

[15] Paulo Feofiloff. Arborescência. Disponível em:http://www.ime.usp.br/∼pf/algoritmos_para_grafos/aulas/arborescences.html.Acesso em: 27 de novembro de 2012.

49

[16] António Ramires Fernandes. Billboarding Tutorial. Disponível em:http://www.lighthouse3d.com/opengl/billboarding/. Acesso em: 16 denovembro de 2012.

[17] Wikipedia. Licença zlib. Disponível em:http://pt.wikipedia.org/wiki/Licença_zlib. Acesso em: 16 de novembrode 2012.

[18] Wikipedia. Ubuntu (operating system). Disponível em:http://en.wikipedia.org/wiki/Ubuntu_(operating_system). Acesso em:27 de novembro de 2012.

[19] Wikipedia. Blender. Disponível em: http://pt.wikipedia.org/wiki/Blender.Acesso em: 27 de novembro de 2012.

[20] GOMES, J.; VELHO, L.. Fundamentos da Computação Gráfica. 1 ed. Riode Janeiro: Instituto Nacional de Matemática Pura e Aplicada - IMPA, 2008.

[21] GAMMA, E.; HELM, R.; JOHNSON, R.E.; VLISSIDES, J.M.. Design

Patterns: Elements of Reusable Object-Oriented Software. 1 ed. EstadosUnidos: Addison-Wesley, 1995.

[22] Wikipedia. Singleton. Disponível em: http://pt.wikipedia.org/wiki/Singleton.Acesso em: 30 de novembro de 2012.

[23] Augusto Schwartz. Glossário-Termos Gráficos. Disponível em:http://augustoschwartz.blogspot.com.br/2008/05/glossrio-termos-grficos.html. Acesso em: 30 de novembro de 2012.

[24] Wikipedia. Produto vetorial. Disponível em:http://pt.wikipedia.org/wiki/Produto_vetorial. Acesso em: 2 de dezem-bro de 2012.

[25] Wikipedia. XML. Disponível em: http://pt.wikipedia.org/wiki/XML.Acesso em: 2 de dezembro de 2012.

[26] Wikipedia. Viewport. Disponível em: http://en.wikipedia.org/wiki/Viewport.Acesso em: 10 de fevereiro de 2013.

50

[27] Wikipedia. Callback (computer programming). Disponível em:http://en.wikipedia.org/wiki/Callback_(computer_programming). Acessoem: 10 de fevereiro de 2013.

51