Um jogo de corrida em ambiente virtual
Apresentação de Projeto de Graduação
Aluno: Túlio Ligneul Santos DRE: 106017420
Orientador: Ricardo Marroquim










Introdução
Ambiente de Desenvolvimento
Movimentação dos Carros
Pista Tipo I
Pista Tipo II
Controlador Heurístico
Controlador Neural
Demonstração
Conclusões
Trabalhos Futuros

Motivação:
 Industria de jogos em crescimento:
▪ Movimenta bilhões de dólares apenas nos Estados Unidos [10].
 Principais atrativos dos jogos atuais:
▪ Interatividade e realismo:
▪ Importantes para a imersão do jogador.

Objetivo:
 Implementar uma versão preliminar jogável de um jogo de
corrida e analisar seus componentes;
 Constituir uma fonte de estudo para o desenvolvimento
de jogos.

Metodologia:
 Preocupação com a imersão do usuário:
▪ Imersão sensorial (audiovisual):
▪ Áudio 3D;
▪ Efeitos gráficos (e.g. Cel Shading).
▪ Imersão baseada em desafios:
▪ Inteligência, ou competitividade, dos oponentes:
 Busca-se um controlador capaz de, pelo menos, completar o percurso de uma
volta da corrida.
▪ Oponentes humanos:
 Partida multijogador em rede;
▪ Realismo físico.
▪ Imersão imaginativa:
▪ Gerada pela narrativa, personagens e ambientação;
▪ Não faz parte do foco do projeto.

Game engines ( ou Motores de jogos):
 Fornecem ferramentas de desenvolvimento e componentes reusáveis;
 Costumam operar através de um sistema integrado de
desenvolvimento (IDE) :
▪ Busca permitir que se produzam jogos de um modo rápido e simplificado.
 Panda3D [22]:
▪ Criada pela Disney e mantida por um grupo de pesquisa da Universidade
Carnegie Mellon;
▪ Gratuita;
▪ Fórum ativo;
▪ Bastante completa:
▪ Simulações físicas;
▪ Técnicas avançadas de renderização;
▪ Monitoramento do desempenho;
▪ Alto grau de customização;

Game engines ( ou Motores de jogos):
 Open Dynamics Engine (ODE) [23]
▪ Engine de física.
▪ Integrada com o Panda3D.
▪ Permite maior controle das rotinas de simulação.
▪ Viabiliza a construção de efeitos mais complexos.

Biblioteca neat-python [11]
 Mesma linguagem de programação utilizada pelo Panda3D;
 Base para a inteligência artificial dos oponentes;
 Treinamento de redes neurais:
▪ Através da neuroevolução com crescimento topológico (NEAT) [2].

Carrega-se o modelo 3D do veículo;

Cria-se um corpo do ODE para o modelo:
▪ Utilizado na simulação física;
▪ Define-se a massa do corpo/body;
▪ Distribuída na forma de uma caixa;
▪ Densidade uniforme;
▪ Envolve todo o volume do modelo.

Associa-se uma geometria ao corpo:
 Utilizada na detecção de colisão;
 Forma de caixa delimitadora:
▪ Envolve todo o volume do modelo;
▪ Detecção de colisões entre carros ou com o cenário.

Cria-se um corpo do ODE para cada roda:
 Utilizada na simulação física;
 Define-se a massa de cada corpo/body;
▪ Distribuída em forma de cilindro;
▪ Densidade uniforme;
▪ Envolve todo o volume de sua respectiva roda.
 Define-se uma superfície/surface para as rodas:
▪ Define atributos físicos;
▪ Ex: coeficiente de atrito.

Associa-se uma geometria ao corpo de cada roda:
 Para detecção de colisão:
 Geometrias em forma de esfera:
▪ Envolve todo o volume do roda;
▪ Detecção de colisões entre as rodas e o chão.

Resultado:

Definem-se as articulações:
 Ligam corpos distintos;
 Permitem o movimento
conjunto entre os corpos das
rodas e do carro;
 Permite rotação e alteração
da direção das rodas;
 Simulam a suspensão do
carro.
Retirado do Manual do ODE[17].

Deslocamentos:
 Para frente:
▪ Uma força é aplicada ao corpo do carro no sentido para frente;
▪ Rodas se movem devido às articulações:
▪ Rotacionadas sobre o eixo horizontal devido ao atrito com o chão.
 Para trás ou frenagem:
▪ Uma velocidade angular e uma força são aplicadas às rodas no sentido para trás.
▪ Rodas se movem devido ao atrito com o chão:
▪ Articulações entre as rodas e o corpo do carro fazem com que o carro se mova.
 Em curva:
▪ Realizado através de mudanças na direção das rodas frontais.
▪ Rotacionadas sobre o eixo vertical.
▪ Deslocamento para frente ou para trás faz com que o carro realize uma curva.

Efeitos sonoros:
 Aceleração do motor;
 Motor ligado;
 Freio.

Terreno 3D gerado através um mapa de altura:
 Imagem em escala de cinza;
 Cores representam deslocamentos em altura:
▪ Preto é altura mínima e branco a máxima;


Textura aplicada sobre a topologia gerada.
Um Shader simula um plano de água que reflete o
cenário.

Idealmente: permite corrida em terreno altamente
irregular;

Não foi encontrada uma configuração de parâmetros
do ODE para suportar tal cenário;
 Os carros escorregavam ao tentar subir uma pequena
elevação.


Terreno projetado sobre o plano XY;
Menu principal do jogo:
 Demonstração do efeito visual planejado.

Delimitação da pista sobre o cenário:


Textura com o desenho do formato da pista .
Teste do jogador sobre a pista:

Mapeamento direto:
▪



Entre coordenadas XY de mundo e posição do pixel na imagem do mapa da
pista.
Verifica a cor do pixel correspondente.
Aplica-se uma penalidade por estar fora da pista
Definição do centro de checkpoints:

Definidos empiricamente:
▪ Distribuídos de modo uniforme e centrados ao longo da pista.

Checkpoints:

Ativado quando um jogador está a um distância mínima de
seu centro.
 Acompanhamento do progresso dos jogadores;
 Definição da colocação de cada jogador na corrida.

Modelo 3D :
 Concatenação de unidades
 Numeração das unidades:
▪ Define a ordem de cada unidade na pista.
 Centros geométricos das unidades:
▪ Definem as posições dos checkpoints.
 Checkpoints:
▪ Planos orientados de acordo com a pista.

Suposições:
 Percurso formado pelos checkpoints é um bom caminho.
 Ajuste incremental da direção do jogador para seguir este caminho resulta em
um bom controlador.

Jogador se move para frente:
 Realizam-se pequenos ajustes na direção do movimento em cada iteração.

Em cada iteração:
▪ θ >0:
▪ Checkpoint à direita do carro ;
▪ Virar para a direita.
▪ θ < 0:
▪ Checkpoint à esquerda do carro;
▪ Virar para a esquerda.
▪ θ = 0:
▪ Checkpoint à frente;
▪ Continuar em frente.
Direção do
movimento
Checkpoint
θ

Rede Neural:
Camada de Entrada
Camada de Intermediária (ou oculta)
Camada de Saída

Rede Neural:
Camada de Intermediária (ou oculta)
Camada de Entrada

Camada de Saída
Modelo Neural:
Pesos Sinápticos
u1
1
u2
2
u3
3
u4
4
Junção Aditiva
 u
i i
Função de Ativação
z
f iui 
Saída
y

8 nós de entrada, referentes à:
 Sensores a -90, -60, -30, 30, 60 e 90 graus;
 Sensor frontal especializado:
▪ Retorna o maior valor entre os obtidos por sensores a -10, 0 e 10 graus;
▪ Procura detectar mais precisamente o final de uma curva.
 Velocidade instantânea do jogador.

2 nós de saída, onde:
 Variam entre -1 e 1;
 Saída Y1:
▪ Andar para frente ou para trás.
 Saída Y2:
▪ Virar para a direita ou esquerda.

Camadas intermediárias:
 Determinadas pelo algoritmo de treinamento.

Função Objetivo / Função de Aptidão:


Procura-se a maximizar;
F (controlador) = (C1  nCheckPointsReached - distance) + C2  avgSpeed;
▪ Maior progresso geral com a menor distância, maximizando a velocidade;
▪ C1 e C2 definidos empiricamente para ajustar a ordem de grandeza das variáveis.

População de 100 indivíduos;

Quantidade máxima de indivíduos em qualquer momento do treinamento.

100 Iterações ou épocas do treinamento;

Para cada iteração do treinamento:



Controladores guiam um jogador durante 500 iterações do Panda3D.
Calculam-se as aptidões de cada controlador;
Ao final, o indivíduo com melhor aptidão é escolhido;


Rede obtida é salva;
Pode ser carregada durante o jogo.

Neuroevolução com crescimento topológico
 NeuroEvolution of Augmenting Topologies (NEAT);
 Utiliza algoritmos genéticos para treinar uma rede neural.
 Inicia com a menor topologia possível:
▪ Entradas ligadas diretamente as saídas.
 Crescimento incremental da topologia da rede:
▪ Dada pela inserção ou alteração de pesos, conexões e nós das camadas
intermediárias;
▪ Somente as estruturas significantes são mantidas;
▪ Buscas em espaços com complexidade incremental.
 Especiação:
▪ Protege inovações estruturais.

Ao final de cada iteração:
 Escolhem-se os indivíduos mais aptos de cada espécie;
 Realiza-se a reprodução dos indivíduos.

Representação das Características do Individuo
 Genoma(Genótipo):
▪ Genes dos Nós:
Nó 1
Entrada
Nó 2
Entrada
Nó 3
Entrada
Nó 4
Saída
Nó 5
Oculto
▪ Genes das Conexões:
Inovação 1
Entrada: 1
Saída: 4
Peso: 0.7
Habilitado
Inovação 2
Entrada: 2
Saída: 4
Peso: 0.5
Desabilitado
Inovação 3
Entrada: 3
Saída: 4
Peso: 0.5
Habilitado
Inovação 5
Entrada: 5
Saída: 4
Peso: 0.4
Habilitado
Inovação 6
Entrada: 1
Saída: 5
Peso: 0.6
Habilitado
Inovação 11
Entrada: 4
Saída: 5
Peso: 0.6
Habilitado
Inovação 4
Entrada: 2
Saída: 5
Peso: 0.2
Habilitado

Representação das Características do Individuo
 Fenótipo:
4
5
3
1
2
 Operador de Crossover / Cruzamento:
Pai 1
Inovação 1
Entrada: 1
Saída: 4
Habilitado
Inovação 2
Entrada: 2
Saída: 4
Desabilitado
Inovação 3
Entrada: 5
Saída: 4
Habilitado
Pai 2
Inovação 1
Entrada: 1
Saída: 4
Habilitado
Inovação 2
Entrada: 2
Saída: 4
Desabilitado
Inovação 3
Entrada: 5
Saída: 4
Desabilitado
Inovação 4
Entrada: 1
Saída: 5
Habilitado
Prole
Inovação 1
Entrada: 1
Saída: 4
Habilitado
Inovação 2
Entrada: 2
Saída: 4
Desabilitado
Inovação 3
Entrada: 5
Saída: 4
Habilitado
Inovação 4
Entrada: 1
Saída: 5
Habilitado
Inovação 5
Entrada: 2
Saída: 5
Habilitado
Inovação 6
Entrada: 3
Saída: 5
Habilitado
Inovação 5
Entrada: 2
Saída: 5
Habilitado
Inovação 6
Entrada: 3
Saída: 5
Habilitado
 Operador de Crossover / Cruzamento:
4
5
5
1
2
4
4
5
1
2
3
1
2
3
 Mutação por inclusão de um novo nó.
Antes
Inovação 1
Entrada: 1
Saída: 4
Habilitado
Inovação 2
Entrada: 2
Saída: 4
Desabilitado
Inovação 3
Entrada: 5
Saída: 4
Habilitado
Inovação 5
Entrada: 2
Saída: 5
Habilitado
Depois
Inovação 1
Entrada: 1
Saída: 4
Desabilitado
Inovação 2
Entrada: 2
Saída: 4
Desabilitado
Inovação 3
Entrada: 5
Saída: 4
Habilitado
Inovação 5
Entrada: 2
Saída: 5
Habilitado
4
4
6
5
1
2
Inovação 6
Entrada: 1
Saída: 6
Habilitado
1
5
2
Inovação 7
Entrada: 6
Saída: 4
Habilitado

Pista Tipo I

Pista Tipo II

Panda3D e ODE:


Forneceram meios de se efetuar desde a criação de uma janela até a realização de simulações
de física.
Neuroevolução com crescimento topológico (NEAT):


Permite construir controladores de carros em ambientes virtuais.
Não é necessário se preocupar com a quantidade de camadas da rede neural:
▪ Não é preciso testar diferentes configurações topológicas de modo manual.

Rede de baixa complexidade:
▪ Apenas três nós intermediários entre as entradas e as saídas.

Controlador neural pouco eficiente:



Guia um carro para completar pelo menos uma volta;
Facilmente derrotado pelo usuário ou pelo jogador controlado pelo método heurístico;
Cardamone et al. [3] construiu um controlador com bom desempenho através do mesmo
método:
▪ Rede obtida pode ser aprimorada.

Passo inicial para a construção de um jogo mais complexo:

Base para estudo e aprendizagem de fundamentos e questões de implementação.

Melhor imersão do usuário no jogo:
 Buscar mais fatores de caráter sensorial, baseado em desafios, ou
imaginativo, por exemplo:
▪ Ambientação de cada corrida, introduzindo outros atores no mundo, fora os jogadores e a
pista.
▪ Animais, pessoas, som do vento, objetos, como construções, etc.

Novo estudo para tornar mais eficiente o controlador neural
 Interagir com o usuário e não somente guiar um carro.

Abordagem mais competitiva pra o controlador neural:
 Constituído de dois controladores, ou duas redes neurais
▪ Um para guiar o carro para completar voltas
▪ Outro para interação com o jogador, impedindo ou realizando uma ultrapassagem.

Gerador de Pistas Tipo II
 Pistas geradas pela concatenação de diversas unidades em um mesmo plano.
 Permite a criação de conteúdo personalizado.

[2] Stanley, K. O., Miikkulainen, R. “Efficient Reinforcement Learning through Evolving Neural Network Topologies”,
In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), 2002.

[3] Cardamone, L., Loiacono, Daniele, Lanzi, P. L, “Evolving Competitive Car Controllers for Racing Games with
Neuroevolution”, In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), 2009.

[4] Togelius J., Lucas, S. M., Nardi, R. de, “Computational Intelligence in Racing Games”, Studies in Computational
Intelligence, v. 71/2007, pp. 39-69, 2007.

[7] Ermy, L., Mäyrä, F., “Fundamental Components of the Gameplay Experience: Analysing Immersion”. In:
Proceedings of DiGRA 2005 Conference: Changing Views – Worlds in Play, 2005.

[10] Entertainment Software Association, “The Entertainment Software Association – Industry Facts”,
http://www.theesa.com/facts/index.asp, 2010, (Acesso em 11/11/2010).

[11] neat-python, “neat-python - Project Hosting on Google Code”, http://code.google.com/p/neat-python/, 2010
(Acesso em 11/11/2010).

[17] Open Dynamics Engine (ODE) Community Wiki, “Manual (All) - ODE Wiki”,
http://opende.sourceforge.net/wiki/index.php/Manual_(All)#Hinge-2 (Acesso em 02/12/2010).

[22] Panda3D, “Panda3D – Free 3D Game Engine”, http://www.panda3d.org/, (Acesso em 03/12/10).

[23] Open Dynamics Engine, “Open Dynamics Engine – home”, http://www.ode.org, (Acesso em 05/12/10).
Um jogo de corrida em ambiente virtual
Apresentação de Projeto de Graduação
Aluno: Túlio Ligneul Santos DRE: 106017420
Orientador: Ricardo Marroquim