A few days ago, the control of some buttons is very expensive, although I know that the state machine should be used, but there is no experience, today I saw the article using a limited state machine under Linux, it mainly introduces FSMC Structuring a limited state machine, it feels not addictive, if you have the opportunity to see the design pattern similar to Action in the simulation Delphi,
Originally from:
http://www-900.ibm.com/developerWorks/cn/linux/l-fsmachine/index.shtml
Finite Automata Machine is an important cornerstone of computer science. It is often referred to as a Finite State Machine in the field of software development. It is a very wide-ranging software design mode (Design Pattern). This article describes how to build a state machine-based software system, and how to automatically generate a practical state machine framework using tools under Linux.
First, what is the state machine limited state machine is a tool for performing object behavior modeling, which mainly describes the status sequence experienced by the object in its life cycle, and how to respond to various events from the outside world. In an object-oriented software system, an object is much simpler or how complicated, it will inevitably experience a complete process from starting to create to the final die, which is often referred to as an object's lifecycle. In general, the object is impossible in its lifetime, it must be used to affect other objects by sending messages, or by accepting messages. In most cases, these news is just some simple, synchronous methods calls. For example, in a bank customer management system, a customer class (Customer) may call the getBalance () method defined in the Account class when needed. In this simple case, class Customer does not require a limited state machine to describe its own behavior, mainly because it is not dependent on a certain state in the past.
Unfortunately, not all situations will be so simple. In fact, many practical software systems must maintain one or two very critical objects, which usually have a very complex state conversion relationship, and need to perform various asynchronous events from the outside. response. For example, in a VoIP telephone system, an instance of the telephone class must be able to respond to a random call from the other party, from the user's button event, and signaling from the network. When dealing with these messages, the behavior to be taken by class Telephone is completely dependent on the state it is currently in, and thus usage the state machine will be a good choice.
The game engine is one of the most successful applications of a limited state machine. Since the design of a good state machine can be used to replace part of the artificial intelligence algorithm, each role or device in the game is likely to embed a state machine. Consider a simple object such as the city gate in the RPG game, it has four states, lock (locked), unlocked, as shown in Figure 1. When the player reaches a door in the state Locked, if he has found the key used to open the door, then he can use it transform the current state of the door to unlocked, further through the handle on the entry door. The transition is OPENED, thereby successfully entered the city.
Figure 1 Controlling the state machine of the city gate
When describing a limited state machine, status, events, conversions, and action are several basic concepts that often encounter.
State (state) means an object in its lifecycle, an object in a particular state inevitably satisfies certain conditions, performing some actions or waiting for certain events. Events refer to those who have a certain location on time and space and is meaningful to the state machine. The event usually causes a state of state, which causes the state machine to switch from one state to another. Transition refers to a relationship between two states, indicating that the object will perform a certain action in the first state, and will enter the second state when a particular condition occurs at a certain event. . Action refers to those atomic operations that can be performed in the state machine. The so-called atomic operation refers to that they cannot be interrupted by other messages in the process of running, and must be executed. Second, the manual preparation state machine is different from other common design patterns, and the programmer wants to add a part of the code for logic control if the programmer wants to join the state machine in its own software system. If the system is complicated enough, this Some of the code is realized and maintained, it is quite difficult. When implementing a finite state machine, using the Switch statement is the simplest and most direct way. The basic idea is to set a CASE branch for each state in the state machine, which is specifically used to control the state. The following code demonstrates how to use the Switch statement to implement the state machine shown in Figure 1:
Switch (state) {
// Handling the branch of the state Opened
Case (OPENED): {
// Execute action Open
Open ();
/ / Check if there is a Closedoor event
IF (closeDoor ()) {
// Current state converted to Closed
ChangeState (Closed)
}
Break;
}
/ / Handling the branch of the status closed
Case (closed): {
// Perform actions Close
CLOSE ();
/ / Check if there is OpenDoor event
IF (OpenDoor ()) {
/ / The current state is converted to OPENED
ChangeState (OPENED);
}
/ / Check if there is a LockDoor event
IF (LockDoor ()) {
// Current status Convert to Locked
Changestate (Locked);
}
Break;
}
// Handling the branch of Locked
Case (Locked): {
// Execute actions LOCK
LOCK ();
/ / Check if there is a unlockdoor event
IF (unlockdoor ()) {
// Current status is converted to unlocked
ChangeState (unlocked);
}
Break;
}
// Processing the branch of UNLOCKED
Case (unlocked): {
// Perform actions unlock
unlock ();
/ / Check if there is a LockDoor event
IF (LockDoor ()) {
// Current status Convert to Locked
ChangeState (Locked)
}
/ / Check if there is OpenDoor event
IF (OpenDoor ()) {
/ / The current state is converted to OPENED
Changesate (OPENED);
}
Break;
}
}
The limited state machine implemented using the switch statement can indeed work well, but the readability of the code is not very ideal. The main reason is that when the conversion between the implementation, check the conversion condition and the status conversion are mixed in the current State in the state. For example, when the city gate is in an Opened state, you need to call the closedoor () function in the corresponding CASE to check if it is necessary to perform status conversion. If yes, you will need to call the ChangeState () function to switch the current state to the closed. Obviously, if there is a need to check the plurality of different conversion conditions separately in each state, and the status machine needs to be switched to different states according to the check results, then such a code will be boring. From the perspective of code reconstruction, it is better to introduce both CHECKSTATECHANGE () and PerformStateChange (), specifically used to check the conversion conditions, and the various actions required to be executed when the conversion is activated. In this way, the program structure will become clearer: Switch (state) {
// Handling the branch of the state Opened
Case (OPENED): {
// Execute action Open
Open ();
/ / Check if there is an incident that excited state conversion
IF (CheckstateChange ()) {
/ / Convert the status of the state machine
PerformStateChange ();
}
Break;
}
/ / Handling the branch of the status closed
Case (closed): {
// Perform actions Close
CLOSE ();
/ / Check if there is an incident that excited state conversion
IF (CheckstateChange ()) {
/ / Convert the status of the state machine
PerformStateChange ();
}
Break;
}
// Handling the branch of Locked
Case (Locked): {
// Execute actions LOCK
LOCK ();
/ / Check if there is an incident that excited state conversion
IF (CheckstateChange ()) {
/ / Convert the status of the state machine
PerformStateChange ();
}
Break;
}
// Processing the branch of UNLOCKED
Case (unlocked): {
// Execute actions LOCK
unlock ();
/ / Check if there is an incident that excited state conversion
IF (CheckstateChange ()) {
/ / Convert the status of the state machine
PerformStateChange ();
}
Break;
}
}
But checkStatechange () and PerformStateChange () These two functions are still in the face of a very complex state, and the internal logic becomes unusually bloated, and may even be difficult to implement.
During a long period, using the Switch statement has always been the only way to implement a limited state machine, even a complex software system such as a compiler, most of them use this implementation. However, as the state machine application gradually, the construction of the state machine is getting more complicated. This method has also begun to face a variety of severe tests, the most headache is that if there is a lot of state in the state machine, or The conversion relationship between state is abnormal, then the state machine constructed simply using the Switch statement will be unmatched.
Third, the automatic generation state machine is not a very easy thing to write state machines, especially when the state machine itself is more complicated, many programmers who have experienced simply describe it " There is no creative process because they need to bring a lot of time and energy to how to manage the state of the state, not the operational logic of the program itself. As a general software design pattern, there will be some commonality between the state machines of various software systems, so people start trying to develop some tools to automatically generate the frame code of the limited state machine, and in Linux There is a very good choice - FSME (Finite State Machine Editor). Figure 2 Visualized FSME
FSME is a QT-based finite state machine tool that allows users to model the state machine required in the program by graphically, and can automatically generate state machine frame code implemented with C or Python. Here, take the state machine of the city gate in Figure 1 as an example, how to use the FSME from the state machine code required in the motion generator.
3.1 State Machine Model First Run the FSME command to start the status machine editor, then click the "New" button on the toolbar to create a new state machine. There are five basic elements for building a state machine in FSME: Events, Input, Output, State, and Transition, can be found in the tree list on the left side of the interface. Among them.
Status modeling Select the "States" item in the tree list on the left of the FSME interface, then press the INSERT key on the keyboard to insert a new state, then enter the name of the state in the "Name" text box in the lower right, and then Click the location of the status to place in the top right, and a new state is created. Use the same method to add all the status required to the state machine, as shown in Figure 3. Figure 3 Status Modeling Event Modeling Select the "events" item in the tree list on the left side of the FSME interface, then press the INSERT key on the keyboard to add a new event, then enter in the "Name" text box in the lower right. The name of the event, click the "Apply" button, a new event is created. All events needed to be added in the same way can be added as shown in Figure 4. Figure 4 Event Modeling Conversion Modeling Status Conversion is the most important part of the entire modeling process, which is used to define a state in the finite state machine how to switch to another. For example, when the state machine used to control the city gate is in an Opened state, if there is a Close event generated at this time, the current state of the state machine will switch to the closed state, such a complete process can be in the state machine model. This is available in CLOSEDOOR. A conversion will be described. To add such a conversion in FSME, first need to select "OPENED" item under "States" in the tree list on the left side of the interface, then press the INSERT button on the keyboard to add a new conversion, followed by the lower right corner "Name" text box Enter the transformed name "closedoor", enter "close" in the "Condition" text box indicating that the condition that triggers the conversion is the generation of event close, select "Closed" item in the "Target" drop-down box indicating The state machine will be switched to the closed state after the conversion occurs, and finally click the "Apply" button, a new status conversion relationship is defined, as shown in Figure 5. Use the same way to add all the transitions needed by the state machine. Figure 5 Conversion Modeling 3.2 Generating the State Machine Framework Use FSME to model not only a visual state, but more importantly, it can automatically generate the state machine framework implemented with C or Python based on the resulting model. First select the "root" item in the tree list on the left side of the FSME interface, then enter the name "doorfsm" of the state machine in the "Name" text box in the lower right corner, and select the state "Opened" from the "Initial State drop-down list" As the initialization state of the state machine, as shown in Figure 6.
Figure 6 Setting the initial attribute
After saving the state machine model as a door.fsm file, use the following command to generate a header file containing a state machine defined:
[xiaowp @ linuxgam code] $ fsmc dog.fsm -d -o doorfsm.h
Further, it can also generate a frame code containing the state machine implementation:
[xiaowp @ linuxgam code] $ fsmc dog.fsm -d -impl doorfsm.h -o doorfsm.cpp
If you want to verify the generated state machine, you only need to manually write a piece of code for testing, you can:
/ *
* Testfsm.cpp
* Test the generated state machine framework
* /
#include "doorfsm.h"
int main ()
{
Doorfsm door;
Door.a (Doorfsm :: Close);
Door.a (Doorfsm :: Lock);
Door.a (Doorfsm :: Unlock);
Door.a (doorfsm :: open);
The limited state machine is driven by an event. In the state machine frame code generated by the FSME, method A () can be used to send a corresponding event to the state machine, thereby providing the "power" required by the state machine normal operation. The state machine is responsible for maintaining an event queue inside, all arriving events will be placed in the event queue, so that they can be processed in sequence in the order of arrival. When processing each arrival event, the state machine will check if the conversion condition corresponding to the state has been satisfied according to the status of the state, and the corresponding state conversion process is activated if the words are satisfied.
Use the following command to compile the generated state machine framework and test code into an executable:
[xiaowp @ linuxgam code] $ g doorfsm.cpp testfsm.cpp -o fsm
Since the -d option is used when the state machine code is generated by the FSMC command, the generated state machine framework will contain a certain debugging information, including the activation event during each state transition in the state machine, the state before conversion, the experience The conversion, the state after conversion, etc., as shown below:
[xiaowp @ linuxgam code] $ ./fsm
Doorfsm: Event: 'Close'
Doorfsm: State: 'OPENED'
Doorfsm: Transition: 'Closedoor'
Doorfsm: New State: 'Closed'
Doorfsm: Event: 'Lock'
Doorfsm: State: 'Closed'
Doorfsm: Transition: 'LockDoor'
Doorfsm: new state: 'locked'
Doorfsm: Event: 'Unlock'
Doorfsm: State: 'Locked'
Doorfsm: Transition: 'unlockdoor'
Doorfsm: New State: 'unlocked'
Doorfsm: Event: 'Open'
Doorfsm: State: 'unlocked'
Doorfsm: Transition: 'OpenDoor'
Doorfsm: new state: 'Opened'
3.3 Customized state machine The currently available state machine has been able to respond to various events from the outside, and appropriately adjust the status of their current situation, that is, the function of the state machine engine has been implemented, the next thing to do is based on the application The specific needs are customized to join the information logic associated with the software system itself for the state machine itself. In FSME, the operation related to specific applications is called output, which is actually some virtual functions that require users to give specific implementation, and automatically generated state machine engines call them when entering or exiting a state.
Still in the state machine that controls the city gate as an example, suppose we want to add some processing logic when entering each state. The tree list on the left side of the FSME interface selects "Outputs" item, then press the INSERT key on the keyboard to add a new output, then enter the corresponding name, then click "in the" Name "text box in the lower right. APPLY button, a new output is created, as shown in Figure 7. Use the same way to add all the outputs needed for the state machine.
Figure 7 Add output
When all outputs are defined, the following can be bound to each state in the state machine. First select the appropriate state in the "State" item on the left side of the FSME interface, then select the output corresponding to this state from the "Available" list box in the lower right corner, then click "<" button to add it to "in" In the list, as shown in Figure 8. The same way can be set for all status of all status in the state machine. The same state can correspond to multiple outputs, where the output in the in list is called when entering the state, and the output in the OUT list will When the state is exited, the order of output call is consistent with the order in the IN or OUT list. Figure 8 is a status setting output
Since the state machine model is modified, we need to generate the framework code of the state machine again, but this time you don't need to add -D parameters:
[xiaowp @ linuxgam code] $ fsmc door.fsm -o doorfsm.h
[xiaowp @ linuxgam code] $ fsmc dog.fsm -d -impl doorfsm.h -o doorfsm.cpp
We add four outputs from EnterOpend, EnterClosed, Enterlocked, and EnterUnlocked, so the generated class Doorfsm will contain the following pure virtual functions:
Virtual void enteropened () = 0;
Virtual void Enterlocked () = 0;
Virtual void Enterunlocked () = 0;
Virtual void EnterClosed () = 0;
Obviously, the state frame generated at this time cannot be compiled directly, we must derive a subclass from class Doorfsm and provide specific implementation of these pure virtual functions:
/ *
* Doorfsmlogic.h
* State machine control logic header file
* /
#include "doorfsm.h"
Class Doorfsmlogic: Public Doorfsm
{
protected:
Virtual void enterpened ();
Virtual void Enterlocked ();
Virtual void Enterunlocked ();
Virtual void Enterclosed ();
}
As mentioned earlier, these functions actually represent the processing logic of the application system. As an example, we just simply output some prompt information:
/ *
* Doorfsmlogic.cpp
* State machine control logic implementation file
* /
#include "doorfsmlogic.h"
#include
Void doorfsmlogic :: enteropened ()
{
Std :: cout << "Enter Opened State." << std :: end1;
}
Void Doorfsmlogic :: Enterclosed ()
{
Std :: cout << "Enter Closed State." << std :: end1;
}
Void Doorfsmlogic :: Enterlocked ()
{
Std :: cout << "Enter Locked State." << std :: endl;
}
Void Doorfsmlogic :: Enterunlocked ()
{
Std :: cout << "Enter unlocked state." << std :: end1;
Similarly, in order to verify the generated state machine, we also need to write a test code manually:
/ *
* Testfsm.cpp
* Test state machine logic
* /
#include "doorfsmlogic.h"
int main ()
{
Doorfsmlogic door;
Door.a (Doorfsm :: Close);
Door.a (Doorfsm :: Lock);
Door.a (Doorfsm :: Unlock);
Door.a (doorfsm :: open);
}
Use the following command to compile the generated state machine framework and test code into an executable:
[xiaowp @ Linuxgam code] $ g doorfsm.cpp Doorfsmlogic.cpp testLogic.cpp -o logic
The results are as follows:
[xiaowp @ linuxgam code] $ ./logic
Enter close.
Enter Locked State.
Enter Unlocked State.
ENTER OPENED State.
This article involves code download: code.zip
4. Summary in object-oriented software systems, some objects have a very complex lifecycle model, using a limited state machine to describe the best way to describe such objects. As a software design pattern, the concept of limited state machine is not complicated, it is not difficult to achieve, but its problem is that when the model of the state machine is complex to a certain degree, it will bring difficulties in implementation and maintenance. . FSME under Linux is a visual limited state machine modeling tool, and supports automatic generation of state machine framework code, with it to build a limited state-based application based application.
Reference
From Wiki Encyclopedia http://en.wikipedia.org/wiki/finite_state_automaton, you can learn about many of the same state machine related calculation theoretical knowledge. The state machine is an important part of UML, and Robert C. Martin introduces how to use the UML language to model the state machine in his article, you can use the UML language. You can use the URL http: // www. Objectmentor.com/Resources/articles/umlfsm.pdf can find this document. FSME is Linux's next QT-based state machine modeling tool that automatically generates state machine frame code, and also supports C and Python language, through the website http://fsme.sourceforge.net/ you can learn about FSME More information and download the latest version of FSME. QFSM is also a state machine modeling tool running under Linux. It not only provides a visual state machine editor, but also enables real-time simulation of the generated state machine, through the website http://qfsm.sourceforge.net/ Learn more about QFSM.
About the author Xiao Wenpeng is a free software enthusiast, mainly engaged in the research of operating system and distributed computing environment, love Linux and Python. You can contact him through xiaowp@263.net, you can also do further communication with him on the website http://www.linuxgam.com.
