Inteligencia Artificial #2 - Máquina de Estados Finitos (FSM)

[Raizen]

Conhecimento necessário : médio​

[box class=windowbg]

FSM (Finite State Machine)​

[/box]
[box class=windowbg2]
Para a segunda aula vamos explicar sobre um algoritmo que é muito utilizado nos jogos que contém I.A. Esse seria o FSM (Finite State Machine), ou Máquina de Estados Finitos. Como definição do método ele depende apenas de uma coisa, que a máquina tenha um estado único a cada momento. Um exemplo prático em jogos, que o NPC tenha apenas uma estado, correndo, voando, atacando etc.
Qual é a maior diferença em relação a aula anterior de Árvore de decisão, a maior diferença é que na realidade não há o dito "tomada de decisão", isso é um estado da máquina e não uma decisão que ele toma a cada X segundos. A máquina sempre irá verificar o estado para saber como agir em tempo real.
Vamos as condições necessárias para o FSM:

[*] Um número finito de estados possíveis para a máquina (Ex: correr, pular e andar)
[*] A máquina pode assumir apenas um estado simultaneamente.
[*] É realizado uma série de verificações para as transições de estado


Explicando com códigos:

	classe Personagem
	  metodo Personagem
	    correndo = Correndo(personagem)
		pulando = Pulando(personagem)
		andando = Andando(personagem)
	  fim metodo
	  metodo estado_inicial()
	    estado = andando
	  fim metodo
	  metodo transicao_estado(estado_novo)
	    estado = estado_novo
	  fim metodo 
      metodo estado_atual()
	    retorna estado
      fim metodo	  
	  fim classe
	    
	classe Correndo(personagem)
		//metodos que demonstram o personagem correndo, imagens, sons etc
	fim classe
	classe Pulando(personagem)
		//metodos que demonstram o personagem pulando, imagens, sons etc
	fim classe
	classe Andando(personagem)
		//metodos que demonstram o personagem andando, imagens, sons etc
	fim classe

Como ele funciona, a máquina tem um estado inicial, no caso parado, sempre que eu quiser mudar o estado dele existe o chamado, transição de estado, essa transição de estado pode ter N condições, usando a mesma lógica do tomada de decisão da aula anterior, você pode sempre verificar se é necessário mudar o estado da máquina. Essa A.I é muito utilizada em jogos de estratégia como Age of Empires, ela permite que sempre seja verificado se cada máquina precisa mudar o estado.

Você pode imaginar as possibiidades assim:

[/box]

[box class=windowbg]

FSM com pilha​

[/box]

[box class=windowbg2]
  Agora que sabem como funciona o FSM, vamos adicionar um pouco de tempero ao algoritmo. Para uma ação mais natural do NPC vamos supor uma certa situação. o FSM verifica que o NPC tem que atacar uma casa, ai ele termina de destruir a casa logo o estado se desliga... E depois? o que aconteceria se usar apenas o método acima ele vai ficar parado até atingir alguma nova condição para mudar a sua ação. Para resolver esse "delay" de estado, podemos usar a pilha.
  Mais especificamente LIFO, qual é o plano aqui, LIFO significa o último que entrou sai, então ao invés de simplesmente mudarmos o estado, vamos empurrando os novos estados e ai caso um estado cumpra a função retiramos ele e seguimos para o estado seguinte. Exemplo prático:
  Adicionar ao NPC "correr em direção a uma edificação"
  Adicionar ao NPC "atacar edificação"
  Edificação destruida, retiro o estado atacar a edificação, o estado anterior seria "correr em direção a uma edificação" , que ele ira realizar.
 
  no nosso código ficaria:
 
 

  	  metodo transicao_estado(estado_novo)
	    estado.empurrar(estado_novo)
	  fim metodo 
      metodo estado_atual()
	    retorna estado.ultimo
      fim metodo	
      metodo remover_estado()
	    retorna estado.remover_ultimo
      fim metodo
 

  Claro que isso pode ser aprimorado com todo o restante da lógica de programação como condições.
[/box]

[box class=windowbg]

Finalizando​

[/box]
[box class=windowbg2]
Agora começou a ficar interessante ! Espero que tenham gostado dessa aulinha e fiquem a vontade para qualquer ponto de melhoria!
[/box]