Visitors – Part I: Identifying the problem

Today I’m going to talk about the Visitor pattern and its usage within the engine. Visitors are a powerful tool used to perform scene traversal operations, like updating world transformation, computing bounding volumes, gathering debug information, updating components, rendering the scene, etc.

Since this is a long topic I decided to split it into several parts, with this one serving as a kind of introduction. So without further ado, let’s get started.

It was late 2007 and Crimild was a lot different than it is right now. By that time, I was following Dave Everly’s design (almost) by heart, dealing with several classes implementing each of the different node types conforming the scene graph hierarchy. Scene traversal operations were limited to a couple of scene updates calls, the rendering pass and collision tests and the entire scene graph was implemented following a variation of the composite pattern, as follows:

Notice how the doSomething() method is propagated throughout the entire class hierarchy

As my experience with scene graphs increased, I started to notice the rising cost of adding new scene traversal operations, requiring the modification of pretty much all of the classes in the hierarchy. For example, in order to add an operation for printing the name and type of all nodes in the hierarchy required to add a new abstract (or virtual) function at the top of the hierarchy (the Node class) and then override it in each of the subclasses (notice the doSomething method in the class diagram above).

Let’s take a break for a moment so I can introduce you to Behaviors. You’ll see the reason behind this soon enough.

The inclusion of Node Behaviors (an early implementation of what is currently known as Node Components) assisted me in the task of reducing the number of core classes, shifting the mechanism for extending the scene graph implementation from inheritance to composition. I’ll talk about behaviors/components in another post, but if you have no idea about the Game Object Component “pattern”, just think about the Strategy Pattern. It’s not the same thing, but it will give you an idea about where this is going.

Anyway, by using behaviors game objects could be created by instantiating any of the standard Node-derived class (GeometryNode, GroupNode, etc.) with one ore more behaviors attached to it. So I ended up with a class hierarchy resembling the following diagram:

Only a handful of nodes and lots of behaviors

This new design ensured a high stability for the Node class hierarchy. It was unlike for developers to create new Node-derived classes, since all of the game specific logic was enclosed in behaviors.

With a stable hierarchy and an ever increasing number of scene traversal operations, that seamed to be perfect scenario for implementing the Visitor pattern. As a side note, I spent some time researching open source engines like OpenSceneGraph and noticed they were already using visitors for scene traversal which gave me the confidence to move forward.

That’s it for today. Next week we’ll talk about how visitors are implemented and used in Crimild.  Stay tunned


One thought on “Visitors – Part I: Identifying the problem

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s