The inference engine for the game will be an implementation of this state and transition system. We will not go to the length of adding a Python interpreter to our game engine. Instead, we will implement a simple logic evaluation system. This will allow us to define all of our transition logic in terms of this logic system. The file format that we will use to hold our inference engine data will be XML. The XML file format has become something of a standard in recent years . The .NET Framework provides a collection of classes to facilitate the reading and writing of XML files.
Our inference engine will be implemented using six interrelated classes. The highest-level class is Thinker . This class encapsulates the entire inference engine, and an instance of this class will be instantiated for each opponent . Each Thinker contains a collection of facts (the information that the opponent knows ) and a collection of states ( AIState ). Each state contains a collection of methods that it will call and a collection of transitions ( Transitioner ) that, when triggered, will change the current state. Each Transitioner holds a collection of expressions ( Expression ) that, when evaluated as true , will activate the transition. Each expression in turn holds a collection of Logic class instances. The Logic class is a comparison between two facts that returns a Boolean result. Each of these classes will know how to read and write its contents to an XML file.
Thinking About Facts
The basis for all decisions made by the Thinker will be the facts that the Thinker knows. Each fact is a named floating-point value. By holding only floating-point values, we simplify the architecture. Holding and manipulating different types of values would add complications that can be avoided at this stage in game engine development. Integer values lend themselves quite easily to being represented as floats. Boolean values are represented by nonzero values. Some of the facts may be loaded from the XML file and never modified. These constants could represent threshold values or comparison against facts acquired from the environment. By using different base facts for different opponents, we can in effect give them different personalities.
The operations that can be used to compare facts are defined in the Operator enumeration (shown in Listing 8 “1). You can see from the listing that the enumeration contains the common numerical comparison operations. It also contains two Boolean comparison operations and two Boolean test operations. The True and False operations work on a single fact. As you will see later in the discussion of the Logic class, the second fact is ignored if presented with these operations.
Listing 8.1: Operator Enumeration namespace GameAI { public enum Operator { Equals, LessThan, GreaterThan, LessThanEquals, GreaterThanEquals, NotEqual, And, Or, True, False }; The Fact class has two attributes per instance of the class (shown in Listing 8 “2). The name attribute allows us to find and reference the facts by only knowing their names . You will see in the higher-level tasks describe later in this chapter how this is used. The value attribute is a float as described earlier. The final attribute, m_Epsilon , is a static attribute used as a constant. It is the tolerance that we will use when checking to see if a floating-point value should be considered true or false .
Listing 8.2: Fact Attributes public class Fact { #region Attributes private string m_Name; private float m_Value; private static float m_Epsilon = 0.001f; #endregion Access to the class is through its properties (shown in Listing 8 “3). The Name property provides read-only access to the property s name. The Value property, on the other hand, is read/write so that full access is provided for the value of the fact. The IsTrue property provides an evaluation of the fact s value against the epsilon . The final property, Epsilon , is a static property that allows the epsilon value to be set programmatically if a different threshold value is desired.
Listing 8.3: Fact Properties #region Properties public string Name { get { return m_Name; } } public float Value { get { return m_Value; } set { m_Value = value; } } public bool IsTrue { get { return (Math.Abs(m_Value) > m_Epsilon); } } public static float Epsilon { set { m_Epsilon = value; } } #endregion The constructor for the Fact class (shown in Listing 8 “4) is very simple. It just takes a supplied string and saves it into the m_Name attribute.
Listing 8.4: Fact Constructor public Fact(string name) { m_Name = name; } The final method in the class is the Write method shown in Listing 8 “5. The reading of Fact data from an XML data file will be done in the Thinker class that holds the collection of facts. The class just needs to know how to write itself out to a file. The argument to the method is a reference to XmlTextWriter . The XmlTextWriter class provides the means to opening a file and writing properly formatted XML tags and data to the file. The Thinker class will create the instance of this class and provide a reference to the objects it holds that must be preserved in the XML file.
Listing 8.5: Fact Write Method public void Write (XmlTextWriter writer) { writer.WriteStartElement("Fact"); writer.WriteElementString("name" , m_Name); writer.WriteElementString ("Value" , XmlConvert.ToString(m_Value)); writer.WriteEndElement(); } } } Here we use three members of the XmlTextWriter class. The WriteStartElement method places the opening tag for this element into the file. Fact elements will contain the name of the fact as well as its current value. This data is written using the WriteElementString method, which takes two strings as arguments. The first string is the field s name within the file and the second is its value. We will use the ToString method of the XmlConvert helper class to change the floating point m_Value data into a string for writing to the file. The writing of the XML element will be concluded with the WriteEndElement method. This method writes out the proper closing tag for the most recent open element, which in this case is a Fact element.
By providing a method to save facts out to a file for loading the next time the game plays, we give our inference engine a way to learn and remember between sessions. By including methods and logic that modifies the behavior-defining facts, we have made it possible for the system to adapt and change over time.
Maintaining a State
The AIState class is the central pillar of our inference engine architecture. It relies on the Transitioner , Expression , and Logic classes to determine the current state. We will work our way up from the most basic of these classes, Logic , to the AIState class itself.
Down to Basics ”the Logic Class
The attributes for the Logic class are shown in Listing 8 “6. Each instantiation of the class holds two Fact objects and an operation that will be performed on the facts when the logic is evaluated. The operation is defined using the Operator enumeration you saw earlier in the chapter.
Listing 8.6: Logic Attributes using System; using System.Xml; namespace GameAI { /// <summary> /// Summary description for Logic /// </summary> public class Logic { #region Attributes private Fact m_first; private Fact m_second; private Operator m_operator; #endregion The class s properties (shown in Listing 8 “7) provide the public interface with the attributes. All three of the properties provide read and write access to their corresponding attributes.
Listing 8.7: Logic Properties #region Properties public Fact FirstFact { get { return m_first; } set { m_first = value; } } public Fact SecondFact { get { return m_second; } set { m_second = value; } } public Operator Operation { get { return m_operator; } set { m_operator = value; } } #endregion The first constructor for the class (shown in Listing 8 “8) does not require that any data be passed in. This is the class s default constructor. It sets the references for both Fact objects to null and defaults the operation to Operator.Equals . This allows us to create an instance of the class even if we don t know yet what data it will hold. This becomes important when we get to the Read method later in the chapter.
Listing 8.8: Logic Default Constructor public Logic() { m_first = null; m_second = null; m_operator = Operator.Equals; } The second constructor for the class (shown in Listing 8 “9) assumes that we know what the data will be when the instance is being created. References to the two Fact objects are passed in as well as the Operator enumeration for the class s logic operation. Remember, a null reference is valid for some of the operations that work only against the first fact.
Listing 8.9: Logic Constructor public Logic(Fact first, Fact second, Operator op) { m_first = first; m_second = second; m_operator = op; } The real work of the Logic class is done in the Evaluate method (shown in Listing 8 “10). This is where we will perform the operation on the facts referenced by the logic. We need to ensure that the software doesn t fail if a fact has not been properly referenced. All operations require that the first fact exists. If it does not, we won t bother trying to do the operation. Instead, we will just return the default return value of false and post a message to the debug console. Any operations that require a second fact will be tested and reported the same way.
Listing 8.10: Logic Evaluate Method  |
public bool Evaluate() { bool result = false; if (m_first != null) { switch (m_operator) { case Operator.And: if (m_second != null) { result = m_first.IsTrue && m_second.IsTrue; } else { Debug.WriteLine("second fact missing in Logic"); } break; case Operator.Equals: if (m_second != null) { result = m_first.Value == m_second.Value; } else { Debug.WriteLine("second fact missing in Logic"); } break; case Operator.GreaterThan: if (m_second != null) { result = m_first.Value > m_second.Value; } else { Debug.WriteLine("second fact missing in Logic"); } break; case Operator.GreaterThanEquals: if (m_second != null) { result = m_first.Value >= m_second.Value; } else { Debug.WriteLine("second fact missing in Logic"); } break; case Operator.LessThan: if (m_second != null) { result = m_first.Value < m_second.Value; } else { Debug.WriteLine("second fact missing in Logic"); } break; case Operator.LessThanEquals: if (m_second != null) { result = m_first.Value <= m_second.Value; } else Debug.WriteLine("second fact missing in Logic"); } break; case Operator.Not Equal: if (m_second != null) { result = m_first.Value != m_second.Value; } else { Debug.WriteLine("second fact missing in Logic"); } break; case Operator.Or: if (m_second != null) { result = m_first.IsTrue m_second.IsTrue; } else { Debug.WriteLine("second fact missing in Logic"); } break; case Operator.True: result = m_first.IsTrue; break; case Operator.False: result = !m_first.IsTrue; break; } } else { Debug.WriteLine("first fact missing in Logic"); } return result; } | |
The Write method for this class (shown in Listing 8 “11) is very similar to the method in the Fact class. For this class, the element name will be Logic and we will save the names of the two facts plus the string value of the Operator enumeration. The ToString method of an enumeration gives us the enumeration name so that Operator.And gets stored as And .
Listing 8.11: Logic Write Method public void Write (XmlTextWriter writer) { writer.WriteStartElement("Logic"); writer.WriteElementString("Fact1", m_first.Name); writer.WriteElementString("Operator", m_operator.ToString()); writer.WriteElementString("Fact2", m_second.Name); writer.WriteEndElement(); } Reading a Logic class from XML is a bit more complicated. The Read method (shown in Listing 8 “12) will get the three strings that were saved into the XML file. It must then associate those strings with the proper facts and enumeration value. The arguments to the method are an instance to the XmlTextReader that was used to open the data file as well as the instance of the Thinker we are loading data for. The Thinker holds the collection of facts that the logic will reference. Therefore we need to get the references from it.
Listing 8.12: Logic Read Method | |
public void Read (XmlTextReader reader, Thinker thinker) { bool done = false; while (!done) { reader.Read(); if (reader.NodeType == XmlNodeType.EndElement && reader.Name == "Logic") { done =true; } // Process a start of element node. else if (reader.NodeType == XmlNodeType.Element) { // Process a text node. if (reader.Name == "Fact1") { while (reader.NodeType != XmlNodeType.Text) { reader.Read(); } m_first = thinker.GetFact(reader.Value); } if (reader.Name == "Fact2") { while (reader.NodeType != XmlNodeType.Text) { reader.Read(); } m_second = thinker.GetFact(reader.Value); } if (reader.Name == "Operator") { while (reader.NodeType != XmlNodeType.Text) { reader.Read(); } switch (reader.Value) { case "And": m_operator = Operator.And; break; case "Equals": m_operator = Operator.Equals; break; case "GreaterThan": m_operator = Operator.GreaterThan; break; case "GreaterThanEquals": m_operator = Operator.GreaterThanEquals; break; case "LessThan": m_operator = Operator.LessThan; break; case "LessThanEquals": m_operator = Operator.LessThanEquals; break; case "NotEqual": m_operator = Operator.NotEqual; break; case "Or": m_operator = Operator.Or; break; case "True": m_operator = Operator. True; break; case "False": m_operator = Operator.False; break; } } } }// End while loop. } } } | |
The method will loop through the lines in the XML file until it reaches a Logic end element. If it finds an element node, it checks the name of that element. It then reads until it finds the next text node. The string at the text node is the value for that element. If this is one of the two Fact nodes, it will call the Thinker s GetFact method to get a reference for that fact and store it within the corresponding attribute.
To evaluate the operation, we are forced to use a switch statement to find the correct enumeration value associated with the string. Unfortunately, C# enumerations do not include a Parse method to complement the ToString method we used when writing the XML file.
Stepping Up a Level ”the Expression Class
The Logic class is our first step hierarchy. The next level is the Expression class. The attributes for this class are shown in Listing 8 “13. An Expression is a means of combining a number of Logic instances together. To accomplish this, it maintains a collection of the Logic that forms the expression as well as a Boolean value that specifies whether the values of the individual logic instances are combined with a logical And or a logical Or operation.
Listing 8.13: Expression Attributes using System; using System.Collections; using System.Xml; namespace GameAI /// <summary> /// Summary description for Expression /// </summary> public class Expression { #region Attributes private ArrayList m_logic_list; private bool m_and_values = true; #endregion There is only one property in the Expression class (shown in Listing 8 “14). The CombineByAnding property is used to set the state of the m_and_values attribute.
Listing 8.14: Expression Property #region Properties public bool CombineByAnding { set { m_and_values = value; } } #endregion The Expression class (shown in Listing 8 “15) has a simple default constructor. The constructor allocates the ArrayList that will hold the logic for the expression.
Listing 8.15: Expression Constructor public Expression() { m_logic_list = new ArrayList(); } We will include a couple of methods to give the ability to change the expression programmatically. The first is the Clear method shown in Listing 8 “16. This method simply removes all of the logic from the list.
Listing 8.16: Expression Clear Method public void Clear() { m_logic_list.Clear(); } Once the Clear method has been used to reset the list of logic, it is ready for new logic to be inserted. The AddLogic method (shown in Listing 8 “17) accepts the passed Logic reference and adds it to the collection.
Listing 8.17: Expression AddLogic Method public void AddLogic(Logic logic) { m_logic_list.Add(logic); } The Evaluate method is the key for the Expression class, just as it was for was the Logic class. The Evaluate method is shown in Listing 8 “18. It works by iterating through the Logic list and accumulating the answer in the result flag. If the results of evaluating the logic are for the first entry in the collection, the result is assigned to the result variable. The remaining results are combined with this one based on the status of the m_and_values attribute. The final accumulated result is the evaluation of the complete expression and returned as the result.
Listing 8.18: Expression Evaluate Method public bool Evaluate() { bool result = false; bool first_logic = true; foreach (Logic logic in m_logic_list) { bool val = logic.Evaluate(); if (first_logic) { result = val; } else { if (m_and_values) { result = result && val; } else { result = result val; } } } return result; } The Expression class must also be able to write itself and restore itself to an XML file. The Write method for the class is shown in Listing 8 “19. This method follows the same pattern as the Write method in the previous classes. It begins by storing the Boolean value. Then it is just a matter of iterating through the list of Logic instances and having each one write itself to the file.
Listing 8.19: Expression Write Method public void Write(XmlTextWriter writer) { writer.WriteStart Element("Expression"); writer.WriteElementString("AndValues", m_and_values.ToString()); foreach (Logic logic in m_logic_list) { logic.Write(writer); } writer.WriteEndElement(); } The Write method for the Expression class (shown in Listing 8 “20) follows a pattern similar to that of the Logic class s Write method. It also takes a reference to the XmlTextReader class and the Thinker associated with this Expression . It loops reading and processing the XML lines until the Expression end element is encountered . Whenever it encounters a logic element, it creates an instance of the class. This method has the class load itself from the XML file and adds it to its collection.
Listing 8.20: Expression Read Method public void Read (XmlTextReader reader, Thinker thinker) { bool done=false; while (!done) { reader.Read(); if (reader.NodeType == XmlNodeType.EndElement && reader.Name == "Expression") { done =true; } // Process a start of element node, else if (reader.NodeType == XmlNodeType.Element) { // Process a text node. if (reader.Name == "Logic") { logic logic = new Logic(); logic.Read(reader, thinker); m_logic_list.Add(logic); } else if (reader.Name == "AndValues") { while (reader.NodeType != XmlNodeType.Text) { reader.Read(); } m_and_values = bool.Parse(reader.Value); } } }// End while loop. } } } Putting the Logic to Work-the Transitioner Class
The Transitioner class is where we put all of this logic evaluation to work. This is the class that handles those lines that ran between the circles in the state diagram (refer back to Figure 8 “1). To accomplish this, the class needs the expression that defines the condition required to make the transition as well as the state it will transition into. The Transitioner class attributes shown in Listing 8 “21 illustrate this.
Listing 8.21: Transitioner Attributes using System; using System.Xml; namespace GameAI { /// <summary> /// Summary description for Transitioner /// </summary> public class Transitioner { #region Attributes private Expression m_expression = null; private AIState m_target_state; #endregion There is no default constructor for the Transitioner class. The constructor (shown in Listing 8 “22) requires both the Expression and the target state. References to both are passed in and stored in the class s attributes.
Listing 8.22: Transitioner Constructor public Transitioner(Expression expression, AIState target_state) { m_expression = expression; m_target_state = target_state; } The Evaluate method (shown in Listing 8 “23) is where we decide whether the state should change or not. The current state is passed into the method. This way we can pass the current state back to the calling method if the state isn t changing. If for some reason there is no expression, we have nothing to evaluate and the state will not change. Otherwise, we evaluate the expression. If the expression evaluates to true, then we will return the target state and the transition will take place.
Listing 8.23: Transitioner Evaluate Method public AIState Evaluate(AIState old_state) { AIState new_state = old_state; if (m_expression != null) { if (m_expression.Evaluate()) { new_state = m_target_state; } } return new_state; } The Transitioner class s Write method (shown in Listing 8 “24) writes the attributes out to the XML file. The name of the target state is saved in the file. We will use this name when we read in the XML and query the Thinker for the corresponding class reference. The Expression is written using its Write method.
Listing 8.24: Transitioner Write Method public void Write (XmlTextWriter writer) { writer.WriteStartElement("Transitioner"); writer.WriteElementString("Target", m_target_state.Name); m_expression.Write (writer); writer.WriteEndElement(); } The Read method for the Transitioner class (shown in Listing 8 “25) loads the expression used by the class. Each AIState holds a collection of Transitioners . When an AIState is loading itself from the XML file, it will call this method and pass in the XmlTextReader and the Thinker reference. The Read method will read the target state and use it when creating the Transitioner instance before having to load its expression.
Listing 8.25: Transitioner Read Method public void Read (XmlTextReader reader, Thinker thinker) { bool done = false; while (!done) { reader.Read(); if (reader.NodeType == XmlNodeType.EndElement && reader.Name == "Transitioner") { done =true; } // Process a start of element node, else if (reader.NodeType == XmlNodeType.Element) { // Process a text node. if (reader.Name == "Expression") { m_expression.Read(reader, thinker); } } }// End while loop. } } } Getting to the Top ”the AIState Class
The Transitioner class gives us the means to sequence from one state to another. Now it is time to look at the AIState class we will use for the states themselves. The attributes for the class are shown in Listing 8 “26. Each state will know its name so that it can be referenced by name. It will also hold a collection of Transitioners to the states that it is connected with. Finally, it will hold a collection of action methods. These methods are executed each pass that the state is active.
Listing 8.26: AIState Attributes using System; using System.Collections; using System.Xml; namespace GameAI { /// <summary> /// Summary description for AIState /// </summary> public class AIState { #region Attributes private string m_name; private ArrayList m_transition_list; private ArrayList m_actions; #endregion The class has a single property (shown in Listing 8 “27). It is a read-only property that returns the state s name so that any class holding a reference to the state can access its name.
Listing 8.27: AIState Properties #region Properties public string Name { get { return m_name; } } #endregion The constructor for the class (shown in Listing 8 “28) takes a string for the state s name as an argument. The string is saved in an attribute for future reference. We also need to initialize the collections so that they are ready to receive data.
Listing 8.28: AIState Constructor public AIState(string name) { m_name = name; m_transition_list = new Array List(); m_actions = new ArrayList(); } The AddAction method (shown in Listing 8 “29) is used to add action methods to the class. The ActionMethod delegate of the Thinker class is a void method that takes a Thinker reference as an argument. The supplied method is added to the m_actions collection.
Listing 8.29: AIState AddAction Method public void AddAction(Thinker.ActionMethod method) { m_actions.Add(method); } The DoActions method (shown in Listing 8 “30) provides the means for the Thinker to execute the state s methods. A reference to the Thinker that called the function is passed in as an argument to each action method held in the collection. By giving each action method this reference, the DoActions method has the ability to query the Thinker for any information it needs about the object it is working on, including a reference to the object itself.
Listing 8.30: AIState DoActions Method public void DoActions(Thinker thinker) { foreach (Action act in m_actions) { act(thinker); } } The Think method (shown in Listing 8 “31) is where the class decides if the current state should change based on current conditions. This method is called by the Thinker class and returns a reference to the desired state. To accomplish this, the method iterates through the collection of Transitioners , calling the Evaluate method for each one. If any Transitioner returns a state other than the current state, we stop evaluating and return that state. Therefore, even if multiple transitions could have been made, only the first transition is actually made.
Listing 8.31: AIState Think Method public AIState Think() { AIState new_state; foreach (Transitioner trans in m_transition_list) { new_state = trans.Evaluate(this); if (new_state != this) { return new_state; } } return this; } We need a programmatic means of adding Transitioners to the state so that we can modify the logic on the fly. The AddTransitioner method (shown in Listing 8 “32) provides this capability by adding the supplied Transitioner reference to the Transitioner list.
Listing 8.32: AIState AddTransitioner Method public void AddTransitioner (Transitioner trans) { m_transition_list.Add(trans); } Due to the way the states interrelate, we need to instantiate all instances of AIState before we populate them with Transitioners . This way we can establish the references to them in the Transitioner by name lookup as the Transitioners are created and loaded from the XML file. To simplify this procedure, we will make two entries into the XML file for each state. The first set of entries will be only the name of the state. This is accomplished by the WriteStateName method, shown in Listing 8 “33, which writes StateName elements with the state name as the value.
Listing 8.33: AIState WriteStateName Method public void WriteStateName(XmlTextWriter writer) { writer.WriteStartElement("StateName"); writer.WriteElementString("name", m_name); writer.WriteEndElement(); } The WriteFullState method (shown in Listing 8 “34) writes the second entry for the state. This entry includes all of the information required to re-create the state. It begins with the name of the state so that we can retrieve the correct state to populate. It then iterates through the collection of Transitioners and has each write itself to the file. Once all of the Transitioners have been written to the file, the method then iterates through the collection of action methods for the state and writes the name of the methods to the XML file.
Listing 8.34: AIState WriteFullState Method public void WriteFullState(XmlTextWriter writer) { writer.WriteStartElement("StateDefinition"); writer.WriteElementString("name", m_name); foreach (Transitioner trans in m_transition_list) { trans.Write(writer); } foreach (Thinker.ActionMethod act in m_actions) { writer.WriteStartElement("StateAction"); writer.WriteElementString("name", Thinker.GetActionName(act)); writer.WriteEndElement(); } writer.WriteEndElement(); } The last two methods provide for the saving of an AIState to an XML file. The Read method (shown in Listing 8 “35) repopulates an AIState based on this saved information. The Read method of the Thinker class will create the state. This Read method then populates it from the data in the file. The method reads the XML file until it encounters the StateDefinition end element marking the end of the data for that state.
Listing 8.35: AIState Read Method public void Read (XmlTextReader reader, Thinker thinker) { bool done = false; Transitioner trans = null; Expression exp = null; while (!done) { reader.Read(); if (reader.NodeType == XmlNodeType.EndElement && reader.Name == "StateDefinition") { done =true; } // Process a start of element node. else if (reader.NodeType == XmlNodeType.Element) { // Process a text node. if (reader.Name == "Target") { while (reader.NodeType != XmlNodeType.Text) { reader.Read(); } AIState state = thinker.GetState(reader.Value); exp = new Expression(); trans = new Transitioner(exp, state); AddTransitioner(trans); trans.Read(reader, thinker); } if (reader.Name == "StateAction") { while (reader.NodeType != XmlNodeType.Text) { reader.Read(); } Thinker.ActionMethod method = Thinker.GetAction(reader.Value); reactions.Add(method); } } }// End while loop. } } } The Target nodes in the file denote Transitioners to a target state. When this node is encountered, we need to get a reference to the target state. The Thinker class s GetState method gives us this reference. We have the Transitioner that we create to target this state load itself from the file and we add the Transitioner to the state s collection.
The StateAction nodes in the XML file contain the name of the action methods that will be called while this state is active. We will need references to the methods themselves to call them while the state is active. The Thinker class has a GetAction method that returns a reference to an action method when supplied with the method s name.
Our Opponent ”the Thinker
The Thinker class brings it all together. This is the class that encapsulates our inference engine and provides the artificial intelligence for our computer opponents. It consists of a collection of sensor methods that run continually, collecting information ( Facts ) that will be used to make decisions regarding what the object should do. It also has a collection of states ( AIState ) with their Transitioner and action methods that define the behavior.
Defining the Thinker Class
The Thinker class uses two delegates (shown in Listing 8 “36) that define the method prototypes that will be used for the sensors and actions. Both methods accept a reference to the Thinker that is calling the method. This provides the method with the context that it will need to work within. Each Thinker holds a reference to the Model that the Thinker is attached to. The only real difference in the delegates is the use to which the methods are put.
Listing 8.36: Thinker Delegates using System; using System.Collections; using System.Threading; using System.Xml; using GameEngine; namespace GameAI { /// <summary> /// Summary description for Thinker /// </summary> public class Thinker : IDisposable { #region delegates public delegate void SensorMethod(Thinker the_thinker); public delegate void ActionMethod(Thinker the_thinker); #endregion The attributes for the Thinker class are shown in Listing 8 “37. A static collection of methods is shared by all instances of the Thinker class. This is the collection that is queried when setting up an instantiation of the class and its states. This collection needs to be populated before any Thinkers are created. The static AddAction method that we will look at shortly is used to populate this collection.
Listing 8.37: Thinker Attributes #region Attributes private ArrayList m_state_list = null; private ArrayList m_sensor_methods = null; private AIState m_current_state = null; private SortedList m_fact_list; private Thread m_think_thread; private Model m_model = null; private bool m_thread_active = true; private static SortedList m_methods = null; #endregion
Each instance of the Thinker class contains the following:
-
Attributes that are specific to that Thinker .
-
A collection of the states that define the logic for that instance.
-
A collection of the facts that the Thinker knows and a collection of sensor methods that are used to keep those facts up to date.
-
A reference to the current state. This is the state that will be executed each pass until one of its Transitioners fires to change the current state.
-
A Thread reference. This is because each Thinker will execute in its own separate thread. This allows each Thinker to take an extended amount of time each iteration to make its decisions without impacting the rendering rate of the application.
-
A m_thread_active flag, which provides a means of signaling the thread that it should be terminated . It defaults to the true state and is set to false when the thread should terminate.
-
A reference to the Model that is using this Thinker for control. This makes the model available to both the sensor methods that will need to know where they are in the world and the action methods that will modify the model s attributes in order to control the model s actions.
The class will have one property. The Self property (shown in Listing 8 “38) provides read-only access to the Model reference held by the class. This is how the methods that need the model will be able to access it.
Listing 8.38: Thinker Properties #region Properties public Model Self { get { return m_model; } } #endregion Constructing a Thinker
The Thinker constructor (shown in Listing 8 “39) does a bit more than the typical constructor that we have seen so far. It accepts the reference to the Model that is controlled by this Thinker . This is saved in an attribute and the three collections are initialized . The novel portion of the constructor is found in the final three lines of the method, which is where we set up the thread that will execute the class and perform the thinking. A thread is created with the Execute method of the class used as the method executed by the thread. The IsBackground flag for the thread is set to indicate that this thread will execute with background priority. The final line starts the new thread executing. By placing this thread creation and management within the constructor, we automatically create new threads each time we create a new Thinker .
Listing 8.39: Thinker Constructor public Thinker(Model model) { m_model = model; m_state_list = new ArrayList(); m_sensor_methods = new ArrayList(); m_fact_list = new SortedList(); m_think_thread = new Thread(new ThreadStart(Execute)); m_think_thread.IsBackground = true; m_think_thread.Start(); } Earlier I mentioned a static method that we would use to populate the static collection of action methods to be shared by all instances of the class. The AddAction method (shown in Listing 8 “40) is that method. By being a static method, it can be used before any of the Thinkers are created. It takes as arguments a string holding the name of the method and a reference to the method. The method must adhere to the ActionMethod delegate structure. The collection of methods uses the SortedArray collection type, which provides quick access to the stored data based on a key value. We will use the string name of the method as our key. By its nature, this collection does not allow entries with duplicate keys. Before we add the method reference to the collection, we will use the Contains method of the collection to check if the key already exists. If it does not, we are free to add the reference and its name to the collection.
Listing 8.40: Thinker AddAction Method public static void AddAction(string action_name, ActionMethod method) { if (!m_methods. Contains (action_name)) { m_methods.Add(action_name, method); } } Since the methods are of little use unless we can provide them upon request, we also need a method for supplying the action methods. This is provided using the static GetAction method shown in Listing 8 “41. A string with a reference name is passed in as an argument and the reference pointer is returned as the result. We start with a method reference set to null. If the calling method asks for a method that is not found in the collection, this is what will be returned. We first check to see if the method s name is found in the collection. If it is, we will use the IndexOf Key method to find the index in the collection for that entry. The method reference is set using the GetByIndex method.
Listing 8.41: Thinker GetAction Method public static ActionMethod GetAction(string action_name) { ActionMethod method = null; if (m_methods.Contains(action_name)) { int index = m_fact_list.IndexOfKey(action_name); method = (ActionMethod)m_methods.GetByIndex(index); } return method; } There will be times when we will need to get the name of a method when given a reference to that method. The static GetActionName method (shown in Listing 8 “42) provides a lookup similar to that found in the previous GetAction method. Instead of getting the index of the entry based on its key, we get the index based on the stored value (the method reference) using the IndexOfValue method of the collection. The GetKey method of the collection will give us the string with the method s name at that index.
Listing 8.42: Thinker GetActionName Method public static string GetActionName(ActionMethod method) { string action_name = null; if (m_methods.Contains(method)) { int index = m_methods.IndexOfValue(method); action_name = (string)m_methods.GetKey(index); } return action_name; } When we discussed the Thinker constructor, we showed the creation of a thread that would be spawned for the execution of the Thinker . This thread uses the Execute method (shown in Listing 8 “43) as the method to be executed. The method will loop as long as the m_thread_active flag is set. Once the method completes, the thread is automatically terminated. The current state is set once the Thinker is fully configured. When the thread sees the reference become nonnull, it will start executing that state. It begins by calling the sensor methods of each of the Thinkers . Remember, these are the methods that provide the information state transitions are based upon. Once all sensor methods have been called, the state is commanded to perform its action methods. Lastly, the Think method of the state is called to determine what state will execute during the next iteration. Since all of this is done in a lower priority background thread, it is quite possible that the image on the screen may be updated several times for each loop through this method. This is fine. In fact, in some games you may find that the computer opponents are simply too good to beat. One of the solutions to that problem would be to lower the thread priority further or add a short delay in this method s iterations so that the opponent is not thinking too fast.
Listing 8.43: Thinker Execute Method public void Execute() { while (m_thread_active) { if (m_current_state != null) { foreach (SensorMethod method in m_sensor_methods) { method(this); } m_current_state.DoActions(this); m_current_state = m_current_state.Think(); } } } We have made the Thinker class inherit from the IDisposable interface. This provides us with the Dispose method (shown in Listing 8 “44) to perform cleanup when the class is no longer needed. In the case of the Thinker class, we need to stop the thread that was created. Since the thread method is looping based on the state of the m_thread_alive flag, we need to clear the flag by setting it to false . The flag will only be checked when the execution of the thread loops back to the beginning, so we will pause until the thread reports that it has terminated by clearing its IsAlive property. The Sleep method allows us to pause for one millisecond after each check until the thread has terminated.
Listing 8.44: Thinker Dispose Method public void Dispose() { m_thread_active = false; while (m_think_thread.IsAlive) Thread.Sleep(1); } Getting Information from the Thinker
We will give the class a number of helper methods so that other methods and classes may query this class for information about the data it holds. The first of these methods is the GetState method shown in Listing 8 “45. This method provides the means of finding a state reference based on the name of the state. Since the state collection is a simple ArrayList rather than a SortedList, we handle the lookup a little differently. We will use the more brute-force method of looping through the states in the collection and checking to see if each state is the one we want. If we find the desired state, we will save its reference. After we finish looping, we will return the reference if we found it. Otherwise, we will return a null to indicate that the state was not found. Since this function is only used when loading or saving a state, we do not need to use a more complicated system just to save the small performance penalty of this type of search.
Listing 8.45: Thinker GetState Method public AIState GetState(string name) { AIState the_state = null; foreach (AIState state in m_state_list) { if (state.Name == name) { the_state = state; } } return the_state; } The GetFact method (shown in Listing 8 “46), on the other hand, will be used often during the execution of the game. This is a good reason to use the somewhat larger but much faster SortedList collection. If the fact exists in the collection, we will return a reference to the fact to the calling method. If it does not, then we will add a new fact to the collection with that name and set its initial value to zero. This allows us to check for facts that have not been set yet without throwing an exception.
Listing 8.46: Thinker GetFact Method public Fact GetFact(string name) { Fact the_fact = null; if (m_fact_list.Contains(name)) { int index = m_fact_list.IndexOfKey(name); the_fact = (Fact)m_fact_list.GetByIndex(index); } else { the_fact = new Fact(name); the_fact.Value = 0.0f; m_fact_list.Add(name, the_fact); } return the_fact; } The complement to the GetFact method is the SetFact method shown in Listing 8 “47. This method takes a string with the Fact s name as well as the value that the fact should take. We look up the fact in the collection and set the value. If the Fact does not exist yet, we will create a new fact with the supplied value and add it to the collection.
Listing 8.47: Thinker SetFact Method public void SetFact(string name, float value) { if (m_fact_list.Contains(name)) { int index = m_fact_list.IndexOfKey(name); Fact fact = (Fact)m_fact_list.GetByIndex(index); fact.Value = value; } else { Fact fact = new Fact (name); fact.Value = value; m_fact_list.Add(name, fact); } } The AddSensorMethod method (shown in Listing 8 “48) is used to populate the collection of sensor methods. It takes a method reference that was passed in as an argument and adds it to the collection that is called by the Execute method each iteration.
Listing 8.48: Thinker AddSensorMethod Method public void AddSensorMethod (SensorMethod method) { m_sensor_methods.Add(method); } The AddState method (shown in Listing 8 “49) is used to add AIState references to our collection of states. Through this method we can programmatically add states to the class. It is also used by the Read method as we are creating the states based on the XML data.
Listing 8.49: Thinker AddState Method public void AddState(AIState state) { m_state_list.Add(state); } Serializing the Thinker
This is all the functionality we need in the Thinker class. All that is left is the ability to read and write the contents of the class to an XML file. The Write method (shown in Listing 8 “50) provides the output portion of this capability. All of the XML Write methods that we have investigated from the other classes worked with an XmlTextWriter that was supplied by the calling method. The Thinker s Write method is the source of the XmlTextWriter that is used. This Write method is supplied with a string that holds the fully qualified path to the XML file that will be written.
Listing 8.50: Thinker Write Method public void Write(string filename) { XmlTextWriter writer = new XmlTextWriter(filename, null); writer.WriteStartDocument(); writer.WriteStart Element("Knowledge"); //Use indentation for readability. writer.Formatting = Formatting.Indented; writer.Indentation = 4; int num_facts = m_fact_list.Count; for (int i=0; i<num_facts; i++) { Fact fact = (Fact)m_fact_list.GetByIndex(i); fact.Write(writer); } foreach (AIState state in m_state_list) { state.WriteStateName(writer); } foreach (AIState state in m_state_list) { state.WriteFullState(writer); } writer.WriteEndElement(); writer.WriteEndDocument(); writer.Close(); } The writer is created using this path as an argument to the constructor. The WriteStartDocument method of the writer puts the standard XML header into the file. The overall element name for the data is Knowledge . We have the writer use tab indenting for the information as it is written to the file. This has no effect on the data itself, but makes the data more legible if we look at the file in a text editor.
The first information written to the file is the collection of facts. We iterate through the collection of facts and have each write itself to the file. We can t use the foreach loop architecture for a SortedList. Instead, we use a standard for loop. The collection of AIStates is an ArrayList. This allows us to use foreach . We will loop through the collection of states twice. The first time through, we will have each state write its name to the file. The second pass we will have each state write its complete state using the WriteFullState method.
Once all of the states have been written to the file, we have captured all of the information for a Thinker . To close the file, we will call WriteEndElement to close the Knowledge element in the file. We will then call WriteEndDocument to finalize the XML and Close to actually close the file itself.
The Read method (shown in Listing 8 “51) re-creates the contents of a Thinker based on the XML data. This is the method that creates the XmlTextReader that is used by the other class s Read methods. Just like the Write method, the Read method takes a string with the fully qualified path for the XML file. Once the file is opened, this method reads the file and processes the element and text nodes that hold our data. The name and value nodes hold our Fact data, and they are written to the file in that order. When we read in the value, we have everything we need to create a Fact , and we then use the SetFact method to create the Fact . The StateName nodes hold the names of all of the states. Each time we hit one, we create a new AIState and add it to our collection of states. The StateDefinition nodes hold the full definitions of the states. When we hit one of these nodes, we get the associated state from our collection. We then have that state load itself from the file. Once we have finished reading the file, we are ready to begin thinking. Remember that the thinking thread does not begin doing actual work until the current state has been set. Assuming that we load at least one state from the file, we set the current state to the first state in the collection. This should always be the default state. A Try/Catch block wraps the entire method so that any errors in loading the file (including not finding the file to load) will result in an appropriate message being displayed.
Listing 8.51: Thinker Read Method | |
public void Read(string filename) { XmlTextReader reader = new XmlText Reader(filename); string name = "unknown"; float float_value; AIState state = null; try { reader.Read(); // If the node has value while (reader.Read()) { // process a start of element node. if (reader.NodeType == XmlNodeType.Element) { // Process a text node. if (reader.Name == "name") { while (reader.NodeType != XmlNodeType.Text) { reader.Read(); } name = reader.Value; } else if (reader.Name == "Value") { while (reader.NodeType != XmlNodeType.Text) { reader.Read(); } float_value = float.Parse(reader.Value); SetFact(name, float_value); } else if (reader.Name == "StateName") { while (reader.NodeType != XmlNodeType.Text) { reader.Read(); } state = new AIState(reader.Value); AddState(state); } else if (reader.Name == "StateDefinition") { while (reader.NodeType != XmlNodeType.Text) { reader.Read(); } state = GetState(reader.Value); state.Read(reader, this); } } }// End while loop. if (m_state_list.Count != 0) { m_current_state = (AIState)m_state_list[0]; } reader.Close(); } catch (Exception e) { System.Diagnostics.Debug.WriteLine ("error in thinker read method/n"); System.Diagnostics.Debug.WriteLine (e.Message); } } } } | |
Supplying Data to the Thinker
With the completion of the Thinker class, we have the complete encapsulation of our artificial intelligence inference engine. Listing 8 “52 gives an example of an XML data file that would be read by the class when creating an instance of a Thinker . Notice that the tags within the data match the element names that we defined within each of the classes that make up a Thinker .
Listing 8.52: Example XML Data File | |
<?xml version="1.0"?><Knowledge> <Fact> <name>race started</name> <Value>0.0</Value> </Fact> <Fact> <name>collision ahead</name> <Value>0.0</Value> </Fact> <Fact> <name>race over</name> <Value>0.0</Value> </Fact> <StateName> <name>Idle</name> </StateName> <StateName> <name>Race</name> </StateName> <StateName> <name>Evade</name> </StateName> <StateDefinition> <name>Idle</name> <Transitioner> <Target>Race</Target> <Expression> <AndValues>true</AndValues> <Logic> <Fact1>race started</Fact1> <Operator>True</Operator> <Fact2>null</Fact2> </Logic> </Expression> </Transitioner> </StateDefinition> <StateDefinition> <name>Race</name> <Transitioner> <Target>Idle</Target> <Expression> <AndVlues>true</AndValues> <Logic> <Fact1>race over</Fact1> <Operator>True</Operator> <Fact2>null</Fact2> </Logic> </Expression> </Transitioner> <Transitioner> <Target>Evade</Target> <Expression> <AndValues>true</AndValues> <Logic> <Fact1>collision ahead</Fact1> <Operator>True</Operator> <Fact2>null</Fact2 > </Logic> <Logic> <Fact1>race started</Fact1> <Operator>True</Operator> <Fact2>null</Fact2 > </Logic> <Logic> <Fact1>race over</Fact1> <Operator>False</Operator> <Fact2>null</Fact2 > </Logic> </Expression> </Transitioner> </StateDefinition> <StateDefinition> <name>Evade</name> </StateDefinition> </Knowledge>
| |
Detecting the World Around Us-Sensor Systems
The Thinker as we have designed it so far can think but has limited information to think about. The opponent for our sample game needs to see the vehicles, obstacles, and course markings in order to steer around the racecourse. We might also want to give it a sense of hearing to detect other cars that are nearby but not in sight. In a military-oriented game, we might also have radar or sonar systems that would detect our opponents. All of these are examples of sensor systems.
Our sensor systems will be implemented as the sensor methods that we provide to the Thinker class. These methods are game specific and not part of the game engine itself. This is why the game engine was built so that the methods are supplied to the engine rather than hard coded. This allows the sensor methods to be specifically targeted to what is needed for that game.
The results of the sensor method will be facts that are set within the Thinker . These facts can then be used by the state transition logic as well as the action methods that put the decisions into effect. For our sample game, we need an opponent that can see the world around him or her in order to drive his or her car. Luckily, we happen to have a class handy that can provide sight to our Thinker . Although the class was designed to assist in culling and rendering, it also has capabilities that we can exploit for this purpose. A camera attached to an opponent vehicle will hold a collection of the objects that are within the viewing frustum of that camera.
The DriverView method (shown in Listing 8 “53) is an example of a sensor method. This method belongs to the Opponent class within the game application that uses the game engine. For this example, we are interested in sensing three types of objects. We want to know the closest red and blue posts that are in sight. These are the course markers, and the logic for the opponent is to stay within these borders, with the red posts to the right and the blue posts to the left. The opponent also needs to know of any obstacles directly in front of his or her car. We will define in front to mean within an arc of 5 degrees in front of the car.
Listing 8.53: DriverView Method | |
public void DriverView(Thinker thinker) { ArrayList objects = new ArrayList(); Opponent self = (Opponent)thinker.Self; Camera eyes = self.Eyes; // Get a local copy of the objects that the camera can see. objects.Clear(); foreach (Object3D obj in eyes.VisibleObjects) { objects.Add(obj); } float range_to_nearest = 10000.0f; float bearing_to_nearest = 0.0f; Object3D nearest_object = null; // Nearest red post foreach (Object3D obj in objects) { if (obj.Name.Substring(0,3) == "red") { float range = eyes.GetDistance(obj); if (range < range_to_nearest) { range_to_nearest = range; nearest_object = obj; } } } if (nearest_object != null) { bearing_to_nearest = Get Bearing (self, nearest_object); thinker.SetFact("red_post_in_sight", 1.0f); thinker.SetFact("red_post_range", range_to_nearest); thinker.SetFact ("red_post_bearing", bearing_to_nearest); } else { thinker.SetFact("red_post_in_sight", 0.0f); } // Nearest blue post range_to_nearest = 10000.0f; foreach (Object3D obj in objects) { if (obj.Name.Substring(0, 4) == "blue") { float range = eyes.GetDistance(obj); if (range < range_to_nearest) { range_to_nearest = range; nearest_object = obj; } } } if (nearest_object != null) { bearing_to_nearest = GetBearing(self, nearest_object); thinker.SetFact("blue_post_in_sight", 1.0f); thinker.SetFact("blue_post_range", range_to_nearest); thinker.SetFact("blue_post_bearing", bearing_to_nearest); } else { thinker.SetFact("blue_post_in_sight", 0.0f); } // Nearest obstacle (vehicles and trees) range_to_nearest = 10000.0f; foreach (Object3D obj in objects) { if (obj.Name.Substring(0,4) == "tree" obj.Name.Substring(0,3) == "car") { float bearing = GetBearing(self, nearest_object); float range = eyes.GetDistance(obj); // Only accept nearest object within +/ 5 degrees. if (Math.Abs(bearing) < 0.087266462599716478846184538424431 && range < range_to_nearest) { range_to_nearest = range; nearest_object = obj; bearing_to_nearest = bearing; } } } if (nearest_object != null) { thinker.SetFact ("obstacle_in_sight", 1.0f); thinker.SetFact("obstacle_range", range_to_nearest); thinker.SetFact("obstacle_bearing", bearing_to_nearest); } else { thinker.SetFact("obstacle_in_sight", 0.0f); } } | |
The method begins by creating a collection to hold the objects currently in view and references to the opponent and its eyes. Since the Thinker is running in a separate thread, we will capture a copy of the references held by the camera. We can then iterate through this list, looking for objects that meet our needs. In the first pass through the collection, we will look for the red posts. The names for all of the posts begin with the color of the post. If we find an object whose name starts with red , we have a candidate object. The camera class provides the GetDistance method that will give us the range from the camera to the object. If the range is less than the closest object encountered so far, we capture that range and the reference to the object. Once we have finished iterating through the objects, we check to see if we have found any red posts. If we have, we calculate the relative bearing to the object and set three facts in the Thinker . The first fact is a flag that indicates we can see a red post by being set to one. The other two facts are the range and bearing that we calculated. If no red posts were seen, then the flag fact is set to zero to indicate the fact.
The next section of code provides the same check for the nearest blue post. After that, we want to look for the nearest obstacle. We will consider the trees and other vehicles as obstacles for this example. We will not worry about the posts or bushes. These will not cause any damage to our vehicle if we hit them. The loop to check for obstacles is similar to the one we used for posts. The major difference is that we calculate the bearing to the object for each object and only include the object as a candidate if the absolute value of the bearing is within 5 degrees.
Putting Decisions to Work ”Action Methods
The sensor methods provide the inputs to the Thinker . To put the decisions of the Thinker into action requires the action methods that are executed within the current state. These methods may be as simple or complex as required to do a specific task. The key is that the task should be quite specific. If we overgeneralize the tasks, we are actually embedding the decision logic within the task itself. Although this may achieve the desired results in the short- term , it reduces the effectiveness of being able to tailor the Thinker through the knowledge files.
The car dynamics model that we will be using for both the player and opponent vehicles requires three control inputs: steering, brake pedal, and accelerator. The player will be using a joystick, mouse, or keyboard to control these inputs. For the opponents, we will use action methods that adjust these values within the dynamics model. The five action methods are shown in Listing 8 “54. These methods ( SteerLeft , SteerStraight , SteerRight , HitTheBrakes , and Accelerate ) will be called every iteration that the associated state remains active. This allows us to adjust the values gradually over time, thereby making the control changes more natural. When we are driving and decide to turn the steering wheel to the left, the wheel does not move immediately to the left extreme. It moves gradually toward the desired position. If the reason we were turning goes away (our state changes), we stop moving the wheel in that direction and move it back to center. These actions behave the same way. Each of these methods is a member of the Opponent class of the game application.
Listing 8.54: Action Methods void SteerLeft(Thinker thinker) { Opponent self = (Opponent)thinker.Self; if (self.Steering > 1.0) self.Steering = self.Steering 0.01f; } void SteerStraight(Thinker thinker) { Opponent self = (Opponent)thinker.Self; if (self.Steering > 0.0) self.Steering = self.Steering 0.01f; else if (self.Steering < 0.0) self.Steering = self.Steering + 0.01f; } void SteerRight(Thinker thinker) { Opponent self = (Opponent)thinker.Self; if (self.Steering < 1.0) self.Steering = self.Steering + 0.01f; } void HitTheBrakes(Thinker thinker) { Opponent self = (Opponent)thinker.Self; self.Gas = 0.0f; if (self.Brake < 1.0) self.Brake = self.Brake + 0.1f; } void Accelerate(Thinker thinker) { Opponent self = (Opponent)thinker.Self; self.Brake = 0.0f; if (self.Gas < 1.0) self.Gas = self.Gas + 0.1f; } Initializing the Opponent
Earlier in this chapter, I mentioned the Opponent class. This class is not part of the game engine. It is a class within the game application that uses the engine. Since it is part of the game, it is allowed to have game-specific logic and code. This class inherits from the Car class, which is also defined in the game application. We will look more closely at the Car class in Chapter 10 when we discuss physics. Suffice it to say at this point that the Car class inherits from the game engine s Model class and controls the movement of the model with a car physics class.
The Opponent class extends the Car class even further by adding Thinker control of the physics inputs. You have already seen the sensor method and action methods that are defined within this class. The remainder of the class is shown in Listing 8 “55. The attributes of this class are a Thinker object and a Camera object. An Eyes property provides external access to this opponent s camera.
Listing 8.55: Opponent Class public class Opponent : Car { #region Attributes private Thinker m_thinker; private Camera m_camera; #endregion #region Properties public Camera Eyes { get { return m_camera; } } #endregion public Opponent(string name, string meshFile, Vector3 offset, Attitude adjust, string knowledge) : base (name, meshFile, offset, adjust) { m_camera = new Camera (name + "cam"); m_camera.Attach(this, new Vector3(0.0f, 0.0f, 0.0f)); Thinker.AddAction("SteerLeft", new Thinker.ActionMethod(SteerLeft)); Thinker.AddAction("SteerStraight", new Thinker.ActionMethod(SteerStraight)); Thinker.AddAction("SteerRight", new Thinker.ActionMethod(SteerRight)); Thinker.AddAction("HitTheBrakes", new Thinker.ActionMethod(HitTheBrakes)); Thinker.AddAction("Accelerate", new Thinker.ActionMethod(Accelerate)); m_thinker = new Thinker(this); m_thinker.AddSensorMethod(new Thinker.SensorMethod(DriverView)); m_thinker.Read(knowledge); } The camera is created and attached to the class s model so that it moves with the car. Each of the action methods is registered with the Thinker class so that references to the methods can be associated with the states as they are created. The Thinker for the class is created with a reference of this instance of the class. The sensor method is provided to the Thinker and its knowledge is loaded from the XML file. When a "RaceStarted" fact is set to true by the main game application, this car will be off and running.
