UNIVERSIDADE FEDERAL DE SANTA CATARINA
DESENVOLVIMENTO DE UM MOTOR PARA JOGOS 2D
Ewerton Conceição
Florianópolis - Santa Catarina
15 de maio de 2012
UNIVERSIDADE FEDERAL DE SANTA CATARINA
1
DEPARTAMENTO DE INFORMÁTICA E ESTATÍSTICA
CURSO DE CIÊNCIAS DA COMPUTAÇÃO
DESENVOLVIMENTO DE UM MOTOR PARA JOGOS 2D
Ewerton Conceição
Trabalho de Conclusão de Curso apresentado como parte
dos requisitos para a obtenção do grau de Bacharel em
Ciências da Computação.
Florianópolis - Santa Catarina
15 de maio de 2012
Ewerton Conceição
2
DESENVOLVIMENTO DE UM MOTOR PARA JOGOS 2D
Trabalho de Conclusão de Curso apresentado como parte dos requisitos para a
obtenção do grau de Bacharel em Ciências da Computação.
Orientador: Prof. Raul Sidnei Wazlawick
Banca Examinadora
Prof. Antônio Carlos Mariani
Prof. Mauro Roisenberg
3
Sumário
Lista de Figuras
Lista de Acrônimos
Resumo
Abstract
1 Introdução ........................................................................................................... 9
1.1 Objetivos ............................................................................................................................... 10
1.1.1 Objetivo Geral ...................................................................................................................... 10
1.1.2 Objetivos Específicos ............................................................................................................ 10
1.2 Metodologia .......................................................................................................................... 10
1.3 Organização do Trabalho ...................................................................................................... 11
2 Fundamentos .................................................................................................... 12
2.1 Estilos de Jogos ...................................................................................................................... 12
2.2 Funcionamento Básico de um Jogo ....................................................................................... 12
2.3 Organização das Entidades do Jogo ...................................................................................... 13
3 Módulo de Desenho .......................................................................................... 18
3.1 Posicionando os Objetos no Mapa ........................................................................................ 18
3.2 Animações ............................................................................................................................. 19
4 Módulo de Física ............................................................................................... 22
4.1 Detecção de Colisão a Posteriori ........................................................................................... 22
4.2 Detecção de Colisão a Priori .................................................................................................. 23
4.3 Etapas da detecção de colisão .............................................................................................. 23
4.3.1 Etapa Ampla .................................................................................................................. 23
4.3.2 Etapa Específica ............................................................................................................. 24
4.4 Coerência Temporal e Coerência Espacial ............................................................................ 24
4.5 Técnicas de Particionamento do Espaço ............................................................................... 25
4.5.1 Quadtree ....................................................................................................................... 25
4.6 Implementação da Detecção de Colisões no Motor ............................................................. 26
4.7 Implementação do Tratamento de Colisões ......................................................................... 26
4.8 Implementação da Simulação de Física ................................................................................ 27
5 Módulo de Áudio ............................................................................................... 29
6 Módulo de Inteligência Artificial ...................................................................... 31
4
6.1 Comportamento de Agentes Baseado em Objetivos ............................................................ 31
6.1.1 Definições ...................................................................................................................... 31
6.1.2 Uso e Implementação ................................................................................................... 32
6.2 Lógica Difusa.......................................................................................................................... 35
6.2.1 Definições ...................................................................................................................... 35
6.2.2 Uso e Implementação ................................................................................................... 35
7 Considerações Finais ....................................................................................... 39
8 Referências Bibliográficas ............................................................................... 40
5
Lista de Figuras
Figura 2.1 Hierarquia orientada a objetos ................................................................. 14
Figura 3.1 Arquivo texto, contendo as posições dos tiles no mapa ........................... 18
Figura 3.2 Mapa de tiles carregado ........................................................................... 19
Figura 3.3 Sprite usada para fazer o Bomberman andar .......................................... 19
Figura 3.4 Principais classes envolvidas em uma animação .................................... 20
Figura 4.1 Volumes envolventes (Kimmerle, 2005) ................................................... 24
Figura 4.2 Quadtree com profundidade igual a 2 ...................................................... 25
Figura 4.3 Componente de física .............................................................................. 28
Figura 5.1 Diagrama de classes do módulo de sons ................................................. 29
Figura 6.1Diagrama de classes da técnica de comportamento de agentes baseados
em objetivos .............................................................................................................. 33
Figura 6.2 Grau de desejo de se executar um objetivo ............................................. 36
Figura 6.3 Quantidade de pontos de vida ................................................................. 36
Figura 6.4 Distância a um item .................................................................................. 37
6
Lista de Acrônimos
2D Duas dimensões
3D Três dimensões
AABB Axis-aligned Bounding Box
CPU Central Processing Unit
DOP Discrete Oriented Polytope
IA Inteligência Artificial
OBB Oriented Bounding Box
RAM Random Access Memory
RPG Role-playing Game
SPU Synergistic Processing Unit
7
RESUMO
No desenvolvimento de jogos eletrônicos, é interessante reutilizar código-fonte, para que o esforço na criação de novos jogos seja diminuído. Os motores de jogos têm esse propósito. No entanto, não há um motor adotado como padrão. Neste trabalho, foi desenvolvido um motor para a família de jogos com jogabilidade 2D. Para isso, foram desenvolvidos pequenos jogos, verificando-se partes do código-fonte que possam ser extraídas para módulos do motor e serem reutilizadas. Foram criados módulos que tratam da parte gráfica, detecção de colisões, sons e inteligência artificial. Neste trabalho, são discutidos conceitos envolvendo os módulos citados anteriormente bem como conceitos básicos sobre programação de jogos.
8
ABSTRACT
In the development of electronic games, it is interesting to reuse source code, so that the effort to create new games is reduced. The game engines have this purpose. However, there is no standard engine. In this work, it was developed an engine for the family of games with 2D gameplay. Thus, it was developed small games, verifying parts of the source code that can be extracted for modules of the engine and reuse. Modules were created that deal with graphics, collision checking, sound and artificial intelligence. In this work, it is discussed concepts involving the modules mentioned above as well as basic concepts of game programming.
9
1 Introdução
Simplesmente mentalizando o termo genérico “jogo”, podemos pensar em
vários tipos de jogos, como jogos de cartas, esportes e jogos eletrônicos. Quando
usado no contexto de jogos eletrônicos, normalmente o termo jogo vem associado a
mundos 2D ou 3D, contendo um humano, um animal ou um veículo como
personagem principal sob controle de um jogador (Gregory, 2009).
Segundo (Sanches, 2009) um jogo é um aplicativo multimídia que funciona
em tempo real, provendo uma resposta da forma mais rápida possível ao jogador.
Este tem a impressão que o jogo avança como um filme ou uma cena da vida real,
apesar de, na prática, o funcionamento ser diferente.
O termo “motor de jogos” começou a ser usado na década de 1990, fazendo
referência à uma conexão com alguns jogos 3D, como de tiro em primeira pessoa,
como o conhecido Doom, da empresa id Software. A arquitetura do jogo Doom tinha
uma separação bem definida entre os componentes principais do software (como
sistema de renderização de gráficos 3D, sistema de detecção de colisão, sistema de
áudio) e as artes, os mundos, e as regras do jogo (Gregory, 2009).
O valor dessa separação se tornou evidente quando os desenvolvedores
notaram que bastaria criar novas armas, cenários e personagens sem precisar fazer
grandes modificações no motor do jogo. Assim, grande parte do código-fonte de um
jogo poderia ser utilizado novamente em vários outros, como bibliotecas para vários
módulos, fazendo com que o trabalho dos desenvolvedores de jogos fosse
diminuído.
Como durante a criação dos primeiros jogos eletrônicos da história existiam
muitas limitações de hardware, o código-fonte tinha que ser muito bem otimizado.
Não havia separação entre partes do jogo, como parte gráfica e parte física.
Hoje em dia, existem vários motores para jogos. Alguns disponibilizam uma
biblioteca de classes, outros um editor que permite construir um jogo a partir de uma
interface gráfica, e também existem os que disponibilizam as duas formas. Como
exemplo de motores de jogos, podemos citar: Unreal Engine 3, CryENGINE 3, Unity
3D, Torque 3D e RPG Maker.
No entanto, nenhum motor é adotado como padrão para desenvolvimento de
jogos. Geralmente, ou é escolhido um motor que seja fácil de usar, do ponto de vista
10
dos desenvolvedores, e que atenda aos requisitos do jogo que se quer fazer ou cria-
se um novo motor, muitas vezes sendo responsável por apenas um módulo do jogo,
como um módulo de física, por exemplo.
1.1 Objetivos
Procurando limitar e também nortear o escopo do trabalho, foram definidos
objetivos para o desenvolvimento do motor. Esses objetivos serão apresentados a
seguir, de forma geral e específica.
1.1.1 Objetivo Geral
Desenvolver um motor para jogos 2D, contendo uma biblioteca multiplataforma
desenvolvida em C++ que facilite a criação de jogos.
1.1.2 Objetivos Específicos
1. Desenvolver uma biblioteca que deve conter módulos que tratem da parte
gráfica, de detecção de colisões, de sons e de inteligência artificial;
2. Comparar técnicas de detecção de colisão em duas dimensões para
otimizar o detector de colisões;
3. A biblioteca deve poder ser usada tanto para criar jogos com jogabilidade
em perspectiva top-down, como para a jogabilidade com rolagem lateral;
4. Verificar na prática os desafios envolvidos na criação de um motor de
jogos.
1.2 Metodologia
Cada família de jogos tem certos requisitos específicos que, muitas vezes, só
são descobertos desenvolvendo pequenos protótipos. Alguns requisitos são comuns
a alguns tipos de jogos, como detecção de colisão e animações, podendo ser
diferente a forma como deve ser implementado (colisão em 2D e em 3D, por
exemplo).
11
Um problema na criação de motores de jogos é tentar fazer o maior motor
possível. No artigo Starting out on Game Programming do site Lazy Foo
Productions, o autor conta que queria fazer uma IA para um jogo da velha que fosse
imbatível. Ele a fez de uma forma que pudesse vencer cada armadilha possível.
Para isso, ele precisou de quarenta mil linhas de código, sendo que a maioria do
código foi copiado e colado, gastando um mês do seu tempo. Depois que ele
descobriu o algoritmo Minimax, viu que poderia ter feito de uma forma melhor e com
muito menos código.
Considerando o problema acima, o desenvolvimento do motor foi feito com
base em protótipos, que são pequenos jogos. Desses jogos, foram retirados os
requisitos do motor. Partes de código que podem reusadas em outros jogos
ajudaram a compor os módulos do motor. O código foi escrito de forma que fosse
flexível e sem adicionar coisas desnecessárias, até o momento em que realmente
seja preciso adicioná-las.
1.3 Organização do Trabalho
O capítulo 2 fala sobre fundamentos dos jogos. O capítulo 3 mostra como foi
feito o módulo de desenho e detalha conceitos sobre animações. O capítulo 4 trata
do módulo de física e explica a detecção de colisões. O capítulo 5 expõe o módulo
de áudio. O capítulo 6 fala sobre o módulo de IA. O capítulo 7 mostra as
considerações finais.
12
2 Fundamentos
2.1 Estilos de Jogos
Existem vários estilos de jogos. De acordo com (Fernandes, 2002), alguns
deles são:
Estratégia em tempo real: normalmente são jogos de batalha, em que o
jogador comanda exércitos, suprimentos, acampamentos e recursos para
superar grupos adversários, como acontece no popular Age of Empires;
Estratégia baseada em turnos: as batalhas ocorrem em tempos
espaçados para que as ações sejam realizadas, o que nos dá tempo para
pensar, mas não diminui a ação. Tornaram-se populares com o
surgimento dos RPGs;
Tiro em primeira pessoa: o jogador controla um personagem, que pode
ser um soldado, por exemplo, e pode usar diversos tipos de armas para
matar os inimigos, como no jogo Battlefield;
Plataformas: conta com rolagem lateral, em que o personagem principal
passa por fases, podendo encontrar um chefe final em cada fase. Como
exemplo podemos citar vários jogos da franquia Super Mario;
Simulação: são jogos que imitam a realidade, simulando corridas de
carros, futebol, voo, entre outros;
RPGs: são jogos que podem conter um ou mais de outros estilos citados
acima. Sua principal característica está no fato de os personagens
possuírem um nível, que aumenta conforme vão ganhando experiência.
Como exemplo, podemos citar jogos da franquia Final Fantasy.
2.2 Funcionamento Básico de um Jogo
Para que um jogador tenha a sensação de que o jogo está fluindo
naturalmente, o processamento dos comandos do jogador, da lógica do jogo e a
atualização da tela tem que ser feitos de forma rápida e sincronizada. Para fazer
isso, um jogo possui o loop principal, responsável pela atualização do jogo, seguindo
os quatro passos abaixo:
13
1. Ler entradas do mouse e teclado;
2. Atualizar os objetos do jogo;
3. Desenhar a cena a partir dos objetos atualizados;
4. Voltar para o passo 1 caso o jogo não tenha sido finalizado.
O jogo é atualizado de forma discreta e a velocidade de atualização dos
objetos é fixa, de acordo com a taxa de quadro por segundo informada. Devido aos
monitores trabalharem, normalmente, com uma taxa de atualização de 60 quadros
por segundo, é comum essa taxa ser usada para atualizar um jogo. Se a taxa de
atualização for maior que o suportado pelo monitor, alguns quadros serão
descartados, mesmo tendo feito todo o processamento necessário para gerá-los.
Por isso, é interessante limitar a taxa de atualização, diminuindo o consumo de CPU
nos jogos em que se poderia ter uma taxa maior.
2.3 Organização das Entidades do Jogo
Cada jogo possui diferentes tipos de entidades, cada uma responsável por
certas tarefas. Normalmente, as entidades são visíveis ao jogador, ocupando algum
lugar no mundo e algumas podem se locomover. Pensando num jogo de aventura,
podemos imaginar algumas possíveis entidades:
Herói;
Inimigo;
Espada;
Arma de fogo;
Carro;
Submarino;
Barco.
A forma tradicional de representar as entidades de um jogo como esse é fazer
uma decomposição orientada a objetos das classes necessárias para o
funcionamento das entidades. Isso geralmente começa com boas intenções, mas é
frequentemente modificado com o progresso de desenvolvimento do jogo,
principalmente se um motor de jogo é usado novamente para criar um jogo diferente
(West, 2007).
14
A figura 2.1 mostra uma possível representação de uma hierarquia orientada
a objetos do jogo de aventura mostrado anteriormente:
Figura 2.1 Hierarquia orientada a objetos
Esse tipo de hierarquia, com uma profunda cadeia de heranças, tende a
possuir uma classe na raiz e nas folhas as classes representando entidades mais
concretas, que são, comumente, visíveis ao jogador. Num jogo real, a hierarquia
tende a ser bem mais profunda e complexa, envolvendo animações, corpos rígidos e
outros componentes, deixando, muitas vezes, as classes das folhas com muitos
métodos que foram herdados e que nunca serão chamados, ou seja, são
funcionalidades desnecessárias que estão numa determinada classe devido à
profunda cadeia de heranças.
Mesmo com esse exemplo simples, outro problema pode ser detectado. É
comum, nos jogos, haver uma variação grande dos requisitos, pois ideias de como
melhorar o jogo podem surgir no meio do desenvolvimento do mesmo. Suponhamos
que, no exemplo do jogo de aventura apresentado anteriormente, alguém teve a
ideia de criar um veículo anfíbio. A hierarquia envolvendo o veículo anfíbio pode ser
vista na figura 2.2, que é uma forma clássica de ilustrar um problema da herança
múltipla, quando uma classe estende a outra duas vezes.
Profundas hierarquias de heranças tendem a criar problemas de
desempenho. Eles ocorrem quando for necessário chamar o construtor de uma
15
classe derivada, tendo que invocar o construtor das classes bases, o que faz o uso
de recursos pesados (Flynt; Salem, 2004).
Figura 2.2 Herança Múltipla.
Outra abordagem para representar os objetos do jogo é uma agregação de
componentes. Uma forma de fazer isso é considerar uma entidade como sendo uma
soma de componentes. Cada entidade poderia ter como componentes um corpo
rígido para representar a sua física e um componente de animação para cuidar da
sua representação visual, por exemplo. Esse é um modelo simples, porém não é o
mais adequado e pode ser melhorado (Flynt; Salem, 2004).
Para explicar melhor o modelo de componentes, o passo 2 do loop principal
será detalhado agora. Primeiro, consideremos que o jogo possui um conjunto de
entidades, cada uma com seus componentes. O jogo pode ser atualizado conforme
o procedimento abaixo, em pseudocódigo:
Jogo::atualizar(real tempo)
início
1. Para cada e ϵ jogo.entidades faça
a. Para cada c ϵ e.componentes
i. c.atualizar(tempo)
fim
16
O procedimento acima é bastante simples, mas existe outra forma para usar o
modelo de componentes e que é superior à primeira, a atualização em lotes. Nesse
modelo, ao invés das entidades atualizarem todos os seus componentes, cada
conjunto de um dado tipo de componente deve ser atualizado de uma vez só. Uma
classe gerenciadora pode ser criada para cada tipo de componente para realizar a
tarefa de atualização. Considerando que certo jogo possui apenas os componentes
de física e de animação, o passo 2 do loop principal e o método atualizar na classe
que gerencia os componentes ficariam assim:
Jogo::atualizar(real tempo)
início
1. gerenteDeFísica.atualizar(tempo)
2. gerenteDeAnimação.atualizar(tempo)
fim
GerenteDeComponentes::atualizar(real tempo)
Início
1. Para cada c ϵ componentes
a. c.atualizar(tempo)
fim
A atualização em lotes traz vários benefícios. De acordo com (Gregory,
2009), alguns deles são:
Máxima coerência na memória cache: os dados de um subsistema do
motor são mantidos internamente e podem ser arranjados numa região
única e contígua da memória RAM, o que leva a máxima coerência
possível na memória cache;
Pipeline eficiente: recursos de hardware especializados podem ser
usados de forma mais eficiente, ganhando mais uma otimização. Como
exemplo, podemos citar o Playstation 3, que possui um conjunto de
microprocessadores de alta velocidade, chamados de SPUs, cada um
com sua área de memória de alta velocidade. Enquanto se processa um
lote de animações, a pose de um personagem pode ser calculada e, ao
mesmo tempo, os dados do próximo personagem são acessados
diretamente na memória da SPU. Processando cada entidade
isoladamente não seria atingido esse nível de paralelismo;
17
Alguns subsistemas não funcionam adequadamente isolados: uma
solução satisfatória para resolver se vários corpos rígidos estão colidindo
não pode ser achada, geralmente, se os objetos forem tratados
isoladamente. As colisões entre os objetos devem ser resolvidas em
grupo, através de uma abordagem iterativa ou resolvendo um sistema de
equações lineares, por exemplo.
18
3 Módulo de Desenho
O motor de jogos desenvolvido contém um módulo responsável por desenhar
os objetos visíveis ao jogador e também realizar animações. Para tornar o módulo
de desenho mais completo, foi usada a biblioteca Guichan, que contém
componentes mais básicos de desenho como áreas de texto, rótulos, botões, entre
outros.
3.1 Posicionando os Objetos no Mapa
Nos jogos 2D, duas formas comuns de jogabilidade são a rolagem lateral e a
perspectiva top-down. Na primeira, a câmera fica posicionada lateralmente e os
personagens se movem de um lado para o outro. Na segunda, também conhecida
como bird’s-eye view, a câmera mostra o jogador e a área em torno dele vistos de
cima. Para que se atenda a essas duas formas de jogabilidade, os objetos que
podem ser desenhados possuem como posição um ponto no mundo.
Outra forma possível para representar a posição dos objetos é usar um mapa
de tiles. Segundo (Fernandes, 2001), um tile é um desenho pequeno, que se
caracteriza por ser sequencial consigo mesmo. Assim, colocando-se vários
desenhos iguais, lado a lado, formam uma única imagem, sem cortes. São ideais
para representar chãos, florestas ou elementos estáticos de um jogo.
Figura 3.1 Arquivo texto, contendo as posições dos tiles no mapa
No protótipo do jogo Bomberman, foi implementado um mapa de tiles. Para
formar um mapa de tiles, geralmente, usa-se um arquivo que mostra as posições
dos tiles no mapa (como na figura 3.1). Cada número representa um tile, que será
19
associado com uma imagem na hora de carregar o mapa. O resultado do
carregamento de um mapa 15x13 pode ser observado na figura 3.2.
Figura 3.2 Mapa de tiles carregado
Por ser mais simples de gerenciar todos os objetos de desenho fazendo com
que eles tenham uma posição no mapa, o mapa de tiles não foi incluído no módulo
de desenho.
3.2 Animações
O processo para fazer uma animação em duas dimensões é simples. Pode-se
pegar um conjunto de imagens que determinam certa movimentação e exibi-las,
sendo que uma nova imagem é exibida de acordo com a taxa de quadros por
segundo.
Figura 3.3 Sprite usada para fazer o Bomberman andar
Por se tratar apenas de exibir imagens com certo “atraso” entre uma e outra
exibição, esse processo pode ser facilmente automatizado para qualquer animação
2D. Só é preciso definir quais são as imagens, a ordem em que serão exibidas e a
taxa de quadros por segundo.
20
No jogo Bomberman, para fazer o personagem se movimentar é usada uma
sprite que possui as imagens da movimentação do mesmo (figura 3.3). Sprites são
as imagens dos objetos do jogo, desenhadas em todos os seus quadros de
animação (Fernandes, 2002). Quando são mostrados sequencialmente, dão uma
sensação de movimento. Quanto mais quadros tiver uma sprite, mais perfeito fica o
movimento.
Figura 3.4 Principais classes envolvidas em uma animação
O módulo de desenho armazena um conjunto de visões das entidades do
jogo. Cada visão pode ter vários objetos desenháveis associados, mas apenas um
será exibido. Um objeto desenhável representa o desenho uma ação do
personagem, que pode ser andar, correr, saltar, entre outras. Cada objeto
desenhável pode ter um componente associado. Esse componente possui um
método update, que será responsável por atualizar o objeto. No caso das
21
animações, há uma classe chamada Animation, que implementa a interface
Component.
A classe Animation faz uma animação sempre da esquerda para a direita. No
entanto, caso um usuário do motor queira fazer a animação de outra maneira ou
criar outro tipo componente, basta que implemente a interface Component do jeito
que desejar. O diagrama da figura 3.4 dá uma visão geral do módulo de desenho.
22
4 Módulo de Física
O módulo de física foi feito, principalmente, para atender ao objetivo de tratar
colisões entre corpos. Porém, em quase todos os jogos, objetos se movem ou
realizam alguma ação em que uma simulação de física é necessária. Assim, foi
definida uma arquitetura que permite a criação de componentes para simular ações
de física, a qual será detalhada no final do capítulo.
Cada entidade pode possuir um corpo rígido associado, para tratar das
ações de física e da detecção de colisão. Segundo (Flynt; Salem, 2004), corpos
rígidos são interessantes de serem usados em jogos porque são perfeitamente
sólidos e não são deformáveis. Isso simplifica a matemática envolvida para simular
os objetos.
Ações que ocorrem em um jogo podem, normalmente, ser representadas por
colisões entre dois ou mais corpos. A detecção de colisões é um fator crítico nos
jogos, devido a três grandes problemas: o alto custo computacional, pois quando se
precisa testar todos os objetos contra todos a complexidade é O(n²); objetos que
podem mover-se muito rapidamente, como projéteis, por exemplo; e objetos que
possuem geometria complexa, como personagens (Ferreira; Ferreira, 2009). A
seguir, serão detalhadas formas de detecção de colisão e métodos para fazê-la de
forma eficiente.
4.1 Detecção de Colisão a Posteriori
A detecção de colisão a posteriori testa se a colisão já ocorreu. A cada passo
da simulação é testado se um objeto tem intersecção com outro. Se tiver, há uma
colisão. É um teste discreto, pois testa apenas um momento no tempo.
Esse teste é mais comum, porém é menos preciso. Um problema dele pode
se manifestar quando dados dois corpos, pelo menos um corpo tem uma velocidade
muito alta e pelo menos um deles seja um corpo pequeno. Dependendo da
velocidade e do tamanho do corpo, como o teste é discreto, pode acontecer de um
corpo atravessar o outro e o teste vai falhar. A solução para o problema acima é
usar uma restrição. A velocidade máxima de um objeto multiplicada pelo passo de
23
tempo de atualização deve ser menor que o tamanho do menor objeto. Para garantir
isso, deve-se reduzir a velocidade máxima ou o passo do tempo de atualização.
Outro problema dessa técnica é permitir sobreposições dos objetos. Quando
uma colisão é detectada, a posição dos objetos deve ser corrigida. Corrigir a posição
dos objetos a fim de tornar a simulação real pode ser complicado. Um método
simples é apenas retornar os objetos para as posições que tinham no passo de
atualização anterior. Esse método funciona bem se os corpos não tiverem
velocidade alta e se o intervalo de atualização não for muito alto. Assim, apesar de
fisicamente incorreto, o tratamento de colisão é imperceptível ao jogador, pois a
posição anterior dos corpos vai ser muito próxima da posição atual.
4.2 Detecção de Colisão a Priori
Uma técnica de detecção de colisão a priori prevê quando uma colisão vai
ocorrer. Com uma técnica a priori, a simulação é avançada até o tempo em que a
colisão vai ocorrer, impedindo que os objetos se sobreponham. Ela é mais realista e
resolve os problemas das técnicas a posteriori, no entanto tem implementação mais
complexa e, geralmente, é usada em jogos em que não se pode ter uma restrição de
velocidade ou do passo máximo do tempo de atualização.
4.3 Etapas da detecção de colisão
Normalmente, as técnicas de detecção de colisão de dividem em duas
etapas. Numa etapa inicial, os objetos são testados aos pares com um método
menos preciso, determinando se há uma chance de estarem colidindo. A segunda
etapa pega os pares da etapa inicial e testa, usando um algoritmo preciso, se há
colisão. As duas etapas serão detalhadas a seguir.
4.3.1 Etapa Ampla
Como foi dito anteriormente, nesta etapa é usado um método menos preciso.
Podem ser usados volumes envolventes para otimizar o teste. A figura 4.1 mostra
tipos de volumes envolventes. Quanto mais para a direita, mais precisa é a
aproximação, porém os custos de atualização, de construção e de realização do
24
teste de colisão se tornam maiores. Quanto menor a precisão do teste, maior é a
chance dele retornar falsos positivos, porém nos casos em que os volumes
envolventes dos objetos não colidem nessa etapa não é preciso usar o teste com
precisão máxima. É aí que está o grande benefício dessa etapa, que é não gastar
tempo usando um teste totalmente preciso (que é computacionalmente caro)
verificando se há colisão com objetos que estão muito distantes entre si.
Figura 4.1 Volumes envolventes (Kimmerle, 2005)
4.3.2 Etapa Específica
A etapa específica recebe os pares candidatos a estarem colidindo obtidos
na etapa ampla. Nessa etapa, é usado um algoritmo preciso para verificar se os
objetos estão realmente colidindo. Aqui, dependendo da forma do objeto, um teste
computacionalmente caro pode ser necessário, mas considerando que o número de
pares testados será muito menor do que a complexidade O(n²), é possível usar o
teste sem causar um grande impacto negativo na fluência do jogo.
4.4 Coerência Temporal e Coerência Espacial
Uma técnica de detecção de colisão que leve em consideração a coerência
espacial vai buscar melhorias de desempenho a partir do princípio de que objetos
distantes entre si não colidem, logo o número de pares de objetos colidindo num
certo instante de tempo tende a ser menor do que o máximo de colisões possíveis.
Já a coerência espacial leva em conta que os objetos se movem relativamente
pouco entre os períodos de atualização. Dessa forma, um objeto que está colidindo
tende a estar colidindo na próxima atualização e os que não estavam tendem a não
estar (Rocha, 2010).
25
4.5 Técnicas de Particionamento do Espaço
A fim de tirar proveito da coerência espacial, o espaço pode ser particionado
em várias células. Ele é dividido recursivamente para se criar uma estrutura
hierárquica que minimize a quantidade de testes. Consequentemente, só é
necessário aplicar o teste de colisão numa mesma célula (Ferreira; Ferreira, 2009).
Várias são as formas de particionamento do espaço. Entre elas, podemos destacar
octrees, árvores BSP, kd-tree e árvores esféricas (Gregory, 2009).
Dividir um espaço em quadrantes é uma forma de particionar o espaço. Num
mundo 3D, se usaria uma octree, num mundo 2D uma quadtree. Como o escopo
deste trabalho se limita a ambientes 2D, a técnica de quadtree será abordada a
seguir.
4.5.1 Quadtree
O termo quadtree é comumente usado para se referir a uma classe de
estruturas hierárquicas com uma propriedade em comum, que é a decomposição
recursiva do espaço (Ferreira; Ferreira, 2009). Elas usam o conceito de estrutura de
dados em árvore, sendo que cada nodo pode ter até quatro filhos, dependendo da
implementação. Existem variações de quadtree em que cada nodo tem exatamente
quatro filhos, com exceção das folhas da árvore.
Figura 4.2 Quadtree com profundidade igual a 2
Uma quadtree divide o espaço em quatro partes iguais, recursivamente, até
que se alcance o tamanho desejado. A figura 4.2 mostra uma quadtree com
profundidade igual a dois. Os objetos são adicionados no quadrante em que
26
estiverem contidos. Se um objeto for maior que o menor quadrante da quadtree,
tenta-se colocá-lo num nodo pai que o contenha. A única exceção é o nodo raiz, em
que basta que ele tenha intersecção com objeto, evitando que o mesmo fique fora
do espaço.
Além da coerência espacial, esta estrutura também tira proveito da coerência
temporal, pois como os objetos tendem a estar próximos das suas posições atuais
nas atualizações seguintes, a atualização dos objetos na quadtree é facilitada,
bastando perguntar se o objeto está contido no nodo atual. Apenas se ele não
estiver contido terá de ser removido e colocado em outro nodo, o que é uma
operação custosa, se tiver de ser aplicada em muitos objetos a cada atualização.
4.6 Implementação da Detecção de Colisões no Motor
A gerência da física é feita pelo gerente de física. Ele possui uma instância
do mundo e este último contém um espaço. O espaço está representado na forma
de uma interface que contém métodos para adicionar, remover e atualizar corpos
rígidos e obter os objetos que estão em estado de colisão. Dessa forma, uma
técnica a priori ou a posteriori pode ser anexada ao módulo de física, simplesmente
implementando a interface Space.
Foram implementados dois espaços, ambos usando-se de técnicas a
posteriori: um genérico, que tem de fazer n² testes (considerando n o número de
corpos) para saber se os corpos estão colidindo, com a única melhoria de possuir
uma etapa ampla e uma específica; e outro que representa uma quadtree, conforme
foi descrita na seção 4.5 e considerando cada nodo sempre com quatro filhos, com
exceção das folhas.
4.7 Implementação do Tratamento de Colisões
Quando colisões ocorrem nos jogos, é provável que algo aconteça com as
entidades envolvidas na colisão. Se um personagem colidiu com uma flecha,
possivelmente ele deve perder certa quantidade de vida, dependendo do jogo. Se
um personagem empurrou uma pedra de um penhasco, ela pode receber a força
aplicada pelo personagem e, de acordo com sua massa, ganhar certa aceleração e
27
começar a se mover. Logo, as entidades envolvidas nas colisões devem ser
avisadas para que certas ações sejam tomadas.
Para fazer isso, o mundo recebe todas as colisões calculadas pelo seu
espaço e avisa ao gerente de entidades que uma colisão ocorreu. Foi permitido que
um corpo rígido não pertencesse a uma entidade, sendo usado apenas no módulo
de física. O gerente de entidades verifica se os dois corpos rígidos envolvidos numa
colisão pertencem a uma entidade. Se ambos são parte de entidades, elas são
avisadas que a colisão ocorreu, através do envio de uma mensagem, feito pelo
gerente de mensagens, e tomam as ações que forem necessárias, inclusive se
forem apenas ações físicas, como no caso de empurrar uma pedra, citado
anteriormente. Se apenas um dos corpos pertencer a uma entidade, a entidade é
avisada sobre com qual corpo ela colidiu. Se ambos os corpos não pertencerem a
uma entidade, apenas é tratada a sobreposição dos corpos, no caso de se fazer uso
de uma técnica a posteriori.
4.8 Implementação da Simulação de Física
Apesar do foco do motor de física neste trabalho ser a detecção de colisões,
é comum que jogos possuam elementos que se encaixem numa simulação de física.
Para se adequar a essa exigência dos jogos, foi implementada uma estrutura que
permite que ações físicas, como simulação de movimentos dos corpos, fossem
representadas.
Foi criada uma classe abstrata a qual representa um componente de física
que pode ser especializado em alguma ação de física sobre certo conjunto de
objetos do jogo. Uma ação física que foi predefinida no módulo de física foi um
movimento.
Há uma classe chamada Movable que estende o componente de física e
possui uma instância de uma classe que implemente a interface Motion, que
representa um movimento. No método update da classe Movable, todos os corpos
rígidos que possuam um mesmo tipo de movimento terão suas posições atualizadas,
a cada quadro do jogo. A figura 4.3 mostra o diagrama de classes para o
componente Movable.
28
Figura 4.3 Componente de física
29
5 Módulo de Áudio
O módulo de áudio foi implementado usando a biblioteca SDL_Mixer. Seu
uso é bastante simples, sendo que o usuário precisa conhecer alguns conceitos
sobre áudio, para que possa saber como passar os parâmetros de inicialização. Os
parâmetros são detalhados a seguir:
Figura 5.1 Diagrama de classes do módulo de sons
Frequência: frequência de saída das amostras, em Hertz. Segundo a própria
documentação da biblioteca, o valor de 22050 Hz é adequado para jogos,
embora se possa querer outro valor, como 44100 Hz, que dá a qualidade de
CD ao som, mas que exige muito mais poder de processamento;
30
Formato: define a quantidade de bits de saída das amostras de som. São
permitidos os formatos de 8 bits e 16 bits;
Canais: define a quantidade de canais da saída de som, sendo que 2 canais
fazem o som ser estéreo e 1 faz o som ser mono;
Tamanho do buffer: tamanho de cada amostra mixada, em bytes. Deixando
este valor muito pequeno, o som poderá ter cortes. Se for grande demais, o
som poderá ter atrasos. 1024 bytes costuma ser um bom valor quando muitos
sons precisarem ser mixados;
Canais de mixagem: define a quantidade de canais usados para a mixagem.
Quanto mais canais, mais processamento será preciso para mixar todos os
sons.
Para carregar um som basta instanciar um objeto da classe Sound,
informando o nome do arquivo que contém o som. O gerente de áudio vai carregar o
som, se o mesmo ainda não tiver sido carregado. Isso impede que o mesmo som
seja carregado várias vezes. A classe Sound contém métodos para tocar um som,
pausar um som, continuar um som, parar um som e também definir o volume de um
som. A figura 6.1 mostra o diagrama de classes do módulo de som.
31
6 Módulo de Inteligência Artificial
O projeto da parte de inteligência artificial de um jogo é um ponto delicado.
Um jogo com uma IA que sempre vence vai deixar o jogador frustrado. Porém, se o
jogador sempre vencer facilmente, o jogo perderá a graça logo. Para (Buckland,
2005), a IA de um jogo deve entreter o jogador, oferecendo boas batalhas, fazendo
com que o jogador vença mais vezes do que a máquina e sinta-se poderoso, astuto,
inteligente e esperto.
As ações de cada personagem podem ser bem específicas de acordo com
cada jogo, tornando-se difíceis de serem reusadas. Foram isolados, para compor o
módulo de IA, duas técnicas que podem ser usadas para simular a inteligência de
um personagem. Uma é a de comportamento de agentes baseado em objetivos e
outra é lógica difusa. Ambas as técnicas serão detalhadas a seguir, bem como suas
respectivas implementações no módulo de IA.
6.1 Comportamento de Agentes Baseado em Objetivos
6.1.1 Definições
Não há um consenso na definição do que é um agente. (Wooldridge, 2002)
define um agente como um sistema computacional situado em um ambiente e que é
capaz de realizar ações autônomas nesse ambiente a fim de atingir seus objetivos.
Outra definição, que muitos pesquisadores de agentes consideram aceitável,
conforme (Bradshaw, 1997), diz que um agente é uma entidade de software, que
funciona de forma autônoma e contínua em um determinado ambiente, o qual pode
conter outros agentes, e que seja capaz de interferir no seu ambiente de uma
maneira flexível e inteligente, sem precisar de orientação humana constante.
O comportamento dos agentes pode ser definido por uma coleção de
objetivos hierárquicos, que podem ser compostos ou atômicos. Um objetivo atômico
é a representação de uma tarefa, ação, ou comportamento simples, enquanto que
um objetivo composto representa uma tarefa mais complexa e é feito de vários
outros objetivos, que por sua vez podem ser compostos ou atômicos, definindo uma
32
hierarquia aninhada. Além disso, os objetivos devem ter a capacidade de monitorar
seu estado e fazer um replanejamento caso falhem (Buckland, 2005).
Um agente com comportamento dirigido por objetivos tenta imitar o
comportamento humano, examinando estratégias de alto nível (objetivos compostos)
e selecionando a que mais se adequar a certa situação. No caso dos jogos, um
personagem pode possuir uma série de objetivos, sendo que ele vai selecionar o
que for mais desejável para ele, baseado no estado atual do jogo. Normalmente,
“ser mais desejável” implica em vencer o jogo. O objetivo de alto nível escolhido será
decomposto em outros, que serão satisfeitos um de cada vez. O objetivo pode falhar
ou pode ser satisfeito e o estado do jogo pode mudar. Tais acontecimentos podem
fazer o personagem repensar seus objetivos e alterar sua estratégia.
6.1.2 Uso e Implementação
A figura 6.1 mostra o diagrama de classes para a técnica de comportamento
de agentes baseados em objetivos que foi implementada no módulo de IA. Um
objetivo composto pode ser criado especializando a classe CompositeGoal. Criar um
objetivo atômico é feito simplesmente especializando a classe Goal. Cada objetivo
contém um método abstrato para obter o quão desejável é de ele ser ativado num
dado momento do jogo. A escolha de qual objetivo ativar é feita pela classe Brain.
Cada entidade que deseja ter seu comportamento dirigido por objetivos deve criar e
adicionar uma instância da classe Brain ao gerente de IA, que quando atualizado
pedirá a todos os cérebros das entidades para que façam a seleção do melhor
objetivo a ser perseguido e o execute.
A forma do cálculo do quão desejável é um objetivo ser executado é um
ponto chave na definição dos objetivos. É interessante que todos os valores do
desejo de executar um objetivo estejam padronizados num intervalo, por exemplo,
de 0 a 1, assim como os valores necessários para calcular o desejo. Dessa forma a
comparação entre os valores fica facilitada (Buckland, 2005).
Um exemplo será dado para mostrar o funcionamento da escolha dos
objetivos, considerando um jogo de aventura em que guerreiros lutam entre si para
ver quem é o mais forte. O intervalo de possíveis valores para o desejo de se
executar um objetivo será [0,1]. Os guerreiros possuem duas armas: uma espada e
um arco-e-flecha. Eles possuem também uma quantidade de pontos de vida e uma
33
quantidade de flechas. No cenário, podem surgir itens que aumentam a quantidade
de pontos de vida ou de flechas. Alguns objetivos possíveis para eles seriam:
Figura 6.1Diagrama de classes da técnica de comportamento de agentes baseados
em objetivos
1. Aumentar pontos de vida: o personagem procura pelo item mais próximo
que aumente seus pontos de vida, planeja um caminho até ele e o segue;
2. Atacar um inimigo com a espada: o personagem se dirige ao inimigo e o
ataca com a espada;
3. Atacar um inimigo com arco-e-flecha: o personagem se posiciona de
forma a acertar uma flechada no inimigo e atira a flecha;
4. Explorar mapa: o personagem escolhe um ponto do mapa, traça um
caminho até ele o segue;
5. Fugir: o personagem procura uma rota de fuga e a segue.
34
Para calcular o quão desejável é do objetivo 1 ser executado, podemos
pensar que procurar por vida é proporcional a quantidade de pontos de vida que o
personagem possui e é inversamente proporcional à distância do item que lhe dará
mais pontos de vida. A fórmula a seguir mostra a relação do desejo de aumentar os
pontos de vida em função da quantidade de pontos de vida atual e da distância do
personagem ao item:
A fórmula acima funciona porque quanto menos pontos de vida o
personagem possuir, maior será o valor do desejo de ir procurar um item que
aumente sua vida. Para a distância, podemos limitar um valor como sendo o máximo
que um personagem irá percorrer para pegar um item. Se a distância entre um
personagem e um item for maior ou igual à distância máxima, então o valor 1 será
usado na fórmula, o que fará o desejo diminuir. Quanto mais próximo de 0 estiver o
valor da distância, maior será o valor do desejo. Tratar a divisão por 0 dependeria
das regras do jogo. Se basta que um personagem toque em um item para pegá-lo, a
distância calculada nunca seria 0, pois o personagem já teria pegado o item. No
entanto, alguns jogos assumem que um comando deve ser dado ao personagem
para que ele pegue o item, mesmo que ambos ocupem a mesma posição. Nesse
caso, apenas seria retornado o valor 1, que representa o maior grau de desejo.
A divisão pode retornar um valor maior que 1. Para que se possam comparar
os graus de desejo da mesma forma, deve ser feito um procedimento que faça com
que o valor volte ao intervalo [0,1]. Esse procedimento depende dos valores
máximos das variáveis que representam os pontos de vida e a distância até um item,
sendo um cuidado a mais que deve ser tomado ao usar esse método.
O grau de desejo dos outros objetivos pode ser obtido de forma análoga ao
que foi feito para se calcular o desejo de ir procurar um item de vida. Para atacar um
inimigo com a espada, pode-se levar em consideração que o ataque será feito com o
personagem muito próximo do inimigo. Logo, quanto menos pontos de vida, mais
arriscada é essa estratégia. Também se pode levar em conta a distância entre os
dois, pois se ela for muito grande pode não valer a pena ir até o inimigo para atacá-
lo. Um ataque com o arco-e-flecha pode levar em consideração apenas a distância,
pois não é necessário se aproximar demais do inimigo e com isso a chance de sofrer
um ataque e perder pontos de vida é menor.
35
Para o objetivo de explorar o mapa, pode-se atribuir um valor constante e
baixo. Assim o personagem só vai explorar o mapa quando não tiver que se
preocupar com outras ações.
O objetivo de fuga pode ser ativado considerando-se a quantidade de pontos
de vida e a distância do item mais próximo que aumente sua vida. Espera-se que o
objetivo escolhido seja aumentar os pontos de vida, mas pode acontecer de não
haver um item disponível ou de ele estar muito longe, o que leva um personagem
que está prestes a morrer a ter que fugir para que possa ter uma chance de
sobreviver.
6.2 Lógica Difusa
6.2.1 Definições
Normalmente, quando as pessoas se comunicam costumam usar termos
linguísticos com algum grau de imprecisão. Apesar disso, as pessoas conseguem se
entender e realizar suas tarefas sem necessitar de uma precisão perfeita e formal.
Fazer uma máquina entender as variáveis linguísticas humanas seria um jeito mais
natural de se fazer a comunicação entre o homem e a máquina.
A lógica difusa foi inventada por Lofti Zadeh e permite a um computador
reagir a regras e termos linguísticos de um jeito similar ao dos humanos. Definições
como “distante”, “fraco” e “ligeiramente” não são representados por intervalos
discretos, mas por conjuntos difusos, permitindo que valores sejam atribuídos a
conjuntos considerando seu grau de pertinência. Esse processo é chamado de
fuzificação. Usando valores difusos, um computador interpreta regras linguísticas e
produz uma saída que ainda permanece difusa, mas que pode ser defuzificada,
como normalmente é usada nos jogos. Esse processo é conhecido como inferência
difusa e é o mais popular uso da lógica difusa (Buckland, 2005).
6.2.2 Uso e Implementação
É possível usar a lógica difusa combinada com o método de comportamento
de agentes baseados em objetivos. Ela poderia ser usada para implementar o
36
método getDesirability, nas classes filhas de Goal e CompositeGoal. Como
determinar o quão desejável é de um objetivo ser executado simplesmente
baseando-se em atributos do jogo e expressões matemáticas não é uma tarefa fácil,
usar a lógica difusa para fazê-lo pode ser um jeito mais intuitivo e natural,
principalmente para desenvolvedores iniciantes, bastando-se apenas que sejam
definidos os conjuntos difusos e as regras para a inferência difusa.
Figura 6.2 Grau de desejo de se executar um objetivo
Figura 6.3 Quantidade de pontos de vida
Considerando o exemplo da seção 6.1.2 e o objetivo 1 lá definido, será
explicado o que seria necessário definir para calcular o grau de desejo usando lógica
difusa. Primeiro, devem ser definidas as variáveis linguísticas difusas. Para este
exemplo, precisa-se de uma variável que represente o grau de desejo de execução
do objetivo, uma que represente a quantidade de pontos de vida do personagem e
outra que represente à distância do personagem ao item mais próximo que aumente
sua vida.
37
Figura 6.4 Distância a um item
Para a variável “grau de desejo”, pode-se ter em mente que ela assume um
valor no intervalo [0, 100]. Podemos definir três termos: desejável, indesejável, muito
desejável. A figura 6.2 ilustra os conjuntos associados aos termos. Para a variável
“pontos de vida”, vamos assumir que um personagem tem, no máximo, 200 pontos
de vida. Ela pode ser definida com os termos “alto”, “normal” e “baixo”, conforme a
figura 6.3. A variável distância pode ser definida pelos termos “perto”, “média” e
“longe”, como foi feito na figura 6.4.
As regras que definem o grau de desejo de se executar o objetivo de
procurar um item de vida são definidas abaixo:
Se a quantidade de pontos de vida é baixa e a distância até o item de vida
mais próximo é baixa, então o objetivo é muito desejável;
Se a quantidade de pontos de vida é baixa e a distância até o item de vida
mais próximo é média, então o objetivo é muito desejável;
Se a quantidade de pontos de vida é baixa e a distância até o item de vida
mais próximo é longe, então o objetivo é desejável;
Se a quantidade de pontos de vida é normal e a distância até o item de
vida mais próximo é baixa, então o objetivo é desejável;
Se a quantidade de pontos de vida é normal e a distância até o item de
vida mais próximo é média, então o objetivo é indesejável;
Se a quantidade de pontos de vida é normal e a distância até o item de
vida mais próximo é longe, então o objetivo é indesejável;
Se a quantidade de pontos de vida é alta e a distância até o item de vida
mais próximo é baixa, então o objetivo é muito indesejável;
38
Se a quantidade de pontos de vida é alta e a distância até o item de vida
mais próximo é média, então o objetivo é indesejável;
Se a quantidade de pontos de vida é alta e a distância até o item de vida
mais próximo é longe, então o objetivo é indesejável;
Como método de defuzzificação, pode ser usado o método “Média das
Máximas”, pois tem precisão próxima a do método do “Centróide”, que é o mais
preciso, e tem custo computacional baixo quando comparado ao “Centróide”.
As regras acima descrevem o grau de desejo de ir procurar um item de vida
de forma natural, como as pessoas fazem no dia-a-dia, o que torna a lógica difusa
uma ferramenta poderosa. Os conjuntos podem ser modificados a fim de se ajustar
o comportamento que se deseja. Por exemplo, o conjunto que define a quantidade
de pontos de vida como baixa poderia ser “esticado” para fazer com que um
personagem fosse mais vezes procurar um item de vida, adquirindo um
comportamento de se preservar antes de pensar em tomar outras atitudes, como ir
atacar. Outras variáveis também poderiam ser exploradas como a força de ataque
de uma arma, cabendo ao desenvolvedor escolher quais variáveis serão levadas em
consideração.
39
7 Considerações Finais
Neste trabalho foram apresentados conceitos básicos de desenvolvimentos
de jogos. Foram discutidos tópicos sobre gráficos, física, áudio e inteligência
artificial.
Desenvolver um motor para jogos está se mostrou uma tarefa extensa. No
entanto, desenvolver jogos do “zero”, sem nenhuma biblioteca para auxiliar é
impraticável nos dias de hoje considerando a complexidade dos jogos criados
atualmente.
Como trabalhos futuros, podem-se criar algumas extensões do motor
desenvolvido:
Adaptar os módulos de física de desenho para suportar jogos 3D;
Criar um módulo para carregar o jogo totalmente de forma parametrizada,
sem possuir parâmetros embutidos no código;
Criar um editor de mapas para os jogos.
40
8 Referências Bibliográficas
Bradshaw, J. M. An introduction to software agents. 1997.
Buckland, M. Programming Game AI by Example. Wordware Publishing, Inc. 2005.
Fernandes M. Programação de Jogos com Delphi usando DirectX. Relativa, 2002.
Fernandes M. Programação de Jogos com Visual Basic usando DirectX. Relativa,
2001.
Ferreira, Rodrigo R.; Ferreia, Rafael R. Algoritmos para Detecção de Colisões em
Ambientes Gráficos Bidimensionais. 29/01/2009. Disponível em:
<http://www.sharpgames.net/F%C3%B3rum/tabid/57/forumid/Artigos/Artigo/tabid/58/
selectmoduleid/376/ArticleID/1603/reftab/54/Default.aspx>. Acesso em: 30 jun. 2010.
Flynt, J.P; Salem, O. Software Engineering for Game Developers. 2004.
Game Engine. 04/11/2010. Disponível em:
<http://en.wikipedia.org/wiki/Game_engine>. Acesso em: 07 nov. 2010.
Gregory, J. Game engine architecture. 2009.
Kimmerle, S. Tutorial: Real-Time Collision Detection for Dynamic Virtual
Environments. 2005.
Rocha, R. S. Algoritmos Rápidos de Detecção de Colisão. 2010.
Sanches, B. C. Funcionamento de um jogo. Disponível em:
<http://www.pontov.com.br/site/arquitetura/51-programacao/112-funcionamento-de-
um-jogo>. Acesso em 07 abr. 2012.
SDL mixer: Tutorials: Playing a WAV Sound File. Disponível em:
<http://content.gpwiki.org/index.php/SDL_mixer:Tutorials:Playing_a_WAV_Sound_Fi
e>. Acesso em: 01 abr. 2012.
Start out on Game Programming. 28/10/2010. Disponível em:
<http://lazyfoo.net/articles/article01/index.php>. Acesso em: 25 nov. 2010.
West, M. Evolve your Hierarchy. 2007. Disponível em:
<http://cowboyprogramming.com/2007/01/05/evolve-your-heirachy>. Acesso em: 08
abr. 2012.
Wooldridge, M. An Introduction to multiagents systems. 2002.
Recommended
