Creating a State Machine without JavaScript libraries

3

I was looking at how to program a state machine on google and I came up with several results that led me to libraries geared to such, but I would like to understand how it is processed and how to get to > state machine simple and functional.

I want to use it for a simple shift game on the canvas element, I'm a beginner in the area and would like any help I could get, grateful!

    
asked by anonymous 03.12.2015 / 01:31

1 answer

3

A finite state machine is a machine with a finite set of states (as the name already says). It is modeled as a graph, in which the vertices are the states and the edges are the transitions. For a given input starting from a certain state, one arrives in another state.

One of the states of the state machine is called the initial state. So for each input symbol, you navigate the transitions from one state to another. Note that the only thing that is memorized is the current state.

Implementing this, maybe what you want is something like this:

function MaquinaDeEstados() {
  var estados = new Map();

  var erro = {
    adicionarTransicao: function(entrada, destino) {
      return this;
    },
    proximo: function(entrada) {
      return erro;
    },
    valor: function() {
      return "{erro}";
    }
  };

  function Estado(valor) {
    var transicoes = new Map();
  
    this.adicionarTransicao = function(entrada, destino) {
      transicoes.set(entrada, destino);
      return this;
    };

    this.proximo = function(entrada) {
      var retorno = transicoes.get(entrada);
      return typeof retorno === "undefined" ? erro : retorno;
    };

    this.valor = function() {
      return valor;
    };
  }

  this.estado = function(chave) {
    var estado = estados.get(chave);
    if (typeof estado === "undefined") {
      estado = new Estado(chave);
      estados.set(chave, estado);
    }
    return estado;
  };
}

/* Teste. Criando uma máquina de estados: */
var chave1 = "A", chave2 = "B", chave3 = "C";
var maquina = new MaquinaDeEstados();
var estado1 = maquina.estado(chave1);
var estado2 = maquina.estado(chave2);
var estado3 = maquina.estado(chave3);
estado1.adicionarTransicao(0, estado1);
estado1.adicionarTransicao(1, estado2).adicionarTransicao(2, estado3);
estado2.adicionarTransicao(3, estado3).adicionarTransicao(2, estado3);
estado3.adicionarTransicao(1, estado1);

/* Teste. Executando a máquina de estados: */
var entrada = [0, 1, 3, 1, 0, 2, 1, "lugar nenhum", 2, 2];
var atual = estado1; // Definimos que este é o estado inicial.
var passeio = atual.valor();
for (k in entrada) {
  var v = entrada[k];
  atual = atual.proximo(v);
  passeio += " " + atual.valor();
}

document.write(passeio);

In the test code, you'll notice the following entry:

[0, 1, 3, 1, 0, 2, 1, "lugar nenhum", 2, 2]

If you click the blue button ► Run code snippet above, it will show you this:

A A B C A A C A {erro} {erro} {erro}

Initially it was in state A (initial state). On receiving the 0, it continued in state A. Upon receiving the 1, it went to state B. From state B on receiving 3 it went to state C, and then returned to A with 1.

If an invalid entry is given, such as "lugar nenhum" of the example, then it goes into the error state, from where it never exits.

Also note that the state machine itself does not store what the current state is. The current state is kept in a variable outside the machine, by the code that is traversing it. This allows us to begin iterating from any state, not necessarily the initial state, and also allows multiple codes to iterate through the same machine into different parts without interfering with each other. Incidentally, this also allows us not to even have to store inside the machine what the initial state is, since we can start from whatever state we want. If an initial state is mandatory, just start from the same state as the example does.

    
03.12.2015 / 02:26