Author Topic: My Game Engine is too Lame  (Read 25023 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'm already using MSVC++ as my IDE... but I'm a cheapskate and I want a more permanent solution than that.

In other news, I learned yet another reason to hate AMD CodeAnalyst:

The symbols it displays aren't saved with the saved session data; it loads them from the executable. I have 15 saved sessions which I just discovered are full of rubbish because it's trying to load the symbols from the current executable, instead of having saved what they were when it initially recorded the data.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
I got ragdoll physics working, sort of! :D So far it's all just simple ball-and-socket joints, with no limitations on how far they can rotate. For what it's supposed to be doing it looks passable; occasionally the bones separate far enough for it to look bad, but I think that's something I can worry about later.

For now, it seems as if I'm going to have to redo the multisphere-multisphere collision detection, because that's where it's taking too long currently. I reckon it shouldn't be hard to do better than 512x(between 3 and 8 vector operations, and 1 to 2 array lookups), right? Because that's what my current solution is. After a little over a month of trying to come up with an analytical solution, I came up with this numerical solution in a single day, and got it mostly working. But it's no longer fast enough for my needs :(

So now I'm trying to come up with a better way to detect whether two multispheres are intersecting, and if they are, to pick a normal vector and center point for the collision. Recall, when I say "multisphere" here I mean "the minimum convex shape which encloses a collection of spheres, not necessarily of equal size", i.e. a bunch of balls in shrink-wrap.

Apparently one fairly common technique is to see if you can prove that they aren't intersecting... i.e. if there exists some plane such that one object is completely on one side of the plane, and the other object is completely on the other side, then they are non-intersecting. And there are ways to come up with a finite set of planes to test, so that if none of the planes in this finite set divide the objects, then no such planes exist. This is what I'm working on now.

There's also something called the Separating Axis Theorem which is a more specific formulation of this, which might be able to get me a normal vector and center point as well.

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Throwing neural nets at my program and hoping it makes it work. So far nothing.

Alright dude, what's going on?
I'm on Facebook! sort of. Zeesixtyfour Fivefiftyfive

-=wxFRED2=-
R.I.P. Oliver
------------
EveningTea: Time to go Freeman on this cultist..
* EveningTea pulls crowbar off his shoulderstrap and charges screaming incoherently across the marsh *
------------
z64555: bro. do you even salad
------------
z64555: suprise double quaternion!

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
Throwing neural nets at my program and hoping it makes it work. So far nothing.

Alright dude, what's going on?

Haha, I was just about to post in here :D



What's been going on since my last post:

The big task for a while now has been getting the character animation and the physics to play nicely together.

I've created a JointConstraint class which does a fairly good job of keeping the same point in two objects together, and can also apply torques to keep them oriented a certain way relative to one another. And I recently added limits on how far it can rotate on each axis. My Doods are held together by these.

So what I've been working on recently is telling the joints what orientations to be in in order to achieve certain tasks... tasks like walking, turning in place, or just not falling over. This is where I'm stuck. If the Dood starts out in its rest pose it will stay upright, but if I try to make him do anything, he falls over.



Here's where neural nets come in:

I was hoping I could train a neural net to operate the leg joints for me. The inputs would be the states of each bone/joint in some form, and the outputs would be the orientations for each joint ... or changes in orientation, or whatever. If I get this working, it would be my first successful attempt to use neural nets.

I've made a NeuralNet struct which basically just stores a matrix. I multiply by the inputs to get the outputs, and then do something like f(x) = x / sqrt(1 + x*x) to keep the range between -1 and 1.  Right now I'm using genetic algorithms to make it "learn", but it's not working very well... if it keeps failing, maybe I will get off my butt and look up how to do back-propagation on the Internets.

In the meantime, I've been trying to simplify the inputs and outputs. I'm thinking about changing stuff to have the following inputs (which is slightly less than what I have now)...

  • For each joint (left & right ankles, knees, hips; base of spine):
    • Relative orientation
    • Relative angular velocity
  • For each foot:
    • Difference from desired position
    • Difference from desired orientation
    • Derivatives of both of the above?
    • Something to indicate if the foot is supposed to be kept in place at the specified pos/ori, or if not, how long until it is supposed to arrive there
  • "Root" stuff, all specified in the coordinate system of the pelvis, torso, or something like that:
    • Gravity vector
    • Position and velocity of the center of mass
    • Desired velocity the CoM should maintain after doing whatever it's doing

Depending how I set things up, that's anywhere between 65 and 90 inputs. From these inputs, it would determine the orientations for each of those joints. That's 3 degrees of freedom for 5 joints (2 ankles, 2 hips, an the base of the spine), plus 1 degree of freedom for each knee, = 17 outputs. For comparison, the setup I have now has 125 inputs and 21 outputs.

Then I would score the neural net based on how well it kept the placed feet in place, got the moving feet to their destinations at the right time, and with the right amount of average velocity left over. And managed not to fall over.



But I'm probably doing this all wrong :(

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Eh, I'm going to have to get back to you on this one. I don't believe neural net's are needed in the application, but I think they'd be fun to play with. Generation training may work well if you can define a criteria to test each generation up against, and then have the program run it for a long while...

During your training/creation of a control system for the legs, make a simplified Dood that has only one spine bone with nothing above it, and have the center of mass at the end of that bone.

Seriously consider using quaternions for the math, back-propagation of linked rotations with them is fantastically easy compared to traditional matrices.

Can you post a pick of the skeleton of one of your dudes?

I'll think about it tomorrow and will edit this post or post anew if necessary.
I'm on Facebook! sort of. Zeesixtyfour Fivefiftyfive

-=wxFRED2=-
R.I.P. Oliver
------------
EveningTea: Time to go Freeman on this cultist..
* EveningTea pulls crowbar off his shoulderstrap and charges screaming incoherently across the marsh *
------------
z64555: bro. do you even salad
------------
z64555: suprise double quaternion!

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
I'm not confident neural nets will help either  :blah:

I've been trying to simplify the problem by only considering the state of the bones from the pelvis down, or possibly including the first bone of the torso, and only affecting the same joints. But I don't think I get away with removing the load of the torso, arms, and head entirely. For now they're just locked in a rigid pose.

I'm already using Quaternions to store the orientations of each bone.

What I would have done is select a "solution" (basically an array of floats, for the 17 degrees of freedom I mentioned earlier) that would best get it from its current state to the desired state. The problem is that I can't tell what the effect of any particular solution would be without fully simulating it for whatever amount of time. Then again, maybe I could simulate just a little bit, to get a sense of what's moving fastest toward the desired state?

I also thought about using a neural net to predict the outcome of a solution... having a neural net which, once trained, would take the current state + a solution as inputs, and would return info about how the simulation would respond to that. And from a conversation I had yesterday, it sounds like neural nets would be better suited to this problem anyway.

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Then again, maybe I could simulate just a little bit, to get a sense of what's moving fastest toward the desired state?

That, and perhaps make an interactive interface where you can control the position of either foot at any given time... so you could position one foot anywhere you want it and see if your current algorithm can keep your Dood balanced.

Of course, there's the old fashioned way of doing it: turn off physics on Actor's and have them run through keyframe animations.  :nervous:
I'm on Facebook! sort of. Zeesixtyfour Fivefiftyfive

-=wxFRED2=-
R.I.P. Oliver
------------
EveningTea: Time to go Freeman on this cultist..
* EveningTea pulls crowbar off his shoulderstrap and charges screaming incoherently across the marsh *
------------
z64555: bro. do you even salad
------------
z64555: suprise double quaternion!

 

Offline Nuke

  • Ka-Boom!
  • 212
  • Mutants Worship Me
Re: My Game Engine is too Awesome
time to break out the pid algorithms.
I can no longer sit back and allow communist infiltration, communist indoctrination, communist subversion, and the international communist conspiracy to sap and impurify all of our precious bodily fluids.

Nuke's Scripting SVN

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
I'm going to try to implement that idea I mentioned about training a neural net to predict the outcomes of certain outputs. And if that works well, maybe I can even train a neural net to skip that step and jut pick the best outputs. Learning how to do backpropagation now. Apparently this thing I'm making is called a Multilayer Perceptron  :nod:.

I reckon neural nets will probably be useful for something, even if it doesn't turn out to be this.  :blah:



Of course, there's the old fashioned way of doing it: turn off physics on Actor's and have them run through keyframe animations.  :nervous:

There are a few things that are making me want to avoid that. For example, I want my bullet-dood collisions to be better than ray-AABB. Also, some of the enemies are going to be big enough that they'll have to do per-bone collision with the player. And also just for the sake of awesome.

 

Offline Nuke

  • Ka-Boom!
  • 212
  • Mutants Worship Me
Re: My Game Engine is too Awesome
problem with neural nets is you got to keep em running, even if you are not using them. i kinda want to see a neural net on chip type processor which does the heavy lifting for you. it would be subdivided into cells, much like an fpga, except instead of being a 1-bit adder/flipflop, it would be a virtual neuron matrix. you could join or divide cells based on the number of independent ais you need, i/o requirements, etc. joining cells makes smarter ais, for robotics applications, divided cells are probibly more suited to games where you need to simulate multiple intelligences. the main advantage is that the chip can run a much higher clock rate than your cpu, since error is tolerable in this application. it would be capable of thinking independent of any command from the cpu, and you only need to bother it when you need to provide stimuli or receive output. main commands would be load matrix, dump matrix, configure, stimulus (input), and reaction (output). the load and dump features would probibly require the device to be digital so that you can save the state of the neural net. but otherwise an analog or mixed device would be preferable. you might be able to do rapid training in software with a teaching program. id really like to see this kind of neural net accelerator.
« Last Edit: August 01, 2012, 07:15:51 pm by Nuke »
I can no longer sit back and allow communist infiltration, communist indoctrination, communist subversion, and the international communist conspiracy to sap and impurify all of our precious bodily fluids.

Nuke's Scripting SVN

 

Offline Thaeris

  • Can take his lumps
  • 211
  • Away in Limbo
Re: My Game Engine is too Awesome
Aardwolf, would it be possible to make a simulation that used the neural network, and then take the output of the simulation and use that as your "locomotion code"? This would allow you to avoid having the network run continually while the game progresses. Applying different code sections to movement depending on the environment ideally would allow for good performance over a wide variety landscapes while minimizing computational draws from the network code, or so I would assume.
"trolls are clearly social rejects and therefore should be isolated from society, or perhaps impaled."

-Nuke


"The Windows Operating System: It can only get worse from here!"

-Me



"Look on the bright side, how many release dates have been given for Doomsday, and it still isn't out yet.

It's the Duke Nukem Forever of prophecies..."


"Jesus saves.

Everyone else takes normal damage.
"

-Flipside

"pirating software is a lesser evil than stealing but its still evil. but since i pride myself for being evil, almost anything is fair game."


"i never understood why women get the creeps so ****ing easily. i mean most serial killers act perfectly normal, until they kill you."


-Nuke

 

Offline Tomo

  • 28
Re: My Game Engine is too Awesome
I kinda want to see a neural net on chip type processor which does the heavy lifting for you.
GPGPU can do that, and relatively easily - inputs and outputs are textures and/or meshes, and a shader does the computations.

GPUs are massively parallel which suit neural nets very well (unlike some other computations)

Integer computations are a pain, but you don't want those for neural nets anyway.

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Integer computations are a pain, but you don't want those for neural nets anyway.

Huh, what?
I'm on Facebook! sort of. Zeesixtyfour Fivefiftyfive

-=wxFRED2=-
R.I.P. Oliver
------------
EveningTea: Time to go Freeman on this cultist..
* EveningTea pulls crowbar off his shoulderstrap and charges screaming incoherently across the marsh *
------------
z64555: bro. do you even salad
------------
z64555: suprise double quaternion!

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
Idunno where this "you got to keep em running" idea is coming from, but it doesn't sound like it pertains to MLPs in the slightest. Not sure what integer maths has to do with anything either  :wtf:




Anyway, I've been rethinking the problem on various levels...


If I stick with per-bone physics for everything...

Revising and rephrasing the problem, the inputs are:
  • The current state of each of the rigid bodies/joints
  • What each foot is supposed to be doing (either staying in place, or moving to a specified new pos/ori). I don't know how exactly I will generate this information, but I don't anticipate it being overly complicated
  • Desired net acceleration; the CoM will be forward from the contact area in this direction
  • Time to plan ahead, probably something like 0.1 seconds

From that, I need to come up with poses (relative orientations) for each joint to move toward, so that they reach that pose at the specified time.

The range of possible positions/orientations for the pelvis in order to achieve an acceptable CoM is somwhat constrained; it has to be within a certain horizontal area in order to keep the CoM balanced, and it has to be at a proper elevation so that both feet can reach it*. The problem is that I'll need to compensate for the torques applied at each joint, and I don't really know how to do that.


Or I could just fake it...

I could do per-bone collisions for bullets colliding with anything, and use a simplified shape for collisions between doods and the environment, or collisions between small objects and larger doods (e.g. for the player vs. an artillery bug; the player would use a simplified shape). I would still need IK or something to make sure feet didn't go through the terrain, even if there's no actual physics backing it up.





*Assume that I won't tell it to put the two feet impossibly far apart.


Edit: I just realized something! If I constrain the placed foot to be immobile w.r.t. the ground, I don't have to worry about any net torques or linear acceleration! Unless of course the thing he's standing on isn't immobile, but whatever; this should be good enough. I'm going to try to implement this.
« Last Edit: August 02, 2012, 04:34:34 pm by Aardwolf »

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Edit: I just realized something! If I constrain the placed foot to be immobile w.r.t. the ground, I don't have to worry about any net torques or linear acceleration! Unless of course the thing he's standing on isn't immobile, but whatever; this should be good enough. I'm going to try to implement this.

That might work, to an extent, of course they'll come a time where you'll need to simulate static and kinetic friction.  :P
I'm on Facebook! sort of. Zeesixtyfour Fivefiftyfive

-=wxFRED2=-
R.I.P. Oliver
------------
EveningTea: Time to go Freeman on this cultist..
* EveningTea pulls crowbar off his shoulderstrap and charges screaming incoherently across the marsh *
------------
z64555: bro. do you even salad
------------
z64555: suprise double quaternion!

 

Offline Nuke

  • Ka-Boom!
  • 212
  • Mutants Worship Me
Re: My Game Engine is too Awesome
I kinda want to see a neural net on chip type processor which does the heavy lifting for you.
GPGPU can do that, and relatively easily - inputs and outputs are textures and/or meshes, and a shader does the computations.

GPUs are massively parallel which suit neural nets very well (unlike some other computations)

Integer computations are a pain, but you don't want those for neural nets anyway.

a purpose build simulated neuron (on a chip) can take up about the same amount of die space than a dram cell. so you could get a denser network that can run faster than anything you could simulate with an array of fpus. a simulated neural net can also only simulate one neuron at a time, so it would take several c/gpu cycles to run one think cycle. and brains dont work in cycles so much in the first place. all neurons operate simultaneously. a purpose built neural net on a chip can be more brain like and be more efficient than simulating the whole thing in software. not to say the gpu couldn't do it. just using an fpu to do the job is kind of like driving a finishing nail with a sledge hammer. to get the most out of a neural net you must abandon binary thinking all together and go pure analog. you want error, you want glitches, you want unpredictable permutations.
I can no longer sit back and allow communist infiltration, communist indoctrination, communist subversion, and the international communist conspiracy to sap and impurify all of our precious bodily fluids.

Nuke's Scripting SVN

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
Oh, I've already got friction. And hypothetically my code is set up to deal with either static or kinetic friction... but in practice, the branch for static friction never executes. Maybe I'll look into it sometime.  :blah:



In the meantime, I've got a performance issue that's tolerable now (when there's only one Dood) but may be a problem later...

Code: [Select]
// enforce joint rotation limits
const float inv_foresight = 360.0f;
const float foresight = 1.0f / inv_foresight;

Vec3 proposed_av = current_av - alpha; // proposed angular velocity
Quaternion proposed_ori = a_to_b * Quaternion::FromPYR(proposed_av.x * foresight, proposed_av.y * foresight, proposed_av.z * foresight); // orientation that would result from that velocity; a_to_b is a quat
Vec3 proposed_pyr = oriented_axes * -proposed_ori.ToPYR(); // rotation in the coordinate system the rotation limits are defined in; oriented_axes is a Mat3

bool any_changes = false;
if(proposed_pyr.x < min_extents.x) { proposed_pyr.x = min_extents.x; any_changes = true; }
else if(proposed_pyr.x > max_extents.x) { proposed_pyr.x = max_extents.x; any_changes = true; }
if(proposed_pyr.y < min_extents.y) { proposed_pyr.y = min_extents.y; any_changes = true; }
else if(proposed_pyr.y > max_extents.y) { proposed_pyr.y = max_extents.y; any_changes = true; }
if(proposed_pyr.z < min_extents.z) { proposed_pyr.z = min_extents.z; any_changes = true; }
else if(proposed_pyr.z > max_extents.z) { proposed_pyr.z = max_extents.z; any_changes = true; }

if(any_changes)
{
// at least one rotation limit was violated, so we must recompute alpha
Vec3 actual_pyr = reverse_oriented_axes * proposed_pyr; // comparable to -proposed_ori.ToPYR(); reverse_oriented_axes is a Mat3
Quaternion actual_ori = Quaternion::FromPYR(-actual_pyr); // comparable to proposed_ori
Vec3 actual_av = (b_to_a * actual_ori).ToPYR() * inv_foresight; // comparable to proposed_av

alpha = current_av - actual_av;
}

This gets called a bunch of times every tick of the simulation with many of the variables unchanged. I've tried to compute-once-and-reuse as much as possible, but there's still a lot of computation going on here.

Explanation of a few functions:

Quaternion::FromPYR - returns a quaternion representing a rotation; param vector's direction = axis of rotation, and magnitude = angle of rotation in radians
Quaternion::ToPYR - inverse of the above; Quaternion::FromPYR(vec).ToPYR() will return vec as long as the magnitude of vec is less than pi.

Oh, and the comments about what data type some things are were added just for this excerpt.



So yeah, how can I make this faster?

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Oh, I've already got friction. And hypothetically my code is set up to deal with either static or kinetic friction... but in practice, the branch for static friction never executes. Maybe I'll look into it sometime.  :blah:

I actually had a code snippet for you... but it escaped me at the moment.  :wtf:



eh... There's no way you can optimize the bounds checks... but if many of the variables are unchanged, you may be able to add a previous_state and check those first before you do the bounds checks.
I'm on Facebook! sort of. Zeesixtyfour Fivefiftyfive

-=wxFRED2=-
R.I.P. Oliver
------------
EveningTea: Time to go Freeman on this cultist..
* EveningTea pulls crowbar off his shoulderstrap and charges screaming incoherently across the marsh *
------------
z64555: bro. do you even salad
------------
z64555: suprise double quaternion!

 

Offline Tomo

  • 28
Re: My Game Engine is too Awesome
Integer computations are a pain, but you don't want those for neural nets anyway.
Huh, what?
What I meant is that f you want to crunch a lot of floating-point numbers fast and can do it in parallel, the GPU is usually the best place to do it.

However, GPUs are optimised for floating-point, so the same is probably not true for integer calcs.

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Integer computations are a pain, but you don't want those for neural nets anyway.
Huh, what?
What I meant is that f you want to crunch a lot of floating-point numbers fast and can do it in parallel, the GPU is usually the best place to do it.

However, GPUs are optimised for floating-point, so the same is probably not true for integer calcs.

That really depends on the GPU themselves, I've read somewhere that nVidia's Fermi architecture can handle both 32-bit int's and floats easily.
I'm on Facebook! sort of. Zeesixtyfour Fivefiftyfive

-=wxFRED2=-
R.I.P. Oliver
------------
EveningTea: Time to go Freeman on this cultist..
* EveningTea pulls crowbar off his shoulderstrap and charges screaming incoherently across the marsh *
------------
z64555: bro. do you even salad
------------
z64555: suprise double quaternion!