Finite State Machines (FSM)
Jason Brownlee
Jason Brownlee
We started out with a definition of finite state machine, learning that it can be used as a control technique for a system, describing states or behaviors of that system, and defining rules or conditions that govern transitions from the systems current state to another state.
Section one showed that a finite state machine is considered to be deterministic which means its actions are easily predictable. A number of extensions to finite state machines such as random selection of transitions, and fuzzy state machines shows us another common type of FSM called non-determinist where the systems actions were not as predictable, giving a better appearance of intelligence.
Next we took a close look at a simple real world implementation and learned how a rocket projectile could be modeled using FSM. This lead us to a more advanced example where we saw the behavior of a semi-intelligent monster modeled using a combination of hierarchical finite state machines and the use of goals as a primary motivator. This showed us a real implementation of a non-deterministic finite state machine where the monsters "melee attack" state was selected using a combination of inputs and a randomly generated number.
Finally we took a broader look at the Quake computer game implementation and examined the framework used to support the monsters that populate the games single player experience. We learned how a polymorphic approach was used for the execution of a monsters "current state" and that input events were also processed using polymorphism allowing any entity finite state machine’s actions to directly effect entities. We saw how a simple framework that supported a variety of state machines could be considered a simple multi-agent system where each individual state machine simple had to plug in relevant monster specific code into the framework.
Finite state machines are a simple and effective artificial intelligence technique for controlling a system and providing the appearance of intelligence. We learned that that the perceived appearance of intelligence is more important than actual intelligence, and that finite state machines are able to provide this perception. This was proven through practical analysis of a computer game, which is a very unforgiving domain when it comes to quality of both product and game playing experience.
[1] D. Gibson, Finite State Machines - Making simple work of complex functions, SPLat Control Pty. Ltd [http://www.microconsultants.com/tips/fsm/fsmartcl.htm], 1999
[2] A. E. Collins, Evaluating the performance of AI techniques on the domain of computer games, [www.dcs.shef.ac.uk/~u8aec/com301], 2001
[3] B. Bruegge & a. H. Dutoit, Object-Oriented Software Engineering - Conquering Complex and Changing Systems, Prentice Hall, 2000
[4] A.Dix, J. Finlay, G. Abowd, R. Beale, Human-Computer Interaction 2nd Edition, Prentice Hall, 1998
[5] P.K. Winston, Artificial Intelligence, Addison-Wesley, 1993
[6] id Software, website: http://www.idsoftware.com
[7] Quake, a computer game by id Software, website: http://www.idsoftware.com/games/quake/quake/
[8] GNU General Public License (GPL): http://www.gnu.org/copyleft/gpl.html
[9] Quake source code released under the GPL, links for engine and game code:
Remember you can visit the Message Store to discuss this tutorial. Comments are always welcome!. There are already replies in the thread, why not join in?