Author Topic: My Game Engine is too Lame  (Read 58211 times)

0 Members and 1 Guest are viewing this topic.

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
Well, I discovered and fixed a major bug with the joint constraint rotation limits --- apparently the oriented_axes matrix was wrong, and it resulted in some crazy whip-like motion.



Unfortunately when I re-enabled enemies (20 of them) the game ran at a craptastic 2 frames a second.

Big-picture pseudocode/outline of my how my physics is set up, relevant to question below:
Code: [Select]
execute at PHYSICS_TICK_FREQUENCY hz:
begin populating a "constraint graph"; a graph where nodes = rigid bodies and edges = physics constraints

do collision detection; contact points get added to constraint graph
add other less transient constraints (e.g. joint & placed foot constraints) to the constraint graph

break the constraint graph into subgraphs (static objects don't merge subgraphs)
for each subgraph:
active_constraints = all the edges in that subgraph
repeat MAX_SEQUENTIAL_SOLVER_ITERATIONS times or until active_constraints is empty:
new_active_constraints = empty
for each constraint in active_constraints:
constraint does its thing
if it applies a nonzero force/torque/impulse/whatever:
add all the other edges from the two nodes this edge connected to new_active_constraints
active_constraints = new_active_constraints

So, the amount of work it has to do per second is proportional to PHYSICS_TICK_FREQUENCY * MAX_SEQUENTIAL_SOLVER_ITERATIONS. Recently I had upped PHYSICS_TICK_FREQUENCY from 60 to 360, but now that I'm having performance issues I've changed it back. I also recently increased MAX_SEQUENTIAL_SOLVER_ITERATIONS from something like 30 to 200, but for again performance reasons I can't keep that up.

Anyway, problem is that whenever there's anything more complicated than a single rigid body colliding with a surface, the algorithm doesn't converge fast enough; it ends up going to the full MAX_SEQUENTIAL_SOLVER_ITERATIONS. And most of the time, most or all of the constraints are active each of those 200 iterations. I've tried using a small nonzero threshold to decide whether to apply a force/torque/impulse/whatever (instead of zero) but it didn't seem to make much of a difference.

So my question now is: is there any way I can get this thing to converge faster? I'm open to some minor refactoring of how it tells constraints to do their thing, if it'll help.



Also, I'm working on the code to pick joint orientations to maintain balance given the position of the feet, etc... With 0 or 1 constrained feet, the solution space is basically an AABB in 3*(number of joints) dimensions. But if I constrain the second foot, that invalidates a huge chunk of my solution space. I could possibly do it by minimizing the difference between where one constraint says a bone should be and where the other one says it should be? I'm already planning on scoring configurations based on how well they keep the center of mass over the feet, keep the torso upright and oriented properly, etc., so maybe I could just incorporate "bone xform consistency" as another part of the scoring criteria?

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
I've given up on trying to solve this with "correct" physics, i.e. achieving balance/locomotion using friction between the feet and the ground. Now it cheats and applies a magical force/torque to each bone to make it conform to the desired pose. And it works.

One of the next things I need to do is set up the actual character animation stuff... and I'm revisiting the idea of neural nets!

The inputs would be:
  • Bone/joint states, possibly expressed as pos/vel/ori/rot for each bone; maybe limited to a subset of the bones' states, e.g. just the lower body.
  • End effector targets, i.e. where I want the feet to go
  • Velocity of the center of mass, or maybe some other representation of "how fast and in what direction am I trying to move?"

From this it would output:
  • Orientations for each joint, maybe limited to a subset of the joints, e.g. just the lower body; the values would be specified for a short time in the future
  • Change in net velocity?

I would train it with examples of actual walking animations for walking on various surfaces. So it would learn to interpolate/extrapolate for other kinds of surfaces. The same setup would probably work just as well for the bugs' walk animation as for the player.




Anyway, I was confused by maths on http://en.wikipedia.org/wiki/Multilayer_perceptron but apparently it's a goddamn typo. Some idiot wrote:

         phi(yi) = tanh(vi)        and         phi(yi) = (1 + evi)-1

When I'm pretty sure it should have been:

         yi = phi(vi) = tanh(vi)        and         phi(vi) = (1 + evi)-1

But I'm not sure that's right, so I'm not going to edit it. Can someone confirm? Also, does what I'm doing make any sense / seem like a good idea?

 

Offline Mongoose

  • Rikki-Tikki-Tavi
  • Global Moderator
  • 212
  • This brain for rent.
    • Minecraft
    • Steam
    • Something
Re: My Game Engine is too Awesome
I think you're right, since y is listed as representing the output value.

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Um... how is your neural network setup, btw? Do you have like a graph or map of all the nodes?

Seeing as NN's are "on the frontier of science," I'm going to get pretty confused very quickly unless you have some sort of map I can look at. :)
Secure the Source, Contain the Code, Protect the Project
chief1983

------------
funtapaz: Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Juche.
z64555: s/J/Do
BotenAlfred: <funtapaz> Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Douche.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
It's an MLP :D

Just a bunch of layers. Every node in one layer is connected to every node of the next layer (with a weight). And it's "feed-forward", i.e. one-directional. I haven't decided on how many nodes will be in each layer yet, though, or how many layers there will be.

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Ok... Not entirely sure why Wikipedia uses tanh as the... activation function? (I prefer the term mapping function, b/c that's what it's actually doing). It could have something to do with neuron simulation rather than anything practical like with a fuzzy logic inference engine (FLIE).

The backpropagation formulae in Wikipedia appears to be right (at least from my experience), although I'm not entirely sure how your going to come up with an equation for dj(n) per node.

I mean, honestly, wtf? dj(n) is most likely vj, or a function thereof? Linear Time-Invarient systems have a desired input, X(s), and an output, Y(s), and typically consists of a controller/compensator in series with a system/plant that it is controlling. Y(s) is the direct output of the plant, and the controller/compensator (usually a PID or something similar) does it's best to make Y(s) match X(s). Whereby, in this sense, dj(n) is analogous of X(s).

...but this is not a LTI system, nor is there a system or plant to be compensated right at that node... it's just the node itself.  :confused:
Secure the Source, Contain the Code, Protect the Project
chief1983

------------
funtapaz: Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Juche.
z64555: s/J/Do
BotenAlfred: <funtapaz> Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Douche.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
Since it seems like you're not getting it, here's a brief overview of how the MLP would function after it's trained:
Code: [Select]
A = the input layer
Do
{
        B = the next layer after A in the MLP
        For each node J in layer B:
                total = 0
                For each node K in layer A:
                        total += weight[J, K] * value[K]
                value[J] = ActivationFunction(total)
        A = B
} until A is the output layer

Or are you just confused by the particular choice of tanh? It has easy-ish derivatives and ranges from -1 to 1, what's not to like?


Anyway, you train it by giving it inputs and the correct outputs that go with them... dj(n) is the "correct" value for the jth output node when given the nth set of inputs. It's only applicable to the output layer, and you have to know what the correct outputs are in order to do any of this.




Meanwhile, I'm making progress on implementing this. I've just gotta figure out these partial derivatives, and then code up the solution and a few other code thingies, and then test it on something simple.

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Alright, I figured out what was bothering me about that page.

The wiki page says that dj( n ) is the desired output from node j, and yj( n ) is the actual output from that same node... however, it doesn't make any sense to get a value directly from the output of the node, because it's not applied directly to whatever system it's supposed to be controlling. This is like auto-tuning a PID controller to an arbitrary value before even attaching the system it's supposed to be controlling.

Now, going back to animations... it might make sense if dj( n ) was known via an animation frame. I don't know if the NN will interpolate between frames correctly, however, because the sequence of placing one foot in front of another is important.

I also don't think your current input/output set will work for inclines, but I guess we'll see what happens. ;)
Secure the Source, Contain the Code, Protect the Project
chief1983

------------
funtapaz: Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Juche.
z64555: s/J/Do
BotenAlfred: <funtapaz> Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Douche.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
@z64555: as I said, you have to know what the correct outputs are in order to do any of this. I give it a set of inputs and the correct outputs that go with it, and it learns. Speaking of which...

void MultiLayerPerceptron::Train(float* inputs, float* correct_outputs, float learning_rate); :D


I implemented something! I've been testing it to verify that the method works as intended... and it doesn't. It sometimes kinda works, but there's definitely something wrong with my implementation, and I don't know what. :(

Example test scenario:

Given this:

        float x = Random3D::Rand(-0.75f, 0.75f);
        float inputs[] = { x, 1 };

I am training it to compute this:

        2.0f * x * x - 0.25f


The error almost always decreases initially, and sometimes it will gradually converge to some fairly small value (e.g. starting at 0.6, getting as low 0.04), but other times it will be stupid and increase. And I'm not talking about a small increase between two trials (i.e. what you might expect if the learning rate were too high); I'm talking about the average over 50-trial intervals gradually increasing from something almost-decent like 0.1 up to something horrible like 0.7.



I'll continue to work on this, and maybe post pseudocode/code if I can't make any progress on my own.







Update/Edit!
Yay, I fixed it.  :D It was something stupid. I had a loop which repeated as many times as there were inputs, when it should have repeated as many times as there were outputs.

Edit II: Never mind it's still broken.









Edit III:
Ok, there are 2 things I'm not sure about.

  • The formulae on the wikipedia article on multilayer perceptrons says...

            delta-wji = -n * (partial derivative of error w.r.t. vj, the "induced local field") * (the output of the previous neuron)

    First off, it took me a long time to figure out wtf "induced local field" was supposed to mean  :mad:, but I eventually noticed that vi in the messed-up formulae at the top was "weighted sum of the input synapses". And then I realized it didn't even matter because I've got a formula for the bottom layer, and then I've got a formula for a layer in terms of the partial derivatives already computed for the layer below it.

    But the question I'm left over with is, why is it multiplying by yi? Is it to make it only change the parts of the NN that are actually in use for the particular sample? If that's it, could negative values of yi be causing it to "un-learn"? :confused: Because if that's it, then this formula must be assuming phi(vi) = (1 + e-vi)-1 ... but I'm using phi(vi) = tanh(vi:blah:



  • I don't get whether I'm supposed to apply the changes as soon as I've computed them, or wait until I've computed all of them. The end of the "Multilayer perceptron" article says
    Quote
    So to change the hidden layer weights, we must first change the output layer weights according to the derivative of the activation function, and so this algorithm represents a backpropagation of the activation function.
    ... which suggests that I need to make the changes as soon as I compute them. But in the article on backpropagation there's this bit of pseudocode1 which pretty clearly indicates that I should wait until I've computed all the changes before I apply them. And it doesn't say anything about the computation of delta_wi depending on the values that were computed for delta_wh:confused:




1 I can't just put this inline because it breaks the [list] tags:

Code: [Select]
    Initialize the weights in the network (often randomly)
    Do

        For each example e in the training set

            O = neural-net-output(network, e) ; forward pass
            T = teacher output for e
            Calculate error (T - O) at the output units
            Compute delta_wh for all weights from hidden layer to output layer ; backward pass
            Compute delta_wi for all weights from input layer to hidden layer ; backward pass continued
            Update the weights in the network

    Until all examples classified correctly or stopping criterion satisfied
    Return the network
« Last Edit: August 22, 2012, 07:22:53 pm by Aardwolf »

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
Ok, I seriously need to figure out this profiler nonsense. For more info on what sort of bull**** I've had to deal with, look at some of my previous posts in this thread. :banghead:

I either need a better profiler, or changed build options.



What I've tried:

I've been using AMD CodeAnalyst. I've tried a few other free profilers, and all of them had the same problems CodeAnalyst had, with worse interfaces.

I've tried changing some build options, but I haven't managed to get the problems to go away... at least, not without making the simulation run at a snail's pace (i.e. unplayable). And I don't remember whether that actually helped with the profiler output  :doubt:



Possible leads?

I'm wondering if it might have something to do with multithreading. There's really only one part of my program that's multi-threaded, and that's the loading screen... it's multi-threaded so that the GUI doesn't lock up while stuff is loading. I suppose OpenAL is also doing its stuff in its own thread (or its own process?).

Also there's the Lua scripting. I imagine that if the profiler tries to examine the call stack when its going from my code through a Lua script and back into my code, it might not be quite accurate... but that just doesn't seem like it could account for the level of bull**** I'm encountering.



Build options stuff:

I'm using MSVC++ Express 2010. My solution is set up with a static library and a handful of executables that are linked with it (e.g. the FPS, and a test program for the destructible terrain). So when I'm making changes I've got two projects' settings to deal with. I've tried disabling various optimization options (albeit not very scientifically), but to no avail.

Things that didn't do it, at least individually or in the combinations I tried them:
  • Turning "Whole Program Optimization" off
  • Turning "Enable Function-Level Linking" off
  • Turning "Enable COMDAT folding" off
  • Turning "Enable Intrinsic Functions" off
  • Turning "Inline Function Expansion" off






Help!

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Do you have some sort of 3rd party utility that you can use to monitor each core's usage?

If you program is indeed using only a one or two cores, then the utility should be able to show it.
Secure the Source, Contain the Code, Protect the Project
chief1983

------------
funtapaz: Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Juche.
z64555: s/J/Do
BotenAlfred: <funtapaz> Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Douche.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
:confused: It only ever uses 50% of my CPU, i.e. one of the two cores.

There's only one "big" thread running when the profiler is active. The only time I explicitly create another thread is the loading screen, and I only unpause the profiler after the loading screen is finished and the game has started. How could a thread which has already finished be causing problems? Or do you think it's some thread I didn't explicitly create, e.g. if OpenAL decided to create a thread?

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Well I mean when your game engine is running by itself, and with the profile inactive. If the profiler's forcing everything to be in a single thread, that could be a big contributer...
Secure the Source, Contain the Code, Protect the Project
chief1983

------------
funtapaz: Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Juche.
z64555: s/J/Do
BotenAlfred: <funtapaz> Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Douche.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
 :confused: :confused: :confused: I do not understand this "forcing everything to be in a single thread" business.

My program is mostly single threaded. That's how I set it up. I didn't tell my code to execute on multiple threads except in the loading screen, so it won't be executing on multiple threads. Maybe some code from some library (e.g. my go-to example: openal32.dll) might be running in a separate thread, but my code by design runs in a single thread.

Do you mean that maybe this profiler is too dumb to deal with a multi-threaded program, and is seeing stuff happening in multiple threads and recording the data wrong because it doesn't know about threads?

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Do you mean that maybe this profiler is too dumb to deal with a multi-threaded program, and is seeing stuff happening in multiple threads and recording the data wrong because it doesn't know about threads?

Yep, that's what I mean.
Secure the Source, Contain the Code, Protect the Project
chief1983

------------
funtapaz: Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Juche.
z64555: s/J/Do
BotenAlfred: <funtapaz> Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Douche.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
Oh, durrr.  :P

Well, I've gone back and looked at the website for AMD CodeAnalyst, and it at least claims to be able to deal with multi-core applications. And considering all the other free profilers I tried had the same or similar bull****, I'm leaning toward it being something with my build options now.

I'll redo the experiment of seeing whether there's any similar bull**** in the debug build... if there isn't, that's progress. If there is, at least I'll know.



Edit: well, apparently there's much less bull**** with the debug build, but there's still some. A few examples:

sqrtf thinks it's calling CibraryEngine::Vec3::operator*=
malloc thinks it's calling boost::unordered_detail::hash_bucket<std::allocator<CibraryEngine::PhysicsConstraint *> >::hash_bucket<std::allocator<CibraryEngine::PhysicsConstraint *> >
CibraryEngine::AABB::AABB thinks it's calling std::allocator<boost::unordered_detail::hash_node<std::allocator<CibraryEngine::RigidBody *>,boost::unordered_detail::ungrouped> >::deallocate
RtlAllocateHeap thinks it's calling CibraryEngine::Octree<CibraryEngine::TriangleMeshShape::NodeData>::ForEach<CibraryEngine::TriangleMeshShape::RelevantTriangleGetter>



And then there's some stuff that I wouldn't quite call "bull****", but which I don't know what to make of. Low-level functions with names like ILT+34825(?_Isnil?$_Tree_valV?$_Tset_traitsPAVPhysicsRegionCibraryEngineU?$lessPAVPhysicsRegionCibraryEnginestdV?$allocatorPAVPhysicsRegionCibraryEngine

I'm getting weighed down by all this bull****... because I don't remember whether I saw that variety of gobbledygook in the release build or not.



Note, the debug build runs at < 1 fps (versus about 16 fps in release).
« Last Edit: September 11, 2012, 12:42:11 am by Aardwolf »

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
:bump:

I tried using the debugger's pause function and looking at the call stack (which should be sort of how the profiler works), and occasionally it comes up with similar kinds of bull****. Here's an example:

When I paused it, the bottommost things on the call stack were:

Code: [Select]
KeyframeAnimation::UpdatePose(TimingInfo)
free(void*)
_CIexp_pentium4()

In other words, bull****. So I used the debugger's "step out" function to see what was really calling that function, and eventually got to CrabBug::PoseCharacter (i.e. not bull****).



Conclusions: it's not a profiler issue, and evidently it's not a threading issue either...

Apparently that _CIexp_pentium4 function is SSE-related, so maybe that's worth looking into? Please advise!


 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Looking better!.  :yes:
Secure the Source, Contain the Code, Protect the Project
chief1983

------------
funtapaz: Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Juche.
z64555: s/J/Do
BotenAlfred: <funtapaz> Hunchon University biologists prove mankind is evolving to new, higher form of life, known as Homopithecus Douche.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
So I'm still working on this...

I recently started on a sizable bit of refactoring. I've changed things so that rays (or point particles, whatever you want to call them) are no longer just RigidBody objects with a specific type of CollisionShape. Now instead there are two classes, RigidBody and RayCollider, which both extend a new class called DynamicsObject, which in turn extends CollisionObject.

Now I've moved on to the second half of the task, creating another subclass of CollisionObject called CollisionGroup class, which represents a bunch of rigid bodies that are confined within a small volume... the goal is to have a single item in the spatial partitioning system which stores all of the bones of a dood... since the doods are small compared to the cells of the grid, it should work out to be more efficient this way.

I'm just about done coding up the CollisionGroup class, and then it'll be time to make the game actually use it... and debug why it doesn't actually work. (Edit: I got it integrated and working :D)




In other news, I discovered something annoying about the protected keyword in C++ (which IIRC was different in C# and/or Java)...

If I have this:
Code: [Select]
class CollisionObject
{
     protected:
          virtual void DoStuff() { Debug("default behavior"); }
};

class RigidBody : public CollisionObject
{
     protected:
          void DoStuff() { Debug("overridden behavior"); }
};

class CollisionGroup : public CollisionObject
{
     protected:
          vector<RigidBody*> children;
          void DoStuff();                        // various attempted implementations below
};

Note, this is altered a bit from my actual code; I removed the intermediate DynamicsObject class for simplicity.


The following code doesn't compile; the compiler complains that CollisionObject::DoStuff is inaccessible, even though CollisionGroup is derived from CollisionObject!
Code: [Select]
void CollisionGroup::DoStuff()
{
     for(vector<RigidBody*>::iterator iter = children.begin(); iter != children.end(); ++iter)
          (*iter)->DoStuff();
}


This doesn't work either:
Code: [Select]
void CollisionGroup::DoStuff()
{
     for(vector<RigidBody*>::iterator iter = children.begin(); iter != children.end(); ++iter)
          ((CollisionObject*)*iter)->DoStuff();
}


There are two ways to make it work, and they both suck. One is to declare CollisionGroup as a friend class in CollisionObject... which is not a good solution, because it means I can't have additional classes that derive from CollisionObject and want to use their peer's DoStuff method, without modifying the declaration of CollisionObject.

The second way (which is what I'm doing now) is equally horrible:
Code: [Select]
void CollisionGroup::DoStuff()
{
     for(vector<RigidBody*>::iterator iter = children.begin(); iter != children.end(); ++iter)
          ((CollisionGroup*)*iter)->DoStuff();
}




I literally shuddered when that compiled successfully.
« Last Edit: October 12, 2012, 06:07:21 pm by Aardwolf »