Understanding State Machines and Their Role in Game AI

Understanding State Machines and Their Role in Game AI

This article explores the concept of state machines and their usefulness in game AI. It covers topics such as what state machines are, how they differ from other automata, and their benefits

  • Uploaded on | 3 Views
  • hredhaan hredhaan

About Understanding State Machines and Their Role in Game AI

PowerPoint presentation about 'Understanding State Machines and Their Role in Game AI'. This presentation describes the topic on This article explores the concept of state machines and their usefulness in game AI. It covers topics such as what state machines are, how they differ from other automata, and their benefits. The key topics included in this slideshow are . Download this presentation absolutely free.

Presentation Transcript

Slide1ICT2191 Topic 4 State Machines Why State Machines? What is a State Machine? Finite State Automata Finite State Machines Using FSMs Use in Game AI Advantages and Disadvantages Hierarchical State Machines Reading :  Champandard Chapters  38, 41 Links to Finite State Machines on website

Slide2Why State Machines?• You may have noticed that the control code for the reactive animats we have experimented with in labs – both in FEAR and GunTactyx – is basically just a large (possibly nested)  if-elseif-else  structure • These work okay for simple behaviour, but can become very difficult to write, read and debug when the animat needs to be more complex • A potentially better model for reactive control is some kind of  state machine  – though as we will see, it is not perfectly suited to reactive control • State machines are widely used both in games and other kinds of intelligent software, so it is well worth studying

Slide3What is a State Machine?• A state machine basically is a way of recognising or generating sequences of events in an orderly fashion • Some sequences are allowed and some are not eg telephone behaviour • Formally, we say that  transitions between the states  are triggered by a  sequence of input symbols  from a defined  alphabet . • If a sequence of symbols is allowed by the  mapping  (state transition diagram) then the sequence is recognised, else it is rejected • Alternatively, we might arrange to drive the system to generate  output symbols  from the states and/or on the transitions

Slide4ICT2194 Finite State Automata • A FSA is a directed graph of nodes connected by arcs called transitions   • FSA can be used to represent classes of state-sequences by the connectivity of the transitions. Imagine a sequence of symbols from the alphabet  {a,b,c} make the transitions • We always begin with the start state (1 – bold circle) and allow the sequence to control the transitions between states. If we end up in final acceptance state (4 - double circle), the sequence is accepted as a member of the class, (outputs a Boolean T); else, it is rejected • This FSA would accept the sequence  abccca , but not the sequence  abcbba . So the state machine can enforce a  grammar – a certain syntax for expressions in a formal language c a b c a 1 2 3 4 Final acceptance state Start state

Slide5ICT2195 Finite State Automata • Formally, a FSA may be represented by as the quadruple                         FSA =  { Σ , Q,  δ  ,F}              where                                Σ   is an input alphabet of symbols  eg {a,b,c}  Q  is a set of states  eg {1,2,3,4}    δ   is a transition function defined over  Σ  and Q  eg state diagram   F  is a subset of Q called accepting (terminal) states eg {4} • One state, q 0  , has a special meaning as the start state   • δ  is a function mapping the set of states Q and the input alphabet  Σ  onto the set of states:   f (Q, Σ ) → Q  This describes the connections in the transition network, as diagrammed by the graph in our example • δ  can also be represented as a table as shown on p.513 of the textbook

Slide6ICT2196 FSAs and Finite State Machines • Similarly, the following FSA could classify sequences of actions as belonging to a class such as  “Rocket jump”   Fire Rocket Jump Look (down) 1 2 3 4 Rocket jump Start state • Finite State Machines  are different. While a FSA may only produce one output if a sequence of transitions is recognised, a FSM may produce output symbols at each transition, or each state   • Therefore, a FSM can be used to  transduce  a sequence of input symbols into a sequence of output symbols within a certain class • One type of FSM called a  Mealy machine  outputs symbols at each transition, and are thus suitable for sequential control of actions

Slide7ICT2197 Mealy Machine • So a Mealy machine may be formalised as for FSA, but requires an alphabet of output symbols, and a function to generate them from transitions                         FSM =  { Σ , Q, Z,  δ  , λ }          where               Σ   is an input alphabet of symbols  eg {a,b,c} Q  is a set of states  eg {1,2,3,4} Z  is an output alphabet of symbols  eg {x,y,z} δ   is a transition function defined over  Σ  and Q  eg state diagram λ   is a function to determine the output symbol Z based on transitions • There is a special start state but no special terminal state • The function  λ  computes an output symbol Z for each transition given the states Q and the input symbols Z  ie  f (Q, Σ ) → Z

Slide8ICT2198 Mealy Machine b/z b/x c/z a/x 1 2 b/y c/x c/y 4 5 3 input symbol output symbol

Slide9ICT2199 Moore Machine • A Moore machine has the same definition as a Mealy machine, but the function  λ  is simpler but less powerful                          FSM = { Σ , Q, Z,  δ  , λ }          where               Σ   is an input alphabet of symbols  eg {a,b,c} Q  is a set of states  eg {1,2,3,4} Z  is an output alphabet of symbols  eg {x,y,z} δ   is a transition function defined over  Σ  and Q  eg state diagram λ   is a function associating states Q with outputs Z • The function  λ  maps states Q directly onto output symbols Z f (Q) → Z

Slide10ICT21910 Moore Machine b b c a x b c a y y z input symbol output symbol

Slide11ICT21911 Using FSMs • There are other types of FSMs too, such as Augmented Transition Networks (ATNs). These are commonly used where efficient parsing of complex patterns of symbols must be recognised, such as in the  natural language processing • Patterns of symbols such as  abccca  which belong to a class acceptable to a FSM are called  regular expressions  or  regular languages . The FSM enforces the  grammar  of a given expression/language • Such state machines may be used to  parse  regular expressions making up an  artificial language , such as Java or C. • They may also be used to parse sentences in a natural language, such as French. This could produce a  syntactical parse tree , a breakdown of the linguistic components such as noun phrase, verb phrase, articles, etc.

Slide12Use in Game AI• Although State Machines are very widely used in actual game code, they are rarely as pure as the FSA or FSM of theory. • You can use FSAs to recognise actions of another player eg observing enemy basic enemy acts, and recognising sequences as belonging to a strategy, or other high level description for decision-making • You can use FSMs to organise complex sequences of behaviour, by making the transitions be triggered by perceptual events in the world, while arranging for states to order procedures calling action functions

Slide13ICT21913 Advantages/Disadvantages of FSMs Pros • Very simple, easy to visualise • Efficient implementation is possible • Theory is well-founded and well understood, algorithms off-the-shelf • Proven popular in computer games and for control of sequences, parsing of artificial and natural languages Cons • Large state machines can become complex to debug • Computationally limited to certain class of problems (regular exp) • The design of a FSM is fixed at design-time, not dynamic • Possible procedural control problems due to sequential chaos, loss of data, and flow of control (see Chapter 38)

Slide14Designing a RCS using State Machine• Begin by listing your 1) inputs (perceptual tests – eg if(sight < 5.0)...)                                        2) states (eg avoid, wander, attack, flee, etc.)                                        3) outputs (eg hurl grenade, drop gun, eat food) • Draw a state transition diagram representing your machine • Actions are represented by procedures within the states that call basic output functions in the game eg run(), turn(), watch() etc. • Question: Where should state transitions be processed? Maybe things change while we’re inside a state procedure, so we should test for updates in there as well as ‘outside’? But this leads to redundancy and loss of performance • So, procedures within a state should be  atomic  – ie once a state has been entered, nothing may interrupt the flow of control for that action

Slide15Designing A RCS using State Machine• Ideally, a reactive system has inputs processed in parallel. Can’t do this with a state machine, whose inputs are sequences of symbols - still rely on a sequence of tests to trigger transitions • There is the question of priorities – we need to ensure that high priority tests get done first, so that their transitions can get in first • There is also the problem of loss of data, since events are happening in real time; might get two important events yet we can only process one at a time • Possible solution – keep tests inside a simplified if-elseif-else structure. Have it generate symbols which are then enqueued onto a short queue • A queue is a First In, First Out (FIF0) data structure. At each perceive-act cycle, the next item in the queue is taken off for processing the transitions to arrive at a state.

Slide16Designing A RCS using State MachineIf (test1) enqueue(o) else if (test2) enqueue(a) else if (test3) enqueue(f) else enqueue (w)       dequeue (next) process state transitions execute state procedure 2. next symbol makes transition in state machine 3. state procedures generate actions w f o a 1. perceptual test enqueues an input symbol symbols move in this direction buffer length of 4

Slide17ICT21917 Hierarchical State Machines • But how can we deal with the problem that complex state machines can be just as difficult to write, debug and modify as other designs • One approach is the concept of hierarchical state machines • Consider the machine at more than one level, with the levels themselves related by transitions • Divide the complexity into parts and have a related set of states - or even a whole nested state machine – regarded from the top level as a single state a b zoom in zoom out a b Abstract Refined

Slide18ICT21918 Summary