Jemgine

I sound like an idiot.

Gravity

You're welcome, spliter.

Node Scripting

Drips

Plasma

Actually it's just metaballs. But it looks neat.

Threading Jemgine

I recently made a false step into threading Jemgine. What I did was make scripts execute in their own thread. My scripting system isn't what you expect, though. There isn't a scripting language. Instead there are nodes connected in the editor. It is a sort of visual scripting language. This actually proved to be a really simple thing to do. But I immediately saw problems.
The simple problem is modifying the physics information associated with an entity. A script might want to apply a force, for example. Now, what happens if the script does this in the middle of the physics module being updated? Well, I don't know. I never actually saw it happen. Or if I did, I didn't recognize it. If that's the case then maybe it isn't such a big deal; but still I don't like it. As I said this is the simple problem. The solution is to queue all physics changes. It makes sense for a script that affects physics to do it through the physics module, and in a threaded situation it definitely has to. The physics module queues up all these impulses and what nots and applies them in between updates. It's not the most elegant solution, but it works well and solves that problem.
The harder problem is not setting data, it's reading it. The physics module updates the position stored in the entity after the update. If a script happens to read the position (or any other property that the physics module is in charge of) right when the physics module is updating it the script could get a half-updated value. I'm not sure if, in C#, it could get a half-modified float, but I know it could get a half-modified vector. Solving this is not hard per-se. What it requires is for the thread updating the physics information to stall any other thread querying that info until it is done with the updating. It sounds simple, but these properties are just simple values. I'd need to attach some access control to them. The simplest way to do that is to require the script to query this data through the simulation (Or the physics module, since it already owns the access control in question) But, this information is redily available through the entity itself. I don't like any solution that requires discipline on the part of the programmer, but I can't think of a better solution.
The hardest problem is when objects are destroyed. Creating them is no problem at all. No script can be using an entity that's not even created yet. But, when an object is deleted, who knows how many scripts are right in the middle of changing it. This might not be a problem. The object instance will remain valid as long as the script is refering to it. That's not the problem. But, it's components might not. Other things might vanish unexpectably if that entity is destroyed. And I see no simple way to solve this.
There are bigger problems. How do I create an entity in one thread if the physics are being created in another? Adding a new physics body in the middle of a physics update would be fatal to the simulation. But I can't delay it. I need those bodies created so I can create the joints. So, I need to stall this creation until the physics thread is done updating. Threading looks less and less valuable.
A database based (excuse me) system doesn't have these same problems. It has other problems, but these that are plaquing me are simple. Unfortunately, a database system isn't going to work with Box2d anytime soon.
So what threading options are available to me? Well, I can go forward with this way which, despite all the problems, does represent a signifigant performance increase, so long as you have multiple cores (And the 360 has 5). I would have to be stalling scripts all the time, but I can mitigate some of that by having multiple script threads running. The main problem here seems to be that scripts and physics run in different threads. What if they ran in the same thread and everything else ran in another? There would still need to be some synchronization. And the script/physics thread would have to keep track of timing information to keep the physics running smooth.

Codeplex

Jemgine is now on codeplex at http://jemgine.codeplex.com/

“Sparse Components”

There was an interesting discussion on the sweng-gamedev mailing list recently about 'sparse components'. It branched into the topic of software architecture and design. In between the bickering and the hate for object-oriented programming and C++, there was some real useful information. As with anything, it takes time to wade through the crap to get the gems, but I've already done that.

Sparse Components aren't a new idea. The term isn't terribly accurate, either. What it is is a step away from the usual way of doing things with object-oriented programming where you'd have an entity object, and a family of virtual functions on that entity object that are over-ridden for specific entity types. The component-based model is already a step away from that, in that there's a single entity type (in the programming language) and you create many entity types (in the game) by mixing and matching components. But in most component-based system, the component object itself is a polymorphic object with behavior controlled by a family of virtual functions. And, in fact, that's how I've been doing it all along; I'll get into why this is or isn't a good idea.

So what's wrong with this approach? It's certainly better than having a hierarchy of entity types for reasons I won't get into here - lets just assume you already know the benefit of the component model and want to use it. The problem is those virtual functions and how you call them. It is not virtual function call overhead; that's so minuscule to not be worth worrying about. If you have a container of heterogeneous types and you're firing off virtual functions on them, you're potentially calling different code for every single call. And that's the problem, you're constantly moving code into and out of the cache. The biggest cost is that cache miss. That's where a non-virtual component interface comes in.

Instead of keeping a list of entities which each contain a list of components, keep several lists of components. A list for physics components, a list for render components, etc. Now you can update all your physics components at once. You can keep using your virtual functions - you'll still see an immediate benefit because each call is going to the same virtual function; the cache will stay nice and warm and you won't miss at all.

But we can go one step better. We keep this list of physics components in the physics module. The physics module knows how to update them, so instead of calling a function on the component, it just does it. Updating these objects becomes a tight loop over homogeneous data. We can do the same for render components to apply transforms or whatever. Instead of a single loop over heterogeneous data doing many things, we have several smaller loops over homogeneous data doing one thing each. There are far fewer cache misses. This is what the term 'sparse components' is failing to describe. The behavior lives in the module, not the component itself.

This isn't quite how I've been doing it. I have something of a hybrid approach going. Some systems work that way, some don't. My physics almost do, entirely accidentally. The physics module is it's own self contained thing, and however it works internally, I don't think it invokes a lot of virtual functions. The cache should be doing fine, and there's not much I can do about it either way anyway. So I was accidentally using a 'sparse component'; my component was just data, no behavior. The behavior was all handled by the module running it. But not every system works this way (And I'm afraid not every system can) but I'm going to do as much as possible to improve it. I might even have to dig into Box2d and make changes there.

This method does not reap a benefit for a small number of game objects and components. Lets make that clear. If there are only a few dozen objects, and especially if they are all different, there is no benefit to structuring your game this way. Several different loops that update just a few objects each isn't going to be faster than a single loop that updates a few dozen objects in different ways. The overhead of the additional lists might even make it slower. You need many objects to reap the real benefits of this approach. Hundreds or thousands of them.

And C# is really, really bad at this sort of thing. Just an FYI. It's because you can't stick classes into continuous memory, and structs can only be dumb data. Maybe it's a good excuse to normalize your data. Mostly it's just a pain in the ass, and almost makes me want to switch back. If only everything else about C# wasn't so nice.

The discussion shifted to stream-based processing and a new way of thinking about your programs. Every program can be broken down into two things. State Objects and Processes. Processes take State Objects as input, and produce State Objects as output. This seems kind of silly and obvious at the same time. That's exactly how every program ever made works, it's just a matter of realizing this, and then using it to our advantage. You already take an object and transform it through some process into a new object. (Okay, you don't always make a copy. But that's just nomenclature pedantry.) But what happens when you structure your program with this in mind? Instead of transforming an object, you transform many objects.

Your process can take a stream of objects and transform them and output another stream of objects. This is the same optimization we got with Sparse Components! I've not yet explored all the benefits of this new way of thinking. There's a psychological barrier; I'm solving problems now that I know how to solve with object-oriented programming techniques. I need a problem that's not trivial to solve with what I already know. This stream-based paradigm is very similar to the graphics pipeline, though. Verticies are input as a stream and processed by the vertex shader, which produces a new stream of verticies. These verticies are fed into the rasterizer or a tessellation shader, and so on. The key here, I think, is that you don't perform the entire operation on each object one at a time, you perform part of the operation on every object, and then more on every object, and so on.

We'll see what happens. First, I need to make some minor changes to Jemgine's physics module. Changes that can take advantage of this new knowledge right now. And then I might explore any benefit an intrusive linked list would have over C#'s generic collections. And I should see if there are any updates to box2d.xna available.

Tracks