Physics(Again)

I haven't had that much time to sit down and code away but, there were a couple things I wanted to mention.

First, multiple inheritance:  it's wonderful.  There's this idea that language features that can result in you shooting yourself in the foot are bad.  I disagree with this.  Language features don't shoot programmers' feet, programmers shoot programmers' feet.  Using a language feature is a privilege.  That feature doesn't owe you anything so if you use it without fully understanding it, too bad.

This does of course mean that if you should never use it in an environment where others may not know it or expect to see it.  As with every feature it has a time and a place, much like how you should be careful about using the ?: operation as it can result in difficult to read code.

Now, I've been shot in the foot before, I'm actually really great at it.  But if you look closely, no two bullet wounds (or at least no.. four, I'm going with four) upon my foot look the same.  And as this project is devoid of other people's feet entirely, I get to experiment.

This brings us back to MI, people have shot themselves in the foot with this before.  Some people with C-style casts and forward declarations, others with diamond inheritance and I'm sure there are many more interesting ways I just haven't run into.  This has resulted in this idea that it's dangerous.  And it is, I suppose. But, more importantly, it's versatile.  The main point I'm getting at is Policy Based Class Design which often relies on MI (and templates.)

My initial idea for the Policy Based Class Design bastardization in C# was to hide all the routing to interfaces in routing interfaces which the PhysicsEngine would inherit from.  This required that those interfaces had either a pointer to an implementation (which isn't allowed) or a function (or property) that would retrieve that pointer, allowing the functions of IBroad, for instance, to be overloaded to a simple routing to that pointer.  This isn't possible because first, interfaces can't have data members and second, properties/functions have to be public, which I don't want.  The solution would be multiple inheritance of classes but, that's not supported in C#.  For shame.

This means I'll have to do the routing within the PhysicsEngine which will cause an even greater level of coupling with implementations and a lower ease of extending.

The second thing I wanted to talk about is the first implementation: the spatial hash grid.

I had considered doing a few different Broad Phases initially, one of them being the Quad Tree which I've already done a couple time.  I settled on the spatial has grid for a few reasons.

0)  It implements all of the extension interfaces I've thought of (IBroad, ICull, IAdjacency).  It does this better than any other implementation I've thought of as each of these are very fast.  The first weeding for all 3 implementations is O(1) (hash grid cells) and the second weeding in O(n) for very low numbers of n (the number of PhysicComponents in the hash cell.)

1) It's scale-able.  The Spatial Hash Grid, perhaps more than any other implementation, scales very well.  You can configure it to use more memory and that will decrease the processing time needed (the n mentioned before will drop) or to use less memory which will increase the processing time.  This is good for an engine that will (eventually) deploy to the Vita (and ps certified smart phones) as well as the Xbox and the PC.

10) I haven't done it before.  I love learning.

Oh, numbered items, how you allow for geeky programmer jokes.

When I have a bit more time I'll discuss the spatial hash grid on it's own.  I should figure out a way to keep track of what blog topics I've promised to post about...

Physics

I did a quick UML of the Physics Engine portion of SBEngine.  I love the idea of UML but, I really need to brush up on it.  I'll do that at some point, make sure my arrows are pointing from A to B instead of B to A and what not.  That doesn't really matter for now, what does matter is that it's all diagrammed out and it's going to be interesting to implement.


The main component of any Physics Engine is the Collisions.  Collisions are traditionally split into two phases: Broad and Narrow.  The Broad phase does fast, inaccurate calculations to weed out the collisions that definitely won't happen, the narrow phase does slow, accurate calculations and passes the results to be handled elsewhere (generally by the Objects that collided).  The Broad phase is further broken down into Partitioning/Sorting and Bounding Volume Collisions.

Now, the Narrow phase and BVC subphase both accomplish what they set out to do and little more.

The Partitioning/Sorting phase, though, can accomplish much more than what it set out to do (weed out impossible collisions.)  What it can do, however, is dependent upon the implementation.  For instance, finding out what is next to a specific object (for AI reasons) is very easy in a Spatial Hash Grid, a little harder in a QuadTree and very annoying in Sort & Sweep (Don't worry, the specifics aren't important now, and I'll cover them in another post sometime.)  So how do we approach this from a design perspective.

What we want is a Physics Engine class that you can configure.  The Physics Engine should be the Gateway into everything.  That said, you should be able to pick what the underlying Broad Phase implementation is but, you shouldn't have to get that implementation every time you want to get the implementation specific function.  Ideally the Physics Engine's interface would change depending on the implementation that you choose.

How I wanted to do this:


template < class BroadPhaseImplementation >
class PhysicsEngine : public BroadPhaseImplementation{
...
};

This is policy based class design.  What's good about it?  It fits this problem perfectly.  If I want to route Drawing through a culling process in my HashGrid, I just expose the public function in HashGrid.  That way that funtion will be in PhysicsEngine<HashGrid> but not in PhysicsEngine<NotHashGrid>.

What I'm going to end up doing:


Now, a large reason I'm building this engine is to have something out there for XNA/PSM development.  This means I'm going to have to use C# and C# does not allow inheritance of their template-equivalent generics.  This means I've had to go about it in a much less 'open' manner.

Every PhysicsImplementation will inherit from the PhysicsImplementation interface.  They'll also potentially inherit from different strategies (like a IGetAdjacency strategy).  The Physics Engine will inherit from all of Strategy interfaces.  If the Implementation supports a particular strategy any call to that strategies functions (PhysicsEngine.GetAdjacency() for instance) will be routed to the implementation.  If the implementation doesn't support it, it'll throw an exception.

Why is this worse:


Runtime errors instead of compile time errors is the big thing.  If you tried calling a function that HashGrid had on a Sort&Sweep PhysicsEngine in the Policy based design, it just wouldn't compile.  In this case it will compile but it will through a run time error.

Extensible; if a new implementation comes to the forefront that happens to allow something that no other implementation before it does, I'll have to create an interface for it, a router for it, have it and the PhysicEngine inherit from the interface.  In the policy based design I could just add the function to the implementation and be done with it. 

I'll post the UML when it's a bit more correct.

SB Engine

The Intro

I’ve decided that I want to develop a game for multiple platforms.  That decision came over time, let’s take a look at its evolution.

First, I needed to develop a prototype.  This was for a class and the prototype had to be in XNA.  I ended up creating a space combat prototype.  It was tons of fun, though it deviated a lot from the initial design.  It ended up as a game in which you would mine an asteroid during a ‘rest’ period and then fight off a wave of enemies followed by another rest period.  The asteroid mining would give you some resource which you could upgrade your ship with.  As a prototype it is great, as a game it is obviously lacking.  I’ll talk more about the prototype (called StarBase hence the SB Engine in the title, more on that later) in another post. 

For now, all that’s important is:

A)  I liked a lot about the game and it inspired me enough to make me want to develop a different, similar game.

B)  I enjoyed creating the quad tree physics the most and it would have completely blown up the Xbox 360 without it (due mainly to a lack of multithreading.)

C)  I made a cool bloom Shader for the lasers which I’ll post about (both my implementation and what I’d do differently.)

D)  I enjoyed XNA.

For a short period of time I considered going back to C++ and making an engine mainly from scratch (I can do that because I'm a student and it'd look good.  You shouldn't do it if you want to make a game.)  I ended up dismissing the idea and went back to XNA, then I heard about PSM and decided to take the challenge of going both routes.

The Thrilling First Act


With all of this in mind I decided that I should look into extending the game; well, more starting from scratch while keeping some of the main concepts alive.  The main reason I decided to go to C# instead of C++ is that it's a lot easier to translate high level ideas into C#.  The quad tree I made would have taken a bit longer in C++ for instance, it probably would have run faster but, it would have been programmed slower.

I'll discuss the specific parts of the engine later on but, for now I'm going to talk about the cross platform nature of the Engine and what that entails.

The first step is going to be figuring out the interface of the Engine.  Some parts will not require porting: the physics for instance will be all coded by me for reasons I'll get into in another post, the Game concept class (such as GameEvent) and many other subsystems which dance the line between Engine and Game.  Some parts will need to be ported, most obviously the Input, the Graphics and the Sound.  This will require me to make an abstraction layer.

The second step will be getting a build system set up.  As fun as it is to open VS, build the XNA project then open PSSuite (based on Mono) and build the PSM project, having an automated process will make my life much, much easier.

The third step will be... Actually coding those parts.  More on that later.

It's going to be very fun.  I just hope I make it through alive.