Triangulating Concave and Convex Polygons — Ear Clipping

The Problem

OpenGL and other low-level rendering APIs are limited to rendering convex polygons. This causes a complications to arise when trying to render concave primitives. In my case, I wanted to be able to render arbitrary 2D "ground,"  and not succumb to manually breaking apart the polygon into OpenGL-compatible primitives. Thus the search for a triangulation algorithm arose. All I could find were algorithm names without accompanying implementations or explanations, and long mathematical abstracts on computational geometry. Any implementations I did find seemed to be extremely over-engineered and over-complicated for easy comprehension and adaptation. I finally settled on writing my own implementation of the ear-clipping algorithm to facilitate triangulation.

What We Will Accomplish

139-vertex polygon

Triangulated

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!

Animating 2D Sprites in OpenGL

In working on my latest game, Praecursor, it came time to develop a system for easily animating sprites on the screen. I found a very nice sprite for a hero on OpenGameArt, and wanted to integrate his various animations into player actions. In the process, I created a CAnimation class that would extend the CRigidBody class, making it eligible to act just like a physical entity and be rendered on the screen with relative ease. The entire process was fairly challenging, requiring a custom file format parser and a new fragment shader. The following is a tutorial-like thought process that went into the development of animate-able sprites.

Layout

The CAnimation class is supposed to act exactly like a regular physical entity, but should support loading of custom .icanim files and have various functions related to animation. These include toggling animation, setting an automatic animation rate, quick-swapping sprite sheets, and manually switching sprites.

Quick-swapping seems like a pointless functionality of an animation class; after all, why not just create a separate instance and load it with the new sprite sheet? Well, I didn't think about this until I started trying to swap-out animations for running, jumping, and standing with the main player instance. When I would just have a list of animations and do m_Player = m_allAnimations[JUMP], the player would lose his physics properties, such as gravity or jump force. I tried a few workarounds, but none of them turned out like expected, so I decided to add a SwapSpriteSheet() method to the CAnimation class. This will attach a new texture to the material and give the shader new parameters based on width and heights.

In the future, I think I will change the class to incorporate animation boundaries, so I don't need to load a separate image for each animate-able action. I would be able to do something like SetAnimationIndex(0, JUMP), and the animation would only loop through sprites [0:JUMP], then if I wanted to just play the standing animation, I could do SetAnimationIndex(JUMP + 1, STAND), assuming the standing animation comes after the jumping one in the sprite sheet. This would likely all but eliminate the need for the swapping method.

Rendering Text in OpenGL Using FreeType Fonts

EDIT (04.14.2013): Tutorial updated to handle new-lines (\n character)

I finally decided to tackle the rendering of TrueType fonts in my engine. It proved to be a much bigger challenge than I had originally anticipated; I perused over dozens of outdated guides, tutorials, code snippets, and documentation files to finally achieve something legible on screen. I decided to provide a complete guide to this process so that if anyone should decide to follow in my footsteps, they will know where to go.

FreeType 2 Installation

OpenGL works with pixels, and TrueType fonts are not stored like image files, so we need the FreeType 2 library to create font bitmaps. If you are well-versed in 3rd party API installation, feel free to skip this section. I have only performed the compilation using Visual Studio 2010 and 2012.

• Download the latest headers for FreeType 2 from SourceForge. As of this write-up, the latest version is 2.4.11.
• Unzip the archive and go to the builds folder to locate your platform. I will be demonstrating this with the win32/vc2010 build.
• Open freetype.sln in Visual Studio. If you are running VS2012, you will need to update the solution to use the latest compiler and libraries.
• Select the Release candidate and go to Build->Build Solution.
• The compiled .lib file will be located in objs/win32/vc2010/freetype[version].lib, where [version] is "2411" as of this writing.
• Copy this file to somewhere in your current project directory's library path.
• Copy the contents of the include/ folder to somewhere in your current project directory's include path.

A Guide to Instanced Geometry

As stated in the title, this is more of a guide than a tutorial. It isn't for the complete beginner, some experience is necessary. Throughout this I assume you have a general knowledge of what a mesh is, basic understanding of how matrices work, basic knowledge of GLSL, and experience with C++ or another object-oriented language. I am just writing about my own personal implementation of instanced geometry, which is definitely open for comments and suggestions. The code snippets are stripped down versions directly from my basic 2D OpenGL rendering engine I have dubbed IronClad.

What Is Instanced Geometry?

Primitive rendering techniques have many copies of a single object's data. Say you wanted to draw a tiled map, with 2 unique tiles. Say, for instance (no pun intended), a floor tile and a wall tile. Now, each of these objects contains, at the very least, 8 floats for vertex positions, and 8 floats for texture coordinates. That's 8 * 4 + 8 * 4 = 64 bytes. If each instance of a tile contains this information for rendering, and you have 1000 wall tiles, that's 64 kilobytes of memory! And that's not even considering the other tile types. Obviously, this is an example of a very simple mesh with only 4 vertices. Most games have models with hundreds if not thousands of vertices, so you can see why it'd be a serious problem to have multiple copies of that data.

Of course, there's a simple solution to this problem; you keep around one copy of the data in the first object you create, and the other objects simply refer to the original, just in their own position. Well, that's exactly where instancing comes in!

Working With Shadows

The logical course of action after finishing lighting is to move on to shadows. I opted for a relatively simple, software-based approach. It involves casting rays from the light source to individual edges of the tiles in the collision map, and drawing black quads based on the rays.

In my current implementation, the shadows are independent of the other lights. Thus, shadows cast by one light will be left untouched if there is another light in the way. This obviously causes problems, and a better method that will calculate cumulative shadows is currently in progress. But for a single light, the following algorithm suffices. Hopefully some OpenGL beginners trying to create shadows can gain some knowledge from my own trial-and-error!

The steps are as follows:

• Determine the light position.

• Cast a ray from the light to the first vertex (top-left point)
• Calculate slope and extend the ray, so instead of it being from the light to the vertex, it goes from the vertex to some really distant value.
• Keep this ray for later (I'll call it TopLeft later).

• Repeat this process for each vertex, so you get 4 rays, which I'll call TopLeft, TopRight, BottomRight, and BottomLeft in the example code below.

• Now that we have determined the sectors for shading, we test to see which quads are necessary to fill. This is not shown in the diagrams, but in practice, if the light is above the tile, the sector created by the TopLeft and TopRight rays will cut across the tile itself, which is obviously undesirable. The following must be true:
• TopLeft.Start.y < LightPos.y     : Draw quad
• TopRight.Start.x > LightPos.x    : Draw quad
• BottomRight.Start.y > LightPos.y : Draw quad
• BottomLeft.Start.x < LightPos.x  : Draw quad

• Draw the quads with whatever rendering method you wish, be it using glBegin()/glEnd(), glDrawArrays(), FBOs, or what have you.

Here is some C++ example source code using immediate mode rendering. CRay2 is just a class containing two CVector2's, which basically are an (x, y) coordinate pair. There is a minor bug with this method, when the LightPos.x is equal to the Ray.Start.x value, the shadow is not created as intended. When I find a fix, I'll update this code. If anyone has a fix, feel free to comment below.

Let There Be Light!

"And George said unto Collapse, "let there be light," and there was, and George saw that it was good."

Edit (2.1.2012): My lighting shader has changed quite a bit since this post; I opted for a multi-pass shader, rather than maxing out the shader variables.

After several weeks of reading about shaders, learning GLSL, learning about lighting, observing other projects, finally writing my own, and spending hours debugging, tweaking, and improving, it's finally done. My shader supports multiple lights, and gets re-written on the fly to support larger and larger amounts, due to GLSL loop limitations. Whenever I want to increase the amount of lights I use, I merely say:

    LightingShader.SetMacro("NUM_LIGHTS", ++lights);

Which will then re-write, re-compile, and re-link the shader with a new light count. Though I was considering not releasing the shader source code, here it is anyway:

Here are some screen-shots of lighting:

Original shader - one light (in-game)

Final shader - multiple lights (test zone)

AI Experimentation

Collapse is a game set in a post-apocalyptic world in which a human-created AI faction known as the Mechs have taken over. Therefore, AI must be an essential part of the programming.
After extensive research in path-finding algorithms, I decided upon the ubiquitous A*. Then, after days of trying to implement it, using many different techniques from just simple std::vector<Node*> lists to a much more complex and efficient std::priority_queue<Node> binary heap, I gave up. None of them worked properly, obviously due to faults in my programming, but I simple couldn't figure it out.
So I settled on a different approach: pre-defined movement paths. Obviously, this would significantly dumb-down AI decision-making, but I had to at least get something working. The map worked fine, but, again, after days of tweaking and planning and modifying, I couldn't even get the enemy tank to follow the path. I used a rather strange approach with lots of vector math and collision detection, which probably wasn't necessary. The algorithm (in pseudo-code) looked something like this:

Spawn:

    Target = FindNearestPath

    End

Update:

    If reached Target

        Target = FindNextTile

        If no Target

            Turn 3 degrees

    Else

        Adjust angle and drive.

    End

FindNearestPath:

    Find tile with minimum distance to entity.

    Return tile

FindNextTile:

    For each tile in AI map

        If tile collides with line-of-sight

          and tile not collides with entity

            Return tile

    Return no tile

Levels in Collapse

Collapse is the first game I've ever made that actually required levels, so it was quite interesting figuring out how to approach level design, loading, and storage. I definitely had to create some sort of level editor in order to easily design levels. Eventually, after much consideration, I decided that the easiest way to approach level handling would be to split every level into 4 basic components: Terrain, Collision, AI, and Game-Logic. 

Terrain

This map is pretty self-explanatory. It's stored with a .ctm extension (Collapse Terrain Map) and contains information about all the tiles on the map. Currently, since my artwork is fairly limited in the tile department, there are only two tiles available for placement: a floor and a wall. I knew that I'd be expanding later, and I couldn't bear to have a massive switch statement for every single type of file. So, I wrote a quick Python script to gather information about which tile images were available to use in the level, and then stored it in a file call ValidNames.dat. The script is really simple, since I have a special folder dedicated to files, it's pretty easy to find them all:

Collision

Having a separate map for collision makes it so I don't need to store which map tiles are passable and which aren't, and it also allows for more flexibility in terms of destroying tiles for any given reason. For example, when the player fires the tank weapons, if they make contact with the collision map, the collision tile contacted is removed and the terrain tile is changed to a "broken" version. The map is stored as a .ccm file (Collapse Collision Map) and just contains x, y coordinates of 32x32 tiles representing impassable areas.

AI

Now you may wonder, why would you need a map for AI? Well, after trying some basic path-finding techniques, A* in particular, I found that I could not do it efficiently enough. Plus, it would mean that all enemies were informed of the player's location, thus always swarming towards him.  So then I decided to opt for a "line-of-sight" approach, but there was way too much collision detection going on due to diagonal lines creating insanely large amounts of rectangles to check collisions with. Even after optimization, it was still ridiculously slow. So, now I've decided that enemies will patrol certain areas, following a predetermined path, and upon making line-of-sight contact with the player (using a much more efficient vector math approach rather than raw line-rectangle collision), turn to a more aggressive path-finding approach to destroy the player. 

Game-Logic

This map, which is still unimplemented, will contain information such as light sources, player spawn-locations, enemy spawn-locations, start/end level markers, maybe some sort of scripted event triggers, and other things that don't fit into the other categories.

My First Game - ShapeWars

When you're only a beginner in game development, it's hard to think of a fun, interesting, challenging, yet not overwhelming idea. More often than not, you're going to make a clone of some other game, be it Mario, Tetris, etc. I saw a few YouTube videos of the infamous game Geometry Wars on the Xbox Live! Arcade and thought it'd be a very perfect fit for a first game.

I spent several months developing my clone, Shape Wars, in C++ using SDL. I had a fairly decent game done, but for a first attempt, as most developers would agree, the code-base was a complete mess. It was impossible to extend or maintain the game in any way. So I started anew. I decided to approach it in a much more professional manner, maintaining a Github, a changelog, a readme, etc.

The release of version 1.0, after a complete re-write was (according to the changelog) on January 13th, 2012. Everything was re-done: the artwork, the music, the level system, the UI, everything. I switched from a level system that read from a file, to one that gradually generated more difficult enemies in increased numbers. I added a (in my opinion) VERY clean menu. From then on, it became a ton easier to maintain everything, but many flaws remained. Even today, there's a really nasty bug in the game that causes a segfault at the most inopportune moments. It has something to do with how I handle bullet and enemy deletion. Pesky std::list and iterators.

Here are a few screenshots:

Main Menu:

In-Game:

Download Link - Github (.zip)

Unwise

Why Start A Blog?

I asked myself this question many, many times before actually beginning. I originally thought it would be extremely time consuming and boring to maintain a dev-blog, but as the change-logs to my games got longer and longer, I felt that starting a blog would make my life easier. This thing should keep me pretty motivated to brainstorm my ideas, release previews, share screenshots, and express my thoughts. Generally, this blog is going to be full of stuff like tutorials, algorithms, code-snippets, screenshots / releases of my projects, and brainstorming ideas about problems I'm having.

My Background

After that, I decided that it was time to leave the turtle of SDL rendering behind and make the jump to 3D. After about a week of experimentation with OpenGL, I realized the amount of math I would need to know for even the simplest game was just too much. Plus, I have absolutely no idea how to use modeling programs, and have no desire to learn. So I retreated back to 2D, except using a mix of OpenGL and SDL. SDL for window and event handling, and OpenGL for rendering. So, with many new-found features at my disposal, I began developing my first full-fledged game: Collapse.
I only got into game-dev fairly recently, maybe a year or so ago. I started out experimenting with Python+PyGame, making simple Snake and Tic-Tac-Toe clones. I felt the curly-brackets calling back to me, so I made the switch to C++ and SDL. The last game I made in purely SDL, ShapeWars, was already pushing the limits of SDL when large quantities of bullets and enemies swarmed. I had to keep all of the game artwork fixed, rotation was simply too slow and not an options.