Máquinas de Estado Finito

Máquinas de Estado Finito

Nome:  Gabriel Bitencourt de Almeida Moura                                RA: 11030113
Nome:  Gustavo Iha Rodrigues de Moraes                                RA: 11038213

Definição: Uma máquina de estados finitos, em inglês Finite State Machine (FSM), é uma modelagem de um comportamento de estados, transições e ações  usada para representar circuitos lógicos ou programas de computadores. No âmbito de jogos, é provavelmente o padrão de software mais utilizado para selecionar o comportamento de agentes reativos. O estado armazena informações sobre o passado; a transição indica a mudança de estados, descrita por uma condição que provoca a reação; a ação é uma atividade a ser realizada em um determinado tempo.        
        As FSM podem ser dividas em dois grupos, segundo a saída que é efetuada: Máquina de Mealy e Máquina de Moore.  A primeira é um sistema sequencial cuja saída no tempo t depende do estado e da entrada no tempo t, ou seja: z(t)=H(s(t), x(t)). Já na segunda, também um sistema sequencial, sua saída no tempo t depende somente do estado neste tempo, assim, podemos modela-la, como: z(t) = H(s(t)).

Aplicação Prática: Uma das aplicações mais simples é um interruptor de luz, que poderia ser representado através do seguinte diagrama:

[pic 2]

Os estados possíveis do interruptor são: ligado (on) e desligado (off). As transições possíveis, ou seja, as mudanças de estado, só ocorrem após o contato e mudança na chave que gera a ação imediatamente: acender ou desligar uma lâmpada que esteja ligada a este circuito elétrico.

[pic 3]Uma aplicação mais sofisticada é a modelagem do comportamento programado dos fantasmas no clássico jogo PAC-MAN. Os fantasmas possuem 3 três ações diferentes:  dispersão no início do jogo, em que os fantasmas se direcionam e movimentam-se em rotas nos cantos do labirinto; caça ao personagem PAC-MAN, em que, assim que os fantasmas são libertos de sua prisão inicial, nesse estado cada fantasma possui uma estratégia de caça diferente; fuga, quando ocorre a transição de estado, para pontos distantes do PAC-MAN de forma aleatória. A transição de estado no jogo ocorre quando o usuário absorve uma pílula de energia.

Referências

Margaret Rouse. URL: http://whatis.techtarget.com/definition/finite-state-machine

Claudius Ptolemaeus, Editor, System Design, Modeling, and Simulation using Ptolemy II, Ptolemy.org, 2014. Capítulo 6.

Mike James. URL: http://www.i-programmer.info/babbages-bag/223-finite-state-machines.html

...