Finate State Machines in Games - Lehigh CSE

Finate State Machines in Games - Lehigh CSE

Reminder Next class (Tuesday) , you should have formed groups and select a topic for presentation among: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) Real-Time Strategy games (Luis Villegas, Dulmovits, Alexander J): I: 8.2, 8.3, II: 7.5, 7.6, III: 4.7, 6.7; IV: 4.1, History of RTS games? - informed Squad tactics (John Formica, Matt Mitchell, David Pennenga ): I: 5.3, 5.4, 5.5. 5.6; II: 3.3, - informed Scripting languages () I: Section 10 (7 chapters) First Person Shooters (Michael Caffrey, Shamus Field, Jon Hardy): I: 8.1, 8.4; II: 7.1, II: 5.2, 5.3, history of FPS? - informed

Racing games () I: 9.1, 9.2, 9.3, 9.4, II: 8.1, 8.2, Role Playing Games (Josh Westbrook, Ethan Harman) I: 8.5, history of RPGs? IV: Stop Getting Side-Tracked by Side-Quests, I: Level-Of-Detail AI for a Large Role-Playing Game, I: A Dynamic Reputation System Based on Event Knowledge - informed Story line, drama (): IV: Implementing Story-Driven Games with the Aid of Dynamical Policy Models, IV: Dialogue Managers, Sport Games (Daniel Phillips, Dan Ruthrauff) I: 9.7, II: 8.4, 8.5, - informed Individual NPC behavior (Daniel Phang, Sui Ying Teoh): I: 2.4, 8.6, 9.6, II: 3.1, 3.2; IV: 5.6, http ://www.aaai.org/Papers/AIIDE/2008/AIIDE08-025.pdf, - informed Player Modeling () IV 7.3, IV: Player Modeling for Interactive Storytelling: A Practical Approach, III: Preference-Based Player Modeling, II: Player Modeling for Adaptive Games, http://www.gamegrep.com/top_list/14266-top_15_best_video_game_storylines_ever/, Dynamic Game Balancing: An Evaluation of User Satisfaction Gustavo Andrade, Geber Ramalho, and Alex Sandro Gomes, Universidade Federal de Pernambuco; Vincent Corruble, Universit Paris 6 Map, World, Wall generation () Most Popular Games Genres Adventure games: Solving puzzles Finding clues E.g., through conversations with NPCs Classic: The Longest Journey (

http://www.youtube.com/watch?v=8XrkGztFr-0) Role Playing Games (RPG) Player assumes fictional roles through Avatars Avatar acquires skills by performing tasks/actions Levels indicate the progress of the avatar Classic: Diablo 2: http://www.youtube.com/watch?v=vl9C8RTu3Oc Most Popular Games Genres (II) Strategy games: resource gathering, managing economy, technology research Real-Time Strategy (RTS) Simultaneous actions (classic: Command & Conquer) Turn-based Games (TBS) Take turns (classic: Civilization II) Sport Games Simulation of actual sport games (classic: FIFA series) Games of chance Outcome highly influenced by a stochastic environment First-person shooter

Controlling avatar in first-person camera view (classic: Duke Nukem) Most Popular Games Genres (III) And many sub-genres Combine and/or enhance main genres Massive Multiplayer Online RPG (MMORPG) RPGs with multiple other players in pervasive worlds Stealth FPS FPS emphasizing stealth over shooting RTS/RPG Combine both aspects (Warcraft III) RTS/FPS Combine both aspects (classic: Battlezone) Finite State Machines in Games http://www.youtube.com/watch?v=3yxoEr5qeEk Original slides by: Jarret Raim FSMs in Theory Simple theoretical construct

Set of states (S) Input signals (I) Transitional function (s,i) A way of denoting how an NPC can change its state over time. FSMs in Practice Each state represents some desired behavior. The transition resides across all states. Each state knows how to transition to other states. Accepting states are considered to be the end of execution for an FSM. Example of an accepting state in a game? Input to the FSM continues as long it has not reached an accepting state. FSMs in Games

Character AI can be modeled as a sequence of mental states. World events can force a change in state. The mental model is easy to grasp, even for non-programmers This is important! Monster In Sight Gather Treasure Flee No Monster Monster Dead Fight

Cornered FSM Example ~E Attack E,~D ~S E S ~E D E: enemy in sight S: hear a sound D: dead E

D E Inspect States Spawn D Patrol D S Events E: see an enemy S: hear a sound D: die Action performed On each transition On each update in

some states (e.g. attack) But it gets even easier (eventon-map) If player walks here then Spawn Mephisto Put 3 orcs here Starting place of player Even at a Larger Scale If player cross here Then declare war Ok Let Us Construct One Finite State Machine

Lets program High Priestess Mar'li Here is she in action Step 1: list states and events Step 2: Construct the Finite State Machine FSM Implementation - Code Simplest method After an action, the state might change. Requires a recompile for changes No pluggable AI Not accessible to nonprogrammers No set structure Can be a bottleneck. void RunLogic( int *state ) { switch( *state ) { case 0: //Wander Wander(); if( SeeEnemy() ) *state = 1;

if( Dead() ) *state = 2; break; case 1: //Attack Attack(); *state = 0; if( Dead() ) *state = 2; break; case 3: //Dead SlowlyRot() break; } FSM Implementation - Macros Forces structure Shallow learning curve More readable Removes clutter by using macros. Easily debugged

Allows focus on important code. bool MyStateMachine::States( StateMachin eEvent event, int state ); { BeginStateMachine State(0) OnUpdate Wander(); if( SeeEnemy() ) SetState(1); if( Dead() ) SetState(2); State(1) OnUpdate Attack(); SetState(0); if( Dead() ) SetState(2); State(2) OnUpdate RotSlowly(); EndStateMachine

} FSM Implementation Scripts Developer creates scripting language to control AI. Script is translated to C++ or bytecode. Requires a vocabulary for interacting with the game engine. A glue layer must connect scripting vocabulary to game engine internals. Allows pluggable AI modules, even after the game has been released. FSM Processing Interpreted Simple and easy to debug. Inefficient since FSMs are always evaluated. Interpreted languages were the rage in AI Event Driven Model FSM registers which events it is interested in. Requires complex Observer model in engine. Hard to balance granularity of event model.

Multithreaded Each FSM assigned its own thread. Requires thread-safe communication. Conceptually elegant. Difficult to debug.. Game Engine Interfacing Simple hard coded approach Allows arbitrary parameterization Requires full recompile Engine AI Function pointers

Pointers are stored in a singleton or global Implementation in Dynamiclink library Allows for pluggable AI. E.g., The Tielt project Data driven An interface must provide glue from engine to script engine. Engine DLL AI Byte Code S. Interface Compiler Engine

AI Optimization Time Management Helps manage time spent in processing FSMs. Scheduled Processing Assigns a priority that decides how often that particular FSM is evaluated. Results in uneven (unpredictable) CPU usage by the AI subsystem. Can be mitigated using a load balancing algorithm. Time Bounded Places a hard time bound on CPU usage. Project # 1 will let you experience this More complex: interruptible FSMs Optimization Level of Detail Its ok to cut corners if the user wont notice. Each level of detail will require programmer time.

The selection of which level to execute can be difficult. Many decisions cannot be approximated. FSM Extensions Extending States Adding onEnter() and onExit() states can help handle state changes gracefully. Example of when to use it in games? Stack Based FSMs Allows an AI to switch states, then return to a previous state. Gives the AI memory More realistic behavior Hierarchical FSMs FSM Example ~S ~E Attack

E,~D Inspect ~E E ~S E S ~E D S E D D E

Attack-P E,S,~D Spawn D Patrol D S Original version doesnt remember what the previous state was. One solution is to add another state to remember if you heard a sound before attacking. FSM Example

Attack-ES E,-D,S,-L S Attack-E E,-D,-S,-L -S L L Retreat-S -E,-D,S,L -L E -E Wander-L E E

-E,-D,-S,L L -L -L E Worst case: Each extra state variable can add 2n extra states n = number of existing states Retreat-ES and remembering N E,-D,S,L actions into the L -S -L

-E Wander Retreat-E E,-D,-S,L -E E -E,-D,-S,-L pass is not possible! (finite automata vs. pushdown automata) D D D D Spawn D

(-E,-S,-L) S Chase -E,-D,S,-L Using a stack allows to remember without the extra states. Stack FSM Thief 3 Stack allows AI to move back and forth between states. Leads to more realistic behavior without increasing FSM complexity.

Hierarchical FSMs Expand a state into its own sub-FSM Some events move you around the same level in the hierarchy, some move you up a level When entering a state, have to choose a state for its child in the hierarchy Set a default, and always go to that Random choice Depends on the nature of the behavior Hierarchical FSM Example Wander Attack ~E E Pick-up Powerup

~S Chase S Start Turn Right D Spawn ~E Go-through Door Note: This is not a complete FSM All links between top level states still exist Need more states for wander

Markov Models : An instance of NonDeterministic FSMs Attack Approach .3 Aim & Slide Right & Shoot Aim & Slide Left & Shoot .3 .4 .3 .3 Start

.4 Aim & Jump & Shoot Selects transition based on probability distributions Have multiple transitions for the same (state,input) pair Adds variety to actions Label each with a probability that it will be taken Probabilities can be learned (Reinforcement Learning) More FSM Extensions Fuzzy State Machines Degrees of truth allow

multiple FSMs to contribute to character actions. Multiple FSMs High level FSM coordinates several smaller FSMs. Polymorphic FSMs Allows common behavior to be shared. Soldier -> German -> Machine Gunner Polymorphic FSM Example Soldier Rifleman Machine Gunner Officer

American German American German American German British Soviet British Soviet British

Soviet Debugging FSMs Offline Debugging Logging Verbosity Levels Online Debugging Graphical representation is modified based on AI state Command line to modify AI behavior on the fly. Case Study: Robocode First determine what states are needed Attack, Evade, Search, etc. Code up the FSM

transition function. Include an error state that is noticeable. Setup debugging. Verbosity levels are a must. Case Study: Robocode Defend Search Implement and test each state separately. A test bot AI might help test single behaviors. (see Target bot) Attack

Defense and Firing Power Enable your bot to dodge incoming fire. Every 20 ticks reverse direction. Adds a circle strafe. Selects a bullet power based on our distance away from the target void doMovement() { if (getTime()%20 == 0) { direction *= -1; setAhead(direction*300); } setTurnRightRadians( t.bearing + (PI/2)); }

void doFirePower() { firePower = 400/target.distance; } targe Searching Reducing the scanner arc allows you to fire faster. If a target hasnt been seen recently, spin. Scan where the target is. Wobble to make sure to find the target. void doScanner() { double radarOffset; if(getTime() - target.ctime > 4) radarOffset = 360;

else radarOffset = getRadarHeadingRadians() absbearing(getX(),getY(),targ et.x,target.y); if( radarOffset < 0 ) radarOffset -= PI/8; else radarOffset += PI/8; setTurnRadarLeftRadians(Normalis eBearing(radarOffset)); } References AI Game Programming Wisdom University of Wisconsin presentation Robocode Website

Recently Viewed Presentations

  • Mendelian Genetics Notes

    Mendelian Genetics Notes

    Mendel's Experiments. Studied the 7 characteristics of pea plants. Round vs. wrinkled peas, yellow vs. green peas, white vs. grey seed coats, inflated vs. constricted pods, yellow vs. green pod color, tall vs. short plants, flowers on sides vs. flowers...
  • University Disabled Students Experiences of Learning, Teaching and

    University Disabled Students Experiences of Learning, Teaching and

    Disability legislation may prove to be a Trojan horse and in a decade, the learning experiences of all students may be the subject of greater negotiation" (Healey 2003: 26). LTA experiences Far fewer adjustments for disabled students would be required...
  • Interconnect and Packaging Chapter 2: Transmission Line Parameters

    Interconnect and Packaging Chapter 2: Transmission Line Parameters

    Arial SimSun Book Antiqua 01090290 1_01090290 Interconnect and Packaging Chapter 2: Transmission Line Parameters Outline Causality Transmission Lines for Digital Systems Transmission Line Structures Time Domain Reflectometer TDR Wave Propagation Wave Propagation LC Measurement Round-Wire Internal RL Internal Impedance of...
  • Summarizing - Hollidaysburg Area School District

    Summarizing - Hollidaysburg Area School District

    Summarizing Using Your Own Words… Summarizing, Paraphrasing, and Quoting You can borrow from the works of other writers as you research. As a good writer, you should summarize, paraphrase and quote to blend source materials in with your own.
  • Alternative Power Options Generation, Storage, Distribution, Safety, &

    Alternative Power Options Generation, Storage, Distribution, Safety, &

    This will our example system #1. High Power Fixed Standalone - PV total of 100-500 watts, 10-20 batteries, AC & genset backup charging, with inverters as needed. Example system #2. High Power Fixed Grid Interconnected - 1kw+ PV, high end...
  • Building Confidence &amp; Community in the High-Engagement Classroom

    Building Confidence & Community in the High-Engagement Classroom

    from "Towards a Vision of Accelerated Curriculum and Pedagogy," by Katie Hern and Myra Snell, founders of the California Acceleration Project: "Many students come into the community college classroom with a history of uneven, fraught, and even traumatic educational experiences...
  • The Appeal to authority

    The Appeal to authority

    Religious moderates in Society argued for the stripping of ornamentation and emotives of the English language (254). They desired simplified language. "Language, it was urged, should be geared for dispassionate, rational - literally prosaic - discourse" (254). Desire for a...
  • Embracing Technology and the Millennials that Love It!

    Embracing Technology and the Millennials that Love It!

    73% of millennials prefer email as primary mode of communication, compared to phone calls or in-person meetings, due to speed, trackability, and ability to grant users forethought when speaking....Businesses have to adopt new practices to connect or we will lose!...