|
|
| 04/11/2003 | Home | Articles | Reviews | Interviews | Glossary | Features | Discussions | Search | Contribute | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Home > Articles > Gaming > Beginner
IntroductionThis tutorial is aimed at explaining, providing tips and techniques, and gives an example to demonstrate the use and purpose of Finite State Machines (which will now be abbreviated FSM). The illustrations and example take use of the Unified Modeling Language (abbreviated UML) because it is a language best suited for it. Although understanding UML is not a requirement for this tutorial or FSMs in general, it is definitely a language you should get to know.Feel free to review the glossary of terms used within this tutorial. It is best that you know what I am talking about before or while you read the content.
Applications of FSMFSMs have been used broadly in the video game industry. Since ID Software released the source code to the Quake and Quake 2 projects, people have noticed that the movement, defensive, and offensive strategies of the bots were controlled by a simple FSM. ID is not the only company to take advantage of this either. The latest games like Warcraft III take advantage of complex FSM systems to control the AI. Chat dialogs where the user is prompt with choices can also be ran by FSMs.Aside from controlling NPCs, bots, dialog, and environmental conditions within video games, FSMs also have a large role outside of the video game industry. For example, cars, airplanes, and robotics (machinery) have complex FSMs. You could even say websites have a FSM. Websites that offer menus for you to traverse other detailed sections of the website act much like a FSM does with transitions between states.
What is a FSM?If you ever seen a flowchart before, you can think of a FSM as the same thing. It has a set of states that follow a certain path. A state has transitions to other states, which is caused by events or actions within a state. Here is a real world example.You are in the kitchen (state) and you felt a sudden urge to drink water. You then decide to walk over to the cupboard and grab a glass. This is an event (walk to cupboard) and you are now in a new state with new options available to you. You then open the cupboard (action) and grab a glass (action). With the glass, you walk over to the sink (event) and turn on the tap (action). Water into poured into the glass (event) and you then drink it (action). So in a nutshell, an event leads you to a state in which you perform an action or several actions (though you do not always have to perform an action). So when you walk to the cupboard, that leads you to the state "At Cupboard" where the typical action is "Open Cupboard". To better demonstrate a FSM, a robot example will be used throughout this tutorial.
Example - RoboticsWith all things in life, careful planning is a must, especially with a FSM. The first step to developing a FSM is to list all the known entities in your problem. Let us start with the robot.
Figure 1.1: Bender, our robot Here is Bender, as you may recognize him from Futurama. Bender would like to turn on and off, walk, run, raise and lower its arms, turn its head, and talk. There are many other features left to be desired, like ducking, jumping, repairing itself, reacting to environments, give it emotions, etc… As you can see, the list goes on and this is quite normal in a FSM. Keep in mind however, as the term finite implies you will need to limit the scope of the problem to a finite set of entities. Since we are limited by time so for the purpose of this tutorial, a subset of entities is chosen. Given these entities, we should construct a table listing all the possible events and states associated with them.
When developing FSMs, you should expect to see an even greater list of events and states to support. As you will see later, as logic errors are common in programming, event errors are common in FSMs. Just before we move on, I would like to make a few notes about the selected states above. States do not have multiple roles. Every time Bender is turned on, the same flow of direction will always occur. If at any time in your projects there is a breech in that flow, it would need to be fixed. This is one of the problems with FSMs because sooner or later someone is going to pick up the pattern. Ways around this would be to add more events to a given situation or randomize the actions performed. Secondly, states are unique. No two states should have the same reaction to a specified event. For example, having Bender "speak" and "shout" are synonymous in terms of speech; therefore we eliminate one while keeping the other and supplement arguments to dictate how a certain text is pronounced (be it calm, yelling, stutter, etc…). Thirdly, state transitions do not normally branch. By branch I mean through the use of conditional statements. For example, Bender has a set of movement options. Such movements can be decided via IF/THEN statements, however it is best to avoid that since the purpose behind states is to replace the need for IF/THEN statements with events. Although states are flexible and do allow such conditional operations, it is always best to avoid them. It reduces complexity and lessens the chance for logic errors. Now that we have a list of events and states, it is best to draw them out. When you visually see your model, it is easier to pick out where things may go wrong or where things could use improvements.
Figure 1.2: Sample state diagram of Bender This model representation is actually wrong. You should note that in a state, you perform a certain action and when you leave that state, the action is no longer performed. In this model, we can only have one state at a time with no transition between them. It is possible for Bender to both walk and then run, so there should be a link between those two states. Since there are only a few movement states, the amount of transitions won't be all that bad. If you were to support a much larger base of states, then you will notice a massive set of transitions between them, undoubtedly creating confusion. Unfortunately there is no way around this. Diagrammatically speaking, you could specify a cleaner set of transitions, but ultimately when you program the states you will still have a complex amount of transitions to support. Here is another way to represent multiple states a bit cleaner.
Figure 1.3. Simplified State Model Here we assign a new state Activity that holds all the activities Bender can do with transitions to itself. This also allows for multiple events to run in parallel so you could walk and talk at the same time. Inevitably, the programming will still be as complex. Take note that on events like talk, you would set up timers to display the text for X amount of seconds. When the timer expires, you would stop talking. Now that we have a state diagram, we need to examine it further and construct a state table. A state table is nothing more than a table listing all the states, the actions to get to them, and the reaction performed by them. For example, when Bender turns on, it puts itself in the turned on state. From here, it is allowed to conduct various movements and shut itself down. When in the activity state, it cannot directly shut itself down. So the state table illustrates to us what and when can Bender perform certain actions.
As you see, defining a complete FSM is an extremely long process and we have not even done any coding yet! The state table is left incomplete as the number of events and actions are quite large, but there should be enough presented to illustrate the idea. Putting it all together, the state diagram helps illustrate what the functionality is like and the state table defines the types of inputs to those functions and the expected outputs. So, with a complete state diagram and state table, you have the blueprints to develop your FSM.
Example - CodeKnowing how to set yourself up for a FSM is one thing, going about programming it is another. There are many ways to program a FSM, so the method I present here is one that I just prefer. I tried to comment the code as best as possible so hopefully my coding style won't be a strain on your eyes =)How The Code Works:
The code does not make use of any conventional programming style. There are no switch statements and there are no IF/THEN expressions. Everything in the FSM is controlled by sending the correct events down the pipeline. After that, the FSM will choose the correct course based on how you configured your states. Also, I have not placed any fancy reactions in the code. I simply want to demonstrate how state transitions occur and provide a clean and elegant interface to handling FSMs. Feel free to add new features and reactions to them.
Code was developed in Visual Studio 7.0 with C++
ConclusionFinite State Machines are widely used in video games to supplement AI given its easy structure and maintenance. When given the problem that requires finite number of solutions, FSMs are definitely an easy method to approach. Just remember the format to help you design and develop FSMs.
1) Review the problem. Write down all the entities involved
GlossaryHere is a list of terminology used throughout the tutorial. If any of these seem unfamiliar to you, it would be helpful to know what they mean before continuing on with the tutorial. They are as follows:
3/10/03: UpdateCypher has ported the FSM code to both Java and Rebol.
Last Updated: 03/10/2003 Article content copyright © Nathaniel Meyer, 2003.
|
|
Print
E-mail description