Saturday, March 19, 2011

World geometry and trees.

When a virtual world has a lot of entities in it, which is not uncommon for modern games, there needs to be a fast way to:

- decide what gets drawn on screen.
- decide what entities are interacting with others.
- decide what geometry to disregard ( geometry that is useless )

The first is decided using multiple methods of culling, some of which include:
 - Frustum culling
 - Back face culling
 - LoD (l evel of detail )
 - PVS ( potential visbility sets )
 - Portals

The more methods you implement, the better suited your engine will be for large enviroments with lot of geometry and entities.  It should also be noted that the more methods used, the more expensive it will cost CPU wise to perform these calculations.  If your implementations are not optimized accordingly i.e seperate threads you can suffer extreme frame rate loss.

So we know how to manage what gets drawn on screen, how do we manage what entites are interacting with each other? To decide whether or not a entity is placed on something or should be falling depends on whether or not something is located underneath it, and in order to determine that, we need a realtime method for asking the question if something is underneath it or not.

You can ask yourself what is a good way to do this. Ultimately, if you're not using a tree you're eventually going to have problems making things fast. The simplest (but useless) way to ask if something is underneath an entity is to check the distance and position of every individual triangle in the world against the entity.  This would give you the most accurate answer but would be slow, O(N) for every single frame, and for an operation that needs to be done multiple times per frame it's not an effective solution.  A tree allows us to do something in a O(log N) fashion, by divding all the worlds triangles in half, or in eighths, or in some other number, as many times needed until we get to the most effective target point.

There are quite a few types of trees that will allow us to do this, to list a few:
 - Octree
 - Binary Space Partitioning Trees ( what Quake uses ) a.k.a BSP
 - KD - Trees

There are thousands, if not millions of tutorials / examples online that can get you started on implementing an efficient and effective tree system for your engine.  The one I would recomend if you're going for a high detailed engine with realtime lighting and raytracing would be KD - Trees.  If you're looking for something that's easy to modify in a realtime enviroment, perhaps a in-game map editor I would suggest Octrees.  If you're looking for a highly optimal solution, then stick to BSP.

you can also give your attempt at implementing your own hybrid, which in some cases might be an optimal choice, however you can easily get lost in your train of thought when you need to manage not thousands but millions of nodes.

Friday, March 18, 2011

Context Creation, Input Management, Joysticks Done Right?

One of the most core thing any engine needs, or rather any program needs is a context. The Context is our interface to communicate visually and physically with our engine, also knonw as the window.  You would assume you could forget about it, only because it seems like such a simple thing.  I can assure you that you're incorrect.  Every operating system has it's own method to manage a window, the keyboard events, mouse events, mouse acceleration, etc etc.  But what are your options as a engine developer if you want to support an array of different operating systems?  Luckily for you there are libraries for this, the two most popular would be SDL  & SFML These are viable options but at some point you will be forced to implement a context for a system that these libraries do not support, perhaps HaikuOS or perhaps a game console.

So my advice as a engine developer is abstraction.  Instead of relying on a specific library like SDL, abstract it so a back-end replacement will be easy on your behalf to tie-in.  I started my personal engine project off with SFML due to its extreme simplicity, however due to lack of support for Direct3D I was forced to migrate over to SDL, which I can validate does allows both OpenGL and Direct3D contexts.

So today I made a bold decision to implement a context management wrapper so I can tie in additional implementations for things SDL does not support.  I had a workable wrapper in about two hours, and I found it so easy to use I decided to implement fall-back methods for X11 and Windows.  Perhaps I don't need it, but it's a good feature to support.  Some companies don't allow the use of SDL because of it's license, the Apple store is an example of this, now thanks to my wrapper and my own individual implementations any game created with my engine can be sold in the Apple store.

The best part is I can still support SDL internally and it will be invisible to anyone using my engine.  So in the sitation where someone does have SDL and would like to use it, it's there for their disposal, all the have to do is #define CONTEXT_SDL

Thursday, March 17, 2011

Engine Coding Tricks

Okay so when it comes to making a game engine sometimes you just need a uniform type that can be assigned any data, usually for a game console or command system of some sort, the only issue is you don't always know the type you're working with.  In some cases I've seen people handle everything as a string, while this may be effective it's in no case efficient.  In other cases I've seen interesting uniform classes that require some serious skill to debug and step through.  Some of the implementations are insane in code length and require outside sources from the all evil boost.

Anyways with some experimenting I've developed a farily straight forward class that allows me to assign any type of data and retrieve that data using the typename as the template paramater.

struct anytype {
   union anycore {
     int        i;
     float     f;
     double d;
     char *  s;
   template<typename T>
   void operator =(T t) { dat = *((T*)&t); }
   template<typename T>
   T get() { return *((T*)&dat); }
   anycore dat;

with this simple structure you can easily assign and get data here is an example:

anytype a[3];
a[0] = "this is a test";
a[1] = 65;
a[2] = 78.76f;

getting the data is just as easy:
char* data0 = a[0].get<char*>();
int     data1 = a[1].get<int>    ();
float  data2 = a[2].get<float> ();

I left out some sanity checks but you get the idea.

C vs C++

Everyone I know always asks me why I bother to use C++ for game engine development.  Their opnions towards C++ are biased and are backed up by links to irrelevance.  Then there are those who ask why I bother to use the Standard Template Library, for which I reply because it's part of C++.

Most of the people I know who work on game engines or games perfer to use C++ minus the STL in favor of using the C library.  Their agruments always evolve around "it's much faster and simpler to debug" senero, which is acceptable given their knowledge of the STL is little to nothing.

It's hard to profile C vs C++ code because the experiment is hard to control, most people compare strings to char pointers and vectors to arrays, yet they have little knowledge of how the STL actually works.

While it's true a std::vector<> compiles down to native array instructions, people actually never believe it.  Everyone I've talked to brings up the argument that they can never view the contents of a std::vector in a debugger so it cannot compile down to native array instructions; this is because you compile debug builds and in the situation of a debug build the std::vector<> is never optimized to native array instructions. Don't belive me take a look for yourself:

Then there are those who complain that a std::string is slower then a char * yet they never seem to compare the most common use of strings because if they did they would be surprised to know that assignment of a string is exactly the same as assignment of the char pointer in speed and in syntax.
They would also be surprised to know that comparision in actuality is exactly the same. It also seems more syntatically correct too. Lets compare shall we:

if(a==b)            // std::string way
if(!strcmp(a,b)) // char * way

Most of their arguments also float around the idea that C++ is just too complicated and the syntax is horrible. Yet in actuality the reason they bring up that argument is because of their inability to learn how templates or class inheritence works, and instead they resort to doing everything the wrong way. If you want to write C then write C in a .c file not a .cpp file, or atleast have the decency to wrap the section of code in a extern "C" scope. If you can't isolate the C-only code because it's scattered all over the place then think about wrighting your project in C!

Graphic APIs -- When will it end?

Recently I've been aggravated at the stupidity involved in graphic apis.  We're all aware of OpenGL's attempt at removing all fixed functionality in favor of a programmable pipeline; however who's inane idea was it to get rid of immediate mode?  Now it takes three times as much code to setup a single quadrant, and involves the use of a shader. I'm told that the 'new and improved' api is suppose to be heaps more efficient and well tailored for modern day GPUs.  Excuse me how is three times the code and the use of a shader more efficient then plotting a GL_QUAD.

With the ongoing efforts of maintaing code, people have resorted to using rendering abstraction libraries like the one used in the clutter project cogl3d, while some are forced to write their own. Consider a situation where I would like to draw a quadrant for systems whos GPUs are incapable of shader programs, what are my options?

Forget about platforms that are old and stop providing support:
I like to support older hardware, only because it expands my user base allowing me to recieve positive feedback and create a reputation that dignifies who I'm and what I'm capable of.

Write individual implementations for individual systems:
While this may work and provide everything I want as a developer, it is a waste, hard to maintain and it's easy to break your legacy functionality when you implement new functionaility.

Write one implementation in OpenGL 2.x and use that:
While in actuality this is a decent method, there is situations where
I would like to take advantage of shaders to provide enhanced visuals, for systems that have the capability to do so.

With that said my options are absoloutly none so I'm forced to pick one, in the end my perfered method of choice is stick to OpenGL 2.x. While this may have serious fallbacks in the future as you would expect, atleast the documentation for OpenGL 2.x is not limited like the new 4.1 specification, and at least I have my quads.