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

0 Members and 2 Guests are viewing this topic.

Offline Aardwolf

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

Progress report! as if anyone cared

I may have made some progress w.r.t. that inconsistent crash! I don't know why I didn't try this sooner...

I modified the loading screen so that instead of taking me to the game when it finished loading, it just dumped me back into the main menu. This allowed me to sit through the load once, and then just hit the "Create Game..." button repeatedly. And from this I discovered that the crashing is not limited to the first load.

Since the stack trace said the problem was in the lua dll, and the last thing the loading screen would say before crashing was "starting game", that suggested that the problem was in game_start.lua, so my next step was to add debug outputs at the beginning and end of that file... using that, I was able to determine that the error was indeed somewhere in that script!

Furthermore, it was giving me more specific error info, from which I determined that the error had something to do with file I/O. So I put debug outputs before and after the place in game_start.lua where I was calling dofile. When it crashed, the first one printed, but not the second one. So the problem was either with dofile, or with the script dofile was executing. I tried putting debug outputs at the top and bottom of that file as well. When it crashed, neither printed. Solution: no dofile. Now I run the script from C++ instead, and it seems to be fixed... ish.

However, now I sometimes get a crash in the code that handles keyboard/mouse input (possibly related to the part of that which talks to Lua). Le sigh  :sigh:

 

Offline Nuke

  • Ka-Boom!
  • 212
  • Mutants Worship Me
Re: My Game Engine is too Crashy
use require, it does some things that dofile doesnt, like making sure it doesnt run the same code multiple times. for example i have a file that handles the opengl frame, the require statements ensure that the files get run once, but doesnt run them again. using a dofile in this situation will load,compile, and execute them each time the loop runs, which is bad on the file system, especially with multiprocessing going on. its slightly different, you must exclude the .lua extension from the file name, it just wont work with it in there.
« Last Edit: February 21, 2012, 11:20:51 am 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 Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Crashy
I'm almost certain that's not the issue.

Apparently, there were some hoops I was supposed to jump through to get Lua to play nice with my multi-threaded loading screen.

My loading screen now uses lua_newthread to create its own Lua state, but I haven't done any of the stuff that tutorial mentions. I haven't had a crash since I made these changes, but as always I won't know whether it's fixed until I find out it's broken.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
About a month ago I was trying to figure out what exactly was making my game run so slowly, and I did some experimentation. In the experiment, I had 100 enemies in the game, and told them all to die at the 5 second mark, producing 100 ragdolls with 21 bones each.

Here's what I observed:

Test #         Condition     Spheres          No constraints     Framerate
1Always true
2 fps
2Always true
Yes
4 fps
3Always false
20 fps
4Always false
Yes
76 fps
5False if both items are ragdolls         
3 fps
6False if both items are ragdolls
Yes
4 fps
7False if both items are ragdolls
Yes
Yes
5 fps
8False if both items are ragdollsYes
3 fps


Condition: Controls whether a pair of objects can collide with one another. This is implemented as a callback which is called every time two objects are near one another. The values returned by this callback were not cached.
Spheres: In these tests, all bones' collision shapes were replaced with spheres with radius 0.5 meters. Normally they use btMultiSphereShapes---a btMultiSphereShape is a convex hull around a collection of 1 or more spheres, so its surface may consist of parts of spheres, cylinders, cones, and planes.
No constraints: In these tests, the constraints that normally hold the bones of the ragdolls together at the joints were removed.



SIMULATING 2100 BALLS ON A TERRAIN MESH SHOULD RUN FASTER THAN 5 FPS! Especially considering they're not even interacting with each other!

It was settled: Bullet had to go.



That was Feb 14th. In the time since then I've made enough progress with my replacement physics engine to recreate that experiment. Much to my dismay, it only got 4-5 fps! :(

But then I realized there was a problem with my TriangleMeshShape::GetRelevantTriangles(AABB relevance) function! It was using an Octree to figure out what triangles might be relevant, but when it found that a leaf node's AABB intersected the relevance AABB, it accepted all of the triangles contained within that node, even if those triangles' AABBs didn't intersect the relevance AABB!

I made the change, and now it gets 20-30 fps! Awesome! :D

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
Multisphere-multisphere collisions work now!  :D But now I've got to figure out how to prevent objects from being pushed through each other.  :(

Given a graph with rigid bodies as nodes and contact points between them as edges, I need to find what impulses to apply at each contact point in order for it to behave physically.

What I have now is void DoCollisionResponse(const ContactPoint& cp); it works when there's only two objects involved, but that's it. The impulse it applies depends on the relative local velocity at the point of contact, and applying the impulse modifies the relative local velocity used when handling subsequent contact points. The result varies depending on which order the contact points are evaluated in, and is wrong either way.



I don't know how to proceed.

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
The impulse it applies depends on the relative local velocity at the point of contact, and applying the impulse modifies the relative local velocity used when handling subsequent contact points. The result varies depending on which order the contact points are evaluated in, and is wrong either way.

Some reading is required. http://en.wikipedia.org/wiki/Elastic_collision

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
Naw man, I know all that stuff already. My DoCollisionResponse function works correctly for a single pair of colliding objects. And I'm not doing perfectly elastic collisions anyway; my game would not be very fun if every floor and wall were covered with repulsion gel. :ick:



The issue is how to deal with multiple objects colliding simultaneously, i.e.:
Given a graph with rigid bodies as nodes and contact points between them as edges, I need to find what impulses to apply at each contact point in order for it to behave physically.

I've made a few more observations since I originally formulated the problem:
  • Done correctly, after all the impulses are applied, no contact point should have an "inward" relative local velocity.
  • It seems like this will be an O(n2) algorithm. Probably.

 

Offline Tomo

  • 28
Re: My Game Engine is too Awesome
I assume you're just running inelastic collisions with an arbitrary coef. of restitution?

Filling a ball pit is seriously computationally expensive.

Can you assume that an object can only collide with one other movable object and an immovable one in any given simulation step? (not necessarily rendered frame)
- I presume the ground can be safely assumed to be immovable.

If you simplify to assume 'dead relative stop' if a collision is below a certain threshold energy it may simplify the problem enough.

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Naw man, I know all that stuff already. My DoCollisionResponse function works correctly for a single pair of colliding objects. And I'm not doing perfectly elastic collisions anyway; my game would not be very fun if every floor and wall were covered with repulsion gel. :ick:

Ok, so are you trying to do inelastic collisions, elastic collisions with kinetic friction, or some sort of combination?

I think your trying to go after elastic collisions with kinetic friction applied, because even inelastic collisions obey the conservation of momentum... which would mean that the collisions would continue forever.

Given a graph with rigid bodies as nodes and contact points between them as edges, I need to find what impulses to apply at each contact point in order for it to behave physically.

Oh, I think I see your dilemma, when considering the contact point edges can be non-perpendicular and non-radial.  :blah:

Quote
I've made a few more observations since I originally formulated the problem:
  • Done correctly, after all the impulses are applied, no contact point should have an "inward" relative local velocity.
  • It seems like this will be an O(n2) algorithm. Probably.

What do mean by item 1?
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 Nuke

  • Ka-Boom!
  • 212
  • Mutants Worship Me
Re: My Game Engine is too Awesome
if every object contains a list of everything that it is currently colliding with, it should be easy to go through all those objects' lists to identify groups of interacting objects. you would of course not traverse over anything that is immovable, getting all the objects that are touching the ground wouldn't help you any. the idea is to find systems of colliding objects so they can be collision responded to. you should know whats colliding with what and where by now. its probibly gonna be n^2 or worse, but if you isolate a subset of objects, then at least n will be smallish.

i figure from that point you would need to break the problem down. you might want to use the object with the most collisions as your main object. most of the objects in the group will likely just have a single collision logged. and there may or may not be intermediate objects in the mix as well. so build a collision hierarchy with your most hit object as the root and the one hitters as the leafs. propagate ke through from leaf to root and back again.

objects in firm contact with eachother (multiple colliding points spaced out about a cg and mostly perpendicular to the velocity), and at very low relative velocity may be considered a single object with combined mass, and forces. if another object hits one of them you might (depending on force vector in relation to the objects' cgs) get some energy transfer through this kind of thing. object a hits object b which is in (firm) contact with object c. so the force applied to b will actually get distributed to both b and c objects by some ratio (massA:massB). if a is bouncy, you may also dump some of the ke back into object a.

you also might step ahead in simulation time by one unit (or one frame), retest the group for collisions, and if any occur, you can compare the points with the previous set and fudge the difference, step back to current time and apply it. theres probibly some 4-d crap you can do here that makes my brain hurt to even think about it.
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
@Tomo & z64555: Inelastic collisions with arbitrary CoR, and friction. Maybe I'll omit the friction at this stage if it seems like it's too complicated with it.

@Tomo: No, I don't think I can assume anything like that. Yes, the ground is immobile. And I plan to make it possible for things to "sleep" when they get within some threshold of stationary... eventually.

@z64555: Yes, the collisions will go on forever. When an object falls and hits the ground, it should eventually come to rest.




A little more info about the problem... here's what a contact point looks like:

Code: [Select]
struct ContactPoint
{
struct Part
{
RigidBody* obj;
Vec3 pos, norm; // both are world coords

Part() : obj(NULL), pos(), norm() { }
} a, b;
};

For every ContactPoint, my algorithm will have to come up with a Vec3 impulse, which will be applied equally and oppositely to the two objects in contact (unless one of them is immobile). The impulse could hypothetically be decomposed into a component parallel to the contact point's normal vector (restitution) and a component orthogonal to it (friction).




And rather than waste more time explaining with words what my code is doing, I'll explain with code. This is the DoCollisionResponse function:

Code: [Select]
void PhysicsWorld::Imp::DoCollisionResponse(const ContactPoint& cp)
{
RigidBody* ibody = cp.a.obj;
RigidBody* jbody = cp.b.obj;

RigidBody::Imp* iimp = ibody->imp;
RigidBody::Imp* jimp = jbody->imp;

bool j_can_move = jimp->can_move;

float m1 = iimp->mass_info.mass;
float m2 = jimp->mass_info.mass;

if(m1 + m2 > 0)
{
Vec3 i_poi = ibody->GetInvTransform().TransformVec3(cp.a.pos, 1.0f);
Vec3 j_poi = jbody->GetInvTransform().TransformVec3(cp.b.pos, 1.0f);

Vec3 i_v = iimp->GetLocalVelocity(cp.a.pos);
Vec3 j_v = jimp->GetLocalVelocity(cp.b.pos);

Vec3 dv = j_v - i_v;
const Vec3& normal = Vec3::Normalize(cp.a.norm - cp.b.norm);

float nvdot = Vec3::Dot(normal, dv);
if(nvdot < 0.0f)
{
float A, B;
GetUseMass(normal, cp, A, B);

float use_mass = 1.0f / A;
float bounciness = iimp->bounciness * jimp->bounciness;
float impulse_mag = -(1.0f + bounciness) * B * use_mass;

if(impulse_mag < 0)
{
Vec3 impulse = normal * impulse_mag;

if(impulse.ComputeMagnitudeSquared() != 0)
{
ibody->ApplyImpulse(impulse, i_poi);
if(j_can_move)
jbody->ApplyImpulse(-impulse, j_poi);
}

float sfric_coeff = iimp->friction * jimp->friction;
float kfric_coeff = 0.9f * sfric_coeff;

Vec3 t_dv = dv - normal * nvdot;
float t_dv_magsq = t_dv.ComputeMagnitudeSquared();

if(t_dv_magsq > 0.001f) // object is moving; apply kinetic friction
{
float t_dv_mag = sqrtf(t_dv_magsq);

GetUseMass(t_dv / t_dv_mag, cp, A, B);
use_mass = 1.0f / A;

Vec3 fric_impulse = t_dv * min(use_mass, fabs(impulse_mag * kfric_coeff / t_dv_mag));

ibody->ApplyImpulse(fric_impulse, i_poi);
if(j_can_move)
jbody->ApplyImpulse(-fric_impulse, j_poi);
}
else // object isn't moving; apply static friction
{
Vec3 df = jimp->applied_force - iimp->applied_force;
float nfdot = Vec3::Dot(normal, df);

Vec3 t_df = df - normal * nfdot;
float t_df_mag = t_df.ComputeMagnitude();

float fric_i_mag = min(impulse_mag * sfric_coeff, t_df_mag);
if(fric_i_mag > 0)
{
Vec3 fric_impulse = t_df * (-fric_i_mag / t_df_mag);

ibody->ApplyImpulse(fric_impulse, i_poi);
if(j_can_move)
jbody->ApplyImpulse(-fric_impulse, j_poi);
}
}
}
}
}
}

Some explanation of a couple of those other functions:

void ApplyImpulse(Vec3 impulse, Vec3 position); "Impulse" is the impulse to be applied, i.e. the change in linear velocity will be this vector divided by the mass. "Position" is the position where I'm applying the impulse (not necessarily on an axis passing through the CoM).

void GetUseMass(Vec3 direction, ContactPoint cp, float& A, float& B); Could possibly use a better name; it's for preparing the inputs to ApplyImpulse. "Direction" is the direction of the impulse I want to apply, and "cp" is used for its position relative to the CoMs. After the function completes, "A" and "B" contain values such that the magnitude of the impulse I need to apply is -(1.0f + bounciness) * B / A. If "bounciness" is one, the collision is perfectly ellastic. If "bounciness" is zero, it is perfectly inelastic (I think).




@Nuke: I've already come up with something to deal with the immobility of the ground... when there's a ContactPoint between a mobile body and an immobile one, instead of reusing the same node for all ContactPoints that immobile RigidBody has, I give that particular Edge a NULL other_node pointer.

Code: [Select]
struct Edge
{
ContactPoint* cp;
ContactPoint::Part* self;
ContactPoint::Part* other;

Node* other_node;
};

struct Node
{
RigidBody* body;
vector<Edge> edges;
};




Edit: @z64555: by
Quote
Done correctly, after all the impulses are applied, no contact point should have an "inward" relative local velocity.
I mean that if I were to evaluate nvdot (from DoCollisionResponse) again for all of the ContactPoints, it wouldn't be negative for any of them.



Edit II: Well that was easier to solve than I expected.

My old code:
Code: [Select]
for(vector<ContactPoint*>::iterator iter = collision_graph.contact_points.begin(); iter != collision_graph.contact_points.end(); ++iter)
DoCollisionResponse(**iter);

My new code:
Code: [Select]
for(int i = 0; i < MAX_SEQUENTIAL_SOLVER_ITERATIONS; ++i)
{
bool any = false;
for(vector<ContactPoint*>::iterator iter = collision_graph.contact_points.begin(); iter != collision_graph.contact_points.end(); ++iter)
if(DoCollisionResponse(**iter))
any = true;

if(!any)
break;
}

Also DoCollisionResponse now returns a bool, true if nvdot was < 0, false otherwise.

And now it works. Mostly.
« Last Edit: May 01, 2012, 09:08:45 pm by Aardwolf »

 

Offline z64555

  • 210
  • Self-proclaimed controls expert
    • Minecraft
    • Steam
Re: My Game Engine is too Awesome
Interesting trick there:
Code: [Select]
float t_dv_magsq = t_dv.ComputeMagnitudeSquared();

if(t_dv_magsq > 0.001f) // object is moving; apply kinetic friction
{
float t_dv_mag = sqrtf(t_dv_magsq);
// ...
}
else // object isn't moving; apply static friction
{
// ...
}

You not only use t_dv_magsq to determine if it's moving or not, but you also use it to determine the non-negative magnitude. What's wrong with using this?

Code: [Select]
float t_dv_mag = t_dv.ComputeMagnitude();

if(t_dv_mag != 0.001f) // object is moving; apply kinetic friction
{
// float t_dv_mag = sqrtf(t_dv_magsq);
// ...
}
else // object isn't moving; apply static friction
{
// ...
}

Are you planning on doing some KE calculations further down the road?

Quote
Quote
Done correctly, after all the impulses are applied, no contact point should have an "inward" relative local velocity.
I mean that if I were to evaluate nvdot (from DoCollisionResponse) again for all of the ContactPoints, it wouldn't be negative for any of them.

Still not quite following. Don't worry though, I'll figure it out once the coffee machine is fixed. :)
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
Progress Update!

I've gone back to working on my destructible terrain stuff, which I'll hopefully be able to integrate into the FPS engine in the not-too-distant future!

Here's some screenshots of the new multi-material feature:



Ignore the weird artifacts most prominently visible around the sandy patches, that issue has been fixed since I took these screenshots. Also I notice the filenames coming from my screenshot grabber are all a month off.

Next on the agenda: Terrain LODs!





Delayed response to z64555:

That's to save doing a square root. Although the function is named "compute magnitude squared", it's not actually taking the square root and then squaring it. Implementation:

   float Vec3::ComputeMagnitudeSquared() const { return x * x + y * y + z * z; }
   float Vec3::ComputeMagnitude() const { return sqrt(x * x + y * y + z * z); }


But anyway I've got that part working now.

 

Offline CommanderDJ

  • Software engineer
  • 210
    • Minecraft
Re: My Game Engine is too Awesome
Hey Aardwolf, sorry to (kinda) derail the thread a bit, but I've been following your progress and for a long time have been considering working on my own game engine. The main problem I keep coming across when I start seriously thinking about it is that there's just so much to do. How did you... start? If you don't mind me asking, that is.
[16:57] <CommanderDJ> What prompted the decision to split WiH into acts?
[16:58] <battuta> it was long, we wanted to release something
[16:58] <battuta> it felt good to have a target to hit
[17:00] <RangerKarl> not sure if talking about strike mission, or jerking off
[17:00] <CommanderDJ> WUT
[17:00] <CommanderDJ> hahahahaha
[17:00] <battuta> hahahaha
[17:00] <RangerKarl> same thing really, if you think about it

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
How did I start with this particular engine, or did I start on the game programming path? Assuming the prior...

First steps I took:
  • Made an OpenGL window. It doesn't have to be OpenGL, but that's what I use.
  • Made an Update function which gets called every frame.
  • Made an Entity class which has an Update function and a Draw function, and call those for all entities every frame.
  • Set up keyboard and mouse input so that you can move a camera (or the player entity) around to look at the various entities in the world.

 

Offline Nuke

  • Ka-Boom!
  • 212
  • Mutants Worship Me
Re: My Game Engine is too Awesome
im still at step 4.
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
Yesterday I re-did the "drop 2100 rigid bodies onto terrain, with no collisions between them" experiment again with my new engine. Under comparable circumstances in Bullet it got 3 fps, and in my engine a month or so ago it got 20-30 fps (although that was with spheres instead of MultiSphereShapes). Yesterday's experiment got 2 fps. :banghead:

This comes after refactoring my PhysicsWorld class, so that what it used to do is now covered by a PhysicsRegion class, of which PhysicsWorld contains multiple instances. Basically a step toward whole-world spatial partitioning.

Anyway, profiler says it's malloc's fault. I reckon I'll have to go back and do some actual design/engineering to clear up this mess.  :sigh:

 

Offline Tomo

  • 28
Re: My Game Engine is too Awesome
I can well believe it's malloc's fault. The usual mallocs really fall to bits once you start fragmenting memory.

You'll need to profile where the mallocs are coming from - pointless object creation is a very common cause.

 

Offline Aardwolf

  • 211
  • Posts: 16,384
    • Minecraft
Re: My Game Engine is too Awesome
When I said "it's malloc's fault" what I really mean is that according to the profiler I'm using says it's the function with the highest 'total' (i.e. self + children). I think it's probably the memory allocations involved in adding elements to a boost::unordered_set, but really I just need to rethink the problem some.




On the subject of profilers, I've been using AMD CodeAnalyst, and I'm getting rather annoyed with it for a number of reasons:
  • Rubbish in the call stack, e.g. malloc calling Vec3::Vec3... complete and utter bull****
  • Long function names being truncated—especially bad for std:: and boost:: stuff—I'll see boost::unordered_set<RigidBody*, followed by 100 characters of default template arguments, and it'll be so long it truncates in or before the name of the member function.
  • Function names don't have arguments, so there's no way to tell which overload of a function is which. In fact I'm not even sure it stores separate data for them.

Really it would be nice if it would record the full call stack, all the way up to main or threadstart for every call stack sample. From what I can tell what Maybe it's going all the way back up to main, but the data it gives me seems to be solely based on the immediate next function down on the stack.



So for example if I were to profile this code...
Code: [Select]
void Eggs() { cout << "Eggs" << endl; }

void Ham() { cout << "Ham" << endl; }

void Seuss(bool eggs)
{
for(int i = 0; i < 10000; ++i)
if(eggs)
Eggs();
else
{
Ham();
Ham();
}
}

void Derp() { Seuss(true); }
void Herp() { Seuss(false); }

int main()
{
Derp();
Herp();

return 0;
}



CodeAnalyst might give me this:

function            self   children   total
main0300301
-      Derp1100101
      Herp1199200
Eggs99099
Ham1980198
Derp1100101
-      Seuss199100
Herp1199200
-      Seuss1198199
Seuss2297299
-      Eggs99099
-      Ham1980198



That much is ok (although I'm not sure CodeAnalyst even does that quite right), but the problem is that if I expand the item Seuss under Herp, it gives me this:

function            self   children   total
Derp1100101
-      Seuss199100
      -      Eggs99099
      -      Ham1980198



That is, it just tells me the info for Seuss in general, instead of specific to when it's being called by Derp... here's how I reckon it ought to look:

function            self   children   total
Derp1100101
-      Seuss199100
      -      Eggs99099




If anyone can suggest for me a better C++ profiler, please do.

 

Offline m!m

  • 211
Re: My Game Engine is too Awesome
The Microsoft profiler does a quite good job but I think it isn't included in the express version so you would need to use one of the expensive versions or for some time you could use the Visual Studio 2012 Release Candidate which is AFAIK currently available for free until the final release is available so you could use that.
I'm not sure how you're handling the build process but from my (short) experiences it's definitely worth the effort of setting up the build environment.