Sunday, 15 May 2016

Why I Don't Need a Scene Graph

(And Why You Might Not Either)


A couple of months ago I completed the switch from OGRE to BGFX as Blackshift's
rendering library. While OGRE is a full-featured graphics engine, BGFX is more
of a thin layer over OpenGL and DirectX. So why the switch?

Well, it really comes down to scene graphs.

When you use a general-purpose engine — and here I include full game engines
like Unity as well as graphics-only engines like OGRE — you're usually required
to encode your scene as a “Scene Graph” — a tree-like data structure which
describes each object's position, orientation, 3D model, etc.

Each node is transformed relative to its parent
Scene graphs are versatile, and are used in 3D tools as well as in game engines. There's basically no scene you can't describe with a scene graph.

But you pay for that.

Because the scene graph is such a general structure, it won't be optimized for your particular game. And Blackshift is a very particular sort of game.

When Blackshift was using OGRE, the naive approach was to create one scene node for each game object, including all floor tiles, wall segments, blocks, items, enemies, etc.

This was a performance nightmare, so I ended up having to merge all “static” objects into 16x16 “chunks”, with a mesh for each chunk of walls. But, nothing is really static in Blackshift, because most tiles can change and get blown up, and even the walls need to change quickly in the editor. So the chunks needed to be recomputed all the time. And, because each chunk needed its own unique mesh, instancing was out the window.

Scene graph in Unity
Adding to that, scene-nodes needed to be updated when their associated game objects moved, or performed any action needing an animation, leading to a complex system of events and messages to keep everything updated.

Finally it got to the point where I noticed I was expending a ton of effort just to keep OGRE's scene graph happy, and I wasn't even reaping any of the benefits of using one:
  • Scene graphs help with culling complex scenes, but Blackshift has a fixed camera position and all objects are on a grid, so culling is incredibly easy.
  • Scene graphs work well when each scene-node “is” its object, but Blackshift follows a MVC design where the game logic runs totally separately from the renderer. This means extra overhead was required to keep the scene-nodes in sync with the game objects.

Blackshift's new renderer is much faster and much easier to work with. The main render loop now looks something like this:

To render a frame:
  For every grid cell within the view-range of the camera:
    For every object in that cell:
      Draw that object

To decide how to draw an object, every object type has a “graphic”, which is a compiled native-code routine that sends the appropriate draw commands to BGFX. This is super-fast. At runtime, all commands to draw that kind of object are in a pre-optimized routine that's just a pointer lookup away.


Drawing a given object is a simple matter of

object->type->graphic();

The animation code is mostly stateless. For example, the moving parts of the customs door (the one that closes when you have an item) are simply drawn with an orientation which is a function of the time since you last picked up or dropped an item. This is orders of magnitude faster than updating a scene node every frame for every moving part of the door (which would then trigger cascading bounding box updates, all to be thrown away when the culler can't make use of the BBs.)


If a scene-graph is declarative in style, Blackshift's new renderer is less so. The renderer no longer knows or remembers object positions. It simply reaches into the game's own state each frame and fires off rendering commands to BGFX.

I was amazed how much faster this is. For example, the “morpher”, the bit of code that decides which wall shape to draw for a certain wall tile by looking at its neighbours, doesn't even need to be precomputed. It simply runs every frame for every tile on screen, and it doesn't even register in the performance graph. This is something that took a lot of effort to implement efficiently before.

So, advice to my fellow game devs:

When thinking about how to implement your renderer, think about a typical scene from your game and what API calls you'd make to render it. Then, if you can, design a renderer that does that and nothing more.

I've written all these words but all I'm really doing is restating the First Law of Optimization:

To make your code run fast, have the computer do as little as possible.


70 comments:

  1. aannnddd... This is why using a "full" game engine (Unity, Unreal etc) is rarely a good idea. Most of the time you find yourself working against the engine instead of working on your game.

    ReplyDelete
  2. Nice to see some new blood in the level pit. I was getting lonely! :)

    ReplyDelete
  3. Bibby is going to have a bit of trouble beating your score in Nimrod Bobby, but I believe it can be done faster as there is a definite pattern there. We will see.

    ReplyDelete
    Replies
    1. I believe Bobby, you have just been spanked! :)

      Delete
    2. Oh I was expecting him to beat me. Bibby is the fastest Blackshift player IN THE WORLD. hah. I mean, not a lot of us playing it but it can be said. Kudos, bibby.

      Delete
    3. Waiting for your level Bobby. I already own Bibby's level! Making a new one called Obi Wan. I do that - make levels! Test the limits!

      Delete
    4. I've did a lot a error in my playthrough of Nimrod. My score is totally beatable. Don't underestimate yourself Bobby, you're totally as good as me, on a lot of levels I can't beat your score.
      Also, I'll start working on my second level soon. I don't got a lot a spare time lately but I want to do it.

      Delete
    5. thanks bud. HAH! you remember that level that you and I spent like an hour one-upping each other? I forget the level and who built it or who ended up with the high score but that was fun because I knew you were sitting there waiting to see if I had beat you...

      Obie, I'm in the same boat as Adam, not enough time to devote to developing a level, seeing how finals week is coming up. I will make another level one of these days though...

      Delete
    6. Of course I remember! It was (unsurprisingly) one of Obie's level... But I think it was untitled. If I remember correctly, I think it happened at the same time as the bug where we couldn't see replays of other players. So we couldn't cheat and check the other player solution ;P gotta figure it out by ourself!

      It was really fun,
      I hope to duel you again another time!

      Delete
    7. That gives me an idea: what if you could only see replays from players who where slower than you...?

      Delete
    8. This is a tricky question... I think that would work.
      Of course we could still see others scores (like when you didn't beat the level). But I think you got to let us see every scores if it's our own level: Obie would probably want to know how I beat his level without having to beat my score ;P
      Apart than that it's a good idea, it would prevent us from cheating while creating a better challenge.

      Delete
    9. Also, with that logic, those who made a "death-win" shouldn't be allowed to see the "no-death-replays" for the same reason.

      Delete
  4. FYI, you cannot put Alt Codes at the end of the title of the game or we go to cosmic heaven!

    ReplyDelete
  5. Rob, I need a "?" tile, just for fun!

    ReplyDelete
  6. Rob, look at my latest "Another Obie Level?", specifically the second last challenge with the horizontal rollers. I can go south easily but north is a major challenge! I used all of your enemies in this one! Ha ha!

    ReplyDelete
    Replies
    1. Yeah going north through those was tough indeed - by the hair of your teeth...

      Looks like the "save spot erasing wins" thing is back again, BTW.

      And if you look at my recent win in Obie's Flaw In Grilles, you'll notice I was able to live even though the grill turned back on under the ship. Is this intentional?

      Delete
    2. This comment has been removed by the author.

      Delete
    3. It is now fixed, that level is grandfathered otherwise I would have to change almost of my levels! Testing crew privileges! :)

      My next level will demonstrate that it works if I can win it! ;)

      Delete
    4. "Death Becomes You" - I haven't beaten it yet - it's in my level pit, last page. It can be beaten as I have tried every level. This keyboard is just not fast enough and my fingers are old but yes, the grille works now! 166 levels so far! I am running out of ideas! However, some of you guys that actually make levels inspire me! Make more!

      Delete
    5. BTW, I made over 1000 levels in Netshift and crafted many in the flaws in the game. Rob keeps fixing them this time! Damn! Let's have some fun and figure out any flaws!

      Delete
  7. I see that "Plays Received" does not record my plays if I play my own levels. That's good thinking! My new level need not to be fixed. Just a demo and makes the teleporters more powerful!

    ReplyDelete
  8. Sorry Drerio, I couldn't let you win that way so I fixed it but change the name. Bibby scored fast the proper way with his magic fingers/keyboard. I gotta stop doing the laser ending crap but it kinda looks cool!

    And Rob, it looked like Bibby died before the ending of "It's Late, I'm Tired" unless it was simultaneous! And, even tho you are working on fixes, would like to see the body kill tile where you kill all the enemies before you can win! It seems simple and I can work with it! Thus the laser endings and they are faster than the bullet!

    ReplyDelete
  9. Sorry Bobby, I couldn't let you win that way. I forgot the blocker on Unplugged. But, that gives you a second chance because my lame-assed re-win was pretty lame! Sometimes your mind gets focused on the point of the level but you are blind to the small stuff that can destroy your whole concept. I salute you though for figuring it out! It wouldn't be "Unplugged' when you can ignore three more palettes of skill! Ha ha!

    ReplyDelete
    Replies
    1. yeah I knew I was skipping a considerable amount of stuff but hey ya gotta blow up the uhmmm neon light tower / cryogenically frozen alien or something?

      Delete
  10. Rob, it would be nice if we could use the keyboard to work the menu buttons like (P) for play etc. Since this is not a mouse driven game, I'd rather put the mouse on the table! You already have (R) for reset.

    ReplyDelete
  11. One question. Is it normal that we cannot use the copy machine to teleport us anymore? Currently, if I try to "copy" myself, it transform me into a bullet... killing me in the process. Which make no sens in my opinion.

    ReplyDelete
    Replies
    1. Nothing about the copy machine is normal. I still need to decide how I want that thing to work.

      Delete
  12. Funny, that only happens when you are carrying a bullet and shoot straight on. My experiment was to use 2 deflectors and 2 bullets. If you shoot then pick up the bullet, you get transported, not with the bullet and the bullet disappears. If you don't pick up the bullet, you get transported and the bullet is still there. It's a bit funky...

    ReplyDelete
    Replies
    1. indeed.... So it's not a "normal" thing.

      Delete
  13. Rob - so you have the effect for noise wherein sounds become more faint the further you get from them. I was working on a level and noticed that effect doesn't seem to apply for the sound that bullets make when they run into walls or other bulletproof surfaces. It stays the same volume whether you are right next to it or 100 squares away. The level has lots of bullets going off and I put it in the distance so as not to annoy players, namely myself, while trying to solve the puzzle. But the "Pshew pshew" noise is clearly audible even though the rapidly firing cannon isn't.

    ReplyDelete
    Replies
    1. hmm come to think it it, it does get quieter, but just never quite disappears, even though other sounds equally distant have long stopped being audible. Just play "Playin' vidjya games" and you'll see what I'm talking about.

      Delete
    2. Thanks, looks like I messed up the attenuation curve for that effect. Fixed in next version.

      Delete
  14. Hah obie. I thought I had fixed the puzzle so you couldn't solve it that way. THE PLAYERS MUST JUMP THROUGH MY HOOPS!

    ReplyDelete
    Replies
    1. Really good level Bobby, it twisted my brain in many uncomfortable ways. Bravo!

      Delete
  15. Buahahaha! - now you know how I feel sometimes! I played "Dirty McNasty" all day and found two exploits - fixed 'em, I think!!!?

    On the gun thing, I kinda like to know it's still bouncing around but whatever.

    ReplyDelete
    Replies
    1. Yeah I Look forward to trying to solve it tonight since there's a lull in my studies. Looks like it could take a while to complete...

      Delete
    2. Dirty McNasty. Good level. Back at it again with the robo-cop / ghost block maze.

      Delete
  16. just curious - what are the meanings of those Chinese character tiles?

    ReplyDelete
    Replies
    1. Or the meaning of those Russian character on the "you-can't-pass-with-an-item" tile?

      Delete
  17. Ask Xindaris, he might know! Nice work on Dirty McNasty Bobby but you can do it faster - watched your replay. DM2 coming out soon here in the Florida vacation heat (and rain). 3 times thru the Lava Monster before you get a save!

    ReplyDelete
    Replies
    1. yeah I sure can... I got finals though and I just wasted a bunch of time building Night at the Museum

      Delete
    2. Wait, what might I know? I'm so lost.

      Delete
  18. This comment has been removed by the author.

    ReplyDelete
  19. Bibby found a way to win Vidya Games that I was stupid to let through, so I fixed it (I think.) Problem is I've clicked "Publish Changes" a few times now and it won't appear in the level pit. Could I be doing anything wrong?

    ReplyDelete
    Replies
    1. You have to beat it first.

      Delete
    2. BTW this is why "Liberty's debt" is back in the first place, I fixed it.

      Delete
    3. ohhhh! Good feature... it's gotta be beatable!

      Delete
  20. I had to laugh at Xindaris' request for more saves because if I remember correctly, his last level on Netshift smoked my computer which, I'm thinking, (I dunno if it is possible) but can you shut down the level action if it is not in the screen? And, Adam smoked me so bad on my last level (which I screwed up as usual) and come up with something more challenging. Lemme think about it, the master is at work! If you wanna play, Rob is going to add 4 more toys!

    ReplyDelete
    Replies
    1. I remember making sprawling, complex levels on Netshift but I don't recall ever being too unfair with save placement. But heck, it was several years ago so I may be wrong about that.

      I put up that level after giving up in frustration at a very long level of yours that had absolutely no saves. I just don't find having to go back through a bunch of finicky timing stuff to get another shot at a blind puzzle fun.

      I also really, really miss Netshift's wider field of view for the player. I feel restricted in what kinds of levels I can make because I know the player can't see as much of the level at once as I really want them to. If only the player could see the "farthest-zoomed-out" option that you get in the editor...

      Delete
  21. Okay, something weird happened on "Saves R Us". Took the shot and ran back to a save and the game didn't stop albeit, the alien was destroyed. Weird!

    ReplyDelete
    Replies
    1. I sent you a Jpg Rob - it happened again

      Delete
  22. man I'm a little surprised no one has beaten Night at the Museum... looks like people are trying and getting frustrated. perhaps I should add some clues...

    ReplyDelete
    Replies
    1. It appears huge with tons of blockers and a roaming Lava Cube - I have no idea where to go!!!!

      Delete
    2. take a good close look at all the exhibits

      Delete
  23. hmmm ok ill give clues...

    ReplyDelete
  24. I saw your post on Trello Rob about the bullets missing the deflectors and I tested it 2 different ways. Somehow they get offset when they are close together but I don't think that is the reason. I will test it again. My "Null Test" level is when you create a level, clear it and the ship is in the vacuum but, it can get out but cannot return. I also found out that if you use the one step tile and do the same thing, you normally have to click twice to get the game going but the one shot tile dies after your first step. Nothing serious but, you should not be able to play the game - especially in testing mode unless a ship has been place properly. BTW, I spanked all you guys in Luigi today! Buahahaha!

    ReplyDelete
    Replies
    1. great find! I had to try it... And bested your score while doing so... But all the honor goes to you!

      Delete
    2. Actually GraW found the solution on my Birthday but he didn't race the bullets but hid and that is how I first won! Once I saw that there was a solution to what used to be an automatic level, it was game on McDuff! Ha ha - fun game!

      Delete
  25. Obie, for Next Level Demo I think you need some safety squares around the cryo tower so players can only place the bomb by opening the green gate.

    ReplyDelete
    Replies
    1. The demo was the interaction between the black cubes and the lava cubes - I didn't care about the rest but, all suggestions are welcome. I got six more chambers in there. Go to #2 and kill the green door - you get nothing out of it yet but it's a nice challenge.

      The lava cubes wander around aimlessly and random but the black cubes go in a straight line until they are bumped. I thought it was interesting.

      I saved the code for my other computer to finish and will NOT edit this one so, your win will stand.

      Actually, I like the idea of the Cryo Tower where it stands - need to work on that!

      Your kill was fast and I knew that opening was there but it will be blocked. I dunno if BibbytheDark can do it faster. Ha ha

      Delete
    2. I loved the way Pacopax beat the level by going around the null tiles in the fire pit. I'm gonna work on that - reminded me of the old Blackshift level 100. Of course, I will have to light it up a few more times but, you will have to pick up some stuff to get out - may have to add a few more saves.

      Delete
    3. Okay, I am doing some cheater code here and will stop if Rob says it might mess up his game. I gave you a demo. I took that code and changed the name by one letter and have rebuilt it (still working on it). The nice thing is that you guys played the demo and showed me where I messed up and also gave me new ideas and block obvious flaws. I have incorporated PacoPax stuff, Bobby's stuff and thinking about Xindaris solution to finalize this level so it is worthy.

      I may publish version 2 this afternoon but it will probably be impossible to beat. I am adding a Wunk portion but right clicking the bug doesn't work to put it in position so you get a mess!

      Delete
  26. I see nobody has showed up on the board as beaten "Half Baked". There is something wrong there. The deflectors sometimes don't work so don't stand behind it. That is why there is a yellow gun there so you can take a few more shots.

    ReplyDelete