The next generation of game engines...


13-05-2007 09:18:39

Yes, this is a repost from here but I wanted to make sure it reaches the right people; so here we go...

Hello everyone,

it's been a while. BUT, in contrary to popular belief, I wasn't sitting at home, doing nothing - at least not exclusively.

I'm making this post for 2 reasons:
1. I'd like to discuss my concepts(partially adapted from sources) for SAGE.
2. I'd like to see if I can find some decent C# coders to help me out on SAGE.

To find out more about SAGE, click here.

First, let me clarify why I think that it is inevitable that game engines concepts need to be redefined.
We all know that GPUs are important to get decent performance in 3D real time simulation. But some of us also know, that in many cases the CPU is the bottleneck - especially if you want to add advanced AIs, physics, runtime optimizations or other 'fancy' stuff.
Problem is, the last big step in CPU development didn't get us much performance for game engines. They doubled theoretical CPU performance - but sadly inaccessible for single threaded processes because they put it on another processor.

Putting resource loading on another thread was a necessary step - taken by many engines already. But to gain any MAJOR benefit from multi-core CPUs, we have to take another huge step.

Well, obviously, our current operating systems and programming languages cannot take advantage of multiple CPUs by themselves, so we have to aid them - by using multiple threads.

Many of you might think that threads are bad for game engines because they add overheads and/or are too slow for the fast pace needed in game engines.
But IMO, using threads is absolutely worth it for the 200% gain in performance - we just have to do it right.

So. How do we DO it right? Good question, that haunted me for the better part of the last two years.

There are 2 general concepts of multi-threading possible in game engines:
- Data Parallelism and
- Context Parallelism.

Data Parallelism would be: Take a game-object (say the player character), pass it through all modules like physics, sound, AI, scripting, graphics, etc while doing the same with other game-objects at the same time on other threads.
In theory that'd be a very good solution because the thread would never have to let go of the game-object he's holding and thus, data-exchange would be minimized.
Problem is: It doesn't work like that. Different modules have different needs, thus the data that can be kept from module to module would be minimal. Further, many modules have to interact game-objects with each other (physics collision anyone?). With each object being on it's own thread, that'd be a royal mess of synchronization.

Context Parallelism, or "Module Parallelism" as I like to call it, would put each major module on it's own thread: physics, graphics, AI, logics, scripting, whatever.
That'd keep the majority of module-related data within the thread while the minimal part of exchangeable data (mainly position and orientation of a game object) would be exchanged between the modules/threads.

To achieve Context Parallelism there are several techniques, detailed here. (won't discuss them here in detail)

So, as you can see, there are ways to maximize the use of threads.
But there are still the downsides like overhead and delays.
Can we nullify them? No.
Can we minimize them? Absolutely.

The main overhead of threads are created by 2 things:
- Thread creation/destruction and
- Thread communication.

Thread creation/destruction is one very simple thing to work around by keeping threads in a pool and reusing them.

Thread communication is a little trickier to optimize.
Most delays in that department are caused by multiple threads trying to access the same resource(be it a file, a device or just an object in your language). You can either let them all have what they want - and risk evil race conditions and memory corruption - or you can limit access to one-at-a-time and have to cope with locking - which could again cause evil things like deadlocks.
OR you can do what the cool kids do: Use Message Queues.
Problem there is, you still can't skip locking - at least not with traditional approaches. But who wants ancient traditions in a next-generation game engine?

As a result of these "issues" I had to base my entire threading concept on a single technology:
Non-Locking Message Queues.
While one might argue that they aren't portable or stable enough and too theoretical to be seriously used for anything... they ARE more portable than FireFox and they ARE more stable than MS Windows... Plus, my tests showed that the theories work - stable and fast.

So, now that I have the concepts and technologies, what is there left to do?
Implement it and beating the industry to it.

I have seen several concepts pursued by commercial companies. Many of those concepts are less bold - more like "improvements" of the old concepts rather than a "redefinition". Others come very close to what I am trying to do.

But all of them have one thing in common: They aren't done yet.

And wouldn't it be great to have advanced technology in open source before the closed source guys get it?

Now, "dear reader",
what do you think of the concepts?
Do they make sense?
Do you THINK it can be done? Why?
Do you have experience in this field that you could share?
Or do you actually want to help me putting this plan into action?



13-05-2007 16:37:29

For sanity's sake I think everyone should post in the main forum.