Creating a C++ Scripting System - part II

Преводни и оригинални статии в областта на разработката на игри.
gemicha
Site Admin
Site Admin
Мнения: 2930
Регистриран: 20 ное 2003 22:20
Местоположение: USA

Creating a C++ Scripting System - part II

Мнение от gemicha » 23 фев 2004 23:29

Creating a C++ Scripting System - part II
Автор: Емил Дочевски
Публикувана: Game Developer Magazine

Predicates

Using function objects to perform actions on an entire set of objects is a powerful feature by itself, but it becomes even more powerful if we define another version of the X function that allows us to call the function object only for selected objects in a set:

Код: Избери всички

template <class Set,class Pred,class Functor>
void X( const Set& set, Pred p, Functor f ) 
{
  for( typename Set::const_iterator i=set.begin(); i!=set.end(); ++i )
  if( p(*i) )
    f(*i);
}

A predicate is a special type of function object that checks a given condition. For example, we can define the following predicate:

Код: Избери всички

struct HasArmor 
{
  bool operator()( const CActor* pObj ) const 
  {
    return pObj->HasArmor();
  }
}
Now we can write something like:

Код: Избери всички

X( grunts, HasArmor(), Attack() );
This will execute the Attack functor on the members of the
grunts set that are armored. Again, exposing the armor property
of objects of class CActor to the script is as easy as writing a simple
predicate.

Type Predicates
In the preceding examples, because Attack::operator() takes CActor* as an argument, the Attack functor can only be used with sets of objects of class CActor. Because any object of class CGrunt is also of class CActor, we can use the Attack functor with a set of grunts too. But what if we have a set of objects of class CRoot? It would be nice to be able to select only the objects of class CActor and execute Attack on them.

To do this, we need our predicates to define an output_type. Then we can design our system so that if an object passes a predicate, we can assume it is of class output_type that the predicate defines. For example, we could use the predicate IsActor that checks if a given object is of class CActor:

Код: Избери всички

struct IsActor 
{
  typedef CActor output_type;
  bool operator()( const CRoot* pObj ) const 
  {
    return 0!=dynamic_cast<const CActor*>(pObj);
  }
};
Note in this case that some compilers do not implement dynamic_cast efficiently because it has to work in nontrivial cases such as multiple inheritance and the like. Instead of dynamic_cast, we could use a virtual member function to do our type checks.

We also need to modify the predicate version of our X template
function:

Код: Избери всички

template <class Set,class Pred,class Functor>
void X( const Set& set, Pred p, Functor f ) 
{
  for( typename Set::const_iterator i=set.begin(); i!=set.end(); ++i )
  if( p(*i) )
    f( static_cast<typename Pred::output_type*>(*i) );
}
The output_type defined by our predicates makes it safe for the X template function to use a static_cast when calling the functor.
Now, if we have a set of objects of class CRoot, we can write:

Код: Избери всички

X( objects, IsActor(), Attack() );
Complex Predicates

So now we have seen how to use predicates to execute a functor on selected objects from a given set of objects. But what if we want to combine multiple predicates to select the objects we need?

Generally speaking, it’s easy to combine multiple simple predicates in a single complex predicate that our X function can check. As an example, let’s define a predicate called pred_or:

Код: Избери всички

template <class Pred1,class Pred2>
struct pred_or {
  Pred1 pred1;
  Pred2 pred2;
  pred_or( Pred1 p1, Pred2 p2 ): pred1(p1),pred2(p2) {
  }
  bool operator()( const CActor* pObj ) const {
     return pred1(pObj) || pred2(pObj);
  }
};
To make it possible to use pred_or without having to explicitly provide template arguments, we can define the following helper function template:

Код: Избери всички

template <class Pred1,class Pred2>
pred_or<Pred1,Pred2> Or( Pred1 p1, Pred2 p2 ) 
{
   return pred_or<Pred1,Pred2>(p1,p2);
}

Код: Избери всички

//LISTING 2. Defining pred_or.

template <class Pred1,class Pred2>
struct pred_or {
  typedef typename select_child<
  typename Pred1::input_type,
  typename Pred2::input_type>::type
  input_type;
  typedef typename select_root<
  typename Pred1::output_type,
  typename Pred2::output_type>::type
  output_type;
  Pred1 pred1;
  Pred2 pred2;
  pred_or( Pred1 p1, Pred2 p2 ): pred1(p1),pred2(p2) {
  }
  bool operator()( const input_type* pObj ) const {
     return pred1(pObj) || pred2(pObj);
  }
};
With the Or function template in place, we can use pred_or to combine the HasArmor and the HasWeapon predicates:

Код: Избери всички

X( grunts, Or(HasArmor(),HasWeapon()), Attack() );
But wait, why did we define pred_or::operator() to take CActor*? This is not ideal, because we want pred_or to be able to combine predicates that take objects of different classes. In addition, our X function requires us to define an output_type. What is the output_type for pred_or?

Let’s extend our system to require that the predicates define not only output_type but also input_type, which is the class of objects the predicate can be checked for. With this in mind, let’s define pred_or as shown in Listing 2.

For this to work, we need two helper template classes, select_child and select_root. We see how they work later, but for now let’s just assume the following: select_root<T,U>::type is defined as the first class in the class hierarchy that is common parent of both T and U, or as void if T and U are unrelated. For example, select_root<CGrunt,CAgent>::type will be defined as CActor.

select_child<T,U>::type is defined as T if T is a (indirect) child class of U, as U if U is a (indirect) child class of T, or as void otherwise. For example, select_child<CRoot,CGrunt>::type is defined as CGrunt, while select_child<CGrunt,CAgent>::type is defined as void.

Indeed, for pred_or::operator() to return true, either the first or the second predicate should have returned true. Since we do not know which predicate returned true, our output_type is the root class of the output_types defined by the Pred1 and Pred2 predicates.

Similarly, because Pred1::operator() takes objects of class Pred1::input_type, and Pred2::operator() takes objects of class Pred2::input_type, pred_or::operator() must take objects that are of both class Pred1::input_type and class Pred2::input_type. This is why we need select_child.

Now let’s define pred_and as shown in Listing 3. Here, the static_cast is justified because C++ always evaluates the left side of operator&& first, and then evaluates the right side only if the left side was true — and we know that if an object passes Pred1, it is of class Pred1::output_type.

Код: Избери всички

//LISTING 3. Defining pred_and.
template <class Pred1,class Pred2>
struct pred_and {
  typedef typename Pred1::input_type input_type;
  typedef typename select_child<typename Pred1::output_type,
  typename Pred2::output_type>::type output_type;
  Pred1 pred1;
  Pred2 pred2;
  pred_and( Pred1 p1, Pred2 p2 ): pred1(p1),pred2(p2) {
  }
  bool operator()( const input_type* pObj ) const {
    return pred1(pObj) &&
              pred2(static_cast<const typename
                        Pred1::output_type*>(pObj));
  }
};
Let’s extend the definition of HasArmor to define input_type and output_type as required:

Код: Избери всички

struct HasArmor {
  typedef CActor input_type;
  typedef input_type output_type;
  bool operator()( const input_type* pObj ) const {
    return pObj->HasArmor();
  }
};
Now, if we have a set of objects of class CRoot, we can do something like this (assuming we have defined a function template And similar to the function template Or):

Код: Избери всички

X( objects, And(IsActor(),HasArmor()), Attack() );
We can even combine pred_and and pred_or in an even more complex predicate expression:

Код: Избери всички

X( objects, And(IsActor(),Or(HasArmor(),HasWeapon())), Attack() );
To complete our set of complex predicates, let’s define pred_not. Because not satisfying a predicate does not give us any additional information about an object, pred_not::output_type is the same as its input_type:

Код: Избери всички

template <class Pred>
struct pred_not {
  typedef typename Pred::input_type input_type;
  typedef input_type output_type; 
  Pred pred;
  pred_not( Pred p ): pred(p) {
  }
  bool operator()( const input_type* pObj ) const {
     return !pred(pObj);
  }
};
Besides being powerful, the complex predicates we defined are also type-safe. Consider the following example:

Код: Избери всички

X( objects, Or(IsActor(),HasArmor()), Attack() );
If used with our class hierarchy, the above example will not compile. This is because if an object passes the predicate, it may or may not be of class CActor, and the compiler will generate a type mismatch error when trying to call HasArmor::operator(). However, if we used And instead of Or, there would be no compile error due to the static_cast in pred_and::operator().

Predicate Expressions

So far, our predicate system is pretty powerful, but nested predicate expressions are not fun. We need to be able to use a more natural syntax. For example, instead of

Код: Избери всички

X( objects, And(IsActor(),HasArmor()), Attack() );
we want to be able to write:

Код: Избери всички

X( objects, IsActor() && HasArmor(), Attack() );
The obvious solution to this problem is to overload the operators we need for predicates. For the system to work, we need to overload the operators in a way that can be used for any predicates, including custom predicates defined further in our project.

However, if we define operator&& the way we earlier defined the Or function template, it would be too ambiguous — we need a definition that the compiler will consider for predicates only. To achieve this, we need some mechanism to distinguish between a predicate and any other type. One way of doing this is to have all our predicates inherit from this common class template:

Код: Избери всички

template <class T>
struct expr_base {
  const T& get() const {
    return static_cast<const T&>(*this);
  }
};
For example, let’s define pred_and like this:

Код: Избери всички

template <class Pred1,class Pred2>
struct pred_and: public expr_base<pred_and<Pred1,Pred2> >{
...
};
With this trick, we can overload operator&& like so:

Код: Избери всички

template <class Pred1,class Pred2>
pred_and<Pred1,Pred2>
operator&&( const expr_base<Pred1>& p1, const expr_base<Pred2>& p2 ) {
  return pred_and<Pred1,Pred2>(p1.get(),p2.get());
}
Following this pattern, we can overload operator || and operator !. Now we can build Boolean predicate expressions that follow the natural C++ syntax, while also taking advantage of the operator precedence defined by the language.

This technique of building an expression tree through operator overloads is commonly known as Expression Templates (see Veldhuizen in For More Information).

Numerical Predicates

Predicates are usually defined as Boolean functions, but we can extend our definition of predicate to include numerical predicates. This is useful for exposing non-Boolean properties of objects. For example:

Код: Избери всички

struct Health {
  typedef CActor input_type;
  typedef input_type output_type;
  int operator()( const input_type* pObj ) const {
    return pObj->GetHealth();
  }
};
Of course, the predicate version of the X template function treats all predicates as Boolean. We can use the Health predicate directly, but then we would only be able to check if the health of an actor is not 0 (or we can check for 0 if we use pred_not).
Obviously, we need to be able to check for other values as well.
So, we can define the following predicate:

Код: Избери всички

template <class Pred,class Value>
struct pred_gt: public expr_base<pred_gt<Pred,Value> > {
  typedef typename Pred::input_type input_type;
  typedef typename Pred::output_type output_type;
  Pred pred;
  Value value;
  pred_gt( Pred p, Value v ): pred(p),value(v) {
  }
  bool operator()( const Pred::input_type* pObj ) const {
    return pred(pObj)>value;
  }
};
Similarly to the case of pred_or, pred_and, and pred_not, we can overload the > operator to provide access to pred_gt:

Код: Избери всички

template <class Pred,class Value>
pred_gt<Pred,Value>
operator>( const expr_base<Pred>& p, Value v ) {
  return pred_gt<Pred,Value>(p.get(),v);
}
Now, we can do something like:

Код: Избери всички

X( grunts, Health()>5, Attack() );
This will execute the Attack functor only on the objects with health greater than 5. As any other predicate that defines input_type and output_type, we can combine pred_gt in complex predicate expressions. For example:

Код: Избери всички

X( objects, IsGrunt() && (Health()>5 || HasArmor()), Attack() );
Following this pattern, we can overload all other comparison operators: <, >=, <=, ==, and !=.

Продължава ...

Отговори