Yet Another Quad Tree Tutorial

There was nothing to show for Screenshot Saturday this week, but that doesn't mean there hasn't been any progress! I spent the weekend writing a quad-tree implementation and integrating it into the existing engine. It was not a very hard process, and there are already dozens of tutorials available online for this, but this guide may still come in handy for someone.

How Do Quad Trees Work

You may be familiar with a binary tree. Essentially there's a "root" structure (known as a "node") that branches out into two nodes (binary = two). Then, each of these nodes splits into two of their own. This continues as long as necessary. The nodes that aren't split are called "leaf" nodes.
Quad trees work exactly the same way, except the nodes are split into four parts rather than two. This is useful for video games because the screen is a rectangle, and can thus easily be split into smaller subsequent rectangles. Here's a screenshot of a stress-test quad tree in progress:

The small, 8x8 quads represent particles with physics. Each quad you see can contain a maximum of 32 (an arbitrary value) particles before it automatically splits into 4 nodes. The tree cannot go more than 6 levels deep, though, because that would eventually cause a stack overflow due to the recursion inherent to quad trees.

You can see this live, in-action by downloading a demo here (pardon the dependencies, I used my old wrapper classes to write this). Hold keys to generate particles, or use the mouse to set them in certain locations. Right-click the mouse to test for a collision with the large blue quad. The result will show up in the console window as a 1 (true) or 0 (false). You can notice that the operation is performed incredibly quickly, even with an insane amount of particles on the screen. That is the power of a quad tree.

Note: If you get DLL errors, you may need to install the VC++ redistributable from here.

Making a Menu

I've been a bit quiet the past few weeks on here, but I've been actively participating in Screenshot Saturday on /r/gamedev. You can see last weeks here, and the one prior here.

This week, I've worked on creating a flexible, slick UI system for making menus. It proved to be pretty complex, and I used a seriously ass-backwards technique to get it accomplished.
You can think of a button as an physical entity, right? You need to be able to check collision, move it around for transitions, and swap textures easily. So I created a CButton class with a CEntity inside. At first, I just had a button texture rendered to the screen as a mesh, and the text rendered on top without being a part of the scene. This worked okay, but I wouldn't be able to add shader effects to the text portion of the buttons, which would look weird. So I had to have them both be a part of the scene.

The problem arose when I wanted to assign a texture to the entity. Since the button background is a texture, and the my text-rendering system renders directly to the frame buffer  there was no way to easily "blit" them together. I decided to create a frame buffer object for every instance of the button (main, hover, click) and render both parts of the button to it, then assign that texture to the button entity.
As you can see, this is serious overkill. It requires three render passes, two different shaders, and a ton of OpenGL state change. I'm not too worried about this, though, since it will only be called at the beginning of the game, prior to any performance-critical sections. It also works fast on my machine, no frame rate issues whatsoever.

After making the button class, I made another, higher-level class to wrap everything up for flexible menu creation. Now I can just call something like
     CMenu::AddButton("Button.tga", "Play Praecursor", math::rect_t(0, 0, 256, 64));
and the wrapper will automatically search for the hover and click versions of the button texture. I added these buttons to a pre-made background, added a lighting effect for a torch (it always looks good), and called it good!

Final result!