Jump to content
  • Advertisement
Sign in to follow this  
  • entries
  • comments
  • views

Implementing the preciousss

Sign in to follow this  


Even though the enthusiasm about the last post about scene management wasn't as overwhelming as the previous one (0 comments instead of the whopping 4), I'm determined to continue. Tonight, I'm going to tell an epic tale about the current implementation of my scene graph.

So, the nodes are in a tree, with only the root node assigned to the World object. A trivial implementation just walked the whole tree each step while each worker processed each node. Slow. A tree is far from the best structure for all the workers, and nodes that are not interesting to a worker shouldn't be processed at all. So, how to keep track of changes to the tree structure and its attributes? Callbacks? No; since a node could potentially be in multiple worlds at a time, a single callback won't do. Signals! Signals are more or less functors implementing the Observer pattern, and here's the trivial implementation and an example of usage:

class Signal(object):
def __init__(self):
self.slots = []

def connect(self, slot):

def disconnect(self, slot):

def __call__(self, *args, **keyargs):
for slot in self.slots:
slot(*args, **keyargs)

foo = Signal()
foo("hi there", 2)

This would result in calls to bar("hi there", 2) and baz("hi there", 2). The Node class has signals for added child nodes, removed child nodes, new (or replaced) attributes and removed attributes. When the World object's rootNode is set, it connects to the node's and all child nodes' signals. When the new node or removed node signals are fired, its signals are connected to or disconnect from, respectively. All signal calls are forwarded to all workers. This is essentially what all caching in the workers is based on, and allows them to have the node in any data structure that best suits their purposes. Here's the code for the added and removed attributes signals, implemented by replacing the attribute setter and getter methods respectively (for those who don't know Python, if you type eg. myNode.foo = 5, it results in a call to Node.__setattr__(myNode, "foo", 5), and attributes whose name starts with an underscore are considered private):

def __setattr__(self, name, value):
object.__setattr__(self, name, value)

if not name.startswith("_"):
self.dirtyAttributeSignal(self, name, value)

def __delattr__(self, name):
object.__delattr__(self, name)

if not name.startswith("_"):
self.removedAttributeSignal(self, name)

Note that no signals are fired for private attributes, since these are used by workers for internal bookkeeping and caching. You might think this is too slow, but modifying the attributes of a node happens far less than using them, so this optimization makes sense. For example, the Space class (as mentioned previously, responsible for spatial relations of nodes) stores nodes in both a list and a space object of ODE for collision detection. Later, it'll be easy to write another space class using an octree or some other more optimized structure without changing the API. Here's how the signal handlers of Space are implemented (I've ripped out some lines irrelevant to the discussion):

def _newNode(self, node):

if hasattr(node, "collisionGeometry"):

def _removedNode(self, node):

if hasattr(node, "collisionGeometry"):

def _dirtyAttribute(self, node, name, value):
if name == "collisionGeometry":

def _removedAttribute(self, node, name):
if name == "collisionGeometry":

def _updateODEGeometry(self, node):
odeGeom = node.collisionGeometry
self._ode.SpaceAdd(self._odeSpace, odeGeom)

def _removeODEGeometry(self, node):
odeGeom = node.collisionGeometry
self._ode.SpaceRemove(self._odeSpace, odeGeom)

(I just realized I could optimize this by passing collisionGeometry to the ODE integration methods and save an attribute lookup) The Physics worker doesn't use any structure to store nodes, since everything is handled by ODE. The Audio and Logic workers use simple lists. The Renderer still walks the graph, but it's a bit more optimized now, and I have quite a few optimization ideas left (there's not even frustum culling implemented yet). And this is all there is to it. Nothing magical (well, except that Python's special attributes whose name is like __something__ are sometimes called magic attributes), but it's really flexible with a simple API that doesn't need to change at all when new features are added or old ones reimplemented or optimized.

I hope this was useful to some people, and I'll gladly answer any questions you might have about the details. If there's interest, I'll continue describing other parts of my engine. Well, at least the parts that I'm happy with. :) Would you like to hear more details about the renderer? Or resource management? Or maybe I should post about the identity crisis of my geometry package, as I'd like some feedback on the issue.

Later, folks.

Btw, I started on my game project this morning. Expect fabulous screenshots in a couple of days.
Sign in to follow this  


Recommended Comments

Thanks for the detailing. I totally forgot about this journal since my last reaction as the last days have been a bit hectic.

I'm not entirely certain I grasp how this works. Presumably each node could possibly store a matrix modifier for example. Does that mean that the renderer would need to store all those nodes in a tree as well somehow? And how about 3D sound?

Share this comment

Link to comment
Wow, Signals look really useful. Big thanks for writing this post up.

I think i'm missing the big picture, possibly due to my novice python skills. Perhaps a sequence or some sort of flow diagram that shows how you use signals in your scene graph would help (only if you have the time!).

Regardless, thanks for the informative journal entry.

Share this comment

Link to comment
Wow, I now have a newfound respect for Python - coding that kind of system in C++ would have been painful, and couldn't possibly have been as elegant...

I think I have fallen in love with __setattr__...

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!