IA e Jogos - Movimentação

Prévia do material em texto

IA e Jogos - Jamisson Freitas
IA e Jogos
Jamisson Freitas (James)
profjamissonfreitas@gmail.com
1
mailto:profjamissonfreitas@gmail.com
IA e Jogos - Jamisson Freitas
Apresentação
● Jamisson Freitas (James)
● Doutorando em Ciência da Computação 
(Cin-UFPE)
● Data Science Manager na Passei Direto
● Co-fundador da WeUp.ai
● Professor e Tutor em cursos de Graduação 
e Pós-Graduação
2
IA e Jogos - Jamisson Freitas
Conteúdo
● Game AI
● Inteligência artificial e Jogos Digitais
● Agentes Inteligentes
● Aplicações
● Técnicas
● Motores de Jogos
● Projeto
3
IA e Jogos - Jamisson Freitas
Referências
4
IA e Jogos - Jamisson Freitas
Técnicas
Movimentação
Pathfinding
Tomada de Decisão
Tática e Estratégia
5
IA e Jogos - Jamisson Freitas
Visão geral
● Técnicas de IA exploradas pela indústria de jogos são mais 
simples quando comparadas com as técnicas exploradas 
na academia e utilizadas em aplicações industriais. 
● Uma das causas desse fato é falta de tempo 
disponibilizado ao desenvolvimento de um jogo digital.
6
IA e Jogos - Jamisson Freitas
Visão geral
● A indústria de jogos digitais passou a pesquisar técnicas 
não só em seus ambientes gráficos, mas também, no 
desempenho, nos movimentos e estratégias calculadas 
pelos personagens.
7
IA e Jogos - Jamisson Freitas
Movimentação
8
IA e Jogos - Jamisson Freitas
Movimentação
Algoritmos básicos de movimento
Movimento em 2D e 3D
Movimento cinemático
Comportamentos de direção
9
IA e Jogos - Jamisson Freitas
Movimentação - Visão Geral
● Um dos requisitos mais fundamentais da IA é mover os 
personagens no jogo de maneira sensata.
● Mesmo os primeiros personagens controlados por IA (os 
fantasmas em Pac-Man ou o adversário em algumas 
variantes de Pong) tinham algoritmos de movimento que 
não eram muito distantes dos jogos na prateleira hoje. 
10
IA e Jogos - Jamisson Freitas
Movimentação - Visão Geral
● O movimento forma o nível mais baixo de técnicas de IA:
11
IA e Jogos - Jamisson Freitas
Movimentação - Visão Geral
● Existem diferentes algoritmos de movimento controlados 
por IA, desde o nível simples do Pac-Man até os 
complexos comportamentos de direção usados para 
dirigir um carro num simulador de corrida.
12
IA e Jogos - Jamisson Freitas
Movimentação - Estrutura do algoritmo
13
IA e Jogos - Jamisson Freitas
Movimentação
● Alguns algoritmos de movimento requerem poucos 
inputs. 
○ Ex. posição do personagem e a posição de um inimigo para 
perseguir, por exemplo. 
● Outros exigem muita interação com o jogo:
○ Um algoritmo de movimento que evita colisões nas paredes, precisa 
ter acesso à geometria da parede para verificar possíveis colisões.
14
IA e Jogos - Jamisson Freitas
Movimentação
● A saída pode variar também. Na maioria dos jogos, é 
normal que os algoritmos de movimento gerem uma 
velocidade desejada.
○ Ex: Um personagem pode ver seu inimigo 
imediatamente a oeste dele e responder que seu 
movimento deve estar a oeste a toda velocidade.
15
IA e Jogos - Jamisson Freitas
Movimentação
● Em muitos jogos antigos → duas velocidades: 
estacionárias e em execução
○ Saída simples: uma direção para se mover. 
(movimento cinemático - não explica como os 
personagens aceleram e diminuem a velocidade).
16
IA e Jogos - Jamisson Freitas
Movimentação
● Algoritmo de Craig Reynolds → movimento dinâmico
○ leva em conta o movimento atual do personagem.
https://www.youtube.com/watch?v=86iQiV3-3IA
17
https://www.youtube.com/watch?v=86iQiV3-3IA
IA e Jogos - Jamisson Freitas
Movimentação
18
http://www.youtube.com/watch?v=86iQiV3-3IA
IA e Jogos - Jamisson Freitas
Movimentação - 2 dimensões
● Muitos jogos têm AI que funciona em duas dimensões. 
● Embora os jogos raramente sejam desenhados em duas 
dimensões, seus personagens geralmente estão sob a 
influência da gravidade, colando-os no chão e 
restringindo seu movimento a duas dimensões.
19
IA e Jogos - Jamisson Freitas
Movimentação - 2 dimensões
● Maioria dos algoritmos clássicos de IA para movimento 
são definidos para 2 dimensões.
● Antes de examinarmos os algoritmos, precisamos 
rapidamente cobrir os dados necessários para lidar com 
matemática e movimentos bidimensionais (2D).
20
IA e Jogos - Jamisson Freitas
Movimentação - Personagens modelados como um ponto
● Um personagem geralmente consiste de um modelo 
tridimensional (3D) que ocupa espaço no mundo do jogo, 
apesar disso, muitos algoritmos de movimento assumem 
que o personagem pode ser tratado como um único 
ponto.
21
IA e Jogos - Jamisson Freitas
Movimentação - Personagens modelados como um ponto
● A geometria do modelo 
tem uma base ortonormal 
em 3D contendo três 
eixos: x, y e z.
● É mais comum que o eixo 
y esteja na direção oposta 
da gravidade (ou seja, 
“para cima”) e os eixos x e 
z no plano do solo.
22
IA e Jogos - Jamisson Freitas
Movimentação - Personagens modelados como um ponto
23
IA e Jogos - Jamisson Freitas
Movimentação - Geometria 2 ½ D
● Matemática da geometria 3D é complicada;
● O movimento linear em três dimensões é bastante 
simples e uma extensão natural do movimento 2D;
● Representar uma orientação tem consequências 
complicadas que é melhor evitar (neste curso);
● Híbrido entre o 2D e o 3D → 2 ½ D
24
IA e Jogos - Jamisson Freitas
Movimentação - Geometria 2 ½ D
● Nós lidamos com uma posição 3D completa, mas 
representamos a orientação como um único valor, como 
se estivéssemos em duas dimensões. 
● Isso é bastante lógico quando você considera que a 
maioria dos jogos envolve personagens sob a influência da 
gravidade.
25
IA e Jogos - Jamisson Freitas
Movimentação - Geometria 2½ D
● Devido a gravidade o personagem é puxado para o chão 
→ opera como se estivesse em 2D, embora saltar, soltar 
saliências e usar elevadores envolva movimentos 3D;
26
IA e Jogos - Jamisson Freitas
Movimentação - Geometria 2½ D
● Se um personagem permanece em pé, então o único 
componente de sua orientação com que precisamos nos 
preocupar é a rotação na direção para cima.
● Trabalhando em 2½ D → a simplificação na matemática 
compensa a menor flexibilidade na maioria dos casos.
27
IA e Jogos - Jamisson Freitas
Movimentação - Geometria 2½ D
● Duas dimensões → precisamos apenas de um ângulo para 
representar a orientação (representação escalar).
● O ângulo é medido a partir do eixo z positivo, em uma 
direção à direita em relação ao eixo y positivo (sentido 
anti-horário ao olhar para baixo no plano x – z acima).
28
IA e Jogos - Jamisson Freitas
Movimentação - Geometria 2½ D
29
IA e Jogos - Jamisson Freitas
Movimentação - Geometria 2½ D
● Representação vetorial
30
IA e Jogos - Jamisson Freitas
Movimentação - Cinemática
● Cinemática (do grego movimento) é o ramo da Física que 
se ocupa da descrição dos movimentos dos corpos.
● Por norma caracteriza-se por partículas ou pontos 
materiais, corpos em que todos os seus pontos se movem 
de maneira igual e em que são desprezadas suas 
dimensões em relação ao problema e à resistência.
31
IA e Jogos - Jamisson Freitas
Movimentação - Cinemática
● Precisamos fazer com que o movimento dos personagens 
pareça mais realista possível;
● Podemos criar algoritmos de movimento para calcular 
uma velocidade-alvo com base apenas na posição e 
orientação, permitindo que a velocidade de saída mude 
instantaneamente.
32
IA e Jogos - Jamisson Freitas
Movimentação - Cinemática
● Algoritmos para suavizar → alterar gradualmente a 
velocidade ao longo do tempo.
33
IA e Jogos - Jamisson Freitas
Movimentação - Cinemática
● Os personagens precisam manter o controle de ambas as 
velocidades lineares e angulares;
○ Rotação → velocidade angular;
○ Velocidade linear → velocidade. 
34
IA e Jogos - Jamisson Freitas
Movimentação - Cinemática
● Comportamentos de direção operam com esses dados 
cinemáticos. 
● Eles retornam acelerações que alteram as velocidades de 
um personagem para movê-las pelo nível. 
●Sua saída é um conjunto de acelerações:
35
IA e Jogos - Jamisson Freitas
Movimentação - Direção do movimento
● Suavizar a mudança de direção
36
IA e Jogos - Jamisson Freitas
Movimentação - Atualizando direção e movimento
● Algoritmo 
simples
37
IA e Jogos - Jamisson Freitas
Movimentação - Taxas de quadros variáveis
38
IA e Jogos - Jamisson Freitas
Movimentação - Taxas de quadros variáveis
● Os jogos mais antigos costumavam usar velocidades por 
quadro, mas essa prática desapareceu em grande parte.
● Atualmente, os jogos (em maioria) são escritos para 
suportar taxas de quadros variáveis, portanto, um
o tempo de atualização é usado.
39
IA e Jogos - Jamisson Freitas
Movimentação - Taxas de quadros variáveis
Testando velocidade dos frames:
https://frames-per-second.appspot.com/
Apesar do padrão ser 24 fps, YouTube libera vídeos de 
jogos com 60 fps:
https://bit.ly/2TG8A7E
40
https://frames-per-second.appspot.com/
https://bit.ly/2TG8A7E
IA e Jogos - Jamisson Freitas
Movimentação - Forças e atuação
● No mundo real, não podemos simplesmente aplicar uma 
aceleração a um objeto e movê-lo. 
● Nós aplicamos forças, e estas causam uma mudança na 
energia cinética do objeto. 
41
IA e Jogos - Jamisson Freitas
Movimentação - Forças e atuação
● Eles vão acelerar, é claro, mas a aceleração dependerá da 
inércia do objeto. A inércia age para resistir à aceleração; 
quanto maior a inércia, menos aceleração para a mesma 
força.
42
IA e Jogos - Jamisson Freitas
Movimentação - Forças e atuação
● Num Jogo, a massa do objeto é a inércia linear e o 
momento de inércia (ou tensor de inércia em três 
dimensões) é aceleração angular. 
● A IA controla o movimento de um personagem aplicando 
forças nele. Essas forças representam as maneiras pelas 
quais o personagem pode afetar seu movimento.
43
IA e Jogos - Jamisson Freitas
Movimentação - Seek e Flee
● Seek (procurar, buscar) tenta corresponder a posição do 
personagem com a posição do alvo. 
● Flee (caminho de fuga) Flee é o oposto de Seek. Tentar 
chegar o mais longe possível do alvo.
44
IA e Jogos - Jamisson Freitas
Movimentação - Seek
● Exatamente como no algoritmo de busca cinemática, ele 
encontra a direção para o alvo e se dirige a ele o mais 
rápido possível.
● Como a saída da direção é agora uma aceleração, ela 
acelerará o máximo possível.
45
IA e Jogos - Jamisson Freitas
Movimentação - Seek
● A maioria dos personagens tem uma velocidade máxima 
que eles podem se deslocar; eles não podem acelerar 
indefinidamente. 
● O máximo pode ser explícito, mantido em uma variável 
ou constante.
46
IA e Jogos - Jamisson Freitas
Movimentação - Seek
47
IA e Jogos - Jamisson Freitas
Movimentação - Seek (pseudo-código)
48
IA e Jogos - Jamisson Freitas
Movimentação - Seek (pseudo-código)
49
IA e Jogos - Jamisson Freitas
Movimentação - Seek
50
IA e Jogos - Jamisson Freitas
Movimentação - Flee
● Fazer um personagem mover-se o mais longe possível do 
alvo. 
● Assim como para a fuga cinemática, basta inverter a 
ordem dos termos na segunda linha da função:
51
IA e Jogos - Jamisson Freitas
Movimentação - Laboratório
https://editor.p5js.org/simontiger/sketches/B1GtGlDGb
52
https://editor.p5js.org/simontiger/sketches/B1GtGlDGb
IA e Jogos - Jamisson Freitas
Movimentação - Arrive (chegada, aproximação)
● Em seek (busca) o personagem sempre se moverá em 
direção ao seu objetivo com a maior aceleração possível.
● Para um alvo constantemente em movimento e o 
personagem precisar persegui-lo a toda velocidade: 
○ Se o personagem chegar ao alvo, ele irá ultrapassar, 
reverter e oscilar pelo alvo, ou será mais provável 
orbitar em volta do alvo sem se aproximar.
53
IA e Jogos - Jamisson Freitas
Movimentação - Arrive (chegada, aproximação)
● Se o personagem deve chegar ao alvo, ele precisa 
desacelerar para que chegue exatamente no local correto
● No arrive o personagem vai direto ao seu alvo, enquanto 
no seek o personagem órbita um pouco e acaba oscilando.
● Naturalmente, o comportamento dinâmico do Arrive é 
um pouco mais complexo que a versão cinemática.
54
IA e Jogos - Jamisson Freitas
Movimentação - Arrive
Alvo
Fixo
55
IA e Jogos - Jamisson Freitas
Movimentação - Arrive (chegada, aproximação)
● A oscilação não é tão ruim para a busca dinâmica quanto 
na busca cinemática: o personagem não pode mudar de 
direção imediatamente.
56
IA e Jogos - Jamisson Freitas
Movimentação - Arrive (Pseudo-código)
57
IA e Jogos - Jamisson Freitas
Movimentação - Arrive (Pseudo-código)
58
IA e Jogos - Jamisson Freitas
Movimentação - Arrive (Pseudo-código)
59
IA e Jogos - Jamisson Freitas
Movimentação - Pursue e Evade
● Qual(is) problema(s) podemos identificar se movemos 
nosso personagens apenas com base na posição?
60
IA e Jogos - Jamisson Freitas
Movimentação - Perseguição 
● Se estamos perseguindo um alvo em movimento, então 
um movimento constantemente na direção do alvo não 
será suficiente.
● No momento em que chegarmos onde está agora, ele já 
terá se deslocado.
61
IA e Jogos - Jamisson Freitas
Movimentação - Perseguição 
● Isso não é um grande problema quando o alvo está 
próximo e estamos reconsiderando a localização dele a 
cada frame.
62
IA e Jogos - Jamisson Freitas
Movimentação - Perseguição 
63
IA e Jogos - Jamisson Freitas
Movimentação - Perseguição 
64
IA e Jogos - Jamisson Freitas
Movimentação - Perseguição - (Pseudo-código) 
65
IA e Jogos - Jamisson Freitas
Movimentação - Perseguição - (Pseudo-código) 
66
IA e Jogos - Jamisson Freitas
Movimentação - Face
● O comportamento do rosto faz um personagem olhar 
para o alvo. 
● Delega ao comportamento de alinhamento para executar 
a rotação, mas calcula a orientação do alvo primeiro.
● A orientação do alvo é gerada a partir da posição relativa 
do alvo para o personagem. 
67
IA e Jogos - Jamisson Freitas
Movimentação - Path Following
● Seguindo um caminho é um comportamento de direção 
que considera um caminho inteiro como um destino. 
● Um personagem com este comportamento deve se mover 
ao longo do caminho em uma direção.
● Calcula a posição de um alvo com base na localização 
atual do personagem e na forma do caminho.
68
IA e Jogos - Jamisson Freitas
Movimentação - Path Following
● Em seguida, entrega seu alvo para o algoritmo de Seek. 
● Não há necessidade de usar o algoritmo do Arrive, porque 
o alvo deve estar sempre se movendo ao longo do 
caminho.
69
IA e Jogos - Jamisson Freitas
Movimentação - Path Following
● A posição final é calculada em duas etapas:
○ 1. A posição atual do personagem é mapeada para o 
ponto mais próximo ao longo do caminho.
○ 2. É selecionado um alvo que está mais adiante no 
caminho do que o ponto mapeado por uma distância 
fixa.
70
IA e Jogos - Jamisson Freitas
Movimentação - Path Following
● Essa abordagem às vezes é chamada de "perseguir o 
coelho", após a maneira como os cães caçam um coelho 
de pano na trilha.
71
IA e Jogos - Jamisson Freitas
Movimentação - Path Following
72
IA e Jogos - Jamisson Freitas
Movimentação - Prevenção de colisões
● Algumas áreas é comum ter um grande número de 
personagens movendo-se pelo mesmo espaço. 
● Desafio: trajetórias que se cruzam e precisam evitar 
colisões constantes com outros personagens em 
movimento. O que pode-se fazer?
73
IA e Jogos - Jamisson Freitas
Movimentação - Prevenção de colisões
● Solução simples: usar uma variação do comportamento de 
evade ou separação, que só é acionado se o alvo estiver 
dentro de um cone na frente do personagem.
74
IA e Jogos - Jamisson Freitas
Movimentação - Prevenção de colisões
75
IA e Jogos - Jamisson Freitas
Movimentação - Prevenção de colisões
● Se houver vários personagens do jogo no cone é 
necessário evitar todos eles;
● Eficiente para poucos personagens;
● O personagem não leva em conta se vai realmente colidir, 
mas ao invés disso, tem uma reação de “pânico” atémesmo se aproximando.
76
IA e Jogos - Jamisson Freitas
Movimentação - Prevenção de colisões
77
IA e Jogos - Jamisson Freitas
Movimentação - Prevenção de colisões
78
IA e Jogos - Jamisson Freitas
Movimentação
79
IA e Jogos - Jamisson Freitas
Referências
80
IA e Jogos - Jamisson Freitas
Referências
● Programming Game AI by Example. Mat Buckland. 
● Artificial Intelligence for Games. Ian Millington, John 
Funge.
81
IA e Jogos - Jamisson Freitas
Links
https://meiobit.com/310886/deepmind-google-inteligencia-artificial-jogos-atari/
https://www.maxwell.vrac.puc-rio.br/7861/7861_3.PDF
https://www.red3d.com/cwr/boids/
https://www.youtube.com/channel/UCC0RqWklkXJwAd_HIsxRZDg
https://github.com/idmillington/aicore
82
https://meiobit.com/310886/deepmind-google-inteligencia-artificial-jogos-atari/
https://www.maxwell.vrac.puc-rio.br/7861/7861_3.PDF
https://www.red3d.com/cwr/boids/
https://www.youtube.com/channel/UCC0RqWklkXJwAd_HIsxRZDg
https://github.com/idmillington/aicore