Ia nos jogos

Inteligência Artificial para Jogos
Planejamento de Trajetória

Prof. MSc. João Ricardo Bittencourt

Update: 10 Set. 2009 [e-mail] “Tome a pílula vermelha” GT-JEDI – Jogos Digitais
Agradeço e dedico estas aulas ao Prof. Osório

Inteligência Artificial para Jogos
UNISINOS

Sumário
1.
2.
3.

Retomando ...
Problema - Encontrar caminho
Buscas com heurística

UNISINOS - João Ricardo Bittencourt

Retomando ...


Jogos de raciocínio (brain taisers) – busca livre



Jogos de tabuleiro (board games) – busca condicionada 

Busca em espaço de estados (trees and adversarial search)



Agora vamos ver problemas com labirintos
 Buscar caminhos (path finding)
 Planejar ações e trajetórias (path planning)
 Deslocamento/navegação (Motion & navigation) UNISINOS - João Ricardo Bittencourt

Encontrar caminho


Problema básico – Encontrar o caminho de um ponto A até um ponto B
 Pode ser encontrar o melhor caminho
• Menor custo, mais rápido, com menos inimigos, com mais itens, ...
 Para responder estas perguntas usamos labirintos!  Labirintos
• Grade
• Mapa
UNISINOS - João Ricardo Bittencourt

Encontrar caminho


Labirintos
 Grade
 Mapa

Grade
Mapa

UNISINOS - João Ricardo Bittencourt

Encontrar caminho


Algoritmos de busca
 Path finding
 Path planning



Usados algoritmos de busca cega/não informada
 Busca em largura
 Busca em profundidade
 Busca exaustiva

UNISINOS - João Ricardo Bittencourt

Encontrar caminho


Principal problema
 Ficar trancado no mapa!



Dependendo do labirinto o problema torna-se intratável – inúmeras possibilidades do espaço de busca



Qual a solução?
 Otimizar!
 E claro ... usar uma heurística

UNISINOS - João Ricardo Bittencourt

Encontrar caminho


Busca com heurística: Cálculo do custo do caminho 3

A

4

5

S

4

B

C

5
G

4

D

2

E

4

F

3

UNISINOS -