Elysian Shadows

Posted: **Wed Apr 18, 2012 10:37 pm**

The concept of Behaviours, or Components, is an alternative to inheritance-based construction of an entity in a game engine. AIGD chapter 17, part 2 (that sounds almost biblical) has a good explanation about this. Basically, what you have is a base Entity class which has references to behaviours that define how it acts, instead of inheriting from a class (which may inherit from another, which may inherit from another, etc). Inheritance is static and difficult to change at redesign-, compile- and run-time.

The common form of a behaviour-based engine is to have behaviour classes to represent aspects of the entities in the game, so:

Code: Select all

class Behaviour {
    public:
        virtual Entity * parent() = 0;
};

class MoveBehaviour : public Behaviour {
    public:
        virtual void update() = 0;
};

class InteractBehaviour : public Behaviour {
    public:
        virtual void interactWith(Entity * other) = 0;
};

// ...

And so on. I'm keeping the interfaces simple, so it doesn't cloud the main subject. Then your Entity and some code that uses it, would be something like:

Code: Select all

class Entity {
    public:
        virtual MoveBehaviour * moveBehaviour() = 0;
        virtual InteractBehaviour * interactBehaviour() = 0;
        // And a pointer to each kind of behaviour an Entity might possibly have.
};

// ...

NPC * createNPC() {
    auto_ptr<Entity> npc(new NPC);
    npc->addMoveBehaviour(new RandomMoveBehaviour);
    npc->addInteractBehaviour(new AttackOnSightBehaviour);
    return npc.release();
}

void update(Entity * e) {
    if(e->moveBehaviour())
        e->moveBehaviour()->update();
}

Think about that comment on Entity's declaration. If you have a long list of Behaviour's, you have to store a pointer to each one, so Entity's in your game can have any kind of Behaviour attached. Also, you can't have more than one Behaviour of each kind (which could be solved by having a data structure to hold any number of MoveBehaviours, another for InteractBehaviours, etc, but read on).

The alternative I'm going to propose aims at providing a generalization to avoid these unneeded pointers, while still maintaining the full power of behaviours. First, we change Entity to store a list (more on this later) of Behaviours.

Code: Select all

class Entity {
    public:
        list<Behaviour *> behaviours() = 0;
        void addBehaviour(Behaviour * behaviour) = 0;
};

NPC * createNPC() {
    auto_ptr<Entity> npc(new NPC);
    npc->addBehaviour(new RandomMoveBehaviour);
    return npc.release();
}

But the problem is we now lost any record of the type of the elements on the list. How do you know which elements are MoveBehaviours, etc? In comes the Visitor design pattern, described on the great book Design Patterns, by the Gang of Four. As a quick side note, I highly recommend that book to intermediate programmers. But back to topic. A small change to Behaviour and a new BehaviourVisitor class:

Code: Select all

class Behaviour {
    public:
        virtual Entity * parent() = 0;
        virtual void accept(BehaviourVisitor * visitor) = 0;
};

class BehaviourVisitor {
    public:
        visitMoveBehaviour(MoveBehaviour *) {}
        visitInteractBehaviour(InteractBehaviour *) {}
        // One visit* method for each of Behaviour subclasses.
};

The accept method is the whole idea behind Visitor. Inside Behaviour subclasses' methods, the type is know (it's a member function, after all). So each subclass, inside accept class the appropriate method on the visitor:

Code: Select all

void MoveBehaviour::accept(BehaviourVisitor * visitor) {
    visitor->visitMoveBehaviour(this);
}

// ...

void InteractBehaviour::accept(BehaviourVisitor * visitor) {
    visitor->visitInteractbehaviour(this);
}

A BehaviourVisitor subclass can do pretty much anything inside the visit* methods. Here is a useful one:

Code: Select all

class BehaviourFilter : public BehaviourVisitor {
    public:
        enum class Type {
            MOVE, INTERACT
        };

        BehaviourFilter(Type type) : m_type(type) {}
        list<Behaviour *> filter(list<Behaviour *> behaviours);

        void acceptMoveBehaviour(MoveBehaviour * moveBehaviour);
        void acceptInteractBehaviour(InteractBehaviour * interactBehaviour);

    private:
        Type m_type;
        list<Behaviour *> m_result;
};

list<Behaviour *> BehaviourFilter::filter(list<Behaviour *> behaviours) {
    result.clear();

    for(Behaviour * b : behaviours)
        b->accept(this);

    return result;
}

void BehaviourFilter::visitMoveBehaviour(MoveBehaviour * moveBehaviour) {
    if(m_type == Type::MOVE)
        result.push_back(moveBehaviour);
}

void BehaviourFilter::visitInteractBehaviour(InteractBehaviour * interactBehaviour) {
    if(m_type == Type::INTERACT)
        result.push_back(interactBehaviour);
}

And an use for it:

Code: Select all

void updateMoves(list<Entity *> entities) {
    BehaviourFilter filter(BehaviourFilter::Type::MOVE);

    for(Entity * e : entities) {
        for(Behaviour * b : filter.filter(e->behaviours())) {
            MoveBehaviour * moveBehaviour = dynamic_cast<MoveBehaviour *>(b);
            moveBehaviour->update();
        }
    }
}

Even though the code setup is really big (considering a real engine, with several types of behaviours) I hope you can see that the usage is the same as the original example, if it used a list of each kind of Behaviour.

This is getting really long, so I think I'll split it into sessions. I don't suppose many (if any) will read this, but, if you did, I'd really appreciate if you shared your thoughts about it.

Posted: **Wed Apr 18, 2012 11:05 pm**

As any (good) alternative, here are the famous lists (kind of sorted by relevance):

Advantages:

Each Entity object won't be filled with pointers it might not really need. Depending on the data structure you choose, no behaviours mean almost no space.
Doesn't require any "type field" or down-cast tests. The only down-casts used used in my example are on the code that uses BehaviourFilter, which are completly type-safe (assuming correctly implemented BehaviourFilter's).
Adding BehaviourVisitor subclasses (i.e., algorithms that iterate over behaviours) is easy. All you have to do is create a new subclass that will do the job, no other files have to be recompiled.
The code for each algorithm is centralized on a single class, BehaviourFilter subclasses. The algorithm's state can be stored on the class, like the result list on BehaviourFilter.
Visitor makes it easy to add operations you didn't think about when designing. We could make a BehaviourGUIFactory that created specific Widgets for each kind of Behaviour (for example), without adding a single line of code to the game engine.
Entity::behaviour provides a single accessor for all behaviours.

Disvantages (still working on it...):

Adding Behaviour subclasses is difficult. You have to change BehaviourFilter's interface to add a new visit* method, and, if you do not provide an implementation for it (make it abstract), you have to change each of its subclasses and add it. Of course, for classes like BehaviourFilter to work properly, you have to add the new method and update the enum, but it won't break anything until you do. Since all Behaviour subclasses use BehaviourVisitor, they would have to be recompiled.
Counter: using the original approach, Entity would have to be updated, to include a pointer to the new Behaviour (incuring the same problem already cited), and any code that uses it will have to be recompiled. Also, after a point in development, it is much more likely that you'll be adding new functionalities, instead of altering the structure of Entity.
You have to search the whole list every time you need to access one.
Counter: if there are few behaviours, it will hardly matter, and that's the case for most entities. On other cases, it probably won't matter too. You can always make a visitor that stores one list for each kind of Behaviour, and access them. But what you gain in flexibility is usualy better than whatever performance you might have.
It's really a lot of code, and it's much harder to understand.
Counter: the idea behind libraries (which is what a game engine really is, in the end) is to make the life of the user easier, not the programmer. As stated above, the setup code is daunting, but its usage is pretty simple.
You have to refactor all the code you already have.
Counter: Yeah, that is bad. But evolution requires change.

Posted: **Thu Apr 19, 2012 8:35 am**

Could you not link the Behavior methods to a Lua script? Not sure what advantages/disadvantages would be present in that scenario as I'm just starting to review Lua Scripting. Also wouldn't pointers take up less memory space than a list?

Posted: **Thu Apr 19, 2012 8:56 am**

mattheweston wrote:Could you not link the Behavior methods to a Lua script? Not sure what advantages/disadvantages would be present in that scenario as I'm just starting to review Lua Scripting.

Yes, you can replace behaviours with scripts, but that would take away much of the flexibility of this approach. You can add and remove behaviours dynamically, combinine behaviours, etc. That would be harder to do with scripts.

mattheweston wrote:Also wouldn't pointers take up less memory space than a list?

Depends on the data structure you use. Without getting on the merits of each kind of data structure, a list would take only the space needed for the number of behaviours that specific object uses, as opposed to one pointer to each kind of behaviour the engine supports (and the usual space that links use, one additional pointer for each element on the list). And if you wanted to support any number of each kind of behaviour using pointers, you'd need one list for each kind.

Posted: **Thu Apr 19, 2012 5:51 pm**

I can only slightly comprehend this, but as far as I can tell I love it.
If you could use an analogy though to explain, that'd be awesome!
“If you can't explain it simply, you don't understand it well enough” - Albert Einstein
Not saying you don't understand it well enough though :P (What is well enough?)

Posted: **Thu Apr 19, 2012 7:49 pm**

Yeah, I understand that. The first time I read the chapter from the book, I didn't get it either. I'll try to explain better, ~~if I can do it during my class.~~ Here it is:

The problem it is trying to solve is that, if you use a list of Behaviour's, once you store them, you loose the concrete type (you don't know if a Behaviour on the list is a Move- or InteractBehaviour). Visitor solves this using two functions, in different classes. A really bad/non-OO/maintenance-hell way of doing this is having a "type" field on Behaviour and do:

Code: Select all

void f(Entity * e) {
    for(Behaviour * b : e->behaviours()) {
        if(b->type() == Behaviour::MOVE) {
            MoveBehaviour * mb = dynamic_cast<MoveBehaviour *>(b);
            // fiddle with mb.
        }
    }
}

There are many problems with this, the classic problems OO was created to solve. The ideal situation would be:

Code: Select all

void f(Entity * e) {
    for(Behaviour * b : e->behavioursOfType(Behaviour::MOVE)) {
        MoveBehaviour * mb = dynamic_cast<MoveBehaviour *>(b);
        // fiddle with mb.
    }
}

To do that, you use the visitor. You call each Behaviour object's accept method, passing the visitor. This will call the accept of the subclass, since it's a virtual method. Inside that method, you know what type of Behaviour that object is. accept on a MoveBehaviour will call MoveBehaviour::accept, while on a InteractBehaviour will call InteractBehaviour::accept. So, inside these methods, we can call the appropriate method on the visitor, BehaviorVisitor::visitMoveBehaviour and BehaviourVisitor::visitInteractBehaviour, respectivly. Then, on these methods, you can put the code for the subclass-specific parts.

Code: Select all

void f(Entity * e) {
    BehaviourFilter filter(BehaviourFilter::MOVE);

    for(Behaviour * b : filter.filter(e->behaviours())) {
        MoveBehaviour * mb = dynamic_cast<MoveBehaviour *>(b);
        // fiddle with mb.
    }
}

You can even create a wrapper function to avoid creating a BehaviourFilter just to filter one list.

Anyway, I hope it becomes a little bit more clear.

Posted: **Thu Apr 19, 2012 11:35 pm**

OK, on the bus home, I thought of an analogy. I'll provide an image, too, so it's easier to see.

Suppose person1, working for company1, wants to call person2, working for company2, but companies don't share private phones. So person1 calls secretary1, and tells her to call company2. secretary1 calls company2, using company2's phone, and is answered by secretary2. secretary2, who knows the internal phones of comapany2, forwards the call to person2.

So: person1 is the engine's code. It needs to use specific methods from a subclass of Behaviour, which is person2. But all it has is company2's phone, the public interface of class Behaviour. So it tells secretary1 to call the company, and she is answered by secretary2, which calls person2. This is analogous to:

secretary1 calls company2: the engine calls Behaviour::accept, the public interface of the Behaviour class, company2.
secretary2 answers and forwards to person2: the specific overridden method on the subclass is called.
person2 gets a direct connection with secretary1: the overridden accept method calls the appropriate visit* method on Visitor.

The final line of communication, the green line, is how the code looks like. The visitor (secretary1) manipulates person2 as person1 instructed it. The red line represents the call stack: Behaviour::accept, SomeConcreteBehaviour::accept, SomeConcreteVisitor::visitSomeConcreteBehaviour.

Wasn't that fun?

Elysian Shadows

Behaviour/Component design

Behaviour/Component design

Re: Behaviour/Component design

Re: Behaviour/Component design

Re: Behaviour/Component design

Re: Behaviour/Component design

Re: Behaviour/Component design

Re: Behaviour/Component design