Máquinas de Estados Finitos Aplicados a Jogos

1
Revista Eletrônica da Faculdade Metodista Granbery
http://re.granbery.edu.br - ISSN 1981 0377
Curso de Sistemas de Informação – N.14, JUL/DEZ2013
Máquinas de Estados Finitos Aplicados a Jogos Eletrônicos
Cesar Roberto de Sousa Loureiro Júnior1
Elena Dias Bastos2
Munir CheikKaled de Moraes3
Paola Jenifer Cañete Rodrigues Gonçalves4
Sérgio Muinhos Barroso Lima5
RESUMO: Atualmente no mercado, percebe-se um crescimento significativo
nas tecnologias na área dos jogos eletrônicos. Os games tem conquistado uma
posição de destaque. O mercado oferece uma gama de possibilidades de acordo
com o gosto de cada usuário. Com o uso da inteligência artificial, os jogos têm
proporcionado desafios de forma à atrair usuários de diversas faixas etárias,
possibilitando o sentimento e sensação de outra realidade com o uso do mundo
virtual. Esse artigo tem por objetivo apresentar a utilização de Máquinas de estados
finitos e suas aplicações em Inteligência Artificial (IA) nos jogos, além de um estudo
de caso do jogo PAC-MAN.
PALAVRAS-CHAVE: Jogos Eletrônicos, Inteligência Artificial, IA, Máquinas de
Estados Finitos, Pac-Man.
ABSTRACT:
Currently on the market, there is a significant growth of the technologies in
the field of electronic games. The games have earned a prominent position. The
market offers a range of possibilities according to the taste of each user. With the use
of artificial intelligence, games have provided challenges in order to attract users of
1
Bacharelando em Sistemas de Informação, Faculdade Metodista Granbery, [email protected].
Bacharelando em Sistemas de Informação, Faculdade Metodista Granbery, [email protected].
3
Bacharelando em Sistemas de Informação, Faculdade Metodista Granbery, [email protected].
4
Bacharelando em Sistemas de Informação, Faculdade Metodista Granbery, [email protected].
5
Mestre em Ciência da Computação, UNICAMP, [email protected].
2
2
different ages, allowing the feeling and sense of another reality with the use of the
virtual world. This article aims to present the use of handling techniques, finite state
machines and their applications in Artificial Intelligence (AI) in games, and a case
study of the game PAC-MAN.
KEY-WORDS: Electronic games, Artificial Intelligence, Finite State Machines,
Pac-Man.
1.
INTRODUÇÃO
A tecnologia, e o avanço no desenvolvimento de softwares, têm-se
reproduzido em máquinas do mundo real. Para que essa interação do mundo virtual
com o real ficasse cada vez mais atrativa e parecida com tarefas do nosso cotidiano.
Para isso, utilizou-se das técnicas da Inteligência Artificial, que teve seu inicio após a
segunda guerra mundial com os estudos do matemático Alan Turing. Desde essa
época começaram então um avanço na IA, com aplicações em jogos eletrônicos, no
intuito de serem cada vez mais atrativos para seus usuários.
Para fazer essa interação da interface dos jogos com os usuários,
utilizam-se várias técnicas de movimentação que serão mais aprofundadas no
decorrer desse artigo. Mais à frente, surgiu a máquina de estados finitos, que pode
ser usada de forma a se estabelecer um padrão de ações ou execuções a partir de
condições atendidas no decorrer dos jogos, o que pode levar o jogo a se tornar
previsível, como também pode ser programada e configurada, podendo tornar o jogo
complexo e imprevisível. A abordagem do estudo de caso Pac-Man, exemplifica o
uso da máquina de estado finito.
O estudo de caso, o jogo Pac-Man, demonstra o surgimento de um
importante marco na aplicação e evolução da IA em jogos. A utilização de máquinas
de estados finitos abriu as portas para novas descobertas e melhorias na sua
aplicação. O Jogo Pac- Man não foi apenas um novo game, e sim um novo conceito
de utilização da IA aliada a Máquina de Estados Finitos em jogos.
Com uma interface simples o jogo Pac-Man encobriu sua complexa
programação, que o torna dinâmico, mesmo sendo uma máquina que realize sempre
o mesmo tipo de execução que se espera em uma máquina de estados finitos.
Através das personalidades (algoritmos de busca) implementadas em cada
3
fantasma, o jogo ganha uma imagem de desafio e superação, pois quanto maior o
cenário a ser percorrido mais difícil é a tarefa de escapar dos fantasmas inteligentes.
2.
Histórico da IA nos Jogos Eletrônicos.
As ciências da computação têm explorado estudos sobre as diversas
tecnologias e diferentes formas de programar, a fim de desenvolver estruturas
capazes de serem inteligentes de maneira que possam ter a capacidade de
aprender novas informações, desta forma é possível que uma máquina ou software
tenha a capacidade de reagir e ter comportamentos de acordo com regras
determinadas, estímulos ou até mesmo ações humanas, isto é, da mesma maneira
que um ser humano reagiria, pensaria ou faria.
O conceito de I.A(Inteligência Artificial) iniciou-se após a Segunda Guerra
Mundial com alguns estudos e trabalhos do matemático Alan Turing que produziu o
artigo "Computing Machinery and Intelligence" dando início aos maiores estudos de
IA, desde então, vem sendo melhorados e implementados até os dias de hoje. Já
para os acadêmicos, a IA é uma gama de possibilidades infinitas de como criar um
ser inteligente usando computadores.
Em 1958, o cientista William Higinbotham (também conhecido por ter
participado do projeto Manhattan, que construiu a bomba atômica), criou o primeiro
jogo eletrônico "Tennis for Two", demonstrado na figura 1, e neste mesmo ano, o
jogo ficou em demonstração para o público, a fim de exibir a capacidade do
laboratório de pesquisa em criar um jogo eletrônico com um computador analógico
ligado a um osciloscópio, capaz de simular uma partida de tênis. Porém
Higinbotham, nunca registrou legalmente sua criação, e um ano após, o jogo foi
descontinuado. No entanto, em 1997, um grupo de engenheiros tentaram recriar o
game para as comemorações de aniversário de 50 anos do laboratório de
Brookhaven, local onde o game foi inicialmente criado. Willy Higinbotham, ficou
conhecido no meio da computação para jogos, somente décadas após sua
invenção, Tennis for Two.
4
Figura 1: O Primeiro Jogo Eletrônico com o auxilio de um Osciloscópio Tennis for Two em 1958. Fonte: (FILGUEIRAS, 2012 )
O jogo “Tennis for Two” propunha uma simulação bem simplificada do
esporte. Um ponto piscando representava a bola e os jogadores manipulavam seu
movimento por cima de uma linha vertical que simbolizava a rede. Não havia na
imagem a representação dos jogadores, apenas da ‘bola’ e da ‘quadra’ de tênis,
numa vista lateral(figura 1). Este jogo nunca saiu do laboratório.
Em 1961 um grupo de estudantes do Massachusetts Institute of
Technology (MIT) programou o primeiro jogo eletrônico interativo na história o
Spacewar, onde duas pessoas controlavam duas espaço-nave diferentes e que
deveriam lutar entre si. O programa foi desenvolvido no DEC PDP-1, um antigo
computador com o tamanho de uma mesa. Os criadores de Spacewar não
pensavam em ganhar dinheiro com a invenção, já que não havia mercado, pois na
época, não existiam ainda os computadores de uso domésticos.
Em 1970, Nolan Bushnell inciou o trabalho na versão fliperama do jogo
Spacewar, chamada Computer Space e no ano seguinte, a empresa Nutting
Associates comprou o jogo, colocando no mercado a primeira máquina de fliperama
da história. Na década de 80 surgiram os primeiros videogames 8-bit: Famicom, da
Nintendo e Master System, da SEGA (Service Games) e a empresa On-Line
Systems (atual Sierra Online) lançaram os primeiros jogos para computador.
No ano de 1978 os jogos eletrônicos tiveram uma grande reviravolta, pois
todos os jogos eram estáticos e não possuíam qualquer inteligência para tornar o ato
de “Jogar” mais divertido e dinâmico. Baseando-se nestes conceitos o inventor
Tomohiro Nishikado desenhou o primeiro jogo com I.A no mundo chamado de
“Space Invaders”, este jogo fazia grandes referências a invasões alienígenas e lutas
5
com espaçonaves. Seus algoritmos de I.A eram totalmente simples de forma que era
possível aprender os padrões de movimentação dos inimigos e prever os seus
movimentos. O jogo Space Invaders foi lançado pela empresa desenvolvedora de
jogos Japonesa Taito Corporation e logo depois continuado pela Empresa
Americana Midway Games. O game fez tanto sucesso que foi um dos primeiros
jogos Arcade a ser transferido para o console do antigo Atari.
A partir da década de 90, os jogos foram evoluindo de forma significativa
e até os dias atuais vem sendo estudados para cada vez mais proporcionar
novidades para seus usuários.
Para Coppin (2012) “inteligência artificial, envolve utilizar métodos
baseados no comportamento inteligente de humanos e outros animais para
solucionar problemas complexos”, baseando-se neste principio, o desenvolvimento
dos games começaram a se apoiar em diversas técnicas que simulem a realidade
com maior número de detalhes possíveis.
Para os programadores de jogos eletrônicos o significado de IA, se difere
do meio acadêmico, pois para este ultimo a preocupação esta em desenvolver
aplicações para resolver problemas complexos, como por exemplo, imitar o
reconhecimento fácil de imagens e objetos que o ser humano é capaz de realizar.
No entanto, os desenvolvedores de jogos se preocupam com a diversão em que os
jogos serão capazes de proporcionar, o objetivo final deles é o resultado e não como
o sistema alcança esses resultados, pois os jogos são negócios e seus
consumidores não estão preocupados em como a IA foi usada e sim com diversão e
desafio que o jogo proporciona para seus consumidores, seus personagens devem
tomar decisões coerentes com o contexto em que está sendo aplicado.
Os primeiros jogos eletrônicos lançados são considerados muitos simples
se comparado com os jogos da atualidade (ver figura 2), pois com a evolução da
tecnologia e da IA em jogos, estes foram ficando mais parecidos com a realidade,
com imagens de alta resolução (figura 3). Os personagens são programados para
usarem técnicas inteligentes de ações humanas, proporcionado mais atração nos
usuários de jogos eletrônicos. A visão atual da inteligência artificial é direcionada a
contribuir com o gamedesign para facilitar as modificações de acordo com a
concepção do jogo, com o intuito de traduzir sentimentos e sensações tornando a
imersão dos jogos muito maior e não apenas encarar as técnicas de IA como uma
simples ferramenta de melhorar a experiência do usuário.
6
Figura 2 - Imagem do jogo Pac-Man, lançado em 1980. Fonte: (ZAGALO, 2011).
Figura 3 - Pac-Man Adventures in Time. Fonte: (UOL JOGOS, 2013).
Segundo TURKLE,
Os avanços tecnológicos permitiram aos designers criarem jogos que
apresentam situações visivelmente atraentes e requerem um
conjunto de habilidades diversificadas que constituem um desafio.
(...) Os designers estão a começar ultrapassar essas limitações.
Novas
gerações
de
gráficos
de
computador
permitirão
às
7
personagens dos jogos gestos e expressões faciais mais realistas.
(1989, p. 68 apud SENA & MOURA).
Além da parte visual, os jogadores buscam jogos com certo equilíbrio de
dificuldade, pois eles não querem algo muito fácil de ganhar, nem muito difícil, para
chegar nesse equilíbrio de nível de dificuldade do jogo, usa-se então a IA, pois é ela
que irá proporcionar a inteligência nos personagens dos jogos que não serão
controlados pelos seres humanos e sim irão interagir com os usuários dos games.
Vale ressaltar com essa evolução dos games, a necessidade de
hardwares potentes para rodar essas aplicações dos jogos de hoje, pois
antigamente com um hardware de uma máquina simples era suficiente, já nessa
nova era dos jogos implementados com abrangentes técnicas de IA, faz-se
necessário máquinas mais eficientes como, por exemplo, mais memória, melhores
processadores, entre outros componentes.
3.
IA em Jogos e as técnicas utilizadas
Uma das mais interessantes áreas de estudo para aplicação da
inteligência artificial atualmente, tem sido a utilização em jogos eletrônicos, com o
objetivo de tornar o mundo eletrônico mais perto da realidade humana.
A Inteligência Artificial sistematiza e automatiza tarefas intelectuais e,
portanto, é potencialmente relevante para qualquer esfera da atividade humana. Já
os Softwares que usam a IA, são produtos intangíveis que utilizam no seu processo
de construção recursos intelectuais humanos, que vão desde sua especificação até
sua distribuição e pleno funcionamento.
Inteligência Artificial é uma das ciências mais recentes, que atualmente
abrange uma variedade enorme de subcampos, que vão desde áreas de uso geral,
como aprendizado e percepção, até tarefas mais específicas, como jogos de xadrez.
A IA otimiza as tarefas que exigem raciocínio e portanto, é um modo de ampliação
nas atividades intelectuais humanas
como meio de auxiliar os processos que
precisam de uma determinada lógica interativa, que neste caso, será abordada pelas
técnicas de IA de maneira a facilitar o processo de desenvolvimento de jogos.
8
3.1. Sistemas especialistas
Sistemas especialistas (SE’s) são uma classe de software que atuam
como colaboradores na tomada de decisão em áreas da ciência dominadas por
especialistas humanos. Um sistema especialista condensa o conhecimento de um
ou mais especialistas e utiliza este conhecimento armazenado para auxiliar na
resolução de problemas do usuário.
Os SE’s são Sistemas Baseados em Conhecimento (SBC’s) que atuam
em áreas e em tarefas bem definidas. Estruturalmente, todo SE é constituído de
duas partes principais: a Base de Conhecimento (BC), que contém o conhecimento
heurístico e fatual sobre o domínio de aplicação do SE, e a Máquina de Inferência
(MI), que usa o conhecimento da BC para construir a linha de raciocínio que leva à
solução do problema.
3.2. Sistemas Baseados em Regras
Uma regra consiste de uma parte “SE”, o lado esquerdo da regra, e de
uma parte “ENTÃO”, o seu lado direito. A parte “SE” lista um conjunto de condições
combinadas de forma lógica e a parte “ENTÃO” representa a ação a ser executada
ou a conclusão a ser deduzido, caso todas as condições da parte “SE” tenham sido
satisfeitas.
3.3. Sistemas Fuzzy
A
Lógica
Fuzzy
(também
chamada
de
lógica
multivalorada)
foi
primeiramente introduzida em 1930 pelo filósofo e lógico polonês Jan Lukasiewicz
através do estudo de termos do tipo alto, velho e quente, ele propôs a utilização de
um intervalo de valores [0,1] que indicaria a possibilidade que uma declaração fosse
verdadeira ou falsa, podendo assim, ser considerada como um conjunto de
princípios matemáticos para a representação do conhecimento baseado no grau de
pertinência dos termos (graus de verdade).
3.4. Raciocínio Baseado em Casos
Case-Based Reasoning (CBR) é uma técnica que utiliza a experiência
passada para resolver problemas. A ideia de CBR é descrever e acumular casos
9
significativos para a área de conhecimento especializado e tentar descobrir, por
analogia, quando determinado problema é “similar" a outro resolvido, aplicando a
solução armazenada ao novo problema semelhante que surgiu.
Um caso é um pedaço de conhecimento contextualizado representando
uma experiência. Ele contém a solução do caso e o contexto onde essa solução
pode ser usada. Um caso pode ser a descrição de um evento, uma história ou algum
registro contendo tipicamente o problema no momento em que o caso ocorreu mais
a solução para esse problema. Desta forma, não é necessário saber como resolver
os problemas, e sim apenas reconhecer se um problema similar foi resolvido no
passado. Por isso, para problemas bem compreendidos que não se modificam com
o tempo, um sistema de regras é mais adequado.
Para melhor contextualizar a respeito da utilização de IA em jogos,
Artero(2009, p.20) explica que:
A atuação em um jogo envolve o uso de estratégias e raciocínio,
próprio de seres inteligentes. Assim, ao longo dos anos, a área de
jogos tem sido um laboratório importante para o desenvolvimento de
varias técnicas de IA. Atualmente, vários jogos de última geração
agregam técnicas de IA, o que significa que os personagens
controlados pela máquina têm o seu comportamento alterado
dependendo do tipo de comportamento do usuário ou, ainda,
modificam sua estratégia após uma derrota, caracterizando um
aprendizado com a sua própria experiência.
Pensando nisso, a indústria de jogos eletrônicos tem investido cada vez
mais em sistemas de jogos que envolvam raciocínio lógico, despertando assim, o
instinto de desafio em seus jogadores.
Alguns anos após os lançamentos de jogos com I.A iniciou-se a corrida
para se desenvolver cada vez mais técnicas e “Engines” capazes de tornar os
games mais interativos, inteligentes e dinâmicos. Foram criadas técnicas para
aperfeiçoar todas as atividades e tomadas de decisão que um game precisaria fazer.
Desta forma, foi possível ampliar a diversidade, a interatividade e a mobilidade do
jogo.
Alguns jogos foram desenvolvidos com o Sistema de I.A Scripts
associada a Máquina de Estado Finito, neste contexto o jogo é baseado em um
algoritmo sequencial que realiza a busca das informações em uma ordem
cronológica ao acontecimento do jogo. Sendo assim, o algoritmo se torna uma I.A
10
responsável por entender onde o jogo se localiza e quais as informações ele deve
apresentar ao usuário.
O Algoritmo é programado para trabalhar uma sequencia que tem Início,
meio e fim, desta forma, o mesmo não retorna para funções iniciais obtendo sempre
uma nova lógica de busca a cada capitulo do jogo. Aliado neste algoritmo de scripts,
foi implementado também a Máquina de Estado Finito, assim, os elementos do jogo
poderiam agir de forma autônoma e também interagir com o jogador.
Um bom exemplo de jogos que utilizam estas técnicas são os Jogos de
Gênero Adventure (do Inglês Aventura).
3.5.
Algoritmo Genético
Uma nova implementação de algoritmos de I.A em Jogos é o Algoritmo
Genético. Este por sua vez foi utilizado em jogos com o intuito de criar
características únicas para determinados elementos dos jogos.
O Algoritmo Genético trabalha de forma a receber um padrão de seleção
e distribuição de conceitos, assim pode selecionar e mutacionar as características
dos elementos. Depois que os elementos são parametrizados e selecionados, estes,
são armazenados em uma base de dados onde podem por sua vez constituir um
grupo de elementos pré-dispostos em um jogo.
Além da utilização do Algoritmo Genético, também é empregada a
utilização da Máquina de Estados Finitos, esta tecnologia reaproveitada na área
automobilística, realizou uma grande ampliação das melhorias de qualidade e
confiabilidade nos produtos desenvolvidos. Uma vez que as empresas tiverem
acesso a novos meios de prever e se antecipar sobre possíveis falhas que
pudessem ocorrer em seus produtos fabricados.
Para contextualizar Vieira (2012), exemplifica o uso do algoritmo genético:
Com essa realidade, algumas empresas têm utilizado técnicas para
automatizar a atividade de balanceamento através de uma simples
aplicação de algoritmo genético, modificando os parâmetros de
performance dos carros.
11
Um bom exemplo deste tipo de integração de tecnologias são os jogos de
corrida, que utilizaram fortemente este tipo de implementação para obter um
ambiente mais distinto com carros mais complexos e característicos para cada
jogador.
4.
Máquina de Estados
Máquina de Estados Finito (do inglês Finite State Machine) ou autômato
finito, é uma forma matemática de representar programas de computadores, pode
ser definido pelo conjunto de estados, alguns dos quais podem ser denominados de
estados finais, incluindo-se as transações entre os estados e as ações. Isto é, a
medida que caracteres de uma determinada String de entrada são lidos, o controle
de uma máquina pode variar de um estado a outro, que será definido de acordo com
o conjunto de regras de transição especificadas para o autômato. Dessa forma, caso
o ultimo caractere da cadeia de String seja reconhecido, este encontra-se em estado
final, do contrario, a String não pertence a linguagem aceita pelo autômato. Um
exemplo de Máquina de Estados, com estados e transições
A figura 4, apresenta o comportamento de um personagem perante as
possíveis situações de um determinado jogo, onde o estado inicial encontra-se
ocioso, e permanecerá nesta situação até que um inimigo seja percebido. Ao se
encontrar um inimigo, o personagem irá persegui-lo até que esteja tão próximo que
possa ataca-lo, passando a efetivar o ataque logo em seguida. Durante a
perseguição e o ataque, a “saúde” do personagem sofre decréscimos; dessa forma,
quando a “saúde” do personagem tornar-se muito baixa, este deverá abandonar o
ataque, e descansar para recuperar a saúde.
12
Figura 4: Exemplo de Máquina de Estados com situações típicas de jogos.
Fonte:(SANTOS, 2004) .
As regras de transição no exemplo da Figura 3, mostram que o valor de
verdade, depende da entrada de dados fornecidos à Máquina pelos processos de
decisões. Esses dados são fornecidos a medida que o personagem percebe a
existência de um determinado inimigo em uma distância que seja possível encontralo. O estado de Ocioso também envolve uma busca de valores de variáveis que
representam a condição do personagem naquele momento. Tais regras de transição
podem ser aplicadas de maneira genérica, possibilitando sua interpretação em
ambos os tipos de Máquina.
A utilização das Máquinas de Estado Finito foi extremamente ampla, em
especial na prática de jogos de luta, onde os oponentes tinham uma série finita de
movimentações e
comportamentos a
partir de
condições pré-definidas e
programadas para os mesmos.
Apesar de ser uma funcionalidade que permite um comportamento
previsível para os jogadores, esta, pode ser amplamente programada, podendo se
tornar extremamente complexa e imprevisível dependendo exclusivamente da
programação e do intuito de sua utilização.
13
Máquinas de estados finitos tem o conceito muito importante em diversas
áreas da informática e são utilizadas em estudos de processos sistemáticos. As
máquinas de estados finitos
“[...] são estruturas lógicas compostas por um conjunto de estados e um
conjunto de regras de transição entre os estados. São ferramentas úteis em
qualquer aplicação que envolva o controle de processos, na qual seja
possível descrever cada uma das situações discretas em que os processos
podem se encontrar a cada momento”. (SANTOS, 2004, p. 11).
Foram essas estruturas lógicas que trouxeram maior dificuldade e
inovação para os jogos, seja nos primeiros consoles e até hoje tendo maior
participação nos cenários totalmente modificáveis e cada vez mais se aproximando
do que é real.
É necessário tratar os dois tipos de máquinas de estados, a determinística
e a não determinística, mostrando suas diferenças. Em seguida abordaremos um
estudo de caso sobre o PAC-MAN, e como funciona toda a lógica de busca de cada
um dos fantasmas que estão inseridos no jogo.
Numa máquina determinística ou autômato finito determinístico (AFD), as
entradas que rotulam as transições de um dado estado, são mutuamente exclusivas,
ou seja, não partilham símbolos comuns.
Nestas máquinas, se conhecermos o estado inicial e a sequência de
entrada então toda a trajetória de estados e a sequência de saída podem ser
determinadas. É um padrão muito usado em jogos para definir o comportamento de
agentes reativos em games. Como vantagem esses algoritmos são fáceis de
programar, depurar e simples de entender além de seu processamento ser de baixo
custo; mas possui uma desvantagem, pois a medida que o usuário vai jogando o
game, logo ele já sabe as medidas para serem tomadas nas ações, devido a
previsibilidade que esta técnica propõe.
Nas
máquinas
não
determinísticas
a
IA,
possui
um
grau
de
indeterminação, podendo ser variável a cada implementação. Estas técnicas são
difíceis de manipular, entender e testar. São mais lentas se comparado com as
técnicas determinísticas, além de ser imprevisíveis. Um bom exemplo seria o
aprendizado que NPC (Non Player Character – Personagem não controlado pelo
jogador), adquire ao jogar com um usuário de game. O comportamento do NPC
14
pode variar de acordo com as medidas tomadas pelo jogador, aumentando assim o
tempo do jogo e a diversão.
Para este desenvolvimento de IA é necessário mais processamento, os
algoritmos são mais complexos, mais difíceis de depurar, mais complicados de
entender, ainda exigem uma atenção dos desenvolvedores para que as possíveis
ações reações do computador estejam dentro do jogo.
5.
Estudo de caso: PAC-MAN.
Após o surgimento dos primeiros jogos com I.A, a Empresa Midway
Games deu continuidade a esta revolução, dando origem a outro famoso game
chamado de Pac-Man. O jogo Pac-Man foi baseado em um algoritmo um pouco
mais complexo e com uma lógica simples. A lógica do jogo é basicamente simples,
uma vez que foi utilizada a Máquina de Estado Finito. Este jogo foi desenvolvido
pela empresa NAMCO na década de 80 onde até então existiam os consoles ATARI.
O Jogo consiste em um mapa onde o jogador deve percorrer todo o labirinto de
forma a recolher todos os objetos dispostos no mesmo. Além de percorrer o labirinto
o jogador também deverá fugir dos fantasmas que o perseguem durante todo o jogo.
Os fantasmas são: Inky, Pinky, Blinky e Clyde, o jogo utiliza Máquinas de
Estados Finitos ou (Finite State Machines - FSM) para controlar os comportamentos
dos fantasmas, os tempos são variáveis de acordo com os níveis do jogo, conforme
ilustra figura 5, e a transição dos estados irá variar segundo o comportamento dos
fantasmas, que será mostrado logo adiante. Esses fantasmas têm três tipos de
comportamentos (também são conhecidos como personalidades), sendo que a
forma de implementação para cada personalidade com uma ação, varia com o tipo
de cada fantasma. Os comportamentos são:

Caçar (Chase)

Fugir (Evade)

Dispersar (Scatter)
15
Figura 5: Movimentação baseada em máquina de estados: Dispersar, caçar e fugir.
Fonte: (LIMA, 2012).
Comportamentos:
A) Dispersar
O estado de Dispersão é responsável por mover os personagens em
direção aos cantos e andar em círculos ficando o mais longe possível do PAC-MAN,
como demonstra a figura 6.
Figura 6: Movimentação baseada em máquina de estados. Fonte: (LIMA, 2012).
B) Fugir: Quando a ação FUGIR é acionada, cada fantasma movimentase mais lentamente com movimentos aleatórios como demonstra figura 7.
16
Figura 7: Movimentação: Fugir . Fonte: (LIMA, 2012).
C) Caçar: Para este comportamento, existem quatro funções de caçar,
implementadas de acordo com a cor de cada fantasma, o algoritmo age de forma
diferente. Cada uma destas funções são descritas e exemplificadas abaixo.
 BLINCK : Nome do fantasma vermelho, que tem como característica
movimentar-se de acordo com a posição do PAC-MAN, seguindo-o como demonstra
a figura 8.
Figura 8: Movimentação: Modo de Caçar do fantasma Blink. Fonte: (LIMA, 2012).
17
 PINKY: Fantasma de cor rosa que movimenta-se mirando quatro
pontos a frente o PAC-MAN tentando assim prever seu caminho como demonstra
figura 9.
Figura 9: Movimentação: Pinky prevendo movimentação do PAC-MAN. Fonte: (LIMA,
2012).
 INKY: Este fantasma azul, movimenta-se mirando em uma combinação
da direção e posição do PAC-MAN e do BLINCK, esse é um código mais apurado
onde está sempre mais próximo do ator, como demonstra a figura 10.
1.
2.
Figura 10: Movimentação: posição e direção x versus. Fonte: (LIMA, 2012).
18
 CLIDE: O fantasma de coloração laranja, quando está em uma posição
longe do PAC-MAN, movimenta-se em sua direção, quando está perto, movimentase em direção ao canto da tela procurando encurrala-lo, como demonstra a figura
11.
Figura 11: Movimentação: encurralar Pac-Man. Fonte: (LIMA, 2012).
O jogo não foi feito para ter fim, porém no level 256 o jogo entra em bug.
Não foram feitas mais fazes após essa por isso o erro e gerado e o sistema dar erros
como: não entende quando o pac-man morre, as esferas que alteram a função do
fantasma para fugir não funcionam, metade do mapa fica desconfigurada, entre
outros como demonstra a figura 12.
Figura 12: Level 256 do Jogo Pac-Man. Fonte: (PITTMAN, 2011).
19
6. CONCLUSÃO
A partir dos temas descritos neste artigo percebe-se a grande importância
da IA (Inteligência Artificial) nos jogos eletrônicos, sem ela seria praticamente
impossível assegurar a atenção dos usuários de games, pois os jogos seriam uma
tarefa muito fácil e repetitiva. A IA propõe técnicas de inteligência humana nos
games, tornando-os atrativos e desafiadores para seus usuários.
Com o avanço significativo da tecnologia, as técnicas de IA vêm sendo
cada vez mais aprimoradas, tornando a realidade virtual muito próxima do mundo
real.
A máquina de estado finito é uma das técnicas de IA mais antigas, no
entanto, vem sendo utilizada atualmente, por motivos como rapidez e as facilidades
de modificação, facilidade de depuração, além de utilizar pouco processamento, são
intuitivas e flexíveis.
O estudo de caso do Pac-Man, sendo um dos primeiros jogos a utilizar a
IA, exemplificou como a máquina de estado finito pode ser usada em um game.
Com o passar dos anos novas técnicas são desenvolvidas e cada vez
mais os jogos se parecem com a realidade, sempre utilizando técnicas de
inteligência artificial.
Atualmente, o mercado oferece uma gama de possibilidades para quem
quer trabalhar na implementação de jogos, existem várias áreas de atuação dentro
dos games, pois o próprio crescimento desse mercado exige que mais pessoas
atuem nesse campo. Para quem gosta dessa área, vale a pena investir nessa
carreira.
Neste artigo concluímos que os jogos eletrônicos aliados as máquinas de
estados finitos, como por exemplo, o Pac-Man, antecessores dos atuais games,
demonstraram um grande avanço para sua época. A máquina de estados finitos
permitiu o avanço dos investimentos em descobertas de novas implementações em
novos gêneros de jogos. Tais descobertas impulsionaram o mercado de jogos
eletrônicos uma vez que os mesmos chamaram a atenção dos jogadores (players)
por sua inteligência e capacidade de imprevisibilidade unindo também um aspecto
simples que se torna extremamente desafiador com o emprego da IA.
20
REFERÊNCIAS BIBLIOGRÁFICAS
A História do Pacman, Disponível em: <http://www.webartigos.com/artigos/ahistoria-do-pacman/46005/> Acessado em: 05/11/2013
ARTERO, Almir Olivette. Inteligência Artificial : Teoria e Pratica. Livraria da Física
- São Paulo, 2009.
BONATO, Vanderlei. Máquinas de Estados. Elementos de lógica digital II.
Disponível em: < http://wiki.icmc.usp.br/images/6/60/Aula_3_-_StateMachineSSC0110_2010.pdf >. Data de Acesso: 28/11/2013.
COPPIN,
Ben.
Inteligência
Artificial.
1º
ed.
LTC.
2012
CORREA, Bruno Duarte, THIAGO, Dias Pastor. A evolução das técnicas de
Inteligência
Artificial.
Disponível
em:<http://sbgames.org/sbgames2012/
proceedings/papers/tutoriais/tutorial-04.pdf>. Acessado em: 28/11/2013.
FERRER, Rafael. Empresa usa inteligência artificial em jogos de RH EXAME.com. Disponível em: <http://exame.abril.com.br/tecnologia/noticias/empr
esa-usa-inteligencia-artificial-em-jogos-de-rh?page=1>. Acessado em: 12/10/2013.
FILGUEIRAS, Fernando; LIMA, Sérgio M. B. Inteligência artificial aplicada aos jogos
eletrônicos. Dissertação(artigo), Faculdade Metodista Granbery, Juiz de Fora, 2012.
FILHO, Glauco B.R. Aplicação de Inteligência Artificial em Jogos Eletrônicos.
Disponível em: <http://fatecindaiatuba.edu.br/reverte/index.php/revista/search/advan
cedResults?subject=jogos%20eletr%C3%B4nicos>. Acessado em : 09/11/2013.
GOLDSTONE, Will. Unity Game Development Essentials. Packt Publishin, 2009.
LAICHT, Glauco David. A INFLUÊNCIA DOS JOGOS ELETRÔNICOS NA
INTELIGÊNCIA ARTIFICIAL. Disponível em:<http://www.ceavi.udesc.br/arquivos/
id_submenu/387/glauco_david_laicht.pdf>. Acessado em: 26/11/2013
LIMA, Edirlei Soares de. Inteligência Artificial. Disponível em : <http://edirlei.3dgb.
com.br/aulas/ia_2012_1/IA_Aula_26_Maquinas_de_Estados_Finitos.pdf>. Data de
acesso: 07/11/2013
21
KISHIMOTO, Andre. Inteligencia Artificial em Jogos Eletronicos. Disponível em:<
http://www.programadoresdejogos.com/trab_academicos/andre_kishimoto.pdf
>.
Data de acesso: 04/12/2013.
PITTMAN,
James.
The
Pac-Man
Dossier.
Disponível
em:
<
http://home.comcast.net/~ jpittman2/pacman/pacmandossier.html> Data de Acesso:
17/11/2013.
RICARTE, Ivan L. M. Autômatos finitos. Disponível em: <http://www.dca.fee.un
icamp.br/cursos/EA876/apostila/HTML/node46.html>. Data de acesso: 30/11/2013.
SANTOS, Gilliard Lopes dos. Máquinas de Estados Hierárquicas em Jogos
Eletrônicos. Disponível em: <http://www2.dbd.puc-rio.br/pergamum/tesesabertas/
0220940_04_cap_02.pdf>. Data de acesso: 04/11/2013.
SENA, Gildeon; MOURA, Juliana. Game cultura. Jogos eletrônicos e Educação:
Novas formas de aprender. Disponível em: <http://www.gamecultura.com.br/
index.php?option=com_content&view=article&id=438#axzz2mWUCRqHC>. Data de
acesso: 03/12/2013.
UOL JOGOS. Disponível em: < http://jogos.uol.com.br/album/pacman_album.htm#foto
Nav=13 >. Data de Acesso: 03/12/2013.
VIEIRA, Everton. Inteligência Artificial nos Games – Mais Aplicações | Abrindo o
Jogo. Disponível em: <http://abrindoojogo.com.br/inteligencia-artificial-nos-games%E2%80%93-mais-aplicacoes>Acessado em: 04/11/2013
VIEIRA,
Everton.
Inteligência
Artificial
nos Games –
Categorias
e
Aplicações ....Disponível em: < http://abrindoojogo.com.br/inteligencia-artificial-nosgames-%E2%80%93-categorias-e-aplicacao > Acessado em: 09/11/2013.
ZAGALO, Nelson. Virtual ILLusion. Disponível em: < http://virtual-illusion.blogspot.
com.br/2011/05/video jogos-no-smithsonian-american-art.html >.2013.