Técnicas de GameAI: Uma visão geral -...

Prof. Marcelo Henrique dos Santos

Técnicas de GameAI:

Uma visão geral - continuação

Técnicas de GameAI

Movimentação

“Estacionando”

”Vagando”

Desvio de Obstáculos

Pathfinding

Simples

Desvio de Obstáculos

A*

Waypoints

Movimentação

“Estacionando”

d = distância calculada

dmin = distância mínima desejada do alvo

fdes = fator de desaceleração (< 1 e depende da dinâmica do jogo) Ex: 0.3

Vaprox = velocidade de aproximação

Vorig = velocidade sem levar em conta a aproximação

Movimentação

”Vagando”

• passar a impressão de movimento aleatório

• 1ª idéia – variar direção do NPC aleatoriamente

problema ...

–não natural - movimentos bruscos

solução ...

Movimentação

”Vagando”

a dinâmica do movimento é controlada por rv, dv e max_dram

Movimentação

Desvio de Obstáculos

• retângulo de detecção ou outras formas. ex:

• largura igual ao raio de “batida”

• quanto mais rápido o veículo mais longo o retângulo fica

Movimentação

Desvio de Obstáculos

• 1º passo – achar o ponto de intersecção mais próximo

...

A. desconsiderar obstáculos fora do alcance do retângulo de detecção

B. desconsiderar obstáculos atrás, converter coordenadas de obstáculos

com possível colisão para coordenadas locais e verificar coordenada y

C. verificar se obstáculos se sobrepõe ao retângulo, expandir raio do

obstáculo por metade da largura do retângulo e verificar coordenada

Movimentação

Desvio de Obstáculos

D. achar o ponto de intersecção mais próximo

Movimentação

Desvio de Obstáculos

• 2º passo – calcular força de frenagem e força lateral

Movimentação

Desvio de Obstáculos

• caso 3D ...

– obstáculos = esferas

– retângulo = cilindro

Pathfinding

• Pathfinding, ou busca de caminhos é um dos problemas mais

comuns no desenvolvimento de jogos, e está presente na maioria dos

gêneros.

• patrulhamento

• desvio de obstáculos

• perseguição

• planejamento de trajetória

• mirar (se tem obstáculo deve ser previsto) mover-se e atirar

Pathfinding

Caso Simples

• pode-se utilizar algoritmos de perseguição e fuga

abstração:

ponto inicial = predador

ponto final = presa

problema ...

obstáculos

Pathfinding

Desvio de Obstáculos

Estratégias

Contornar Obstáculos

– obstáculos maiores

– critério de saída do modo “contorno”...

pseudo-código pathfinding simples + desvio

Início

ENQUANTO

não chegou ao destino

ESCOLHA um próximo passo rumo ao destino

SE o local está vazio, mova-se até ele

SENÃO escolha outra direção segundo estratégia de

desvio de obstáculos

FIM ENQUANTO

Fim

Verificar textos deste slide que estão “Atrás” do código e

eu não consegui decifrar...)

Pathfinding

Waypoints

• utilização de rotas interligando os pontos principais

em um mapa é uma técnica usada em jogos.

• cada nó do grafo representa um waypoint que

contém informações sobre como chegar até os nós vizinhos.

exemplo: jogos de corrida.

Na pista pode ser definidas diversas

rotas com características diferentes.

Cada carro começa seguindo uma rota

e muda quando necessário

(ex: carros na sua frente)

Pathfinding

A*

• cálculo de caminho ótimo + desvio de obstáculos

• modelagem:

(quadrado, retângulos, hexágonos, outros)

– utilização de grafo (vizinhança)

– cada ladrilho = um nó no grafo

Pathfinding

A*

A* mantém duas listas:

– nós abertos: armazena todos os nós que precisam ser

verificados,

– nós fechados: armazena os nós que não precisam

mais ser verificados no momento.

Pathfinding

A*

• o ponto crucial aqui é escolher qual dos nós fará

parte do caminho a ser percorrido.

• função de avaliação F(n) que é o resultado da soma

F(n) = G(n) + H(n)

• onde G(n) custo do nó inicial ao nó candidato ex: 10 quadrado horizontal ou vertical e de 14 diagonal(~10*√2)

• e H(n) é a função heurística, indica o custo estimado do nó

candidato até o destino final

ex: método Manhattan, número de quadrados horizontal e

vertical até o alvo, ignorando movimento diagonal, e ignorando

qualquer obstáculo que pode estar no caminho

Pathfinding

A*

1. coloca-se o nó inicial na lista de abertos;

2. nós adjacentes (filhos) também na lista de abertos,

se não estiverem, menos obstáculos ou nós da lista de

fechados;

3. coloca-se o nó inicial na lista de nós fechados;

Pathfinding

A*

4. se nó adjacente está na lista aberta, verificar se o

G agora é mais baixo do que o já na lista se não for,

não fazer nada;

se for, trocar o pai do nó adjacente para o nó selecionado e

recalcular o F;

5. repetir até nó-destino ser adicionado à lista de abertos

(algoritmo termina em “sucesso”), ou a lista de abertos fique

vazia (falha na busca de um caminho).

Pathfinding

A*

Exemplo

legenda:

verde = lista aberta

azul = lista fechada

Algoritmos de busca em grafo:

B*

• Bellman-Ford algorithm

• Best-first search

• Bidirectional search

• Breadth-first search

D*

• Depth-first search

• Depth-limited search

• Dijkstra's algorithm

• Floyd–Warshall algorithm

• Hill climbing

• Iterative deepening depth-first search

• Johnson's algorithm

• Uniform-cost search

Algoritmo MiniMax

• Faz uma caminhamento em profundidade completo da árvore!

• Se a profundidade é m e em cada estado existem b jogadas

possíveis, a ordem de complexidade é O(bm)

• Ou seja esse algoritmo não é prático para jogos reais

• Mas serve para análise matemática e como base para

algoritmos mais eficientes

Multiplayer games

O MiniMax pode ser estendido para jogos com múltiplos jogadores

Uso de um vetor de utilidades

Alianças

Podem ocorrer naturalmente no processo de maximizar a função de

utilidade

Qual o problema com o MiniMax?

Alpha-Beta Pruning

Problema com o MiniMax

# de estados é exponencial

Pruning = Poda

Não examinar grandes partes da árvore,

diminuindo assim o custo

Alpha-Beta Prunning

Retorna a mesma ação do MiniMax, mas elimina

caminhos que não influenciam a decisão

α-β pruning example

α-β pruning example

α-β pruning example

α-β pruning example

α-β pruning example

Alpha-Beta Pruning

a = o maior valor já

encontrado no caminho

(melhor alternativa p/ MAX)

ß = o menor valor já

encontrado no caminho

(melhor alternativa p/ MIN)

Se v é pior que alpha,

MAX vai evitá-lo

Alpha-Beta Pruning

• A eficiência do algoritmo depende da ordem

em que os nodos são examinados

Decisões Imperfeitas, em Tempo Real

Minimax mesmo c/ Alpha Beta Prunning não

é factível para jogos complexos

Solução:

Parar a busca antes de chegar ao final

É necessário:

Função de Avaliação (Evaluation Function):

fornece uma estimativa da utilidade daquele

estado (Heurística)

Teste de Parada (Cutoff Test): decide em quando

parar a busca

Funções de Avaliação

• Devem tentar manter a mesma ordenação da função de utilidade final

• Não podem demorar muito

• Devem estar relacionadas com as “chances de ganhar o jogo”

• Chances? Jogo é determinístico!?

• Incerteza computacional ao invés de incerteza da informação

Funções de Avaliação

• Análise de características (features) do estado corrente

• Divisão em classes de equivalência • Conjuntos de estados com características similares

• Para cada classe, determina-se por experiência: •%Vitórias, %Empates, %Derrotas

• Função de avaliação é calculada como uma média ponderada. •Ex. 72% Vitória, 20% Derrota, 8% empate

Eval(S) = (0.72 x 1) + (0.2 x -1) + (0.08 x 0) = 0.52

•Requer muitas classes e experiência...

Funções de Avaliação

• Uma forma mais fácil é dar valor diretamente as

features •Xadrez: Peão = 1, Cavalo / Bispo = 3, etc...

•“Estrutura de peões”, “Proteção do rei”, etc...

• A função de avaliação é computada através de uma

combinação linear ponderada •Eval(S) = w1.f1 (s) + w2.f2 (s) + ... + wn.fn (s)

•Funções não lineares também podem ser usadas •Um par de bispos tem mais valor que o dobro de um só

•Leva em consideração as outras peças

•De novo, experiência / aprendizado é necessário

Teste de Parada

• If Cutoff-Test(State, Depth) return Eval(state)

• Forma mais comum: profundidade fixa

• Problemas: e se na próxima jogada...

Teste de Parada

• A função de avaliação somente deve ser aplicada

a estados que não vão sofrer mudanças bruscas

de valor •Quiescence Search

• Efeito Horizonte: jogada

catastrófica que vai

acontecer inevitavelmente

em um futuro próximo,

fora do horizonte de busca

Poda

• Singular Extensions • Ultrapassar a profundidade limite para ações que

são “claramente melhores”

Na prática, diminui o branching factor (poda)

• Forward Prunning • Ignorar certos movimentos possíveis

• Humanos fazem isso inconscientemente

• Não há garantias...

• Interessante para movimentos simétricos

Xadrez na Prática

• Suponha uma função de avaliação e um PC que

• consiga investigar 10^6 nodos/s

• 200 x 10^6 nodos por jogada (3 minutos)

• Branching Factor: 35: 35^5 = 50 x 10^6

• Minimax = 5 jogadas (jogador mediano)

• Alpha-Beta = 10 Jogadas (expert)

• Para virar um Grande-Mestre: • Função de avaliação bem ajustada

• Banco de jogadas (abertura e término)

• Supercomputador...

Jogos Não-Determinísticos (sorte)

• Exemplo: Gamão

• As jogadas possíveis são determinadas

depois que se jogam os dados

• Não é possível construir uma árvore como no

caso do xadrez e aplicar o minimax

• Solução: • Incluir nodos intermediários com as chances

• Algoritmo: ExpectiMinimax