SceneGraph Sample

So, scene graphs! I used to love the darned things, but now I have some mildly mixed feelings on them. Regardless, they're still pretty awesome, so I whipped up a quick bit of sample code! (Full source can be found at the bottom of the article)

But first, a quick description of what a scene graph is. It's basically a tree-like structure used to represent the data in your game's scene. The advantage of using a tree structure, is that you can use the parent/child relationship to inherit information, like position and orientation! This can make it extremely easy to do things like... stick arrows into people's knees! Or a helmet on top of your player's head, y'know, possibly even things like containers and inventories.



Just re-using an illustration I made last time I talked about scene graphs. It's still pertinent ;)

As it so happens, it's not all that hard to do this through code. So here's a quick 3D example of using a scene graph inside of XNA 4.0.

It's impossible to use a DrawableGameComponent for our scene graph nodes, primarily because the LoadContent method is declared as protected, but if you're familiar with XNA, then you'll notice that the SceneNode class very much resembles a DrawableGameComponent.

class SceneNode
    {
        #region Fields
        /// <summary>
        /// A list of child SceneNodes underneath this node.
        /// </summary>
        List<SceneNode> mChildren;
        #endregion

        #region Properties
        /// <summary>
        /// Our link back to the game that created us, allows us to add content and the like
        /// </summary>
        public Game        Game      { get; protected set; }
        /// <summary>
        /// The parent node in the SceneGraph heirarchy, if this is null, then it has to 
        /// be the top item in the tree.
        /// </summary>
        public SceneNode   Parent    { get; protected set; }
        /// <summary>
        /// A 3D location and orientation! Does cool things, check it =D
        /// </summary>
        public Transform3D Transform { get; set; }
        /// <summary>
        /// Sets whether or not this node is drawing. Defaults to true.
        /// </summary>
        public bool        Visible   { get; set; }
        /// <summary>
        /// This sets if the node will actually update and draw, it might be a productive 
        /// idea to attach an event of some sort to this property. Defaults to true.
        /// </summary>
        public bool        Enabled   { get; set; }
        /// <summary>
        /// This is the transform matrix that takes into consideration all of the parent
        /// node locations.
        /// </summary>
        public Matrix      TransformMatrix
        {
            get
            {
                if (Parent == null)
                    return Transform.Transform;
                else
                    return Transform.Transform * Parent.TransformMatrix;
            }
        }
        #endregion

        #region Constructor
        /// <summary>
        /// Basic constructor, copies and initializes values
        /// </summary>
        /// <param name="aGame">A link to the game that created us!</param>
        /// <param name="aParent">The parent node for this SceneNode, can be null to indicate a top level SceneNode</param>
        public SceneNode(Game aGame, SceneNode aParent)
        {
            Game      = aGame;
            Parent    = aParent;
            Visible   = true;
            Enabled   = true;
            mChildren = new List<SceneNode>();
            Transform = new Transform3D();

            // if there is a parent object, add this object to the parent's children
            if (Parent != null)
                Parent.mChildren.Add(this);
        }
        #endregion

        #region Virtual methods
        public virtual void Initialize ()
        {
            // initialize all child nodes
            for (int i = 0; i < mChildren.Count; i++)
                mChildren[i].Initialize();
        }
        public virtual void LoadContent()
        {
            // load content for all child nodes
            for (int i = 0; i < mChildren.Count; i++)
                mChildren[i].LoadContent();
        }

        public virtual void Update(float aTime)
        {
            // update andy child nodes that are actually enabled
            for (int i = 0; i < mChildren.Count; i++)
                if (mChildren[i].Enabled)
                    mChildren[i].Update(aTime);
        }
        public virtual void Draw  (float aTime)
        {
            // draw them if they're visible, and enabled
            for (int i = 0; i < mChildren.Count; i++)
                if (mChildren[i].Visible && mChildren[i].Enabled)
                    mChildren[i].Draw(aTime);
        }
        #endregion
    }

And that's reasonably straightforward, there's really nothing all that tricky in there. After that's out of the way, all you need to do is.. either inherit from it, or set up a component system! Inheritance is the easiest, so here's an example of a basic 3D object that uses the SceneNode.

class Basic3DObject : SceneNode
    {
        #region Fields
        string mModelName;
        Model  mModel;
        #endregion

        #region Constructor
        public Basic3DObject(Game aGame, SceneNode aParent, string aModelName)
            : base(aGame, aParent)
        {
            // store for loading later
            mModelName = aModelName;
        }
        #endregion

        #region Overrides
        public override void LoadContent()
        {
            // load the model we have stored!
            mModel = Game.Content.Load<Model>(mModelName);

            // need this still, that way any child objects can still get loaded
            base.LoadContent();
        }

        public override void Draw(float aTime)
        {
            // Copy any parent transforms.
            Matrix[] transforms = new Matrix[mModel.Bones.Count];
            mModel.CopyAbsoluteBoneTransformsTo(transforms);

            // Draw the model. A model can have multiple meshes, so loop.
            foreach (ModelMesh mesh in mModel.Meshes)
            {
                // This is where the mesh orientation is set, as well 
                // as our camera and projection.
                foreach (BasicEffect effect in mesh.Effects)
                {
                    effect.EnableDefaultLighting();
                    effect.World      = transforms[mesh.ParentBone.Index] * TransformMatrix;
                    effect.View       = Camera.ViewMatrix;
                    effect.Projection = Camera.ProjectionMatrix;
                }
                // Draw the mesh, using the effects set above.
                mesh.Draw();
            }

            base.Draw(aTime);
        }
        #endregion
    }

And again, you can see it behaves almost exactly the same as a regular DrawableGameComponent! So it's not all that different from what you've already been working with~ Lastly, putting it all together in an example:

Spinning spaceships! Not the most practical thing, but hey.

public class Game1 : Microsoft.Xna.Framework.Game
    {
        GraphicsDeviceManager graphics;
        SpriteBatch spriteBatch;

        // scene nodes, for easy access
        SceneNode mRoot;
        SceneNode mCenterShip;
        SceneNode mMiddleShip1;
        SceneNode mMiddleShip2;

        SceneNode mOuterShip1;
        SceneNode mOuterShip2;
        SceneNode mOuterShip3;
        SceneNode mOuterShip4;

        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            Content.RootDirectory = "Content";
        }

        protected override void Initialize()
        {
            mRoot = new SceneNode(this, null);

            // set up a large ship in the center, everything will rotate around it
            mCenterShip = new Basic3DObject(this, mRoot, "Ship");

            // set up two orbiting ships, note that their parent is mCenterShip
            mMiddleShip1 = new Basic3DObject(this, mCenterShip, "Ship");
            mMiddleShip1.Transform.Position = new Vector3(500, 0, 0);
            mMiddleShip1.Transform.ScaleSc  = 0.5f;
            mMiddleShip2 = new Basic3DObject(this, mCenterShip, "Ship");
            mMiddleShip2.Transform.Position = new Vector3(-500, 0, 0);
            mMiddleShip2.Transform.ScaleSc  = 0.5f;

            // set up two orbiting ships per orbiting ship, note how the scale is the same,
            // but when running, they're still smaller.
            mOuterShip1 = new Basic3DObject(this, mMiddleShip1, "Ship");
            mOuterShip1.Transform.Position = new Vector3(500, 0, 0);
            mOuterShip1.Transform.ScaleSc  = 0.5f;
            mOuterShip2 = new Basic3DObject(this, mMiddleShip1, "Ship");
            mOuterShip2.Transform.Position = new Vector3(-500, 0, 0);
            mOuterShip2.Transform.ScaleSc  = 0.5f;
            mOuterShip3 = new Basic3DObject(this, mMiddleShip2, "Ship");
            mOuterShip3.Transform.Position = new Vector3(500, 0, 0);
            mOuterShip3.Transform.ScaleSc  = 0.5f;
            mOuterShip4 = new Basic3DObject(this, mMiddleShip2, "Ship");
            mOuterShip4.Transform.Position = new Vector3(-500, 0, 0);
            mOuterShip4.Transform.ScaleSc  = 0.5f;

            // do a really simple, easy camera setup
            Camera.ProjectionMatrix = Matrix.CreatePerspectiveFieldOfView(MathHelper.PiOver2, 800f / 480f, 0.1f, 2000f);
            Camera.ViewMatrix       = Matrix.CreateLookAt(new Vector3(500, 500, 500), Vector3.Zero, Vector3.Up);

            base.Initialize();
        }

        protected override void LoadContent()
        {
            // Create a new SpriteBatch, which can be used to draw textures.
            spriteBatch = new SpriteBatch(GraphicsDevice);

            // only need the one call, everything gets passed down, since it's a SceneGraph =D
            mRoot.LoadContent();
        }

        protected override void Update(GameTime gameTime)
        {
            // Allows the game to exit
            if (Keyboard.GetState().IsKeyDown(Keys.Escape))
                this.Exit();

            // rotate the very middle ship, which should rotate all the ships, based on the SceneGraph architecture
            if (Keyboard.GetState().IsKeyDown(Keys.Q))
            {
                mCenterShip.Transform.Rotation += new Vector3(0, 0.05f, 0);
            }
            // rotate the middle ships
            if (Keyboard.GetState().IsKeyDown(Keys.W))
            {
                mMiddleShip1.Transform.Rotation += new Vector3(0, 0.05f, 0);
                mMiddleShip2.Transform.Rotation += new Vector3(0, 0.05f, 0);
            }
            // and lastly
            if (Keyboard.GetState().IsKeyDown(Keys.E))
            {
                mOuterShip1.Transform.Rotation += new Vector3(0, 0.05f, 0);
                mOuterShip2.Transform.Rotation += new Vector3(0, 0.05f, 0);
                mOuterShip3.Transform.Rotation += new Vector3(0, 0.05f, 0);
                mOuterShip4.Transform.Rotation += new Vector3(0, 0.05f, 0);
            }

            // only need the one call, everything gets passed down, since it's a SceneGraph =D
            mRoot.Update((float)gameTime.ElapsedGameTime.TotalSeconds);

            base.Update(gameTime);
        }

        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.CornflowerBlue);

            // only need the one call, everything gets passed down, since it's a SceneGraph =D
            mRoot.Draw((float)gameTime.ElapsedGameTime.TotalSeconds);

            base.Draw(gameTime);
        }
    }

So hopefully that's at least a little bit informative =D The full source code includes a few extra things not shown above, so check it out!

Source code can be downloaded here

Scene graphs vs. regular lists

When I first got into game development, I used simple lists to hold everything in my game. It worked out quite well, it was simple, and it wasn't overly complicated. But like any programmer, I have an insatiable desire to improve my code, to make things more powerful and flexible. It didn't take me long to find out about scene graphs, which is a remarkably intuitive and powerful way to store my game objects.

In case you aren't familiar with the idea of the scene graph, I highly recommend looking into it, even if you ultimately end up not using it, it's a good thing to at the very least consider.


An example of a simple scene graph, illustrating a child/parent relationship for position and more

However, I recently encountered the Unity editor, learned it, and worked with it extensively, and discovered that they don't seem to use a scene graph. The only parent/child relationships going on appeared to be done primarily through the transform components exclusively.

Now I thought this was a pretty intriguing idea, and with my recent focus on extreme simplicity in coding, I thought, "Well why not? A scene graph does make things more complicated and difficult to search through..." and the train suddenly left the station. What if I returned to using a simple list to represent my scenes?

Returning to the earliest example of a scene graph that I had seen, Morrowind, I suddenly realized something. Morrowind is a huge game, having to represent seamless landscapes that cover large amounts of land. Fitting all that data into a single list is impossible, and more or less has to be stored in a hierarchical fashion to facilitate loading.

Now, while I would love to make games on the scale of Morrowind, as an independent hobbyist developer, I don't. Mine are extremely small levels that are easily represented by a basic list, isn't a scene graph overkill? I think it is.

I'm working on a 2D framework for ImagineCup 2011, and have already started implementing this idea. I guess we'll see how it goes =D