Finite State Machines in Computer Theory

FINITE STATE MACHINES Computer theory covers several types of abstract machines, including Finite State Machines.

FINITE STATE MACHINES Also known as Finite State Automata Also known as FSM, or State Machines

FACTS ABOUT FSM, IN GENERAL TERMS Finite State Machines are important part of intelligent systems. The most famous FSM is the Turing Machine, which can represent the logic of almost any computer algorithm. FSMs exist in everything from elevators to traffic lights; from vending machines to combination locks; from credit card number validation to complex artificial intelligence systems.

MAIN FSM CATEGORIES Acceptors Transducers Sequencers

ACCEPTORS Acceptor machines are useful in creating simple grammars. If it is possible to build an FSM to represent a grammar, it is called a regular language. A single acceptor statement in a regular language is called a regular expression. Example: When you learn a new programming language for the first time, you see a sub-language that has syntax rules. Regular expressions are used to define the syntax.

TRANSDUCERS Transducers read input files and generate a corresponding output file. These tools are used to consolidate multiple files into a single large data file. Example: Transducers convert from generic data into a game's final memory format for faster loading time.

SEQUENCERS Sequencer are FSMs are used to control a sequence of events or actions. Example Sequencers can be used to model game behavior.

SEQUENCERS STORE TWO TYPES OF INFORMATION A set of states that represent the scenarios of the game. These are the configurations that the AI will be immersed in. A set of transitions that are conditions that move a behavior from one scenario to another. These scenarios are described as the transition between two states in a directed way. FSM sequencers depict a complete network or collection of possible actions (the states) and ways to change from one action to the other.

EXAMINE A BASIC VIRTUAL PET 1. A pet isHUNGRY. 2. If you provide it with food, the pet isEATING that food, it will not be hungry anymore. 3. After eating (consuming energy calories), the pet isPLAYING. 4. Pet isHUNGRY again after burning calories all the consumed calories during play. Three states are described: isHUNGRY, isEATING, isPLAYING. Statements that describe how and when the states are altered are called transitions.

TRANSITIONS Assume the pet begins in a isHUNGRY state. If the user supplies food, the pet is in the state of isEATING. If food is consumed and the stomach is full, the pet will transition into the isPLAYING state. A pet is always in one of a finite number of states. A Transition is based on two things: the current state, and actions and conditions.

FSM: VIRTUAL PET Note: A dead pet cannot be revived.

IMPLEMENTATION Use a switch statement. Each of the cases in the switch controls a specific state and evaluates the possibility of changing states due to a specific transition in the automata being selected. Each state's activities can be divided into specific areas: a. The name of the state b. The default actions to be carried out in that state c. The calculations to perform in order to evaluate outgoing transitions

const isHUNGRY:int = 1; const isEATING:int = 2; var state:int; switch (state) { case isHUNGRY: // default actions to be carried out when the pet is hungry break; case isEATING: // default actions to be carried out when the pet is eating break; . . . }