Bruno Rodrigues de Andrade - UnB Gama

Transcrição

Universidade de Brasília - UnB
Faculdade UnB Gama - FGA
Engenharia de Software
Jogadores Automatizados: Uma abordagem
orientada à Inteligência Artificial
Autor: Bruno Rodrigues de Andrade
Orientador: (Profa . Dra . Milene Serrano)
Brasília, DF
2015
Bruno Rodrigues de Andrade
Jogadores Automatizados: Uma abordagem orientada à
Inteligência Artificial
Monografia submetida ao curso de graduação
em (Engenharia de Software) da Universidade de Brasília, como requisito parcial para
obtenção do Título de Bacharel em (Engenharia de Software).
Universidade de Brasília - UnB
Faculdade UnB Gama - FGA
Orientador: (Profa. Dra . Milene Serrano)
Coorientador: (Prof. Dr. Maurício Serrano)
Brasília, DF
2015
Jogadores Automatizados: Uma abordagem orientada à Inteligência Artificial/
Bruno Rodrigues de Andrade. – Brasília, DF, 201571 p. : il. (algumas color.) ; 30 cm.
Orientador: (Profa . Dra . Milene Serrano)
Trabalho de Conclusão de Curso – Universidade de Brasília - UnB
Faculdade UnB Gama - FGA , 2015.
1. Inteligência Artificial. 2. Jogadores Automatizados. I. (Profa . Dra . Milene
Serrano). II. Universidade de Brasília. III. Faculdade UnB Gama. IV. Jogadores
Automatizados: Uma abordagem orientada à Inteligência Artificial
CDU 02:141:005.6
Jogadores Automatizados: Uma abordagem orientada à
Monografia submetida ao curso de graduação
em (Engenharia de Software) da Universidade de Brasília, como requisito parcial para
obtenção do Título de Bacharel em (Engenharia de Software).
Trabalho aprovado. Brasília, DF, 06 de julho de 2015:
(Profa . Dra . Milene Serrano)
Orientador
(Prof. Dr. Maurício Serrano)
Coorientador
Prof. Dr. Edson Alves da Costa Junior
Convidado 1
Prof. Dr. Fábio Macedo Mendes
Convidado 2
Brasília, DF
2015
Agradecimentos
Agradeço a Deus acima de tudo, que me deu a oportunidade única de estudar em
uma universidade federal e tem me sustentado em toda essa caminhada. Sem a ajuda
dele, todo o meu esforço teria sido em vão.
Agradeço a meus pais Júlio Falcão e Denise Nery que desde antes de eu ingressar
na universidade sempre apoiaram meus sonhos e objetivos, proporcionando um suporte
emocional indispensável em toda a minha carreira acadêmica. Sou muito grato pelo investimento deles e sua preocupação com a minha formação e vida profissional.
Agradeço a meu irmão Matheus Rodrigues que desde criança foi meu companheiro
e amigo, fazendo parte da minha história desde o começo.
Agradeço à todo o corpo acadêmico da Falcudade UnB Gama por terem contribuído na minha formação acadêmica ao longo de cinco anos ampliando meus conhecimentos sobre Engenharia de Software e contribuindo para me tornar um profissional
qualificado no mercado de trabalho.
Agradeço à professora Milene Serrano e ao professor Maurício Serrano que com
excelência e dedicação me orientaram e guiaram por todo esse processo de escrita deste
Trabalho de Conclusão de Curso, sempre me motivando à realizar um excelente trabalho
desde o começo.
Agradeço os meus colegas e amigos de trabalho Felipe Perius, Henrique Prudêncio,
Luís Rezende e Thamara Gabriella que trabalharam comigo no desenvolvimento do jogo
Lost Gems, tema deste Trabalho de Conclusão de Curso.
Agradeço à Joice Rute Alves que também sempre esteve perto me animando e
motivando para conquistar meus objetivos afim de que possamos construir uma longa
vida juntos no futuro.
Agradeço aos demais amigos e companheiros que também proveram um suporte
emocional e intelectual importantíssimo para a minha formação acadêmica e profissional.
“Não vos amoldeis às estruturas deste mundo,
mas transformai-vos pela renovação da mente,
a fim de distinguir qual é a vontade de Deus:
o que é bom, o que Lhe é agradável, o que é perfeito.
(Bíblia Sagrada, Romanos 12, 2)
Resumo
O estudo de agentes autônomos tem sido amplamente discutido desde a aparição de jogos
eletrônicos ao redor do mundo. Vários cientistas e acadêmicos têm empreendido esforços
para definir uma Inteligência Artificial de jogadores automatizados adequada em contextos e jogos diferentes. O presente trabalho descreve uma proposta de desenvolver agentes
automatizados para o jogo Lost Gems. Estes agentes possuem uma série de comportamentos pré-programados: percorrer o mapa, atirar em inimigos, capturar um objeto na
base inimiga, entre outros. Essas estratégias serão implementadas utilizando-se de Máquina de Estados Finitos, Comportamentos de Direção, Grafos, algoritmo de busca de
menor caminho e metodologias ágeis. Os agentes automatizados devem agir simulando o
comportamento de jogadores humanos afim de que o jogo se torne mais competitivo, e
equilibrado na sua dificuldade.
Palavras-chaves: inteligência artificial. agentes automatizados. algoritmos. máquina de
estados finitos. comportamentos de direção. grafos.
Abstract
The study of autonomous agents has been widely discussed the emergence of electronic
games around the world. Several scientists and scholars have made efforts to set a properly
Artificial Inteligence of autonomous players in different contexts and games. This paper
describes a proposal to develop automated agents for the game Lost Gems. These agents
have a number of pre-programmed behaviors: scroll the map, shoot in enemies, capture
an object in the enemy base, among others. These strategies will be implemented using
Finite State Machine, Steering Behaviours, graphs, shortest path algorithm and agile
methodologies. Automated agentes should act simulating the behavior of human players
in order that the game becomes more competitive and balanced in its difficulty.
Key-words: artificial inteligence. automated agents. algorithms. finit state machines.
steering behaviours. graphs.
Lista de ilustrações
Figura 1 – Uma hierarquia de comportamentos de movimento. (REYNOLDS, 1999) 29
Figura 2 – Vetores de posição e velocidade sob um personagem. (BEVILACQUA, 2012) 31
Figura 3 – Seek (BUCKLAND, 2005) . . . . . . . . . . . . . . . . . . . . . . . . . 32
Figura 4 – Flee (BEVILACQUA, 2012) . . . . . . . . . . . . . . . . . . . . . . . . 33
Figura 5 – Arrival (REYNOLDS, 1999) . . . . . . . . . . . . . . . . . . . . . . . . 33
Figura 6 – Wander (REYNOLDS, 1999) . . . . . . . . . . . . . . . . . . . . . . . 35
Figura 7 – Obstacle Avoidance (BUCKLAND, 2005) . . . . . . . . . . . . . . . . . 35
Figura 8 – Diferentes tipos de caminho. (BUCKLAND, 2005) . . . . . . . . . . . . 36
Figura 9 – Representação de um Grafo. (FEOFILOFF et al., 2011) . . . . . . . . 36
Figura 10 – Representação de uma Lista de Adjacência. (CORMEM et al., 2002) . 37
Figura 11 – Pseudo-código da Busca em Largura (SILVA, 2005). . . . . . . . . . . . 38
Figura 12 – Pseudo-código do Algoritmo A*(SILVA, 2005) . . . . . . . . . . . . . . 39
Figura 13 – Diagrama de Classes. (GAMMA et al., 2000) . . . . . . . . . . . . . . 40
Figura 14 – Metodologia Scrum (DESENVOLVIMENTOÁGIL.COM.BR, 2014) . . 42
Figura 15 – Processo do TCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Figura 16 – Mapa do jogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Figura 17 – Mapa com grafo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Figura 18 – Diagrama de Estados - Perfil Atacante . . . . . . . . . . . . . . . . . . 55
Figura 19 – Diagrama de Classes - Perfil Atacante . . . . . . . . . . . . . . . . . . 57
Figura 20 – Diagrama de Estados - Perfil Defensor . . . . . . . . . . . . . . . . . . 58
Figura 21 – Diagrama de Classes - Perfil Defensor . . . . . . . . . . . . . . . . . . . 59
Figura 22 – Exemplo de um mapa representado por Grid . . . . . . . . . . . . . . . 61
Figura 23 – Representação inicial do mapa com grafo. . . . . . . . . . . . . . . . . 62
Figura 24 – Aplicação executando em um simulador. . . . . . . . . . . . . . . . . . 63
Lista de tabelas
Tabela 1 – Cronograma do TCC 01 . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Tabela 2 – Cronograma do TCC 02 . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Lista de abreviaturas e siglas
IA
NPC
Non-Player Character
FSM
Finit State Machine
TCC
Trabalho de Conclusão de Curso
GoF
Gang of Four
IDE
Integrated Development Environment
BSD
Berkeley Software Distribution
XNU
X is Not Unix
GUI
Graphical User Interface
Lista de símbolos
∈
Pertence
L
Lista de nós
G
Grafo
V
Vértice
A
Aresta
Sumário
1
INTRODUÇÃO
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.1
Contextualização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.2
Questão de Pesquisa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.3
Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4
Objetivo Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5
Objetivos Específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.6
Organização do Documento
2
REFERENCIAL TEÓRICO . . . . . . . . . . . . . . . . . . . . . . . 27
2.1
Inteligência Artificial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.1
Máquinas de Estados Finitos . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2
Domínio de Jogos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.1
Jogadores Automatizados . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.2
Comportamentos de Direção . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.2.1
Seek
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
2.2.2.2
Flee
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
2.2.2.3
Arrival
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
2.2.2.4
Wander
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.2.2.5
Obstacle Avoidance
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.2.2.6
Path Following
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
2.2.3
Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2.3.1
Algoritmos de Grafos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
2.2.3.2
Lista de Adjacência
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
2.2.4
Busca em Largura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2.5
Algoritmo A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.3
Engenharia de Software . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3.1
Padrão de Projeto: State . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3.2
Scrum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.4
Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3
SUPORTE TECNOLÓGICO . . . . . . . . . . . . . . . . . . . . . . 43
3.1
Ferramentas de Desenvolvimento . . . . . . . . . . . . . . . . . . . . 43
3.1.1
Xcode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1.2
Sprite Kit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1.3
OS X Yosemite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1.4
Git . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
. . . . . . . . . . . . . . . . . . . . . . . 25
3.1.5
Bitbucket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.1.6
3.1.7
3.2
LaTeX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
OCLint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4
METODOLOGIA
4.1
4.2
Engenharia de Software Experimental . . . . . . . . . . . . . . . . . . 47
Pesquisa Exploratória . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3
4.4
4.5
Planejamento dos Passos Metodológicos . . . . . . . . . . . . . . . . 48
Modelagem dos Passos Metodológicos . . . . . . . . . . . . . . . . . 50
Cronograma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.6
5
5.1
PROPOSTA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Mapa do jogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2
5.2.1
5.3
Comportamento dos agentes automatizados . . . . . . . . . . . . . . 55
Perfil Atacante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Perfil Defensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.4
5.5
Nível de dificuldade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6
6.1
PROVA DE CONCEITO . . . . . . . . . . . . . . . . . . . . . . . . 61
Representação do Mapa em Grafos . . . . . . . . . . . . . . . . . . . 61
6.2
6.3
Comportamentos de Direção . . . . . . . . . . . . . . . . . . . . . . . 62
Status Atual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
APÊNDICES
67
APÊNDICE A – CÓDIGO FONTE DA CLASSE STEERINGBEHAVIOURS 69
23
1 Introdução
Este capítulo tem como objetivo introduzir o leitor no assunto deste trabalho. São
discutidos o Contexto do Trabalho, a Questão de Pesquisa, a Justificativa, o Objetivo
Geral, os Objetivos Específicos tal como a Organização do Documento.
1.1 Contextualização
Lost Gems1 é um jogo eletrônico desenvolvido para a plataforma iOS feito essencialmente por cinco desenvolvedores: Bruno Rodrigues, Luís Rezende, Felipe Perius,
Henrique Prudêncio e Thamara Gabriella. O desenvolvimento se deu entre novembro de
2014 à março de 2015 durante o projeto BEPiD (Brazillian Educational Program for iOS
Developers)2 . A seguir será apresentado, em linhas gerais, o contexto do jogo.
Basicamente, o jogo prevê em seu contexto duas naves espaciais as quais levam diversos personagens. Essas naves caem, acidentalmente, em um planeta considerado hostil.
As naves necessitam de duas gemas mágicas (ou seja, são artefatos que funcionam como
combustível para a nave) para funcionarem e escaparem do planeta. Entretanto, quando
as naves caíram, cada qual teve uma gema mágica destruída no acidente. Agora, para os
personagens e as naves saírem do planeta, os mesmos devem se enfrentar, no intuito de
conquistar a gema mágica da equipe inimiga, trazendo-a de volta à nave. Nesse caso, apenas uma equipe sairá vencedora dessa competição. Ao longo da partida, os personagens
podem ferir os inimigos com tiros bem como habilidades específicas.
Vários jogadores podem se conectar no jogo via rede Wi-Fi ou Bluetooth, formando
assim equipes diferentes, com quantidades de jogadores variáveis. Com isso, o jogo visa
estabelecer uma interação maior entre os jogadores aumentando a competitividade e a
diversão.
Um problema evidente que pode ocorrer é a questão do balanceamento do jogo
quando, por exemplo, um time possui mais jogadores que outro. Nesse caso, uma equipe
obterá vantagem numérica sobre a outra.
Outro problema evidente que acontece no jogo é que um jogador não pode jogar
Lost Gems sozinho (um modo Single Player), pois é necessário que outros jogadores se
conectem à partida para que esta ocorra.
1
2
PERIUS, Felipe. LostGemsBigFinal. Brasília: 2015. 13 slides, color
<http://www.bepid.org.br>
Capítulo 1. Introdução
24
1.2 Questão de Pesquisa
Com base nos problemas apresentados no tópico anterior, pode-se levantar a seguinte questão de pesquisa: É possível desenvolver jogadores automatizados no Lost Gems,
considerando uma abordagem orientada à Inteligência Artificial, que simulassem o comportamento de jogadores humanos, sendo, portanto, capazes de equilibrar as equipes envolvidas em uma partida, mantendo a competitividade do jogo?
1.3 Justificativa
Várias atividades da Engenharia de Software tradicionalmente requerem esforços
humanos intensivos e impõem encargos sobre a inteligência humana. Para reduzir os
esforços humanos e os encargos sobre a inteligência humana nessas atividades, técnicas de
Inteligência Artificial (IA), que visam a criação de sistemas de software que apresentam
algum tipo de inteligência humana, têm sido empregadas para auxiliar ou automatizar
essas atividades na Engenharia de Software (XIE, 2013).
Muitos jogos têm agentes controlados por computador que jogam contra um jogador. O comportamento desses agentes é descrito por meio da Inteligêncua Artificial (IA) no
jogo. A IA é um componente importante do jogo, e precisa ser desenvolvida com cuidado
e adaptada com regularidade (HASTJARJANTO; JEURING; LEATHER, 2013).
A Inteligência artificial de jogos passou por uma revolução silenciosa nos últimos
anos. Já não é algo que a maioria dos desenvolvedores consideram apenas para o fim do
projeto, quando o prazo de conclusão está acabando e o publicador está pressionando para
que o jogo seja disponibilizado no mercado. Mais recentemente, a inteligência artificial de
jogos é algo que é planejado, algo que os desenvolvedores estão deliberadamente a tornando
tão importante como os gráficos ou efeitos sonoros. Adicionalmente, vale salientar que o
mercado está repleto de jogos de todos os tipos, e os desenvolvedores estão procurando
refinar seus jogos no intuito de torná-los mais reconhecidos. Um jogo com oponentes
verdadeiramente “espertos” ou personagens que não são jogadores é automaticamente
notado, não importando, muitas vezes, como ele é ou como se parece (BUCKLAND,
2005).
1.4 Objetivo Geral
Desenvolver jogadores automatizados no Lost Gems, usando recursos de inteligência artificial (ex. algoritmos clássicos e conhecidos no contexto de jogos), com capacidade
de desempenhar ações simulando o comportamento de jogadores humanos.
1.5. Objetivos Específicos
25
1.5 Objetivos Específicos
No intuito de atingir o objetivo geral, alguns objetivos específicos merecem menção,
dentre eles:
• Investigar algoritmos de Inteligência Artificial, conhecidos e aplicáveis no contexto
de jogos;
• Implementar estratégias específicas para viabilizar algumas ações por parte dos jogadores automatizados, como se os mesmos estivessem sendo controlados por jogadores
humanos. Nesse cenário, destacam-se as seguintes ações:
– Andar pelo mapa;
– Desviar de obstáculos;
– Capturar a gema inimiga na base inimiga;
– Levar a gema capturada na base inimiga à base aliada;
– Enfrentar jogadores da equipe inimiga à base aliada;
– Recuperar gema de sua equipe, a qual se encontra fora da base;
– Defender a gema de sua equipe, para que a mesma não seja capturada pela
equipe inimiga, e
– Possuir dificuldade customizável pelo jogador.
• Testar as estratégias implementadas com base em recursos da Engenharia Experimental;
• Estabelecer uma forma organizada, estruturada e orientada às boas práticas da
Engenharia de Software no intuito de conduzir o processo investigativo, a implementação bem como os testes mencionados nos objetivos específicos anteriores.
1.6 Organização do Documento
Este documento está organizado em capítulos com sub-tópicos. São estes:
• Referencial Teórico: Neste capítulo encontra-se uma fundamentação teórica dos
conteúdos que são utilizados ao longo da realização desse TCC.
• Suporte Tecnológico: É descrito quais ferramentas foram e serão utilizadas para
o desenvolvimento do trabalho como um todo.
• Metodologia: Neste capítulo são descritos os passos metodológicos para o desenvolvimento do trabalho bem como a implementação dos agentes automatizados.
Capítulo 1. Introdução
26
• Proposta: É descrito a proposta, e apresentados a arquitetura e os algoritmos a
serem utilizados.
• Prova de Conceito: É descrito como as estratégias foram escolhidas, e uma prova
de conceito implementada.
27
2 Referencial Teórico
Neste capítulo, será apresentada uma descrição detalhada dos conceitos e conteúdos a serem trabalhados ao longo do desenvolvimento do TCC 01 e TCC 02. Todos os
conceitos estão embasados em artigos científicos e livros publicados na área de Tecnologia
da Informação.
2.1 Inteligência Artificial
Inteligência Artificial (IA) é uma nova ciência tecnológica, que pesquisa e desenvolve métodos, técnicas e aplicações para simular, extender e expandir a teoria da inteligência humana. IA é um ramo da ciência da computação que tenta entender a essência
da inteligência e produzir uma nova máquina inteligente que pode realizar reações similares à inteligência humana. A pesquisa no campo da inteligência artificial inclue robótica,
reconhecimento de fala, reconhecimento de imagem, processamento de linguagem natural
e sistemas especialistas (NING; YAN, 2010).
De acordo com o autor Li (2009) é: um sistema computacional que possui conhecimento e comportamento humano com habilidades como por exemplo: aprender, inferir,
julgar, resolver o problema, memória, conhecimento e entender a linguagem natural humana.
Com base no trabalho dos autores Hosea, Harikrishnan e Rajkumar (2011), Inteligência Artificial inclue:
• Jogos eletrônicos: programar computadores para jogar jogos como xadrez e damas, os quais demandam algoritmos baseados em raciocínio lógico;
• Sistemas especialistas: programar computadores para tomar decisões em situações da vida real (por exemplo, alguns sistemas especialistas ajudam médicos a
diagnosticarem doenças baseados em sintomas);
• Linguagem natural: programar computadores para entender a linguagem natural
humana;
• Redes neurais: sistemas que simulam inteligência pela tentativa de reproduzir os
tipos de conexões físicas que ocorrem em cérebros de animais, e
• Robótica: programar computadores para perceber e reagir a outros estimulos sensoriais.
Capítulo 2. Referencial Teórico
28
2.1.1 Máquinas de Estados Finitos
Em jogos eletrônicos, Máquinas de Estados Finitos, ou do inglês Finit State Machine (FSM), são tipicamente usadas para modelar o comportamento de NPCs, para
fazê-los reagir a eventos do jogo o mais natural e inteligente possível. FSM consiste em
um conjunto de estados, que representam algum tipo de ação ou comportamento, e uma
coleção de transições para cada estado, que especificam as reações dos NPCs aos eventos
do jogo (HU; ZHANG; MAO, 2011).
De fato, Máquinas de Estados Finitos são a abordagem mais popular para algoritmos de Inteligência Artificial em jogos, por várias razões, incluindo: facilidade de entendimento, facilidade de implementação, eficiência, dentre outras. Facilidade de implementação também permite uma prototipação rápida e mais iterações de desenvolvimento. FSMs
são leves e rápidas, o que é sempre importante em sistemas real-time. Comparado com outros esquemas de controle, FSMs são mais fáceis de testar e validar (HU; ZHANG; MAO,
2011).
Existem outros esquemas de controle equivalentes, como por exemplo a máquina
de Moore e a de Mealy1
2.2 Domínio de Jogos
2.2.1 Jogadores Automatizados
Neste trabalho, a expressão “Jogadores Automatizados” é considerada sinônima às
expressões “Personagens Automatizados”, “Agentes Automatizados” e Non-player Characters (NPCs).
Em geral, quando se fala em desenvolver comportamentos de um bot, o termo
NPC refere-se a um agente que é capaz de jogar um jogo por si só. No entanto, alguns
autores restringem ainda mais a definição acima de um NPC, sendo esse considerado um
personagem do jogo, o qual enfrenta um jogador humano. Já um agente que joga por si
só, sem oponentes humanos, é chamado simplesmente de bot (RECIO et al., 2012). Ao
longo desse trabalho, os dois termos, NPCs e bots, serão utilizados como sinônimos.
Uma das muitas contribuições históricas da Inteligência Artificial aos jogos eletrônicos consiste em gerar agentes autônomos ou NPCs. Em geral, um agente se concentra
em desenvolver estratégias em um jogo competitivo, ajustando o nível do jogo de acordo
com as habilidades de um jogador humano, ou através do desenvolvimento de estratégias
e comportamentos sememelhantes a humanos. Bots de um jogo podem ser criados por
diversas técnicas de inteligência artificial (RECIO et al., 2012). Algumas dessas técnicas
são citadas neste trabalho.
1
<http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Seq/fsm.html>
2.2. Domínio de Jogos
29
2.2.2 Comportamentos de Direção
No final de 1980, o cientista da computação Craig Reynolds desenvolveu o algoritmo Steering Behaviours (Comportamentos de Direção) para personagens animados.
Esses comportamentos permitiram aos elementos individuais percorrerem em seus ambientes digitais de maneira “realista”, com estratégias de fuga, vagueação, chegada, perseguição, escape, entre outras. Utilizado no caso de um único agente autônomo, esses
comportamentos são simples de serem entendidos e implementados (SHIFFMAN et al.,
2012).
O comportamento de um personagem autônomo pode ser melhor entendido sendo
dividido em várias camadas. Essas camadas são destinadas para clareza e especificidade
na discussão que vai se seguir. A Figura 1 mostra uma divisão do comportamento de
movimento para personagens autônomos em uma hierarquia de três camadas: seleção de
ação, direção e locomoção (REYNOLDS, 1999).
Figura 1: Uma hierarquia de comportamentos de movimento. (REYNOLDS, 1999)
Na camada Seleção de Ação, um agente possui uma meta (ou metas) e pode selecionar uma ação (ou uma combinação de ações) baseada(s) naquela meta (SHIFFMAN et al.,
2012). Reynolds (1999) descreve várias metas e ações associadas, tais como: buscar um
alvo, evitar um obstáculo, e seguir um caminho.
Neste trabalho, várias dessas ações serão implementadas e combinadas com outros
algoritmos. Outros detalhes serão apresentados no capítulo 4, Proposta.
Uma vez que uma ação foi selecionada, o agente deve calcular seu próximo movimento (essa é a camada de Direção). Esse próximo movimento será uma força; mais
especificamente, uma força direcional (SHIFFMAN et al., 2012). Reynolds (1999) desenvolveu uma fórmula simples de força direcional que será utilizada ao longo deste trabalho:
30
steering_f orce = desired_f orce − current_velocity
(2.1)
A locomoção de um personagem autônomo pode ser baseada na representação
de sua animação. Um personagem pode ser representado por uma simulação balanceada
baseada na física de caminhar, proporcionando uma animação realista e uma locomoção
comportamental. Ou um personagem pode possuir um modelo de locomoção muito simples
para que uma representação estática (como uma nave espacial) ou pré-animada (como uma
figura humana realizando um ciclo de caminhada) seja anexada. Resumindo, a locomoção
pode ser restringida ao movimento inerente a um conjunto fixo de segmentos pré-animados
(andar, correr, parar, virar à esquerda, entre outros) que são selecionados de forma discreta
ou misturados (REYNOLDS, 1999).
A seguir, é apresentado um cenário fictício elaborado por Reynolds (1999) para
exemplificar o seu algoritmo de modo mais simples.
Considere, por exemplo, alguns vaqueiros cuidando de um rebanho de gado em
um campo. Uma vaca vagueia para longe do rebanho. O chefe dos trabalhadores diz à
um vaqueiro para buscar a vaca que fugiu. O vaqueiro diz “giddy-up” para o seu cavalo
e orienta-o para a vaca, possivelmente evitando obstáculos no caminho. Neste exemplo, o
chefe dos trabalhadores representa a seleção de ação: percebendo que o estado do mundo
mudou (uma vaca deixou o rebanho) e estabelecendo uma meta (recuperar a desgarrada).
O nível de direção é representado pelo vaqueiro, que decompõe o objetivo em uma série de
sub-metas simples (abordar a vaca, evitar obstáculos e resgatar a vaca). Uma sub-meta
corresponde a um comportamento de direção para a equipe vaqueiro-e-cavalo. Usando
vários sinais de controle (comandos vocais, estímulos, rédeas), o vaqueiro dirige seu cavalo
em direção ao alvo. Em termos gerais, estes sinais expressam conceitos como: ir mais
rápido, ir mais devagar, vire à direita, vire à esquerda e assim por diante. O cavalo
implementa o nível de locomoção. Admitindo os sinais de controle do vaqueiro como
entrada, o cavalo move-se na direção indicada. Este movimento é o resultado de uma
interação complexa da percepção visual do cavalo, o seu sentido de equilíbrio, e de seus
músculos aplicando torque às articulações de seu esqueleto.
A implementação de todas as forças envolvidas nos comportamentos de direção,
podem ser atingidos através de vetores matemáticos. Uma vez que essas forças irão influenciar a velocidade e posição do personagem, é uma boa abordagem usar vetores para
representá-los também. Mesmo que um vetor possua uma direção, este será ignorado
quando relacionado à direção (supondo que o vetor posição aponta para a localização
atual do personagem). A Figura 2 representa um personagem posicionado na coordenada
(x, y) com uma velocidade (a, b) (BEVILACQUA, 2012).
31
Figura 2: Vetores de posição e velocidade sob um personagem. (BEVILACQUA, 2012)
O movimento é calculado usando a integração de Euler
position = position + velocity
2
(BEVILACQUA, 2012):
(2.2)
A direção do vetor velocidade irá controlar para onde o personagem está indo;
enquanto seu comprimento (ou magnitude) irá controlar o quanto o personagem irá se
mover a cada frame. Quanto maior for o comprimento, mais rápido o agente se moverá.
O vetor velocidade pode ser truncado para garantir que ele não será maior do que um
determinado valor, geralmente, velocidade máxima (BEVILACQUA, 2012).
Utilizando dessas premissas matemáticas e físicas, vários Comportamentos de Direção podem ser derivados. Alguns destes serão utilizados na construção na Inteligência
Artificial dos agentes automatizados em Lost Gems. A seguir, são apresentadas descrições
de alguns desses comportamentos.
2.2.2.1 Seek
Seek (ou Buscar) atua para orientar o personagem para uma posição específica no
espaço global. Este comportamento ajusta o personagem de modo que sua velocidade está
alinhada radialmente no sentido do alvo. Isso é diferente de uma força atrativa (como a
gravidade) que produziria um caminho orbital ao redor do ponto de destino. A “velocidade
desejada” (ou “desired velocity” ) é um vetor na direção do personagem para o alvo.
O comprimento da “velocidade desejada” poderia ser max_speed (velocidade máxima),
ou pode ser a velocidade atual, dependendo da aplicação específica. O vetor de direção
(ou steering vector) é a diferença entre esta velocidade desejada e a velocidade atual do
personagem (REYNOLDS, 1999).
2
<http://tutorial.math.lamar.edu/Classes/DE/EulersMethod.aspx>
32
As fórmulas de cálculo da força de direção (steering) são:
desired_velocity = normalize(position − target) ∗ max_speed
(2.3)
steering = desired_velocity − velocity
(2.4)
A Figura 3 ilustra o cálculo de vetores para o comportamento Seek. O vetor pontilhado mostra como a adição da força direcional à velocidade atual produz o resultado
desejado (BUCKLAND, 2005).
Figura 3: Seek (BUCKLAND, 2005)
2.2.2.2 Flee
Flee (ou Fugir) é simplesmente o inverso de Seek e age para digirir o personagem
de modo que a sua velocidade esteja alinhada radialmente para longe do alvo. Os pontos
da velocidade desejada ficam na direção oposta (REYNOLDS, 1999).
As fórmulas de cálculo da força de direção (steering) são:
desired_velocity = normalize(target − position) ∗ max_speed
(2.5)
(2.6)
A Figura 4 ilustra o novo vetor desired_velocity que é calculado subtraindo a posição do alvo, o que produz um vetor que vai do alvo para o personagem. (BEVILACQUA,
2012)
33
Figura 4: Flee (BEVILACQUA, 2012)
2.2.2.3 Arrival
O comportamento Arrival (ou Chegada) é idêntico ao Seek enquanto o personagem
está longe do seu alvo. Mas ao invés de se mover até o alvo na velocidade máxima, este
comportamento resulta no personagem reduzindo a velocidade à medida que se aproxima
do alvo, eventualmente diminuindo até parar na posição do alvo, como ilustrado na Figura
5 (REYNOLDS, 1999).
Figura 5: Arrival (REYNOLDS, 1999)
34
As equações abaixo demonstram o cálculo da força de direção do comportamento
Arrival:
target_of f set = target − position
(2.7)
distance = length(target_of f set)
(2.8)
ramped_speed = max_speed ∗ (distance/slowing_distance)
(2.9)
clipped_speed = minimum(ramped_speed, max_speed)
(2.10)
desired_velocity = (clipped_speed/distance) ∗ target_of f set
(2.11)
(2.12)
2.2.2.4 Wander
Wander (ou Vaguear) produz um algoritmo que faz o personagem andar em um
caminho aleatório. Aparentemente utilizar valores aleatórios para a movimentação do objeto pode ser uma boa opção, mas é necessário que os passos seguintes do personagem
sejam coerentes com seus passos anteriores. Para isso, mantem-se a direção do objeto
realizando pequenos deslocamentos em cada frame. Nesse cenário, a melhor técnica encontrada é manter o vetor direção apontando para um ponto em uma esfera situada à
frente do personagem. O raio da espera restringe a movimentação máxima desse objeto,
sendo que o posicionamento desse círculo mais próximo do personagem faz com que tenha
movimentos mais bruscos; e mais longe garante movimentos mais suaves. O raio da esfera
também interfere na movimentação. Sendo esse raio maior, possibilita uma maior variedade de direções para as quais o personagem pode se locomover. Sendo esse raio menor,
garante que sua rota será mais coerente (BUCKLAND, 2005).
2.2.2.5 Obstacle Avoidance
Obstacle Avoidance (ou Evitar Obstáculos) é um comportamento que direciona
um agente a evitar obstáculos que estejam em seu caminho. Um objeto é qualquer objeto
que pode ser aproximado em um círculo. Isso pode ser alcançado direcionando um agente
de forma a manter a área de um retângulo - uma caixa de detecção, estendendo a frente
do agente - livre de colisões. A largura da caixa de detecção é igual ao raio delimitador
35
Figura 6: Wander (REYNOLDS, 1999)
do agente, e seu comprimento é proporcional à velocidade atual do agente - quanto mais
rápido for, maior será a caixa de detecção (BUCKLAND, 2005).
Figura 7: Obstacle Avoidance (BUCKLAND, 2005)
2.2.2.6 Path Following
Path Following (ou Seguimento de Caminho) cria uma força de direção que move
um agente por meio de uma série de pontos formando um caminho. Alguns caminhos
possuem um ponto inicial e final, e outras vezes eles dão a volta em torno de si formando
um caminho fechado e interminável (BUCKLAND, 2005).
Segundo BUCKLAND (2005), o modo mais simples de seguir um caminho é definir
o ponto de passagem atual para o primeiro lugar em uma lista, usar o algoritmo Seek até
que o agente alcance o ponto. Em seguida, deve-se definir o próximo ponto de passagem e
usar o Seek para alcançar o ponto e assim por diante, até que o ponto de passagem atual
seja o último ponto na lista. Quando isso acontece, o agente deve usar o algoritmo Arrive
no ponto de passagem atual, ou, se o caminho é uma volta fechada, o ponto de passagem
deve ser definido como o primeiro na lista novamente, e o agente continua sucessivamente
utilizando o algoritmo Seek.
36
Figura 8: Diferentes tipos de caminho. (BUCKLAND, 2005)
2.2.3 Grafos
2.2.3.1 Algoritmos de Grafos
Feofiloff et al. (2011) dizem que um grafo é um par (V, A) em que V é um conjunto
arbitrário e A é um subconjunto de V. Os elementos de V são chamados vértices e os de
A são chamados arestas.
Uma aresta como {v, w} será denotada simplesmente vw ou por wv. Diremos que
a aresta vw incide em v e em w e que v e w são as pontas da aresta. Se vw é uma aresta,
diremos que os vértices v e w são vizinhos ou adjacentes. De acordo com esta definição,
um grafo não pode ter duas arestas diferentes com o mesmo par de pontas (ou seja, não
pode ter arestas “paralelas”). Também não pode ter uma aresta com pontas coincidentes
(ou seja, não pode ter “laços”). A Figura 9 ilustra um desenho de um grafo cujos vértices
são t, u, v , w, x, y , z e cujas as arestas são vw, uv , xw, xu, yz e xy (FEOFILOFF et al.,
2011).
Figura 9: Representação de um Grafo. (FEOFILOFF et al., 2011)
Segundo (FEOFILOFF et al., 2011), muitas vezes é conveniente dar um nome ao
grafo como um todo. Se o nome do grafo for G, o conjunto dos seus vértices será denotado
por V (G) e o conjunto das V (G) suas arestas por A(G). O número de vértices de G é
denotado por n(G) e o número A(G) n(G) de arestas por m(G). Portanto,
n(G) = |V (G)| e m(G) = |A(G)|.
37
2.2.3.2 Lista de Adjacência
Um grafo G = (V, E) é representado por uma coleção de listas de adjacência ou
como uma matriz de listas de adjacência. A lista de adjacência (que será utilizada para
desenvolver o algorimo de travessia desse trabalho) consiste em um arranjo de adjacência
de |V | listas, uma para cada vértice em V. Para cada u ∈ V, a lista de adjacências Adj.
[u] contém (ponteiros para) todos os vértices v tais que existe uma aresta (u, v) ∈ E
(CORMEM et al., 2002). A Figura 10 a) representa um grafo não orientado que possui
oito vértices e nove arestas. A Figura b) representa um grafo não orientado como uma
lista de adjacências.
Figura 10: Representação de uma Lista de Adjacência. (CORMEM et al., 2002)
2.2.4 Busca em Largura
A busca em largura é um método de busca que utiliza uma fila para determinar a
ordem de visitação dos vértices (First in Firt Out, isto é, o primeiro que entra é o primeiro
que sai). Esta busca examina todos os vértices de certo nível do grafo antes dos vértices
do nível abaixo. Se o grafo é finito e se existe uma solução, então ela será encontrada por
este método (SILVA, 2005).
Em uma busca em largura a partir de um vértice v, espera-se que todos os vizinhos de v sejam visitados antes de continuar a busca mais profundamente. O algoritmo
mostrado abaixo ilustra de forma suscinta este tipo de busca (SILVA, 2005).
2.2.5 Algoritmo A*
Segundo Rabin (2002), o algoritmo A* deve encontrar um caminho entre dois
vértices em um grafo. Existem muitos algoritmos de busca, mas o A* encontra o menor
caminho, se existir, e fará isto relativamente rápido – é isto que o diferencia dos outros.
O algoritmo A* atravessa o grafo marcando vértices que correspondem às várias posições
exploradas. Esses vértices gravam o progresso da busca. Além de guardar a posição do
38
Figura 11: Pseudo-código da Busca em Largura (SILVA, 2005).
vértice em um espaço 2D, cada um desses vértices têm 3 atributos principais chamados
comumente de F, G e H (SILVA, 2005):
• O atributo G de um determinado vértice é o custo que se tem desde o vértice de
inicio até este vértice destino;
• O atributo H de um vértice é o custo estimado do caminho deste vértice até o vértice
final. H entende-se por heurística e significa “estimativa bem comportada”, visto que
realmente não se conhece esse custo;
• O atributo F é a soma de G e H. F representa a melhor avaliação para o custo de
um caminho passando através de um determinado vértice. Quanto menor o valor de
F, para um determinado vértice, maiores são as chances de ele fazer parte do menor
caminho.
O objetivo de F, G e H é quantificar o quão promissor é o caminho passando por
determinado vértice. O atributo G pode ser calculado. Ele é o custo para chegar ao vértice
corrente. Desde que se tenha explorado todos os vértices que apontam para este, sabe-se
o valor exato de G. Entretanto, o atributo H é completamente diferente. Desde que não se
saiba quanto além está o vértice final depois deste, deve-se estimar este valor. Na melhor
das avaliações, o F fica mais próximo do valor correto, e mais rápido o A* encontra o fim
com um pequeno esforço de empenho (RABIN, 2002). A Figura 12 mostra o algoritmo
A* em pseudo-código.
Como é demonstrado na Figura 12, o algoritmo A* mantém duas listas de vértices,
uma para vértices abertos e outra para fechados. O vértice raiz é o primeiro a entrar na
lista de abertos, e seu custo é marcado como zero. Como ele é o melhor e o único vértice
da lista, ele é o primeiro a ser analisado.
2.3. Engenharia de Software
39
Figura 12: Pseudo-código do Algoritmo A*(SILVA, 2005)
2.3 Engenharia de Software
2.3.1 Padrão de Projeto: State
O padrão State é um dos vinte e três padrões GoF3, destacado como um padrão
comportamental que se preocupa com os algoritmos e as atribuições de responsabilidades
entre objetos. O State permite que um objeto mude seu comportamento em tempo real.
Durante sua execução, e dependendo do estado interno do objeto, esse padrão permite
lidar com alterações comportamentais, dando uma falsa sensação de o objeto ter mudado
de classe. Esse padrão é utilizado quando o comportamento do objeto depende do seu
estado ou quando existirem operações condicionais muito grandes (SALES, 2008).
A base do State é uma classe abstrata que representará os estados em comum. Sub3
GAMMA, Erich; HELM, Richard; JOHNSON, Ralph; VLISSIDES, John. Padrões de Projeto: Soluções reutilizáveis de software orientado a objetos. Porto Alegre: Bookman, 2000. 364 p.
40
classes, filhas dessa classe abstrata, sobrescrevem os comportamentos com detalhamento
mais específico. (SALES, 2008).
A seguir, será apresentado um exemplo de aplicação do padrão State elaborado
por GAMMA et al. (2000).
Considere a classe TCPConnection que representa uma conexão numa rede de
comunicações. Um objeto TCPConnection pode estar em diversos estados diferentes: Established (Estabelecida), Listening (Escutando) e Closed (Fechada). Quando um objeto
TCPConnection recebe solicitações de outros objetos, ele responde de maneira diferente
dependendo do seu estado corrente. Por exemplo, o efeito de uma solicitação de Open
(Abrir), depende de se a conexão está no seu estado Closed ou no seu estado Estabished.
O padrão State descreve como TCPConnection pode exibir um comportamento diferente
em cada estado.
A ideia chave deste padrão é introduzir uma classe abstrata chamada TCPState
para representar os estados da conexão na rede. A classe TCPState declara uma interface
comum para todas as classes que representam diferentes estados operacionais. As subclasses de TCPState implementam comportamentos específicos ao estado. Por exemplo,
as classes TCPEstablished e TCPClosed implementam comportamentos específicos aos
estados Established e Closed de TCPConnection.
A Figura 13 ilustra esse raciocínio em um diagrama de classes.
Figura 13: Diagrama de Classes. (GAMMA et al., 2000)
A classe TCPConnection mantém um objeto de estado (uma instância da subclasse
de TCPState) que representa o estado corrente na conexão TCP.
Connection delega todas as solicitações específicas de estados para este objeto
de estado. TCPConnection usa sua instância da subclasse de TCPState para executar
operações específicas ao estado da conexão.
2.3. Engenharia de Software
41
Sempre que a conexão muda de estado, o objeto TCPConnection muda o objeto
de estado que ele utiliza. Por exemplo, quando a conexão passa do estado Established
para o estado Closed, TCPConnection subtituirá sua instância de TCPEstablished por
uma instância de TCPClosed.
2.3.2 Scrum
Scrum é uma metodologia ágil para gestão e planejamento de projetos de software. No Scrum, os projetos são dividos em ciclos (tipicamente mensais) chamados de
Sprints. O Sprint representa um Time Box dentro do qual um conjunto de atividades
deve ser executado. Metodologias ágeis de desenvolvimento de software são iterativas, ou
seja, o trabalho é dividido em iterações, que são chamadas de Sprints no caso do Scrum
(DESENVOLVIMENTOÁGIL.COM.BR, 2014).
As funcionalidades a serem implementadas em um projeto são mantidas em uma
lista que é conhecida como Product Backlog. No início de cada Sprint, faz-se um Sprint
Planning Meeting, ou seja, uma reunião de planejamento na qual o Product Owner prioriza os itens do Product Backlog e a equipe seleciona as atividades que ela será capaz de
implementar durante o Sprint que se inicia. As tarefas alocadas em um Sprint são transferidas do Product Backlog para o Sprint Backlog(DESENVOLVIMENTOÁGIL.COM.BR,
2014).
A cada dia de uma Sprint, a equipe faz uma breve reunião (normalmente de manhã), chamada Daily Scrum. O objetivo é disseminar conhecimento sobre o que foi feito
no dia anterior, identificar impedimentos e priorizar o trabalho do dia que se inicia. Ao
final de um Sprint, a equipe apresenta as funcionalidades implementadas em uma Sprint
Review Meeting. Finalmente, faz-se uma Sprint Retrospective e a equipe parte para o planejamento do próximo Sprint. Assim reinicia-se o ciclo, conforme pode ser visto na Figura
14 (DESENVOLVIMENTOÁGIL.COM.BR, 2014).
42
Figura 14: Metodologia Scrum (DESENVOLVIMENTOÁGIL.COM.BR, 2014)
2.4 Considerações Finais
Para se desenvolver a Inteligência Artificial de agentes autônomos, é necessário um
vasto conhecimento de técnicas clássicas de Inteligência Artificial. Neste trabalho, utilizarse-ão os conceitos Padrão de Projeto State, Máquinas de Estado, Comportamentos de
Direção, grafos, algoritmo A* entre outros.
43
3 Suporte Tecnológico
A seguir, serão descritas as principais ferramentas, com as quais se pretende conduzir o desenvolvimento desse trabalho.
3.1 Ferramentas de Desenvolvimento
3.1.1 Xcode
Xcode1 é uma IDE (Integrated Development Environment) que contém um conjunto de ferramentas de desenvolvimento de software. Desenvolvida pela empresa Apple.Inc 2 , essa ferramenta IDE apoia o desenvolvimento de software para sistemas OS X e
iOS. Lançada pela primeira vez em 2003, a última versão estável está disponível na Mac
App Store gratuitamente para usuários do sistema OS X Yosemite. Programadores que
possuem uma conta desenvolvedor da Apple, podem baixar os pré-lançamentos de versões
da ferramenta e versões anteriores através do domínio Apple Developer.
3.1.2 Sprite Kit
Sprite Kit é um framework de desenvolvimento de jogos para sistemas iOS que
fornece uma infra-estrutura de renderização de gráficos e de animação que pode ser usada
para animar imagens com texturas abritárias ou sprites. Sprite Kit utiliza um loop de
renderização tradicional, onde o conteúdo de cada quadro é processado antes do mesmo
ser renderizado. O jogo determina o conteúdo da cena e como esses conteúdos mudam em
cada quadro. Sprite Kit faz o trabalho de renderizar os quadros de animação de forma
eficiente utilizando hardware de vídeo. Sprite Kit é otimizado de forma que as posições
dos sprites podem ser alterados arbitrariamente em cada quadro da animação (APPLE,
2014).
Sprite Kit também fornece outras funcionalidades que são úteis para jogos, incluindo suporte para reprodução de som básico e simulação de física. Além disso, Xcode
fornece suporte embutido para Sprite Kit de modo que efeitos especiais complexos e texturas em atlas podem ser criados diretamento na IDE(APPLE, 2014).
1
2
<https://itunes.apple.com/us/app/xcode/id497799835>
<http://www.apple.com>
Capítulo 3. Suporte Tecnológico
44
3.1.3 OS X Yosemite
OS X3 (pronuncia-se OS Ten) é um sistema operacional proprietário baseado no
kernel Unix intitulado XNU, desenvolvido, fabricado e vendido pela empresa Apple.Inc.
Esse sistema operacional é destinado exclusivamente aos computadores Mac, combinando:
a experiência adquirida, a tradicional GUI desenvolvida para versões anteriores do Mac
OS, e um estável e comprovado núcleo. A última versão do OS X possui certificação UNIX.
Assim, o OS X, lançado inicialmente pela Apple Computer em 2001, é uma combinação
do Darwin (um núcleo derivado do micronúcleo Mach) com uma renovada GUI chamada
Aqua. As primeiras versões do Mach (não-micro núcleo) foram derivadas do BSD Berkeley
Software Distribution 4 .
O OSX v10.10 “Yosemite” é o décimo primeiro sistema operacional da família
OS X, sendo o sucessor do OSX v10.9 “Mavericks”. Anunciado em junho de 2014, pela
primeira vez desde “Aqua”, traz mudanças significativas na interface gráfica, adotando
transparências e design mais “limpo” inseridos no iOS 7. Foi lançado em 16 de outubro
de 2014.
3.1.4 Git
Git5 é um sistema de controle de versão distribuído e um sistema de gerenciamento
de código fonte, com ênfase em velocidade. O Git foi inicialmente projetado e desenvolvido
por Linus Torvalds para o desenvolvimento do kernel Linux, mas foi adotado por muitos
outros projetos.
3.1.5 Bitbucket
Bitbucket6 é um serviço de hospedagem de projetos controlados através do Mercurial e Git, sistemas de controle de versões distribuído. Bitbucket possui um serviço grátis
e um comercial, sendo escrito em Python.
3.1.6 LaTeX
LaTeX7 é um sistema de preparação de documentos para a composição tipográfica
de alta qualidade. É mais frequentemente usado para documentos técnicos ou científicos de
médio a grande porte, mas ele pode ser usado para quase qualquer forma de publicação.
LaTeX não é um processador de texto. No caso, LaTeX incentiva os autores a não se
3
4
5
6
7
<http://www.apple.com/osx/>
<http://www.bsd.org/>
<https://git-scm.com/>
<https://bitbucket.org/>
<http://latex-project.org/intro.html>
3.2. Considerações Finais
45
preocuparem muito com a aparência de seus documentos, e sim em obter o conteúdo
certo.
LaTeX é baseada na linguagem TeX de Donald E. Knuth. LaTeX foi desenvolvido
pela primeira vez em 1985 por Leslie Lamport, e agora está sendo mantido e desenvolvido
pelo Projeto LaTeX3 , disponível gratuitamente.
3.1.7 OCLint
OCLint8 é uma ferramenta de análise estática de código com finalidade de melhorar
a qualidade e reduzir defeitos. A ferramenta inspeciona código C, C++ e Objective-C
procurando potenciais problemas como:
• Possíveis erros (cláusulas if /else/try/catch/finally vazias);
• Código não utilizado (variáveis locais e parâmetros não utilizados);
• Código complicado (alta complexidade ciclomática);
• Código redundante, e
• Más práticas de programação.
Para o desenvolvimento de qualquer trabalho, é de suma importância definir quais
ferramentas serão utilizadas afim de se chegar ao resultado previsto. No TCC 01, ferramentas de escrita de documentos foram bem exploradas. Para o TCC 02, ferramentas
de escrita de código e de gerenciamento metodológico serão amplamente utilizadas no
decorrer da implementação.
8
<http://oclint.org/>
47
4 Metodologia
Neste capítulo, serão descritos os passos metodológicos que orientaram e orientarão
o desenvolvimento do TCC 01 e TCC 02, respectivamente.
4.1 Engenharia de Software Experimental
As metodologias específicas são necessárias para ajudar a estabelecer uma base
de engenharia e de ciência para a Engenharia de Software. Exitem quatro métodos relevantes para condução de experimentos na área de Engenharia de Software: científico, de
engenharia, experimental, e analítico (TRAVASSOS; GUROV; AMARAL, 2002).
O método experimental sugere o modelo, desenvolve o método qualitativo e/ou
quantitativo, aplica um experimento, mede e analisa, avalia o modelo e repete o processo.
Isto é uma abordagem orientada à melhoria revolucionária. O processo se inicia com
o levantamento de um modelo novo, não necessariamente baseado em um modelo já
existente, e tenta estudar o efeito do processo ou produto sugerido pelo modelo novo
(TRAVASSOS; GUROV; AMARAL, 2002).
Supõe-se que a abordagem mais apropriada para a experimentação na área de Engenharia de Software seja o método experimental que considera a proposição e avaliação
do modelo com os estudos experimentais. Entretanto, existe a possibilidade da utilização
de outros métodos. Às vezes, é necessário aplicá-los para a resolução dos problemas de
Engenharia de Software. Por exemplo, o método científico pode ser utilizado para compreender a maneira como o software está sendo construído por uma organização, avaliando
se uma ferramenta pode ser utilizada para automatizar o processo; o método de engenharia ajuda a demonstrar que uma ferramenta possui um desempenho melhor do que
outra; o método analítico pode provar modelos matemáricos para conceitos, como o crescimento da confiabilidade, a complexidade do software, o projeto ou código propenso a
erro (TRAVASSOS; GUROV; AMARAL, 2002).
Um experimento deve ser tratado como um processo da formulação ou verificação de uma teoria. A fim de que o processo ofereça os resultados válidos, ele deve ser
propriamente organizado e controlado ou, pelo menos, acompanhado. Com o propósito
de atingir estes objetivos, várias metodologias da experimentação possuem diferentes
características como, por exemplo, as fases do processo de experimentação, a maneira
da transformação dos conceitos abstratos do domínio às métricas concretas, o objetivo
principal da experimentação, as ferramentas do empacotamento, dentre outros detalhes
(TRAVASSOS; GUROV; AMARAL, 2002).
Capítulo 4. Metodologia
48
4.2 Pesquisa Exploratória
A pesquisa exploratória é realizada, segundo Vergara (2000), em áreas em que
existe pouco conhecimento acumulado e sistematizado. É, portanto, adequada para o
objetivo de aumentar o número de conhecimentos sobre o assunto, ou, nas palavras de
Gonçalves e Meirelles (2004, p. 37), é “realizada para descobrir ou descrever melhor o(s)
problema(s)-raiz que são apontados através de sintomas (ou queixas) para se alcançar os
objetivos.” Jr. et al. (2005) afirmam que a pesquisa exploratória é útil para o pesquisador
que não sabe muito.
LAKATOS e MARCONI (2001) consideram que a pesquisa exploratória deve estar
voltada para a formulação de questões ou de problemas de investigação, que aumentem a
familiaridade do pesquisador com o assunto, desenvolver hipóteses sobre o tema pesquisado e modificar ou esclarecer conceitos. DENCKER (2001) observa que as pesquisas exploratórias utilizam grande quantidade de dados extraídos de fontes secundárias, estudos
de casos selecionados e de observações informais, sendo os meios mais comuns de pesquisa
exploratória a pesquisa bibliográfica e o estudo de caso. Para Samara e Barros (2007), a
pesquisa exploratória tem como principais características a informalidade, a flexibilidade
e a criatividade, permitindo um primeiro contato com a realidade a ser investigada.
4.3 Planejamento dos Passos Metodológicos
Como o objetivo do trabalho é desenvolver a inteligência artificial de bots, a pesquisa será basicamente exploratória e experimental. No contexto do TCC 1, a pesquisa
exploratória foi bastante cabível, pois houve um estudo aprofundado de técnicas e algoritmos relacionados aos agentes autônomos e o conhecimento obtido foi documentado.
Inicialmente, foi feito um levantamento bibliográfico de várias abordagens de IA
para jogadores automatizados visando proporcionar maior familiaridade com o problema,
analisando algoritmos clássicos de Máquinas de Estados, Comportamentos de Direção e
afins. Tal estudo produziu insumos para a atividade Escolha de Estratégias de Implementação de IA, onde foram avaliadas todas as estratégias pesquisadas. As estratégias
que mais se adequarem ao contexto do jogo foram selecionadas para fins de implementação. Entende-se por adequadas as estratégias que possibilitarem, dentre outros aspectos
desejados:
• Melhor desempenho;
• Maior fidedignidade à questão de pesquisa (i.e. ter jogadores automatizados capazes
de jogar como se fossem jogadores humanos, equilibrando o jogo);
• Melhor abordagem em atendimento todos os objetivos específicos;
4.3. Planejamento dos Passos Metodológicos
49
Após a processo de escolha da estratégia, a proposta foi elaborada, o suporte
tecnológico definido e o referencial teórico refinado. Tais ações são representadas pelas
atividades Elaborar proposta e Levantar suporte tecnológico e pelo artefato Referencial
Teórico refinado. Estes passos fornecem base para o Desenvolvimento da Prova de Conceito, onde a arquitetura da Inteligência Artificial dos bots foi desenvolvida junto com a
Prova de Conceito. Terminada a Prova de Conceito, o Trabalho de Conclusão de Curso
(TCC) 01 foi escrito. Posteriormente, será apresentado à banca avaliadora. As sugestões
da banca serão coletadas para que o devido refinamento possa ser feito.
Pretende-se que as atividades de desenvolvimento sejam guiadas pela metodologia
ágil (Scrum, ou mesmo uma adaptação da mesma. Dado o uso da metodologia Scrum,
tem-se que o backlog será retroalimentado à medida que as pesquisas forem sendo consolidadas. Como os NPCs precisam possuir um nível alto de qualidade no que diz respeito à
inteligência (precisam ter um comportamento similar ao de jogadores humanos), os testes
funcionais serão definidos e realizados no contexto do TCC 02 usando, adicionalmente,
uma ferramenta de análise cobertura bem como uma ferramenta para análise estática de
código. Como os NPCs precisam parecer bem convincentes ao usuário, testes com usuários
finais também serão realizados.
A ferramenta a ser utilizada para análise estática do código será OCLint. A análise
de cobertura será feita através de um plugin desenvolvido por terceiros chamado XcodeCoverage1 .
A modalidade de pesquisa científica bem como de desenvolvimento do trabalho
serão refinadas ao longo da realização do trabalho. Entretanto, acredita-se que a candidata
à modalidade de pesquisa científica será pesquisa-ação 2 com cenário de uso ou mesmo
estudo de casos 3 . Entretanto, utilizar-se-á essa modadalidade com um foco maior na
análise dos resultados.
Quando os NPCs estiverem completamente desenvolvidos e testados, documentarse-ão os resultados obtidos para a escrita do TCC 02. Este será apresentado à banca, e em
seguida, refinado com base nas sugestões apontadas. A integração dos NPCs com o jogo
oficial e a publicação do jogo da App Store é a última fase de todo o ciclo de realização
do trabalho proposto.
O fluxo das macro atividades metodológicas destacadas nessa seção será ilustrado
na Figura 15, apresentada na próxima seção. Essa figura compreende a modelagem dos
passos metodológicos. Essa modelagem foi definda no Bizagi4 .
1
2
3
4
<https://github.com/jonreid/XcodeCoverage>
TRIPP, D. Pesquisa-ação: uma introdução metodológica. Educação e Pesquisa, Scielo, v. 31, p. 443 – 466, 12 2005. Disponível em: <http://www.scielo.br/scielo.php?
script=sci_arttext&pid=S1517-97022005000300009&nrm=iso>.
<http://www.fecap.br/adm_online/art11/flavio.htm>
<http://www.bizagi.com/>
Capítulo 4. Metodologia
50
4.4 Modelagem dos Passos Metodológicos
O fluxo está organizado quanto as atividades realizadas ao longo do TCC 01 bem
como quanto as atividades previstas para o TCC 02.
Figura 15: Processo do TCC
4.5. Cronograma
51
4.5 Cronograma
A Tabela 1 e Tabela 2 apresentam os cronogramas para, respectivamente, a realização do TCC_01 e a realização do TCC_02. O cronograma do TCC_02 está sujeito a
futuras alterações, conforme o andamento do trabalho.
Atividades
Levantamento Bibliográfico
Escolher Estratégias de Implementação de IA
Desenvolver Prova de Conceito
Elaborar Parte Escrita do TCC 01
Apresentar TCC 01 à banca
Aplicar correções da banca ao TCC
Março
X
Abril
X
X
Maio
X
X
X
X
Junho
Julho
X
X
X
X
Tabela 1: Cronograma do TCC 01
Atividades
Definir Estratégia de Teste de IA
Implementar NPCs
Testar solução
Documentar Resultados
Elaborar parte escrita do TCC 02
Apresentar TCC 02 à banca
Realizar correções no TCC 02
Agosto
X
X
Setembro
Outubro
X
X
X
X
X
X
Novembro
Dezembro
X
X
X
X
Tabela 2: Cronograma do TCC 02
Uma metodologia de desenvolvimento bem definida é essencial para o sucesso de
qualquer trabalho. Vários conceitos de Engenharia de Software são e serão utilizados no
decorrer do desenvolvimento deste trabalho, tais como: metodologia de pesquisa científica
(ex. exploratória, quantitativa e qualitativa), metodologia de desenvolvimento (ex. adaptação do Scrum), metodologia de análise de resultados (ex. pesquisa-ação e cenários de
uso), planejamento de prazo, verificação e validação, entre outros.
53
5 Proposta
Após várias pesquisas e levantamentos bibliográficos, definiu-se uma estratégia de
implementação dos agentes automatizados a qual será apresentada nesse capítulo.
5.1 Mapa do jogo
Os agentes automatizados devem percorrer o mapa do jogo com fluidez e sem se
chocarem nos obstáculos. A Figura 16 ilustra o mapa que será utilizado para desenvolver
a Inteligência Artificial desses bots.
Figura 16: Mapa do jogo
No canto inferior esquerdo e no canto superior direito ficam posicionadas as gemas
Capítulo 5. Proposta
54
que serão capturadas de ambas as equipes.As bases são as posições iniciais de todos os
jogadores (humanos e automatizados) no início da partida. As árvores e as pedras são os
obstáculos do mapa que os jogadores não podem se chocar.
Para que os agentes possam percorrer o mapa, é necessário que possuam um guia
de quais posições devem seguir afim de que posssam chegar até o seu objetivo. Para tanto,
utilizar-se-á a estratégia de grafos no mapa, onde cada nó indicará para qual posição no
mapa o agente deve se movimentar. A Figura 17 mostra uma representação de nós e
arestas que pretende-se implementar no mapa. Essa representação servirá de base para a
locomoção de todos os agentes automatizados do jogo.
Figura 17: Mapa com grafo.
Os círculos pretos representam os nós, e as hastes pretas as aretas. Os números
dentro dos nós tem o propósito de nomeá-los. Cada nó possui uma referência x,y que
representam a sua posição no mapa em pontos cartesianos, e uma referência para os nós
vizinhos. Cada aresta possui um atributo que indica a distância entre dois nós em termos
de pixels. A Figura 17 servirá de referência para explicação dos algoritmos e de alguns
comportamentos dos agentes no jogo.
5.2. Comportamento dos agentes automatizados
55
5.2 Comportamento dos agentes automatizados
Sabe-se que os agentes que irão atuar no jogo Lost Gems possuem uma série de
comportamentos. Esses comportamentos devem realizar afim de que os objetivos estabelecidos possam ser cumpridos de forma satisfatória. Para tanto, dividiu-se o comportamento
dos agentes em dois macro perfis: atacante e defensor.
5.2.1 Perfil Atacante
O agente atacante é responsável por tomar a iniciativa de procurar a gema no
mapa, capturá-la e levá-la até a base aliada para ganhar a partida. Também deve atacar
os inimigos que encontrar em seu caminho, assim como persegui-los. Essa perseguição
é temporária, acabando quando um tempo limite for atingido ou o quando o agente
“morrer” ou derrotar o seu oponente. Após o fim da perseguição, o jogador automatizado
deve continuar a sua busca pela gema, ou levar a gema à base aliada.
Esse comportamento foi deduzido de forma a se adequar a uma Máquina de Estados, onde cada comportamento é um estado da máquina. A Figura 18 indica um diagrama
de estados pensado para o perfil atacante de forma a facilitar a compreensão e a modelagem do comportamento do agente.
Figura 18: Diagrama de Estados - Perfil Atacante
56
No estados “Andando procurando a gema” e “Levando gema inimiga à base aliada”, o agente deve percorrer o mapa afim de alcançar uma das bases. Para que isso seja
possível, o jogador automatizado deve seguir caminhos pré-estabelecidos, a saber, uma
lista de nós sequenciais que possuem referência para sua própria localização. O agente
deve seguir essas listas de forma sequencial começando do primeiro nó da lista, ou o último, dependendo de qual base ele está indo. Os caminhos formados por nós são (L é uma
lista que contém a referência dos nós, e os números são os identificadores de cada nó de
acordo com a Figura 17):
• L = {1, 4, 9, 15, 16};
• L = {1, 4, 3, 2, 8, 13, 16};
• L = {1, 5, 10, 12, 15, 16};
• L = {1, 5, 10, 12, 11, 9, 15};
• L = {1, 4, 3, 2, 6, 7, 8, 13, 16} e
• L = {1, 5, 11, 9, 15, 16}.
Cada vez que entrarem nos estados “Andando procurando a gema” e “Levando
gema inimiga à base aliada”, os agentes atacantes devem escolher aleatoriamente um dos
caminhos citados anteriormente para seguirem (caso a gema inimiga esteja localizada na
base). Os mesmos utilizarão os Comportamentos de Direção Path Following e Obstacle
Avoidance quando seguirem por um caminho, afim de que seu movimento não pareça
muito “robotizado”.
Quando os bots atacantes entrarem no estado “Atacando”, eles devem usar os
Comportamentos de Direção Seek e Obstacle Avoidance na perseguição do inimigo, enquanto estiverem nesse estado. Também devem atirar no inimigo enquanto o perseguem,
ou utilizar uma habilidade específica (a escolha de uso da habilidade específica será feita
de forma aleatória). Quando saírem desse estado, os agentes devem usar o algoritmo de
busca de menor caminho A* para chegarem até à respectiva base.
Caso os agentes atacantes capturarem a gema inimiga que se encontra fora da
base, eles devem usar o algoritmo A* para encontrar o caminho de sua base, e em seguida
segui-lo utilizando do Comportamento de Direção Path Following.
5.3. Perfil Defensor
57
A Figura 19 demonstra um diagrama de classes proposto para o comportamento
do agente atacante.
Figura 19: Diagrama de Classes - Perfil Atacante
Nota-se que a utilização do Padrão de Projeto State para construir o diagrama.
Nesse caso, cada estado do agente é uma classe única, que herda de uma classa abstrata
“State”, que por sua vez possui uma relação de agregação com a classe “BotAttacker”.
A classe “Steering Behaviours” possui os métodos que realizam as ações dos comportamentos de direção que o bot desempenhará. A classe “PathManager”possui os métodos
que gerenciam os caminhos a serem seguidos; um método realiza o sorteio dos caminhos
pré-estabelecidos, e outro realiza o algoritmo A* para encontrar o menor caminho entre
a posição do bot e a posição da gema.
5.3 Perfil Defensor
O agente defensor é responsável por patrulhar a base aliada de modo a evitar que
outros jogadores capturem a gema, e também buscar a gema roubada no mapa e retornála à base de origem. O bot defensor deve atacar inimigos assim como o agente atacante,
mas apenas por um período de tempo pré-estabelecido, pois seu papel principal é “vigiar”
a base aliada e recuperar a gema perdida.
Esse comportamento foi deduzido de forma a se adequar a uma Máquina de Estados, onde cada comportamento é um estado da máquina. A Figura 20 indica um diagrama
de estados elaborado para o perfil defensor de forma a facilitar a compreensão e a modelagem do comportamento do agente.
Quando o agente defensor entra no estado “Patrulhando a base”, ele deve utilizar
o Comportamento de Direção Wander em torno da base, afim de que o seu movimento
pareça real e não “robotizado”.
58
Figura 20: Diagrama de Estados - Perfil Defensor
Caso encontre algum inimigo (entrando no estado “Atacando”), o agente deve
utilizar o Comportamento de Direção Seek e Obstacle Avoidance para perseguir o inimigo
enquanto estiver nesse estado. Também deve atirar no inimigo enquanto o persegue, ou
utilizar uma habilidade específica (a escolha de uso da habilidade específica será feita de
forma aleatória). Após a perseguição, quando entrar no estado “Retornando à base”, o
bot defensor deve usar o algoritmo de busca de menor caminho A* para chegar até à base
aliada.
Se o bot entrar no estado “Buscando a gema aliada”, o mesmo deve utilizar o
algoritmo A* de busca de menor caminho para chegar até a gema roubada. Como a posição
da gema pode mudar a cada instante, o bot deve executar o algoritmo a cada 2 segundos
para se obter a localização da gema de forma mais otimizada. Para seguir o caminho
definido pelo A*, o agente deve utilizar os Comportamentos de Direção Path Following e
Obstacle Avoidance quando seguirem por um caminho, afim de que seu movimento não
pareça muito “robotizado”.
A Figura 21 demonstra um diagrama de classes proposto para o comportamento
do agente defensor.
5.4. Nível de dificuldade
59
Figura 21: Diagrama de Classes - Perfil Defensor
Nota-se que, assim como no diagrama do agente atacante, Padrão de Projeto State
foi utilizado para construir o diagrama. Percebe-se isso porque cada estado do agente é
uma classe única, que herda de uma classa abstrata “State”, que por sua vez possui uma
relação de agregação com a classe “BotDefender”. A classe “Steering Behaviours” possui os
métodos que realizam as ações dos comportamentos de direção que o bot desempenhará.
A classe “PathManager”possui os métodos que gerenciam os caminhos a serem seguidos
(um método realiza o sorteio dos caminhos pré-estabelecidos, e outro realiza o algoritmo
A* para encontrar o menor caminho entre a posição do bot e a posição da gema).
5.4 Nível de dificuldade
Propõe-se que os agentes automatizados, quando prontos, sejam capazes de enfrentar outros agentes semelhantes e também jogadores humanos. Para tanto, o jogo deve
ser equilibrado de forma que o usuário não se sinta frustrado com um nível de dificuldade muito alto ou entediado por causa de uma dificuldade muito baixa. Pensando nisso,
definiu-se três níveis de dificuldade que podem ser escolhidos pelo usuário: Fácil, Médio e
Difícil.
Para exemplificação dos níveis, assumiu-se que um jogador possui uma quantidade
de energia total E e que cada tiro básico disparado por este subtrai um dano D de E de
outro jogador.
Cada nível terá as seguintes particulariedades:
• Fácil: Os bots possuem uma quantidade total de energia E/2 e tiram dano D/2 de
cada jogador atingido;
• Médio: Os bots possuem uma quantidade total de energia E e tiram dano D de cada
jogador atingido, e
60
• Difícil: Os bots possuem uma quantidade total de energia E*2 e tiram dano D*2 de
cada jogador atingido.
Desenvolver a Inteligência Artificial de agentes automatizados pode ser bastante
complexo e custoso. As estratégias clássicas já estabelecidas e amplamente difundidas no
meio científico apoiam esse desenvolvimento, permitindo estabelecer algoritmos elegantes
e funcionais de IA para agentes autônomos.
Todo o jogo será escrito na linguagem de programação Objective-C, utilizando-se
a bilbioteca Sprite Kit. A implementação dos bots em Lost Gems será feita orientandose: pelo Padrão de Projeto “State”(porque é perfeitamente cabível para uma Máquina
de Estados), pelos algoritmos de Comportamentos de Direção elaborados por Reynolds
(1999) para dar mais fluidez ao movimento dos agentes, pelos caminhos pré-estabelecidos
por meio de uma lista de nós a serem percorridos no mapa (apenas para o bot atacante),
e por fim, pelo algoritmo A* de busca de menor caminho, tanto para o agente atacante
como para o defensor.
Todo esse desenvolvimento é apoiado por uma pesquisa exploratória afim de se
obter a melhor estratégia de implementação, e uma pesquisa guiada pela Engenharia
de Software Experimental. A implementação em si será guiada pela metodologia ágil
Scrum, com sprints de duas semanas. Serão avaliadas quantas histórias de usuário serão
concluídas a cada sprint, com o objetivo de quantificar a produtividade de desenvolvimento
e implementação dos algoritmos propostos.
Após a conclusão de cada história, essa será testadas utilizando-se de critérios que
serão definidos posteriormente. Procurará, adicionalmente, realizar verificação e validação.
A primeira no intuito de verificar a aplicação em si através, por exemplo, de testes unitários
combinados à cobertura de testes ou mesmo de testes de carga para avaliar o desempenho.
A segunda com o apoio de usuários reais, visando avaliar se a IA dos bots é satisfatória
de acordo com os objetivos pré-estabelecidos.
Todo o controle de versão do código gerado será feito a partir da ferramenta Git,
e enviado ao servidor remoto BitBucket.
61
6 Prova de Conceito
Para que as técnicas e abordagens de Inteligência Artificial escolhidas fossem melhor compreendidas, desenvolveu-se uma prova de conceito. Essa prova de conceito permitiu a obtenção de um melhor entendimento das estratégias de implementação escolhidas
para o desenvolvimento da aplicação. Este capítulo também visa exemplificar e justificar
a escolha das estratégias adotadas para a implementação dos agentes automatizados.
6.1 Representação do Mapa em Grafos
Primeiramente, analisou-se o problema de como gerar caminhos e pontos no mapa
afim de que os agentes possam se movimentar seguindo esses pontos. Para isso, considerouse a estratégia de Grids(RABIN, 2002, p. 560) e de grafos para a representação do espaço
onde o agente pode se locomover. A abordagem de grafos foi escolhida pois segundo Rabin
(2002) enquanto uma típica célula de uma Grid é conectada com oito células vizinhas,
conforme é vista na Figura 22, um nó de um grafo pode ser conectado a qualquer número
de nós. Isso faz com que grafos de nós se tornem muito mais flexíveis do que Grids.
Figura 22: Exemplo de um mapa representado por Grid
Para a representação do grafo, deduziu-se uma malha com um número elevado de
nós. A Figura 23 exemplifica essa representação, onde cada nó (círculos pretos) estaria
ligado ao nó vizinho através de uma aresta invisível.
Nessa representação de mapa, considerou-se utilizar o algoritmo de Busca em Largura para se determinar o menor caminho entre dois dados nós. Tomou-se essa decisão
Capítulo 6. Prova de Conceito
62
Figura 23: Representação inicial do mapa com grafo.
pois esse algoritmo não faz uso da distância entre os nós (peso das arestas) para o cálculo
do caminho. Entretanto, após se analisar outras estratégias e algoritmos (A* por exemplo) concluíu-se que essa representação de mapa demandaria uma quantidade excessiva e
desnecessária de memória do hardware, pela grande quantidade de nós e arestas a serem
gerados.
Com base nisso, desenvolveu-se uma nova representação do mapa com grafos, agora
com menos nós e arestas. A Figura 17 localizada no capítulo 5 mostra essa abordagem.
Nessa representação, as arestas possuem um peso, que é a distância em pixels que cada
nó possui um do outro. Para busca de menor caminho optou-se pelo algoritmo A*, já que
os nós possuem pesos diferentes uns dos outros.
6.2 Comportamentos de Direção
Para validação dos Comportamentos de Direção, codificou-se em Objective-C três
das estratégias criadas por Reynolds (1999): Seek, Flee e Arrive. O apêndice 1 mostra o
código implementado.
6.3. Status Atual
63
Os exemplos gerados demonstram um quadrado azul que possui uma tragetória
fixa, e um quadrado vermelho que executa várias ações. A Figura 24 demonstra a aplicação
sendo executada em um simulador de iPhone.
Figura 24: Aplicação executando em um simulador.
A classe “SteeringBehaviours.m” possui três métodos que executam os algoritmos
de direção. A assinatura deles são:
• -(CGPoint) seek:(CGPoint)targetPos;
• -(CGPoint) flee:(CGPoint)targetPos, e
• -(CGPoint) arrive:(CGPoint)targetPos andDeceleration:(float)slowingRadius.
O parâmetro “targetPos” é uma estrutura que possui duas variáveis (x,y) que
representam a posição atual do quadrado azul em cada frame da simulação. O parâmetro
“slowingRadius”representa a distância mínima exigida entre o quadrado azul e o vermelho,
para que este comece a desacelerar.
Cada método retorna uma vetor de força direcional que atua sobre o quadrado
vermelho. Na simulação, pode-se perceber que os algoritmos implementados atendem
bem ao contexto pretendido.
6.3 Status Atual
Como demonstrado no capítulo 5, já se possui vários insumos para o desenvolvimento dos jogadores automatizados.
Capítulo 6. Prova de Conceito
64
Já se esquematizou o diagrama de classes para ambos os perfis de bots (atacante e
defensor), assim como os respectivos diagramas de estados. Os diagramas de classes foram
escritos seguindo o Padrão de Projeto State.
Também foram definidas as localizações aproximadas dos nós do grafo a ser implementado, bem como as suas arestas. Para busca de menor caminho no grafo, definiu-se
o algoritmo A*.
Para que o agente automatizado possa desenvolver várias ações de movimentos no
mapa, foram definidos alguns comportamentos de direção a serem implementados (Seek,
Arrive, Flee, Obtacle Avoidance e Path Following). Implementou-se uma simulação dos
comportamentos Seek, Arrive e Flee em Objective-C.
Para o TCC 2, espera-se escrever histórias de usuário que exemplificam as funcionalidades principais, e em seguida implementá-las no tempo designado pelas sprints.
Testes unitários serão escritos e o código será analisado por ferramentas de análise estática,
e de análise de cobertura de código.
Analisar-se-ão os resultados obtidos por meio da modalidade de pesquisa científica
pesquisa-ação, com cenário de uso ou mesmo estudo de casos.
Percebeu-se que o desenvolvimento da prova de conceito foi de grande valia para a
validação das ideias e algoritmos propostos. Analisar diferentes algoritmos e abordagens
também foi fundamental para que uma proposta coerente e embasada fosse escrita.
Considera-se que para o TCC 1, o trabalho está bem detalhado e desenvolvido. Já
se possui diagramas de classe, de estado, algoritmos definidos, entre outros insumos.
65
Referências
APPLE. About Sprite Kit. 2014. Disponível em: <https://developer.apple.com/library/
ios/documentation/GraphicsAnimation/Conceptual/SpriteKit_PG/Introduction/
Introduction.html>. Citado na página 43.
BEVILACQUA, F. Understanding Steering Behaviors: Seek. 2012.
Disponível em: <http://gamedevelopment.tutsplus.com/tutorials/
understanding-steering-behaviors-seek--gamedev-849>. Citado 5 vezes nas
páginas 13, 30, 31, 32 e 33.
BUCKLAND, M. Programming Game AI by Example. 1. ed. [S.l.]: Wordware Publishing,
2005. 495 p. Citado 6 vezes nas páginas 13, 24, 32, 34, 35 e 36.
CORMEM, T. H. et al. Algoritmos: teoria e prática. 2. ed. Rio de Janeiro: Campus,
2002. Citado 2 vezes nas páginas 13 e 37.
DENCKER, A. d. F. M. Métodos e técnicas de pesquisa em turismo. 4. ed. São Paulo:
Futura, 2001. Citado na página 48.
DESENVOLVIMENTOÁGIL.COM.BR. Scrum. 2014. Disponível em: <http://www.
desenvolvimentoagil.com.br/scrum/>. Citado 3 vezes nas páginas 13, 41 e 42.
FEOFILOFF, P. et al. Uma introdução sucinta à teoria dos grafos. 2011. Disponível em:
<http://www.ime.usp.br/~pf/teoriadosgrafos/>. Citado 2 vezes nas páginas 13 e 36.
GAMMA, E. et al. Padrões de Projeto: Soluções reutilizáveis de software orientado a
objetos. Porto Alegre: Bookman, 2000. 364 p. Citado 2 vezes nas páginas 13 e 40.
GONçALVES, C. A.; MEIRELLES, A. de M. Projetos e relatórios de pesquisa em
Administração. São Paulo: Atlas, 2004. Citado na página 48.
HASTJARJANTO, T.; JEURING, J.; LEATHER, S. A dsl for describing the artificial
intelligence in real-time video games. 3rd International Workshop on, p. 18, May 2013.
Citado na página 24.
HOSEA, S.; HARIKRISHNAN, V.; RAJKUMAR, K. Artificial intelligence. In:
Electronics Computer Technology (ICECT), 2011 3rd International Conference on. [S.l.:
s.n.], 2011. v. 4, p. 124–129. Citado na página 27.
HU, W.; ZHANG, Q.; MAO, Y. Component-based hierarchical state machine - a reusable
and flexible game ai technology. In: Information Technology and Artificial Intelligence
Conference (ITAIC), 2011 6th IEEE Joint International. [S.l.: s.n.], 2011. v. 2, p.
319–324. Citado na página 28.
JR., J. H. et al. Fundamentos de métodos de pesquisa em Administração. Porto Alegre:
Bookman, 2005. Citado na página 48.
LAKATOS, E. M.; MARCONI, M. d. A. Fundamentos de metodologia científica. 4. ed.
São Paulo: Atlas, 2001. Citado na página 48.
66
Referências
LI, H. Application of artificial intelligence in computer aided instruction. In: Test and
Measurement, 2009. ICTM ’09. International Conference on. [S.l.: s.n.], 2009. v. 2, p.
221–224. Citado na página 27.
NING, S.; YAN, M. Discussion on research and development of artificial intelligence. In:
Advanced Management Science (ICAMS), 2010 IEEE International Conference on. [S.l.:
s.n.], 2010. v. 1, p. 110–112. Citado na página 27.
RABIN, S. AI game programing wisdow. Massachusets: Charles River Media, 2002.
Citado 3 vezes nas páginas 37, 38 e 61.
RECIO, G. et al. Antbot: Ant colonies for video games. Computational Intelligence and
AI in Games, IEEE Transactions on, v. 4, n. 4, p. 295–308, Dec 2012. Citado na página
28.
REYNOLDS, C. W. Steering behaviors for autonomous characters. In: Game developers
conference. [S.l.: s.n.], 1999. v. 1999, p. 763–782. Citado 9 vezes nas páginas 13, 29, 30,
31, 32, 33, 35, 60 e 62.
SALES, S. Padrão de projeto: State. Faculdade de Ciências e Tecnologia – FIB - Centro
Universitário da Bahia, p. 4, Setembro 2008. Citado 2 vezes nas páginas 39 e 40.
SAMARA, B. S.; BARROS, J. C. Pesquisa de Marketing: Conceitos e metodologia. 4.
ed. São Paulo: Pearson Prentice Hall, 2007. Citado na página 48.
SHIFFMAN, D. et al. The nature of code. [S.l.]: D. Shiffman, 2012. Citado na página 29.
SILVA, J. B. D. Estudo comparativo entre algoritmo A* e busca em largura para
planejamento de caminho de personagens em jogos do tipo Pacman. 2005. Citado 4
vezes nas páginas 13, 37, 38 e 39.
TRAVASSOS, G. H.; GUROV, D.; AMARAL, E. Introdução à engenharia de software
experimental. [S.l.]: UFRJ, 2002. Citado na página 47.
VERGARA, S. C. Projetos e relatórios de pesquisa em administração. 3. ed. São Paulo:
Atlas, 2000. Citado na página 48.
XIE, T. The synergy of human and artificial intelligence in software engineering. 3rd
International Workshop on, p. 25–26, May 2013. Citado na página 24.
Apêndices
69
APÊNDICE A – Código Fonte da classe
SteeringBehaviours
//
//
S t e e r i n g B e h a v i o r s .m
//
//
Network t e s t M u l t i p e e r
//
//
C re a te d by Bruno Ro d ri g ue s de Andrade on 1 2 / 0 6 / 1 5 .
C o p y r i g h t ( c ) 2015 Bruno Ro d ri g ue s de Andrade . A l l r i g h t s
reserved .
//
#import " S t e e r i n g B e h a v i o r s . h "
#import " RedSquare . h "
@implementation S t e e r i n g B e h a v i o r s
− ( instancetype ) i n i t
{
s e l f = [ super i n i t ] ;
if ( self ) {
s e l f . wanderTarget = CGPointMake ( 0 , 0 ) ;
}
return s e l f ;
}
−(CGPoint ) s e e k : ( CGPoint ) t a r g e t P o s {
CGPoint d e s i r e d V e l o c i t y = CG Po int Mult iplySca la r (
CGPointNormalize ( CGPointSubtract ( t a r g e t P o s , s e l f .
r edSqua r e . p o s i t i o n ) ) , s e l f . r edSqua r e . maxSpeed ) ;
return CGPointSubtract ( d e s i r e d V e l o c i t y , s e l f . r edSqua r e .
vectorVelocity ) ;
}
APÊNDICE A. Código Fonte da classe SteeringBehaviours
70
−(CGPoint ) f l e e : ( CGPoint ) t a r g e t P o s {
double p a n i c D i s t a n c e = 1 0 0 ;
i f ( CGPointDistancePoints ( s e l f . r edSqua r e . p o s i t i o n , t a r g e t P o s )
> panicDistance ) {
return CGPointMake ( 0 , 0 ) ;
}
CGPoint d e s i r e d V e l o c i t y = CG Po int Mult iplySca la r (
CGPointNormalize ( CGPointSubtract ( s e l f . r edSqua r e .
p o s i t i o n , t a r g e t P o s ) ) , s e l f . r edSqua r e . maxSpeed ) ;
return CGPointSubtract ( d e s i r e d V e l o c i t y , s e l f . r edSqua r e .
vectorVelocity ) ;
}
−(CGPoint ) a r r i v e : ( CGPoint ) t a r g e t P o s a n d D e c e l e r a t i o n : ( f l o a t )
slowingRadius {
CGPoint d e s i r e d V e l o c i t y ;
CGPoint t o Ta r g et = CGPointSubtract ( t a r g e t P o s , s e l f .
r edSqua r e . p o s i t i o n ) ;
double d i s t = CGPointLength ( t o Ta r g et ) ;
i f ( d i s t < slowingRadius ) {
double speed = d i s t / s l o w i n g R a d i u s ;
speed = [ s e l f t r u n c a t e S p e e d : speed a n d V e l o c i t y : s e l f .
r edSqua r e . maxSpeed ] ;
d e s i r e d V e l o c i t y = CG Po int Mult iplySca la r (
CG Po int Mult iplySca la r ( CGPointNormalize ( t o Ta r g et ) ,
s e l f . r edSqua r e . maxSpeed ) , speed ) ;
}
else {
[ s e l f seek : targetPos ] ;
d e s i r e d V e l o c i t y = CG Po int Mult iplySca la r ( CGPointNormalize
( d e s i r e d V e l o c i t y ) , s e l f . r edSqua r e . maxSpeed ) ;
71
}
return ( CGPointSubtract ( d e s i r e d V e l o c i t y , s e l f . r edSqua r e .
vectorVelocity ) ) ;
}
−(CGPoint ) p u r s u i t : ( Square ∗ ) eva der {
CGPoint toEvader = CGPointSubtract ( eva der . p o s i t i o n , s e l f .
r edSqua r e . p o s i t i o n ) ;
double lookAheadTime = CGPointLength ( toEvader ) / ( s e l f .
r edSqua r e . maxSpeed + CGPointLength ( eva der .
vectorVelocity ) ) ;
CGPoint a s = CGPointAdd ( eva der . p o s i t i o n ,
CG Po int Mult iplySca la r ( eva der . v e c t o r V e l o c i t y ,
lookAheadTime ) ) ;
return [ s e l f s e e k : CGPointAdd ( eva der . p o s i t i o n ,
CG Po int Mult iplySca la r ( eva der . v e c t o r V e l o c i t y ,
lookAheadTime ) ) ] ;
}
@end

Bruno Rodrigues de Andrade - UnB Gama

Transcrição

Documentos relacionados

Naruto Shippuden Ult. Ninja Storm 3

Colonizadores de Catan

Ídolos

Ficha de Protótipo Gamerama Qual o nome do jogo? Jogo da

brilhantemente ganho pelos Pittsburgh Steelers, lembrei-me

Desenvolvimento de Software de Qualidade através de

primeira prova do predator 10-ball championship tour

OBSERVATÓRIO TRANSNACIONAL DE JOGO REMOTO

Swatch Golf Cup - Lisbon Sports Club

UNIVERSIDADE PAULISTA – UNIP – CAMPI BRASÍLIA

Bendito TCC por Rachel Eid Polito* O TCC (ou Trabalho de