Clever Geek Handbook

Implémentation concise de machines à états finis dans Matlab, Octave, C

Pertinence



Les machines à états finis (fsm) sont utiles. Ils peuvent être particulièrement demandés dans des environnements où, en principe, il n'y a pas de multitâche développé (par exemple, dans Octave, qui est en grande partie un analogue gratuit de Matlab) ou dans des programmes pour microcontrôleurs où RTOS n'est pas utilisé pour une raison quelconque. Jusqu'à récemment, je n'étais pas en mesure de décrire succinctement la machine à états, même si je voulais vraiment le faire. Laconique, c'est-à-dire sans eau, sans créer de classes inutiles, de structures de données, etc. Maintenant, cela semble avoir fonctionné et je suis pressé de partager ma trouvaille. J'ai peut-être inventé le vélo, mais il est également possible que quelqu'un trouve un tel vélo utile.



Informations initiales



La machine d'état est spécifiée :



  • ensemble d'états
  • ensemble d'événements
  • une table de transition (c'est-à-dire dans quel état pour quel événement ce qui est fait et dans quel nouvel état la transition est faite)


L'objectif qui se tenait devant moi



Il y a un langage impératif, je vais considérer Octave, mais ça peut être Matlab et C, par exemple. Ce langage prend en charge :



  • les fonctions
  • pointeurs de fonction
  • ce que les langages impératifs supportent généralement (boucles, instructions conditionnelles, etc.)


J'aimerais que les concepts de base du langage (fonctions, structures de données, tableaux ou autre) correspondent d'une manière ou d'une autre à ce qui est nécessaire lors de la mise en œuvre d'un FSM. Le bénéfice est que :



  • le code sera auto-documenté
  • Doxygen ou d'autres utilitaires d'analyse de code et de génération de documentation de code offriront des avantages supplémentaires.


Description de l'idée



  • Le comportement au sein de l'état doit être décrit par une fonction. Par conséquent, une fonction est un bon candidat pour qu'un nom corresponde à un état.
  • L'événement doit également être détecté par la fonction, donc, pour les noms d'événements, vous pouvez également utiliser les fonctions
  • La table de transition peut être spécifiée soit sous la forme d'une structure de données, soit sous la forme d'expressions switch/case au sein des états


Quel est le problème avec la définition de la table de saut en tant que structure de données ?



  • La table peut être assez grande et complexe. Dans ce cas, la structure de données cessera de tenir dans l'écran et le support d'une telle table ne sera pas si pratique.
  • La structure de données nécessite une sorte d'objet en mémoire. C'est un inconvénient supplémentaire.
  • La structure de données nécessite sa construction spéciale (très probablement étape par étape) - cela rend la structure du programme plus belle, mais il ne sera pas si pratique d'analyser une telle machine à états plus tard.


Par conséquent, ici, j'utiliserai une instruction switch / case.



La seule structure de données sera une variable où sera stocké l'état de la machine.

Les états eux-mêmes seront identifiés par les gestionnaires de fonctions qui géreront le comportement de la machine dans cet état. Par example: 



function [new_state  data] = state_idle(data)
    if data.block_index == 10
        new_state = @state_stop;
    else
        % do something
        data.block_index = data.block_index + 1;
        printf('block_index = %d\n', data.block_index);
    end
end

function [new_state data] = state_stop(data)
    % set break flag
    data.stop= 1;
end
fsm_state = @state_idle;
data = struct();
data.block_index = 0;
data.stop = 0;

while (1)
    [fsm_state data] = fsm_state(data)
    if data.stop
        break;
    end
end


Dans ce code, toute l'idée, en fait, est décrite. En C, au lieu d'un gestionnaire de fonction, il y aura un pointeur de fonction, tout le reste reste le même.



Exemple de la vie réelle



A titre d'exemple, j'ai implémenté le jeu Life de John Conway sur Octave . Si vous le configurez en mode 100 x 100, il simulera le travail de 10 000 machines d'état et en même temps, il fonctionnera assez efficacement. Dans sa forme la plus simple (pas d'événements), le code du jeu ressemble à ceci : 



%    'alive',   
%    
% ,      ./fsm_life/state_alive.m
function [new_state] = state_alive(neighbours)
    alive_count = sum(sum(cellfun(@(x)x == @state_alive, neighbours)));
    alive_count -= 1;
    if (alive_count == 2) || (alive_count == 3)
        new_state = @state_alive;
    else
        new_state = @state_dead;
    end
end

%    'dead',   
%    
% ,      ./fsm_life/state_dead.m
function [new_state] = state_dead(neighbours)
    alive_count = sum(sum(cellfun(@(x)x == @state_alive, neighbours)));
    
    if (alive_count == 3)
        new_state = @state_alive;
    else
        new_state = @state_dead;
    end
end


%  .
% ,      ./life.m
addpath('fsm_life');   %       
debug_on_error(1);   %   -  -     

%   30  30
size_x = 30;
size_y = 30;

%     ,    30%  
init_alive_percentage = 30;

%   ( //).
% initialization selection:
%init = 'random';
%init = 'cycle';
init = 'glider';

%   -  cell-array,   function handlers   
%    
field = cell(size_y, size_x);
%     " "
[field{:}] = deal(@state_dead);

%     ,  "",  .
switch (init)
case 'random'
    init_alive_count = round((size_x * size_y) * init_alive_percentage / 100);

    for n=(1:init_alive_count)
        x = floor((size_x-0.0000001)*rand())+1;
        y = floor((size_y-0.0000001)*rand())+1;
        field{y,x} = @state_alive;
    end
case 'cycle'
    field{2,1} = @state_alive;
    field{2,2} = @state_alive;
    field{2,3} = @state_alive;
case 'glider'
    field{1,3} = @state_alive;
    field{2,3} = @state_alive;
    field{3,3} = @state_alive;
    field{3,2} = @state_alive;
    field{2,1} = @state_alive;
end

%      
printf("Initial distribution:\n");
cellfun(@(x)x == @state_alive, field)

% simulation
for step = (1:100)

    %        .
    field_new = cell(size(field));

    %    
    for x=(1:size_x)
        for y=(1:size_y)

            %   ,     
            x_min = max(x-1, 1);
            x_max = min(x+1, size_x);
            y_min = max(y-1, 1);
            y_max = min(y+1, size_y);

            %       
            neighbours = field(y_min:y_max, x_min:x_max);

            %    :
            %    ,   . 
            field_new{y,x} = field{y,x}(neighbours);
        end
    end

    %       
    field = field_new;

    %      
    printf('Distribution after step %d\n', step );
    cellfun(@(x)x == @state_alive, field)

    %      
    figure(1); imagesc(cellfun(@(x)x == @state_alive, field));

    %         Ctrl+C
    pause(0.05);
end


Si vous voulez plus d'auto-documentation et une définition explicite des événements, alors 3 fonctions supplémentaires responsables des événements seront ajoutées aux deux fonctions responsables des états : 



function event = event_die(neighbours)
    alive_count = sum(sum(cellfun(@(x)x == @state_alive, neighbours)));
    alive_count -= 1;
    if (alive_count == 2) || (alive_count == 3)
        event = '';
    else
        event = 'die';
    end
end

function event = event_spawn(neighbours)
    alive_count = sum(sum(cellfun(@(x)x == @state_alive, neighbours)));
    if (alive_count == 3)
        event = 'spawn';
    else
        event = '';
    end
end

function event = event_survive(neighbours)
    alive_count = sum(sum(cellfun(@(x)x == @state_alive, neighbours)));
    alive_count -= 1;
    if (alive_count == 2) || (alive_count == 3)
        event = 'survive';
    else
        event = '';
    end
end

function [new_state] = state_alive(neighbours)
    event = '';
    event = [event, event_die(neighbours)];
    event = [event, event_survive(neighbours)];

    switch event
    case 'die'
        new_state = @state_dead;
    case 'survive'
        new_state = @state_alive;
    otherwise
        msg = sprintf('Unknown event: %s\n', event);
        error(msg);
    end
end

function [new_state] = state_dead(neighbours)
    
    event = event_spawn(neighbours);
    
    switch event
    case 'spawn'
        new_state = @state_alive;
    case ''
        new_state = @state_dead;
    otherwise
        msg = sprintf('Unknown event: %s\n', event);
        error(msg);
    end
end


Le script principal dans ce cas restera le même.



Voici un exemple de la façon dont le planeur rampe du coin supérieur gauche au coin inférieur droit : J'ai

image



posté les sources sur le github : https://github.com/tminnigaliev/octave_life



Upd. : Malgré le fait que j'ai déclaré que cela idée peut également être implémentée au moyen du langage C, la mise en œuvre peut ne pas être si simple. S'il est implémenté en C, alors l'état sera représenté par le type de données T, qui sera un pointeur vers une fonction qui prend un tableau (ou un pointeur vers un tableau) d'éléments de type T et renvoie un type T. C'est plus facile à dire qu'à écrire. Néanmoins, j'essaierai d'implémenter quelque chose comme ça plus tard et écrirai un autre article où je décrirai l'implémentation C.


More articles:


All Articles