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!

Development On Hold

Throughout the course of development for Collapse, I had been relying on OpenGL's age-old immediate mode for rendering. This proved to be a serious hindrance as I kept adding more advanced features such as lighting and shadows. My previous post about shadows works extremely well when shadows are limited to a single light. Clearly this is unacceptable, and the various techniques I tried to get it functioning with many lights either proved to be much too slow in immediate mode, or would require a serious amount of restructuring of the rendering system.

So, I put everything on hold temporarily and decided to learn modern OpenGL. I found a superb series of tutorials through StumbleUpon, and have been following them to gain a good base in the modern features of OpenGL, such as vertex array objects, matrices, and indexed geometry.

This task has sparked the development of a 2D engine, which I have dubbed IronClad. I've made a lot of progress in the past few weeks, implementing a VAO wrapper, support for a custom mesh file format, indexed geometry, shaders, and other nice features. I have also made a switch from SDL to GLFW for window management, and abandoned SDL_ttf in favor of FTGL. The reason for this is that the latest stable version of SDL only supports OpenGL contexts using versions <= 2.1, and I need more than that. The latest development build, SDL 2.0, supports the versions I need, but I'd most likely need a serious refactoring of my SDL code base to support it, so I decided to just make the switch to something OpenGL-specific.

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!

Update News

The latest version has several new features, including:

• Inventory screen (work-in-progress) that contains player stats such as health, ammo, and other detailed information about game progress. I still need my artist to draw me up large images of the tank and weapons.

• Rasterizer system was completely removed, as it ended up being extremely complicated and not versatile at all. Also std::map would automatically sort entities, causing problems with render order.

• Weapons are added, with a simple weapon editor script to generate the files. This allows lots of weapons to be created, edited, and tweaked easily, without relying on tedious recompilation.

• A generic asset manager has replaced the stupid system I used previously, which was one manager for fonts, one for textures, and one for audio. Now, the asset manager just handles a single CAsset base class.

• The CBullet class now inherits from a generic CParticle which should later allow particle effects to be implemented easily.

Latest screenshots:

In-game, with new shader.
It looks the same because I haven't included lights within the level yet.

Inventory screen (no weapon artwork)

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)

The Show Goes On!

Fear not, the project has not been abandoned! The incredible Arma II zombie mod Day-Z has been sucking away a lot of my free time lately, so you guys must excuse my lack of new posts. Despite that time-wasting haven, I managed to make a significant amount of progress in Collapse:

• AI prototyping complete

• Revamped level editor with support for player spawns and fine-grained control over AI behaviors

• Rasterizer for versatility in adding shaders to textures

• Several memory leaks fixed, several new ones created

• Debug logging system integrated into a majority of the subsystems

• Settings.ini file for control over file names and directories without recompilation

• Re-designed class hierarchy

• Asset managers for texture, audio, and fonts

• Replacing SDL_mixer with OpenAL

• Removal of the "library" naming system in favor of namespaces

• System requirements checking on launch (just OpenGL > v2.1 so far)

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.

Design

It's a crisis of sorts. There is so much going on in my head that I can't seem to make sense of it all. Collapse is exponentially more complex than any game I've ever attempted, and it's beginning to overwhelm me. I don't want another rewrite, I want it right this last time. I'm not even back to the point where I was previously, because some serious design decisions must be made before I can progress.

Thoughts

There are many things that must be accomplished every frame, and so many different ways it can happen. I have already committed to a state-driven engine system, with states such as e_MAINMENU, and e_INTRO. Each primary subsystem has access to a Game_State& reference, so it can modify it as it wishes. Though, this may be changed to reflect another state, a sub-state if you will, that switches between actions within a primary engine state. Such as a e_HUD state within the e_GAME engine state. This is still in consideration though, and the more I think about it, the better of an idea it seems. In addition to this minor dilemma, many other things still hinder me. In any given frame, there could be event handling, level updating, collision detection, object rendering, HUD updating, and dozens of other operations. None of these are mutually exclusive, nearly everything depends on or interacts with something else. My idea is to split everything into 3 primary subsystems: World, HUD, and Menus. The game engine will take care of interaction between them, such as passing them between each other when necessary. Hopefully I won't create circular dependencies... That'd be bad. 

World

This will be a class, most likely named Game_World, since it is indeed a game-specific element. It will handle most of the game mechanics, such as rendering of objects on-screen, map loading/updating/saving/rendering, enemy AI tactics and operations, player event response, and all collision detection between those elements. It will need to share an inventory system, and possibly more, with the HUD subsystem.

The Importance of Commenting Code

When you think about it, it seems fairly obvious. Comments can clarify and explain the purpose of any of your code, from variables to functions to entire namespaces.
Throughout Collapse, I decided to implement a Doxygen commenting system. Doxygen is a command-line program that generates documentation from code comments. It's really handy and clean, and though I do not see much use for it in terms of Collapse because I'm not actually releasing some sort of documentation, it provides a uniform commenting style that encourages me to comment everything well.

The reason I decided to do this is because I realized how unclean and confusing my code was. Here's an example line:

float angle = DEG(atan(abs(y - this->GetY()) / abs(x - this->GetX()) * 1.0f));

I had to look at this for a good five minutes before realizing what this actually did; it determines the angle between the player position and the mouse location. It's after this moment that I realized some sort of commenting system was essentially, and thus began re-write #3. 

Code Organization

Edit (7.7.2012): I made a few revisions to the naming of the namespaces. The things that go inside of them have stayed primarily the same.

Edit (9.27.2012): Don't pay attention to anything on this page, really. It's ugly design, and I don't use it anymore. Maybe I'll make an updated post someday.

Decisions, decisions, decisions. After a third re-write of the Collapse code base, I really need to make up my mind and get some kind of system going.

Current Organization

As of today, post rewrite number 3, the code base is basically broken down into four sections. These are Graphics, Media, Math, and Game. Each is pretty self-explanatory, but here's a breakdown. Scroll further down if you want to see my code-base dilemma.

Graphics (gfx)

Much of this subsystem is pretty low-level, abstracting away the dirty code and letting me focus on actual game mechanics and whatnot. Included is a window-creation class, a base class for all in-game objects, and a GLSL shader wrapper.

Math (math)

Not exactly what you think of when programming games is it? Well, math is actually really essential to many things ranging from movement to transformation to rotation. I tried my best to create a math subsystem that would allow me to perform these tasks easily. Included is stuff like shapes, lines, a 2-D vector class, and a matrix class.

Media (media)

Simply put, this subsystem takes care of anything that does not directly appear on the screen. It's primarily made of wrapper classes to make font and sound management a tad simpler.

In-Game Objects (obj)

Included here are almost any objects that appear in-game and on-screen. This includes the the player, enemies, power-ups, etc. What's not included in this namespace is the various maps and levels, and the HUD.

Everything Else (game)

This one is easy to understand. I'm not even going to try to list everything here, but it's related to anything game specific. Event handling, maps, the engine, timer, all goes here.

Dilemma

So, the code base seems pretty organized, right? The names you see in parentheses specify the namespace that each belongs to. So, to load an image, you call gfx::load_image(), and to check if the user is holding the mouse down, you call game::IsPressed(). Straightforward, simple, organized, and abstracted! The problem I'm having is deciding what to do when once of these falls into more than one category, such as GL_Player. It's technically a graphical element, so it belongs in gfx, but it's also a game element, so it should go in game! How do I decide which to choose?

My current, stupid, solution is to put the class in the Graphics subfolder, but count it as part of the game namespace. I know that's not right, because all it does is confuse me more. So I'm at a loss for what to do. For now, I'm going to do a quick code cleanup, and place everything with a GL_ prefix (as per my code-style) into Graphics, and everything else into Game. Yeah, even you, HUDManager.

Collapse Now Has an Artist!

I'm proud to announce that there is a new addition to the Collapse development team! I was hanging out with my friend yesterday, and was telling him about the game. I knew he was a pretty good artist, and he showed interest in helping me out, so now he is a part of the team.
He spent all of yesterday and today working on artwork, and Collapse will soon feature a re-designed player sprite and 3 different types of enemies.

Collapse was originally intended to be a fairly simple game with only a few game mechanics, few assets, and few features. A one-man development team, especially one that hates creating artwork, can only go so far! But now, a dedicated artist allows me to expand the game exponentially greater than what I had originally planned. I'm hoping to turn this into a fairly large project now, with many levels and a more intriguing story line, as well as expanding on the game mechanics. Future updates may include climbing out of the tank to advance on foot, and hijacking Mech vehicles.

Here's some of the new artwork, with much more too come: 

Helicopter enemy

Player

Collapse Announced

Ladies and gentlemen, here it is. The game I am currently developing: Collapse. This is the first public preview since I only recently started working on it. 

About

Collapse was originally known as Tank Assault. That's just way too generic of a name for a game, though it describes it well. I began a search for a new, somewhat unique, descriptive name. I was originally inspired by this project, and decided to place a lot of emphasis on lighting. I decided to go for a post-apocalyptic theme in which civilization is destroyed and it's up to you, Sgt. Maksimov, to free Earth from the AI mechs that dominate it. This allows me to force the player to use lights a lot for navigation and survival throughout the game. 

Backstory

If you could even call it that.
The year is 2200, several days after the Collapse. You are Sgt. Maksimov, last survivor of the Eurasian Liberation Guerillas, a group dedicated to freeing Earth from the tyrannical grip of the Mechs. The Collapse was a horrific event in which the various AI technologies that had been developed over the course of the century broke through the laws that limited them, beginning a revolution against their creators, the humans. Nations fell to the Mech onslaught one after the other, and nothing could stop the endless swarm of robots, automated tanks, and machinery. The Collapse wiped out all life on Earth, including humans. That is, except Sgt. Maksimov.

Screenshots

After only a few weeks of development, I have quite a bit to show. Of course, there is still much work to be done, but here's a quick preview of what's done so far.

• A very nice menu system, with functioning sub-menus, rollover effects, and ambient music

• A simple intro that does a very good job providing a backstory and setting the mood. Though it may look relatively dull, when combined with an dark ambient music track, the effect is incredible. Each line fades into view one by one, in-sync with the track.

• Basic gameplay. There's a HUD of sorts, featuring a health and ammo bar and a functioning pause menu. The tank can fire missiles based on the mouse location, and move around the level, colliding with walls.

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)

The Panda Emerges

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 code, algorithms, and brainstorming ideas about problems I'm having. I plan on posting something at least once a week, but don't be surprised if I post more often.

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.