INF 1771 – Inteligência Artificial
Aula 21 – Máquinas de Estados Finitos
Edirlei Soares de Lima
<elima@inf.puc-rio.br>
Introdução
•
Máquinas de Estados Finitos (Finite State Machines - FSM)
são provavelmente o padrão de software mais utilizado em
ara selecionar o comportamento de agentes re
Máquina de Estados
•
Uma máquina de estados é um modelo matemático usado
para representar programas.
–
–
–
Conjunto de estados.
Regras de transição entre estados.
Estado atual.
Máquina de Estados
•
•
Um exemplo bem simples de uma FSM é um interruptor de
luz.
Switch On
On
Off
Switch Off
Em um jogo normalmente uma FSM não é tão simples assim,
visto que geralmente os agentes podem ter um conjunto
muito maior de estados.
Exemplo – Pac-Man
•
•
Os fantasmas Inky, Pinky, Blinky e Clyde do
jogo Pac-man são implementados via FSM.
Os fantasmas tem 3 comportamentos:
–
–
–
Caçar (Chase)
Fugir (Evade)
Dispersar (Scatter)
•
•
A transição de estados ocorre sempre que o
jogador conseguir alguma pílula de energia.
A implementação da ação caçar de cada
fantasma é diferente.
Exemplo – Pac-Man
•
Máquina de Estados:
tempo_dispersar >= 5 (sec)
tempo_caçar >= 20 (sec)
Dispersar
Caçar
tempo_player_
energia >= 10 (sec)
player_pegou_
energia == true
Fugir
•
Os tempos variam em cada nível do jogo.
Exemplo – Pac-Man
•
Comportamento de Dispersar:
–
Mover em direção aos cantos
e ficar andando em círculos.
tempo_dispersar >= 5 (sec)
Dispersar
tempo_caçar >= 20 (sec)
Exemplo – Pac-Man
•
Comportamento de Fugir:
–
Movimentar-se mais lentamente com
movimentos aleatórios.
tempo_player_
energia >= 10 (sec)
player_pegou_
energia == true
Fugir
Exemplo – Pac-Man
•
Comportamento de Caçar:
–
Movimenta-se mirando na posição do Pac-Man.
tempo_dispersar >= 5 (sec)
tempo_caçar >= 20 (sec)
Caçar
tempo_player_
energia >= 10 (sec)
player_pegou_
energia == true
Exemplo – Pac-Man
•
Comportamento de Caçar:
–
Movimenta-se mirando na posição 4 tiles
tempo_dispersar >= 5 (sec)
tempo_caçar >= 20 (sec)
Caçar
tempo_player_
energia >= 10 (sec)
player_pegou_
energia == true
Exemplo – Pac-Man
•
Comportamento de Caçar:
–
Movimenta-se mirando em uma posição que combina a
posição/direção do Pac-Man e do Blinky
tempo_dispersar >= 5 (sec)
tempo_caçar >= 20 (sec)
Caçar
tempo_player_
energia >= 10 (sec)
player_pegou_
energia == true
Exemplo – Pac-Man
•
Comportamento de Caçar:
–
Quando está longe do Pac-Man, movimenta-se em direção ao Pac-
Man. Quando está perto, movimenta
tempo_dispersar >= 5 (sec)
tempo_caçar >= 20 (sec)
Caçar
tempo_player_
energia >= 10 (sec)
player_pegou_
energia == true
Exemplo – Pac-Man
•
•
Fim de jogo?
Teoricamente Pac-Man foi
projetado para não ter fim,
mas… no level 256…
Exemplo – Quake
•
•
Os NPCs do jogo Quake também são
implementados via FSM.
Estados/Comportamentos:
–
–
–
–
–
–
Procurar Armadura (FindArmor)
Procurar Kit Medico (FindHelth)
Correr (RunAway)
Atacar (Attack)
Perseguir (Chase)
...
•
Até mesmo as armas são
implementadas como uma mini FSM.
–
–
–
Mover (Move)
Tocar Objeto (TouchOject)
Morrer/Explodir (Die)
Exemplo – FIFA20XX
•
•
O comportamento dos jogadores é
definido através de FSMs.
Estados/Comportamentos:
–
–
–
–
Driblar (Dribble)
Correr Atrás da Bola (ChaseBall)
Marcar Jogador (MarkPlayer)
...
•
Os times também usam FSMs para
definir comportamentos em grupo.
–
–
–
Defender (Defend)
Atacar (Attack)
...
Máquina de Estados
Implementação
void run(int *state){
switch(*state){
case 0: //procurar inimigo
procurar();
case 2: //recarregar energia
recarregar();
if(encontrou_inimigo)
if(energia > 90)
*state = 1;
*state = 0;
break;
break;
case 1: //atacar inimigo
atacar();
case 3: //fugir
fugir();
if (morto){
if(!encontrou_inimigo){
if(energia < 50)
morrer();
*
state = -1;
*
state = 2;
else
state = 0;
}
if (matou){
*state = 0;
*
}
}
break;
if(energia < 50 || inimigo_forte)
state = 3;
break;
}
*
}
Vantagens
•
Elas são rápidas e simples de implementar – existem várias formas de
implementar e todas são muito simples.
•
•
•
Gastam pouco processamento.
São fáceis de depurar – quando o numero de estados é pequeno.
São intuitivas – qualquer pessoa consegue entender o seu significado
apenas olhando para a sua representação visual. Isso facilita o trabalho do
game designer, que muitas vezes não tem conhecimento de linguagens de
programação.
•
São flexíveis – podem ser facilmente ajustada pelo programador para
prover comportamentos requeridos pelo game designer.
Problemas
•
•
Á medida que a complexidade do comportamento dos
agentes aumenta, as FSMs tendem a crescer de forma
descontrolada.
As FSMs se tornam terrivelmente complexas quanto levam em
consideração ações muito básicas necessárias a um agente.
•
•
A representação visual torna-se intratável.
Comportamentos complexos são necessários em jogos
modernos.
FSM um Pouco Mais Complexa…
Máquina de Estados Finita Hierárquica
•
É possível organizar uma FSM usando máquinas de estados
finitas hierárquicas (HFSM).
•
Níveis mais altos lidam com ações mais genéricas, enquanto
níveis mais baixos lidam com ações mais específicas.
•
•
Cada estado pode ser uma nova FSM.
Infelizmente, a hierarquia não reduz o número de estados. Ela
pode somente pode reduzir significativamente o número de
transições e tornar a FSM mais intuitiva e simples de
compreender.
Máquina de Estados Finita Hierárquica
Máquina de Estados Finita Hierárquica
Leitura Complementar
•
Millington, I.; Funge, J.: Artificial
Intelligence for Games, 2nd Ed.,
Morgan Kaufmann, 2009.