AN OBJECT-ORIENTED APPROACH FOR HIERARCHICAL STATE MACHINES

Please download to get full document.

View again

of 7
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Film

Published:

Views: 0 | Pages: 7

Extension: PDF | Download: 0

Share
Related documents
Description
AN OBJECT-ORIENTED APPROACH FOR HIERARCHICAL STATE MACHINES WILLIAM MALLOUK 1 ESTEBAN CLUA 2 1 Wet Productions LLC 2 Departamento de Informática PUC-Rio / VisionLab
Transcript
AN OBJECT-ORIENTED APPROACH FOR HIERARCHICAL STATE MACHINES WILLIAM MALLOUK 1 ESTEBAN CLUA 2 1 Wet Productions LLC 2 Departamento de Informática PUC-Rio / VisionLab Abstract Finite Machines have been widely used as a tool for developing video games, especially as pertains to solving problems related to AI, input handling, and game progression. In this paper, we introduce a practical technique that can highly improve the productivity of development of Finite Machines in video games. This technique consists of adapting concepts of OOP for use with Hierarchical Finite Machines in an entirely visual system. An open source implementation of the technique that can be used as middleware in most games is also provided. Keywords: Artificial Intelligence, Hierarchical Machines 1 Introduction FSM (Finite Machines) is a technique that appears in many different forms and is used in major game titles such as Quake, Fifa Soccer, and Warcraft. In fact, FSM is the most popular approach for AI algorithms used in games [4]. In this paper, we demonstrate how Hierarchical Finite Machines can be combined with Object-Oriented Programming techniques to obtain productivity and HFSM reuse. We also provide an open-source implementation of the technique as middleware that can be used in nearly any game. 1.1 Previous Works Although our approach to Finite Machines is original, many of the ideas were inspired by [4] and [5]. Particularly, the implementation of the visual system for designing state machines is based on the ideas introduced in [2]. Our visual state machine XML parser, VDX2HSM, is an improved version of the tool created by the referenced author. See section seven of this article for more details on it. 2 Hierarchical Finite Machines In Games We recall from [1] and [4] the idea of Finite Machines and Hierarchical Machines as used in games. An HFSM is a FSM in which states can be decomposed into other FSMs [4], as depicted in Figure 1. KeyPress : KeyRelease : condition Composite Walk KeyPress : A KeyRelease : A KeyPress : Run Sub-s of Figure 1. Hierarchical Finite Machine In the figure above, the decomposition of the state is shown. In HFSMs, each sub-state is capable of being a composite state as well, forming a tree of state machines. This approach is convenient, especially when the state machine being modeled is huge and, therefore, presents the potential for confusing representation. 3 Object Oriented Approach This paper introduces an hybrid system, where HFSMs are merged with concepts of OOP to create the Object-Oriented Hierarchical Machines technique. Particularly, we adapted the concepts of Class Hierarchy, Inheritance, Class, Method, and Data Abstraction for use with HFSMs in an entirely visual system. In this paper, we assume that the reader is familiar with these concepts. Other related works are presented in [1] and [6]. 4 Object Oriented Hierarchical Machines Object-Oriented Hierarchical Machines, also known by the acronym, OOHSM, the result of combining Hierarchical Machines with the Object-Oriented Programming concepts mentioned above. The OOHSM technique consists of the following elements combined with each other: Machine, Base Machine, Sub Machine, Abstract, Abstract Machine, and Concrete Machine. We will see that each of these elements is analogous to an OOP element as we define them and provide examples of use in the next subsections. To simplify the task of defining these elements, we have used properties of the UML (Unified Modeling Language) class diagram notation [7] because of its semiotic. 4.1 Machine Using our new notation, we visually redefined state machines. Figure 2 contains a state machine with two states represented using our new notation. For the sake of simplicity, we can omit the details of the sub-states of a composite state, as was done with the composite state of figure 3. Note that a state machine can have as many composite states as necessary. CharacterBehavior KeyPress : Backward KeyRelease : Backward Backwards Figure 2. A Machine CharacterBehavior KeyPress : KeyRelease : Hit Water Hit Ground Figure 3. Composite with omited Sub-s 4.2 Base Machine and Sub Machine In OOHSM, state machines can inherit properties from other state machines, forming an inheritance hierarchy that is similar and analogous to OOP inheritance. In Figure 4, the state machine CharacterBehavior is a supermachine of PaladinBehavior, and the state machine PaladinBehavior is a base machine of CharacterBehavior. The difference between sub-machines and sub-states should be clear. Each composite state has one or more sub-states, and each state machine can have one or more sub-machines. From the definitions above, it becomes aparent that a state machine is analog to a class, and that a composite state is analog to a method. In some programming languages we can also compare an object with OOHSM instance, which is the terminology that will be used in the implementation of this work, which will be discussed later this article. machines can be used when extended by state machines that contain the definitions for the abstract states contained therein. A sample abstract state machine is illustrated in figure 6. CharacterBehavior EntityAI KeyRelease : KeyPress : Backward No one is near Hit Water Backwards Walk Around KeyPress : KeyRelease : Backward Found someone Hit Ground PaladinBehavior Figure 6. Sample Abstract Machine Figure 4. OOHSM Inheritance 4.3 Abstract An Abstract is an undefined composite state. Throughout this paper, a dotted circle, such as the one in figure five, will be used to describe abstract states. The concept of abstract state is analogous to that of abstract or virtual method in OOP. 4.5 Concrete Machine A concrete machine is defined as an OOHSM that has no Abstract s. The state machines shown in figures 2 and 3 are examples of concrete state machines. Concrete state machines are analogous to concrete classes in OOP. In figure 7, we present an instantiable, and concrete state machine based on the EntityAI abstract state machine shown in figure 6. No one is near EntityAI Hit Water Walk Around Figure 5. Abstract Notation Found someone Hit Ground 4.4 Abstract Machine A state machine containing at least one abstract state is called an abstract state machine. Abstract state machines cannot be instantiated or used directly because at least one of its composite states is undefined. Abstract state FighterAI Figure 7. An inherited abstract state machine The FighterAI state machine shown above has only one composite state called. The composite state is the definition for the abstract compound state, which, in turn, is declared in the abstract state machine EntityAI. FighterAI inherits all the concrete states from EntityAI and provides an implementation for the abstract state. Therefore, FighterAI is a concrete state machine, and it can be used or instantiated. 5 Notation Details The Unified Modeling Language provides a graphical representation of class that permits us to visualize an abstraction regardless of the programming language being used. The UML class element is a description of a set of objects that share the same attributes, operations, relationships, and semantics. [7] Also, class diagrams provide several types of relationships such as dependencies, refinement, associations, and generalizations. The notation used in this paper borrows elements from the Unified Modeling Language and from the standard state machine notation that is used by many authors, including [3]. We also introduced two new elements: the composite state symbol and the abstract state symbol. The diagram shown in figure 8 labels all the elements used throughout this paper. The UML Class symbol was used to represent a state machine, as discussed in section 4.1. Abstract state machine names are written in italics. Concrete state machine names are written in normal text. Generalization was the only relationship type borrowed from the UML and it is used to model inheritance. Elements that were borrowed from the standard state machine notation are state, transition, and transition condition. Finally, the newly introduced symbols are the abstract state symbol and composite state symbol. The latter is also used when overriding composite and abstract states. Abstract Concrete condition Wander Hungry Wander Overriden Abstract AbstractBehavior Look for Food Not Hungry NPCBehavior Abstract Found Food Figure 8. Notation details Composite Generalization (inheritance) 6 Comparison With Other Techniques Below we provide a comparison with Finite Machines and the Design Pattern, which are both related and relevant to this work. 6.1 Finite Machines One of the design goals of OOHSM is that all properties pertaining to Finite Machines should also be applicable to them. More notably, the following constraints are applicable to both FSM and OOHSM. Operations are synchronized by discrete clock pulses. There is a finite number of states that the machine can attain (even though it is easier to create an OOHSM with a large number of states) At any given moment the machine is in exactly one of its states. What the new state Eat Overriden Eat Class ( Machine) will be depends on the input, as well as what the current state is. The machine is capable of output, through user-defined functions. Finite Machines are deterministic. OOHSM also suits the formal definition of Finite Machine provided by [3]: M = [S, I, O, f s, f o ] is a finite-state machine if S is a finite set of states, I is a finite set of input symbols, O is a finite set of output symbols, and f s and f o are functions where f s :SxI S and f o :S S. The machine is always initialized to begin in a fixed starting state s 0. OOHSM are in essence finite state machines, with the difference that OOHSM provide notational tools that give several advantages in the design phase, allowing, for example, the construction of very large state machines, and reuse of these state machines, as it was discussed above. 6.2 The Design Pattern The pattern [11] is a behavioral software design pattern used to represent the state of an object. It is a solution to the problem of how to make behavior depend on state. It consists of defining a context class that presents a single interface to the world, a abstract class and several subclasses of it, each of which defining a different behavior. The main difference between the Pattern and OOHSM is that in the pattern each state should be modeled as a separate class, and thus requires a separate implementation. In OOHSM, states do not require implementation. Each OOHSM state can have data or code related to it, but none are mandatory. Another difference is that the pattern does not specify where transitions should be defined whereas OOHSM transitions should be fully defined in OOHSM diagrams. 7 Sample Uses Good examples of game genres that can take advantage of OOHSM are Fighting Games and RTS (Real-Time Strategy) Games. In many RTS games, different unit types share the same AI pattern repeatedly. The shared AI elements can be defined in base machines, and the AI elements that are specific for each unit type can be defined in separate state machines that inherit from the previously defined base machines. We observed that in fighting games such as Street Fighter, Tekken, and Dead or Alive, multiple characters share the same set of basic movements such as kick, jump, and punch, as well as a set of character-specific moves. We concluded that in these types of fighting games, the shared moves can be defined in base machines, and the character-specific moves can be defined in sub-machines. 8 Benefits of using OOHSM There are two main advantages for using OOHSM at the implementation of games. These advantages are described below: - Reduced Development and Maintenance Time: OOHSM can save development time considerably when developing games that have HFSM with repeated patterns. Taking the genres defined in section five as examples, a great amount of development time can be saved by working only once on the behaviors for characters and units as defined in base machines. Maintenance can also be expedited because every character or unit which inherits from a state machine in a game can be updated by changing that state machine alone. - Ease of Use: As a result of using a visual system to create the state machine diagrams, it becomes easy for non-specialized personnel (non-programmers) to create OOHSMs to describe the behavior of characters in games. This is especially important, because many times game designers are responsible for the definition of AI. A visual OOHSM system obviates the need for additional programming, even at scripting level. 9 Sample Implementation A sample implementation of an Object-Oriented Hierarchical Machine Engine is provided in form of a middleware written in C++, and it can be obtained at [8]. The implementation is distributed as a software library called Cadabra OOHSM. Cadabra OOHSM is bundled into the Cadabra 3D SDK, a 3D graphics and game engine developed by the first author. The Cadabra SDK and Cadabra OOHSM are both open source under the LGPL terms. The architecture of our solution is fully Object Oriented. Figure 8. contains a high-level class diagram describing the main components and their relationships. Serialization Framework contained in the Cadabra OOHSM package. Files of the.hsm format can also be created from diagrams made using diagram authoring tools such as Dia [9] and Microsoft Visio [10]. In the distribution, a tool is included to convert OOHSM diagrams created with Microsoft Visio into.hsm files. This tool, called VDX2HSM, parses xml data from the Visio vdx files and uses the Serialization Framework to create.hsm files. This idea is based on the work of Sunbir Gil [2]. VDX2HSM integrates easily into build processes, allowing VDX files to become direct assets for games. 10 Summary This paper introduces a simple method that can be used to save development time in a variety of game genres. Object-Oriented Hierarchical Machines are the result of combining objectoriented programming concepts and hierarchical finite state machines. It also provides a middleware solution that can be used to visually design OOHSMs and integrate them within nearly any game. Figure 9. Cadabra OOHSM Class Diagram Each state machine is used through one or more a MachineInstance object. MachineInstance is a lightweight object that represents a particular Machine. This allows, for example, the same Machine object to be used with hundreds of NPCs at the same time, with minimal memory consumption. Each of a Machine can carry as much custom information as needed. Full access to this data may be obtained through EventListeners. EventListeners can be attached to Machines, s, or MachineInstances to handle events. The Cadabra OOHSM package also defines a custom file format:.hsm. Each.hsm file stores one Object-Oriented Machine. Files of the.hsm format can be generated by the 11 Acknowledgements The second author is grateful to both FINEP and CAPPES for sponsoring aspects of his research. He also wishes to express his gratitude to VisionLab and to the Computer Science department of PUC-Rio. 12 References [1] Finite Machine, en.wikipedia.org/wiki/ Finite_state_machine, last visited [2] Gill, S. Visual Machine AI Systems, [3] Gersting, J. Fundamentos Matemáticos para a Ciência da Computação, Portuguese, p. 398, Fourth Edition. [4] Baillie, P. Programming Believable Characters in Computer Games, pp [5] Jacobs, S. Visual Design of Machines, Game Programming Gems 5. [6] The free dictionary of computing: [7] Booch, G; Rumbaugh, J. and Jacobson, I. The Unified Modeling Language User Guide, pp 82, 1999, Adison- Wesley. [8] [9] [10] [11] Gamma, E; Helm, R; Johnson R. and Vlissides J. Design Patterns: Elements of Reusable Object-Oriented Software, pp 231, 2001 Addison-Wesley.
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks