Algoritmos de busca em tempo real aplicados a jogos digitais (PDF

��

Eder L. Trindade Ricardo P. Martins Ferreira Eduardo P. C. Fantini Hugo B. de Paula

Pontifícia Universidade Católica de Minas Gerais

� ��

Restrições de tempo de resposta e de recursoscomputacionais oferecem um desafio para o empregode técnicas sofisticadas de Inteligência Artificial nosjogos. Neste artigo estudamos como aprimorar osalgoritmos de busca em tempo real encontrados naliteratura. Em especial, investigamos como permitirque vários agentes se desloquem simultaneamente noambiente de um jogo. Também foi feito um estudo decaso em um jogo real, o �� para avaliar ocomportamento desses algoritmos em jogos digitais.

��: Inteligência Artificial, Agentes, ��, ��, RTA*, ��

� ��:[email protected]{poley,hugo}@[email protected]

��

Os jogos digitais são ambientes propícios para aaplicação de técnicas de inteligência artificial (IA). Porum lado, estes ambientes limitados, onde as regrascostumam ser bem definidas, servem comolaboratórios para testes [Waveren, 2001]. Por outrolado, a IA ainda tem muito a contribuir para odesenvolvimento dos jogos. Restrições de tempo deresposta e de recursos computacionais oferecem umdesafio para o emprego de técnicas sofisticadas de IAem jogos digitais.

O planejamento de trajetória é um dos problemaspresentes nos jogos onde técnicas de inteligênciaartificial são usadas com sucesso. Em muitas situaçõesos movimentos de um agente/personagem não podemser tratados como deslocamentos simples controladospelo jogador. Nestes casos, é útil o emprego dealgoritmos para o mapeamento do ambiente em umgrafo e de algoritmos de busca de caminhos entre aposição atual no grafo e a posição desejada do agenteno jogo [Nonnenmacher et al, 2007].

A maioria dos jogos digitais resolve o problema debusca de caminhos com soluções baseadas noalgoritmo A* [Millington, 2006]. O algoritmo A* é umalgoritmo informado de busca ótima, ��. Nosalgoritmos de busca �� [Russell and Norvig,2004], a fase do planejamento – mapeamento doambiente e busca no grafo – antecede a fase daexecução, quando o agente se desloca pelo caminhoescolhido. Os algoritmos de busca ��nem sempresão capazes de atender as necessidades de tempo de

resposta em um jogo. Quando um personagem ficaimóvel aguardando o cálculo de uma trajetória, acadência do jogo pode ficar prejudicada. Assim, umadecisão rápida para o próximo movimento, mesmo quenão ótima, em algumas situações é mais importante doque esperar o cálculo do melhor movimento. Estasdificuldades ficam evidentes quando é necessáriocalcular simultaneamente a trajetória de diversospersonagens.

Entre as soluções adotadas na literatura para lidar comos requisitos de tempo de resposta para o problema deencontrar caminhos, os algoritmos de busca ��,conhecidos como algoritmos de busca em tempo realsão freqüentemente adotados [Russell and Norvig,2004]. Apesar de não tratarmos característicasrelacionadas a tempo, adotamos o termo “tempo real”por ser o termo utilizado na literatura. Os algoritmosde busca em tempo real são algoritmos onde as fasesde planejamento e de execução são alternadas. Oagente planeja e executa alternadamente osmovimentos até alcançar o objetivo. Embora não sejamótimos, se algumas condições forem atendidas, comocondições de conexidade do grafo, eles conseguemorientar o agente até o objetivo, mesmo quando o grafosofre alterações durante o deslocamento do agente.Este comportamento é relevante em jogos digitaisporque, muitas vezes, o ambiente é dinâmico.

Neste artigo estudamos como aprimorar os algoritmosde busca em tempo real encontrados na literatura. Emespecial, investigamos como permitir que váriosagentes se desloquem simultaneamente no ambiente deum jogo. Realizamos um estudo comparativo entrealgoritmos de busca em tempo real presentes naliteratura e nossas adaptações. Também foi feito umestudo de caso em um jogo real, o �� paraavaliar o comportamento de alguns algoritmos debusca em tempo real. O �� é� um� jogodigital do tipo MMORPG (�� ) em terceira pessoa [Origin, 2008],o qual possibilita a interação do jogador com umcomplexo ambiente virtual. Os resultados obtidos nosexperimentos quantitativos e qualitativos realizadosindicam a eficácia do uso de algoritmos de busca emtempo real em jogos digitais.

O restante do artigo é organizado da seguinte forma. Apróxima seção apresenta alguns dos principaisalgoritmos de busca em tempo real. A Seção 3apresenta as adaptações propostas e na Seção 4 sãoapresentados os resultados computacionais e asalterações feitas no emulador do �� , o ��. Na última seção são apresentadas algumasconclusões e oportunidades para trabalhos futuros.

SBC - Proceedings of SBGames'08: Computing Track - Full Papers Belo Horizonte - MG, November 10 - 12

VII SBGames - ISBN: 85-766-9204-X 141

�� - ��

Os algoritmos de busca em tempo real propõem umasolução de compromisso entre a qualidade da decisãode qual é o próximo estado que um agente deve visitare o tempo para calcular esta decisão [Koenig, 2006].Existem vários artigos que sugerem a implementaçãode algoritmos de busca em tempo real em jogos digitais[Koenig, 2006][Koenig, 2007][Sun, 2008]. Entretanto,estes artigos não apresentam nenhuma implementaçãoem um ambiente de jogo real.

A busca em tempo real foi motivada primeiramentepela robótica sensível a tempo [Koenig, 1999] e emseguida por jogos digitais, abrangendo os jogos de RTS(��), de FPS (��) e deRPG (�� ). Em todos eles o tempodesempenha um papel fundamental, uma vez quevários agentes fazem buscas de caminhossimultaneamente e é exigido do jogo um tempo deresposta muito rápido para garantir o ��[Bulitko et al., 2007]. Encontrar caminhos em jogos écomputacionalmente muito caro. No jogo RTS “�� !!”, por exemplo, o �� consome entre60 e 70% do tempo de simulação [Pottinger, 2000].

O problema de encontrar caminhos em grafos érepresentado da seguinte forma: considere um Grafo�"#�� $ onde # representa um conjunto de vértices, representa um conjunto de arestas, ! representa ovértice inicial e representa o conjunto de vérticesfinais. Um caminho é um subconjunto conexo do grafo�. O problema consiste em determinar um caminho de! para�.

Nas subseções seguintes descrevemos dois algoritmosde busca em tempo real clássicos, %�� &��'�e o ��&��'�[Korf 1990]. ��

O algoritmo LRTA* [Korf 1990] (%�� &��') é um algoritmo de busca informada e em temporeal. Ele não é ótimo, ou seja, não garante que seráencontrado o melhor caminho entre o nó inicial e o nóobjetivo. O algoritmo possui conhecimento dalocalização do vértice objetivo e utiliza estainformação para eleger a próxima posição do agente.No contexto onde realizamos os experimentosutilizamos a distância �� como medidaheurística da distância até o objetivo.

O LRTA* inicia com um agente localizado no vérticeinicial. No passo seguinte, o agente se desloca para ovizinho mais promissor de acordo com a função decusto. A busca termina quando o agente encontra umvértice objetivo. A cada iteração o agente atualiza aestimativa da distância até o objetivo melhorando ainformação sobre o grafo. Na fase de planejamento oagente calcula para os nós vizinhos a função de custo

Figura 1: Execução do LRTA*

Figura 2: Pseudocódigo do LRTA*

(")��*$�+��"*$�,�-")��*$ onde * é um vértice vizinho, ) éo vértice corrente, �"*$ representa o valor atual daheurística de * até o objetivo e -")��*$ é o custo daaresta do vértice corrente ) até *. O agente atualiza aheurística do vértice corrente com o menor valor de(")��*$ e move-se para ele. O processo então reinicia.



A Figura 1 ilustra um exemplo de execução doLRTA*. O nó inicial é o vértice A e o nó objetivo é ovértice D. O algoritmo calcula a heurística de cadavértice, consideremos o seguinte estado corrente:�"�$�+�./��"0$�+�12��"-$�+2��"3$�+�/4�� O Algoritmo RTA* [Korf 1990] ( ��&��') é umalgoritmo de busca por qualquer caminho e em temporeal semelhante ao LRTA*. A diferença entre oLRTA* e o RTA* é que o RTA* atualiza a heurísticado vértice corrente com o segundo melhor valor de(")�� *$ mantendo uma informação mais precisa dografo. A Figura 3 apresenta o pseudocódigo do RTA*.

Figura 3: Pseudocódigo do RTA*

!��"��# ��

Neste trabalho estudamos algoritmos de busca emtempo real e propomos novos algoritmos adotandoduas estratégias:

• Investigamos o efeito nos algoritmos da faltade informação sobre o ambiente de busca.Propomos uma variação no algoritmo RTA*melhorando o aprendizado do agente sobre oambiente;

• Estudamos diversos agentes no processo debusca. Propomos um algoritmo baseado emsistemas multiagentes onde agentescompartilham informação, o que pode agilizaro processo de busca.

Figura 4: Execução do RTA*

A seguir apresentamos dois algoritmos o ��&��'�� onde melhoramos o aprendizado do algoritmo ��&��' e o �� &��', onde mais deum agente cooperam para agilizar o processo de busca.�!�� $��%�� $�

O ��&�� '� �� (RTA*P) é uma variação doalgoritmo ��&��', onde a novidade é acrescentarmais informação ao algoritmo. No RTA* o algoritmoanalisa todos os vizinhos do vértice corrente paraescolher o vértice mais promissor e atualizar aheurística do vértice corrente com o segundo melhorvalor de custo. Contudo esse algoritmo descarta asinformações previamente calculadas sobre os outrosvizinhos. O algoritmo RTAP armazena também qual éo vizinho do segundo melhor valor de custo e qual é ovalor do terceiro melhor custo. Caso o agente retorne aum vértice já expandido o agente desloca-se para ovértice de segundo melhor custo e atualiza o valor daheurística do vértice corrente com o terceiro melhorcusto, sem a necessidade de realizar nova análise dosvizinhos.

O RTA*P ilustra o comportamento do agente quandoaumentamos seu aprendizado sobre o ambiente.Comparamos o RTA*P e o RTA* em diversassituações explorando ambientes com e seminformação. O RTA*P inicia com um agentelocalizado no vértice inicial, no passo seguinte o agentese desloca para o vizinho mais promissor. A buscaencerra quando o agente encontra um vértice objetivo.



Figura 5: Execução do RTA*P

A cada iteração o agente atualiza a estimativaheurística do vértice. Na fase de planejamento o agentecalcula para todos seus vizinhos a função de custo(")��*$�+��"*$�,�-")��*$ onde ) é o vértice corrente, * éum vértice vizinho de ), �"*$ representa o valor daheurística da distância de * até e -")��*$ é o custo daaresta do vértice corrente ) até o vizinho *. O algoritmotambém armazena qual o vértice �")$ possui o segundomenor valor da função de custo e o valor do terceiromenor valor da função de custo, �")$. Se o vértice )ainda não foi visitado o agente atualiza a heurística dovértice corrente com o segundo menor valor de (")��*$e move-se para o vizinho de menor (")��*$. Se o vértice* já foi visitado o agente não calcula a função de custopara os vizinhos de * e caminha para o vértice �"*$atualizando a heurística �"*$� +� �"*$. A Figura 5apresenta um exemplo de execução do RTA*P. AFigura 6 apresenta o algoritmo RTA*P.

Figura 6: Pseudocódigo do RTA*P

!�!�� &�� O �� &�� '� (RRTA*) é um algoritmo de buscainformada em tempo real baseado em sistemasmultiagentes [Yokoo and Ishida, 1999] [Wooldridge,2002]. O RRTA* é formado por dois ou mais agentesque dividem informação para encontrar um caminhoentre dois nós. Vamos discutir neste artigo o caso comapenas dois agentes. Chamamos o primeiro agente deA e o segundo agente de B. O agente A é o agenteresponsável por encontrar um caminho entre o nóinicial e o nó final passando pelo nó origem de B. Oagente B tem o objetivo de encontrar um caminho entreum nó qualquer do grafo que é seu nó inicial e o nóobjetivo. O nó de origem de B deve pertencer aocaminho de A. Assim, o agente B antecipa oconhecimento sobre o grafo para A. Neste artigovamos utilizar como estratégia para a escolha daposição inicial de B o ponto médio da semi-reta entre onó inicial e o nó objetivo.



O RRTA* é formado por duas esferas de decisão: umaesfera tática onde o algoritmo coordena os agentes euma esfera operacional onde os agentes executam abusca.

Na esfera tática o agente A começa a busca no nóinicial. O algoritmo elege um vértice para B iniciar abusca, neste caso, o ponto médio da semi-reta entre onó inicial e nó objetivo. O agente B tem a função deencontrar o nó objetivo e A, a priori, tem o objetivo deencontrar o vértice por onde B iniciou a busca. Quandoo agente A encontrar o nó por onde B partiu ou algumvértice que foi caminho de B o agente A passa aprocurar o nó objetivo. A busca termina quando oagente A encontra o nó objetivo.

Figura 7: Estratégia de posicionamento dos agentes - RRTA*- Ponto Médio – Dois Agentes

�Figura 8: Execução do RRTA*

Na esfera operacional, ambos agentes utilizam oalgoritmo RTA* para realizar a busca. O agente Brealiza a busca a procura do nó objetivo marcando osnós por onde passou, o agente B marca no nó visitadoqual é o próximo nó que ele irá visitar. O Agente Arealiza a busca e quando encontra um nó visitado por Bsegue as marcações deixadas por B sem fazer qualquerverificação, assim o agente A utiliza do conhecimentodo grafo adquirido na busca de B. A Figura 7 ilustra adefinição das posições inicias dos agentes.

Nos exemplos adotados neste trabalho o algoritmotraça uma semi-reta entre o nó inicial e o nó objetivo.

O algoritmo calcula o ponto médio desta semi-reta. Ascoordenadas do ponto médio são definidas pelaequação: onde 5 representa a

ordenada do ponto médio, 61 a ordenada do nó inicial e6. a ordenada do nó objetivo, 7 representa a abscissado ponto médio, �1 representa a abscissa do nó inicial e�. representa a abscissa do nó objetivo.

Figura 9: Pseudocódigo do RRTA*

A estratégia para posicionamento dos agentes dependemuito do tipo do grafo. Apresentamos um critério maisdidático, contudo outros critérios podem ser adotados.A Figura 9 apresenta o pseudocódigo do algoritmoRRTA*, o procedimento RTA* além de executar umaiteração da busca RTA* marca os nós por onde Bpassou e o agente A quando encontra um nó visitadopelo agente B segue a marcação sem analisar osvizinhos. O primeiro passo do algoritmo é posicionaros agentes, o agente A é posicionado no nó inicial e oagente B é posicionado no nó escolhido. O algoritmoatribui ao agente A a função de encontrar o nó poronde B iniciou a busca e ao agente B a função deencontrar o nó objetivo. No segundo passo os agentesexecutam a busca utilizando o algoritmo RTA*, oagente B durante a busca deixa marcas que depoispoderão ser seguidas pelo agente A.



Quando o agente A encontra o ponto por onde Biniciou a busca ele passa a procurar o nó objetivo. Oagente B termina sua busca quando encontra o nóobjetivo, quando encontra com o agente A ou quando oagente A encontra o nó objetivo. Quando o agente Aencontra as marcas deixadas pelo agente B ele passa asegui-las, assim o agente A aproveita o conhecimentodo grafo adquirido por B durante sua busca. A buscatermina quando o agente A encontra o nó objetivo. AFigura 8 apresenta a execução do RRTA*.

Realizamos experimentos como o RRTA* apenas emgrafos conexos, a estratégia de posicionamento dosagentes utilizando o ponto médio deve ser usada emsomente em grafos conexos.

'��()� �� *��

Foram realizados dois grupos de experimentos. Oprimeiro grupo trata de um estudo comparativo entreos diferentes algoritmos propostos na literatura e osnovos algoritmos propostos neste trabalho em umambiente estruturado. São ambientes típicos para testesde algoritmos de busca [Koenig, 2006][Koenig,2007][Sun, 2008]. O segundo grupo trata deexperimentos qualitativos onde algoritmos de busca�� são aplicados em um jogo MMORPG - o�� para avaliar seus comportamentos emum ambiente de jogo real.

Os ambientes estruturados são labirintos representadosem grafos 4-conexos gerados aleatoriamente detamanho entre 100 a 1.000.000 vértices. São labirintosquadrados de tamanhos entre 10 x 10 a 1000 x 1000.Escolhemos o jogo eletrônico �� por suagrande popularidade e por possuir um emulador deservidor – o ��– de código aberto o qual permitealterações nos algoritmos de busca. Os experimentosforam realizados em uma máquina com processador!�� -�� .�3�� 2.2 Ghz, 2 GB de Memória RAM,sistema operacional 8��9� XP �� 2002�� * 2. Utilizamos como compilador o0��-,,�0�� 6.0.

'�� ()� �� +��,�� -��

Para comparar o desempenho dos algoritmosconsideramos o número médio de vértices expandidose o tempo médio de execução de cada algoritmo.Consideramos como vértices expandidos os vérticespor onde os agentes passaram e o tempo de execuçãode um algoritmo representa o tempo em milissegundosgasto para atingir o objetivo. Estes dados são as médiasdas execuções do mesmo algoritmo no mesmo grafo.Para cada grafo executamos repetidamente o mesmoalgoritmo. Limitamos o tempo total de execução doalgoritmo e, por isso, os grafos maiores foram menosexecutados.

Para a realização dos experimentos foramdesenvolvidos dois geradores de grafos: gerador degrafos aleatórios (GCA), e gerador de grafos conexos(GCC). O tamanho do grafo corresponde ao produto donúmero de colunas pelo número de linhas do grafo. Porexemplo, um grafo de tamanho igual 1/4/// vérticespossui 1// colunas e 1// linhas.

Definimos como vértices obstáculos os vértices quepossuem grau zero. Os geradores recebem comoparâmetros os vértices iniciais e finais, o tamanho, opercentual do número de arestas ou o percentual devértices obstáculos, o grau médio do grafo e o tipo dografo. O tipo do grafo é definido pelas distâncias entrenós vizinhos que podem ser constantes ou aleatórias.

Tabela 1: Número de execuções dos experimentosquantitativos em grafos baseados em labirintos

O gerador de grafos aleatórios (GCA) garante ageração de grafos com pelo menos um caminho entre ovértice inicial e o vértice final, mas não garante que ografo seja conexo. Por este motivo, nos grafos geradospelo o GCA não é possível garantir o funcionamentocorreto do algoritmo RRTA* utilizando a estratégia deposicionamento pelo ponto médio. No GCA opercentual de vértices obstáculos define a densidade dografo, uma vez que o obstáculo possui grau zero econseqüentemente o número de arestas é menor. A

O Gerador de grafos conexos (GCC) garante aexistência de caminhos entre quaisquer vértices dografo, ou seja, todos os vértices estão interligados.Este algoritmo contempla a geração de grafos detamanhos e densidades diferentes. Os grafos são nomáximo 4-conexos, ou seja, cada vértice possui nomáximo quatro vizinhos. Os pesos das arestasrepresentam as distâncias entre os vértices que podemser uniformes ou aleatórias. No GCC a quantidade dearestas define a densidade do grafo, consideramos umgrafo com 100% de densidade quando todos os vérticespossuírem grau igual a quatro.

Os experimentos foram separados em dois subgruposdistintos, o primeiro são experimentos executados nos



grafos gerados pelo GCA e o segundo nos grafosgerados pelo GCC.

Utilizamos como heurística a distância de �� epara cada subgrupo estudamos o comportamento dosalgoritmos em grafos onde os pesos das arestas sãoiguais, em grafos onde os pesos das arestas sãoaleatórios ou em situações sem heurística. Para osgrafos gerados pelo GCA não estudamos o RRTA*porque a estratégia de posicionamento através do pontomédio não é adequada neste tipo de grafo.

A Tabela 1 apresenta o número de execuções dosalgoritmos RTA*, RTA*P e RRTA* nos experimentosdeste artigo, foram realizados 111600 execuções para oGrupo I e 167400 execuções para o grupo II.

Figura 11: Gráfico da média do número de vérticesexpandidos para grafos gerados pela GCA com pesos

variados entre 1 á 10

Figura 12: Gráfico da média do tempo de execução paragrafos gerados pela GCA com pesos variados entre 1 a 10

Foram gerados 200 grafos para cada configuração,onde 100 têm peso uniforme nas arestas e 100 possuempesos aleatórios. Cada configuração é definida peloalgoritmo que o criou: GCA, ou GCC; pelo seu númerode vértices: 100, 10.000, 1.000.000; e pelo percentualde vértices obstáculos, no caso dos grafos gerados peloGCA ou pela percentual de arestas, para os grafosgerados pelo GCC.

Os resultados são apresentados em gráficos de barrasonde as colunas estão ordenadas de acordo com alegenda, não sendo necessário orientar-se pela cor.�� os experimentos do Grupo I foram realizadosem grafos com pelo menos um caminho entre o vérticeinicial e o vértice final (grafos gerados pelo GCA), masnão necessariamente conexos. Cada vértice possui nomáximo quatro vizinhos, a quantidade de vérticesobstáculos define a densidade do grafo.

A Figura 11 compara o número de vértices expandidosversus o percentual de vértices obstáculos nos grafosdo grupo I. O número de vértices expandidos aumentaquando o percentual de vértices que são obstáculosaumenta. O RTA* e o RTA*P empatam quando ografo não possui obstáculos. À medida que aumenta onúmero de vértices que são obstáculos o RTA*apresenta resultados melhores que o RTA*P. Estadiferença é menor em grafos com pesos aleatórios.

A Figura 12 compara o tempo de execução (emmilissegundos) com o percentual de vértices obstáculosnos grafos do grupo I. Os algoritmos gastaram maistempo para solucionar os problemas quando o grafopossui 40% de vértices obstáculos. O RTA* e oRTA*P apresentam comportamentos semelhantes. Nãohá diferenças nos resultados entre os grafos comarestas com pesos uniformes e os grafos com arestascom pesos aleatórios.

�� : os experimentos do Grupo II foramrealizados em grafos conexos gerados pelo algoritmoGCC. Cada vértice possui no máximo quatro vizinhos,a quantidade de arestas define a densidade do grafo. Asfiguras 13 e 14 comparam o número de vérticesexpandidos versus o percentual de densidade nosgrafos do grupo II. Os gráficos não indicam umarelação direta entre o número de vértices expandidos ea densidade do grafo.

O RTA*P e o RTA* apresentam resultadossemelhantes. O RRTA* apresenta número de vérticesexpandidos maior que o RTA*. Entretanto, sedividirmos o número de vértices expandidos pelonúmero de agentes temos uma média de vérticesexpandidos menor que o RTA*. Sem utilizarheurísticas, o RTA*P expande menos vértices que oRTA*.

As figuras 15 e 16 comparam o tempo de execução(em milissegundos) versus o percentual de vértices dedensidade nos grafos do grupo II. O RTA* e o RTAPapresentaram desempenhos semelhantes. Não hádiferenças nos resultados dos grafos com arestas compesos uniformes e arestas com pesos aleatórios.O RTA* gasta mais tempo para executar a buscaquando não utiliza heurística. O RTA*P é mais estávele mais eficiente que o RTA* em todas as densidades.Em grafos com pesos aleatórios a diferença entre oRTA*P e o RTA* é menor, mesmo assim o RTA*P émais eficiente.



Figura 13: Gráfico da média do número de vérticesexpandidos para grafos gerados pela GCC com pesos

constantes

Figura 14: Gráfico da média do número de vérticesexpandidos para grafos gerados pela GCC com pesos

constantes e sem a utilização de heurística

Figura 15: Gráfico da média do tempo de execução paragrafos gerados pela GCC com pesos constantes

Figura 16: Gráfico da média do tempo de execução paragrafos gerados pela GCC com pesos variados entre 1 a 10 e

sem a utilização de heurística

Existem vários emuladores de servidor para o ��: �5, �%, ��: e �� [Wikipedia,2008]. Escolhemos o �� versão 2 RC2 pelo fatodo mesmo ser bastante utilizado. O �� possuicódigo aberto e recria por meio da plataformaMicrosoft.NET o ambiente de um servidor para o�� . No �� é possível personalizargrande parte das características funcionais do jogo emanipular ;�-� (�� ). O teste dealgoritmos de busca �� implementados no ��teve como objetivo avaliar qualitativamente, no fluxodo jogo, a capacidade de um agente ;�- determinarsua trajetória e executá-la.

O �� apresenta situações onde odeslocamento dos ;�-� é dirigido por algoritmo debusca. Os movimentos de animais de estimação dojogador, denominados �� representam uma destassituações. Os �� são agentes ;�-� que se descolampelo mapa entre obstáculos em busca de umdeterminado alvo, o qual pode ser um agressor, umalvo de perseguição móvel ou o seu respectivo dono, ojogador, Figura 17.

O algoritmo de busca utilizado pelo emulador� ��é o A*, com área de busca bastante limitada (38 x 38quadrantes). O mapa completo do jogo possui 6144 x4096 quadrantes, sendo que cada um possui até oitovizinhos. A restrição na área de busca é motivada peloônus no tempo de resposta e de recursoscomputacionais.

Ao analisar os algoritmos de busca do ��, osquais se comportam de forma equivalente aosservidores oficiais de �� , constatamos acombinação de dois algoritmos O primeiro algoritmo éexecutado quando não há obstáculos entre o ;�- e oseu alvo. Este algoritmo é uma simples tentativa deandar em linha reta na direção do alvo, intercalandocom movimentos aleatórios quando é necessário umdesvio simples. Nos casos onde essa tentativa nãoobtém sucesso, um algoritmo A* é executado. Se umobstáculo intransponível surge repentinamente na rotado ;�-, a busca é cancelada e o primeiro algoritmo éexecutado novamente.

Os algoritmos de busca �� são capazes deencontrar um caminho até o objetivo, se o mesmoexistir. O processamento dessa busca não ocasionalentidão perceptível no servidor. O A* também resolvea busca em todo o mapa do jogo se ampliamos sua áreade busca. Contudo percebemos que as respostas dojogo ficam criticamente lentas, principalmente quandomais de vinte agentes executam a busca ��simultaneamente.

A vantagem dos algoritmos �� em relação aos �� é a ótima solução com o menor número de passosentre dois pontos. Por esse motivo, a busca �� éutilizada em grande parte dos jogos. Porém, quando o



jogo possui características de um sistema em temporeal, como os �� e &� (��) , abusca �� compromete a sua cadência.

A utilização de busca �� consome maior tempo deprocessamento para o primeiro passo do agente do quea busca ��. Na busca ��, toda a rota écalculada antes do primeiro passo do agente, enquantoque na busca �� cada passo pode ser planejado eexecutado logo em seguida. Pelo fato dos jogos digitaisem tempo real terem características dinâmicas, os alvostambém se movimentam e as rotas se modificam,inutilizando grande parte do cálculo da busca ��, aqual deve ser refeita.

O �� utiliza algoritmo de busca �� com áreade busca bastante limitada em torno do agente (Figura18a) e ignora os obstáculos dinâmicos do trajetocalculado. Porém esses ajustes no algoritmo provocamdois problemas de jogabilidade. O primeiro é aimpossibilidade de calcular uma rota quando háobstáculos fixos seccionando a área de busca doagente, Figura 18b. O segundo é a sobreposição deagentes durante e após o caminhamento,impossibilitando a seleção unitária dos mesmos parademais atividades ��, Figura 18d.

Implementamos no �� os algoritmos de busca �� RTA* e LRTA* com o intuito de observar, naperspectiva do jogador, o diferencial em relação ao usodo A*.

Nos experimentos, diferentemente dos pseudocódigosda literatura, não pré-calculamos as heurísticas de cadavértice do mapa, pois no �� cada ;�-necessitaria calcular e armazenar 6144 x 4096 valoresheurísticos cada vez que uma nova busca fosseiniciada. Então optamos por calcular as heurísticasnecessárias em tempo de execução e associamos a cadaagente uma árvore binária para armazenar apenas asheurísticas atualizadas durante a busca. Essa árvorecomeça vazia e à medida que o agente se desloca, asatualizações heurísticas são inseridas na árvore.Quando o agente alcança o seu objetivo ou quando oalvo se desloca, a busca é dada como encerrada ou seprepara para calcular outro trajeto. Nesse instante aárvore binária é reiniciada.

Observamos que os algoritmos �� resolvem osproblemas gerados pela utilização de busca ��com área limitada. Os agentes são capazes de caminharaté o seu alvo sempre que existir um caminho válidoem qualquer parte do mapa e os agentes jamais sesobrepõem, Figura 18e. Essas soluções melhoramconsideravelmente a jogabilidade com os ��.

Um problema observado com os algoritmos ��ocorre quando há muitos obstáculos na vizinhança dos;�-� formando uma área côncava. Nesse caso os;�-� parecem, por um momento, estarem perdidos.Este efeito acontece porque os movimentos dos ��acompanham o planejamento do algoritmo. Apesar

dessa desvantagem, os agentes encontram seu objetivo,Figura 18c. Este problema pode ser resolvidocalibrando o número de iterações que o agente deveplanejar a rota antes de se deslocar efetivamente noambiente do jogo.

Figura 17: Um jogador de e seus .

Figura 18: Comparações entre algoritmos (a, b, d) e(c, e) em situações observadas no .

.��*�� # �/��

Em jogos digitais existem situações onde é necessária autilização de algoritmos de busca. A maioria dos jogoseletrônicos resolve o problema de busca com soluçõesbaseadas no algoritmo A*. Os algoritmos de busca �� consomem mais recursos que os algoritmos de



busca ��. A utilização de algoritmos de busca �� em jogos digitais economiza processamento ememória viabilizando a busca simultânea de váriosagentes em ambientes mais complexos. Outravantagem é que os algoritmos de busca ��encontram a solução mesmo em ambientes dinâmicossem a necessidade de recalcular toda a trajetória.

O RRTA* ( �� &��') distribui a busca emmais de um agente e é útil em situações onde a buscapossa ser dividida, em jogos digitais, com váriosjogadores podemos distribuir a busca e também utilizareste algoritmo em situações de perseguição. Apesar doRRTA* apresentar números que indicam que ele émenos eficaz que o RTA*, ele encontra caminhos paramais de um agente. Para conseguir o mesmo resultado,o RTA* teria que executar uma busca para cadaagente.

Quando dispomos de heurísticas adequadas o RTA* émais eficiente que o RTA*P. Entretanto existemsituações em que não possuímos heurísticas, porexemplo, em alguns jogos digitais não conhecemos aposição do vértice objetivo. Para estas situações oRTA*P é mais eficiente que o RTA*. O RTA*P é maisestável que o RTA*, em grafos 4-conexos o número devértices expandidos e o tempo de execução do RTA*Psofrem menos variação que os do RTA* quandoacrescentamos, retiramos ou apenas modificamos aheurística. Quando o RTA* apresenta-se mais eficienteque o RTA*P esta diferença não é grande, por isso autilização do RTA*P em jogos digitais é indicada.

O emulador �� é um ambiente adequado parateste de algoritmos de busca em jogos pois mostrou sersuficientemente completo e flexível.

Aplicar algoritmos de busca �� em jogos digitais émotivado pelo fato desses experimentos nos levarem auma melhor observação do comportamento dos agentesda inteligência artificial (IA) em situações diversas.Tais observações são inspirações para novas idéias deimplementações. A percepção humana sobre ainteligência de um agente de IA pode ser presumidaquando há uma imersão no universo de ação domesmo, essa especificidade é bastante comum nosjogos. Os algoritmos �� são eficientes nos jogospossibilitando a busca em ambientes dinâmicos eprovendo a possibilidade de executar a busca para umnúmero maior de agentes.�.��/��

Propusemos alguns algoritmos e estudamos ocomportamento de algoritmos de busca em tempo realem jogos digitais. Contudo ainda é necessário avaliarestes algoritmos em outros jogos e em contextosdiferentes.

A estratégia de posicionamento do RRTA* éfundamental para sua eficiência, é necessário estudaroutras estratégias e validá-las no contexto de jogos

digitais além de explorar o potencial do RRTA* emsituações de perseguição.

É importante investigar o comportamento de outrosalgoritmos de busca �� em jogos eletrônicos eestudar a complexidade e a completude dos algoritmospropostos.

� - �0��

Bulitko, V, Sturtevant, N, Lu, J., & Yau, T. 2007.

Koenig, S. 2006.

Koenig, S. 1999.

Koenig,, S. , Likhachev, M., and Sun, X., 2007.

Korf, R. E. 1990.

Millington, I. 2006.

Nonnenmacher, V., Ferreira, S. and Osorio, F. 2007.

Origin – Ultima Online.

Pottinger, D. C. 2000.

Rabin, S. 1995.

Russel, S. and Norvig, P. 2004.

Sun, X., Koenig, G., and Yeoh, W.. 2008.

Van Waveren, J. M. P. 2001.

Wikipedia -

Wooldridge, M. 2002.

Yokoo, M.And Ishida, T. 1999.



Documents

Algoritmos de busca em tempo real aplicados a jogos digitais (PDF