Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 22 Jan 2011
Offline Last Active Jan 19 2013 06:39 AM

#4903293 Code Examples

Posted by on 16 January 2012 - 11:45 AM

What are the best resources on the web for finding everything from little tidbits of code to fully working games? I would like to have some insight on the formatting/trends/layout that others use.

You can check out the source code which accompanies my article on making a platform game:


The free version (top) will give you a bunch of example code which you can observe :)

Cheers, Paul.

#4902743 A common question, where to begin?

Posted by on 14 January 2012 - 02:13 PM

I know this is a very common question, but where do I begin?

I wrote an article recently that should fit the bill - its about the process of making a game, from design, prototyping, implementation, testing and release aimed at the absolute beginner:


Hope it helps!

Cheers, Paul.

#4879183 Physics Engine Basics

Posted by on 01 November 2011 - 03:17 AM

I just bought real-time collision detection and should be here tomorrow. I have used newton game physics for years at a very minimal rate but I would like to work on my own physics possibly or at least read up on it. Any other recommendations, really I would be happy just learning collision response between a stack of boxes.

Stacks of boxes are about the most complex and difficult thing to solve in physics simulation full stop! :)

I would start learning at a more basic level...

I wrote these three tutorials which you might find useful which describe:

The basics of a physics engine, Collision detection and Advanced physics engine topics, in that order:


Cheers, Paul.

#4871008 Determine contact edge of 2 boxes

Posted by on 10 October 2011 - 02:42 AM


I have a "simple" problem, yet I could not figure out how to solve this. Assume I have 2 boxes, 1 is static (the black one), the other one is moving (please look at the attachment).

I have sketched 3 cases in the picture. All 3 moving boxes have the same movement direction. I want to determine WHICH edge of the static black box is hit first by the moving box (I need this to resolve the collision)
So in my sketch the green and blue box will hit +Y edge of the black box. The red box will hit the -X edge of the black box. If the blue box was smaller, it would hit the -X edge. So its obvious that the contact edge depends on the extent of the static box, the moving box and the direction.

Do you know a "simple" algorithm to detect the contact edge (the edge where the first contact occurs)?

Yes :)

For each pair of boxes:

* Expand the large box by the extents of the smaller box
* Shrink the smaller box down to a point
* Ray-cast from the point along the velocity of the smaller box
* Intersection point is the first point of contact between the boxes, get the edge from this

Cheers, Paul.

#4867110 Contact Points[2D][Edge vs Point]

Posted by on 29 September 2011 - 03:09 AM

My Question is:
How do you guys find your contact points(Edge vs Point)?
Am i going in the right direction with my method or am i completely wrong?

Take a look at my article on the physics and collision detection of an angry birds style game - scroll down a bit, I discuss generating the contact set which sounds like what you are after:



Cheers, Paul.

#4858346 The Expensive Square Root Function

Posted by on 06 September 2011 - 03:20 PM

You get a sign that has to do with the notion of orientation. You can take the absolute value if you want, but the sign is often helpful (for instance, when computing that area of any polygon, you can simply add up the

The sign also tells you if you have the polygon winding order round the wrong way, because it will be negative in that case :)

(for instance, when computing that area of any polygon, you can simply add up the signed areas of the triangles formed by each side of the polygon and an arbitrary point).

Actually, an interesting property of the area calculation means you can calculate the area of a polygon simply by looping over the vertices and summing the cross-product of sequential vertices like this:

public function GetArea( ):Number
	var area:Number = 0;
	for ( var i:int = 0; i<m_numPoints; i++ )
		var P0:Vector2 = m_localSpacePoints[i];
		var P1:Vector2 = m_localSpacePoints[(i+1)%m_numPoints];
		area += P0.Cross( P1 );
	return area/2;

No matter what space those vertices are in, the area returned by this function is the same, which is slightly counter intuitive but makes for a nice tight loop :)

Cheers, Paul.

#4857217 OBB Quaternion problem!

Posted by on 03 September 2011 - 11:57 AM

Thanks again.
Is there any problem with my solution?I created a simple cube that rotated around X and Y axis for each 45 Degrees then exported that to FBX files with up vector Y (as i working with in XNA).but that previous method will show this values:

Posted Image

X: 59.9999884718182 Y: 135.00000833715 Z:45.000001142915

Why all three values (X&Y&Z) are changed?And another question can i use Absolute bone transform matrix of my model for this purpose?this is absolute bone transform of this model (one mesh one matrix for abs transforms):

{M11:1.796051 M12:-1.796051 M13:-6.18749E-16 M14:0}
{M21:1.27 M22:1.27 M23:-1.796051 M24:0}
{M31:1.27 M32:1.27 M33:1.796051 M34:0}
{M41:2.811808 M42:-4.598695E-17 M43:0.9372684 M44:1}

PS:I cant get your mean by saying this :

export the rotation from 3ds max

how can i export my rotation with my model and then use it in XNA?I have all corners coordinates so how can i create rotation matrix with them?can u explain it?
MyOBB.Corners[0] ,..., MyOBB.Corners[7]
they are vector3D types.so i can normalize them and so on...
Thanks a lot dude for helping me for free.

You might be able to use the bone matrix - if you normalise the axis vectors, that should represent the rotation.

Regarding exporting the rotation, it sounds like all you need is the bone matrix.

Your solution seems to be generating Euler angles, which you don't want - just keep the matrix, or turn it into a quat :)

Cheers, Paul.

#4857088 The Expensive Square Root Function

Posted by on 03 September 2011 - 04:01 AM

Ok, lets sort this out :)

The area of a triangle is simply half of the 2d cross-product of two of the triangle axis.


No need for sqrt() at all.

#4857082 OBB Quaternion problem!

Posted by on 03 September 2011 - 03:49 AM

You can form the matrix for the rotation just by normalising each one of the vectors at a corner of the OBB (depending on your coordinate system), and using those as your rows of the matrix.

However, it would be much better to just export the rotation from 3ds max along with the model :)

Cheers, Paul.

#4856917 OBB Quaternion problem!

Posted by on 02 September 2011 - 02:41 PM

You can calculate it from the OBB axis, but why not just export the rotation quat from max along with the rest of the model? :)

Cheers, Paul.

#4855061 help: advancing part of a frame

Posted by on 29 August 2011 - 08:25 AM

Ok, lets visit the update loop for the physics engine I describe in my angry birds tutorials:

public function Update(dt:Number):void
	// add gravity and generate motion bounds
	for ( var i:int=1; i<m_rigidBodies.m_Num; i++ )
		var p:RigidBody = m_rigidBodies.Get(i);
		// apply gravity
		p.m_vel.MulAddScalarTo( kGravity, dt );
		// generate new motion bounds for collision
		p.GenerateMotionBounds( dt );
	// collision detection
	for ( i=1; i<m_rigidBodies.m_Num-1; i++ )
		var rbi:RigidBody=m_rigidBodies.Get(i);
		for ( var j:int=i+1; j<m_rigidBodies.m_Num; j++ )
			var rbj:RigidBody=m_rigidBodies.Get(j);
			// simple broad-phase
			var overlap:Boolean = AABB.Overlap( rbi.m_MotionBounds, rbj.m_MotionBounds );
			if ( overlap )
				// narrow phase
	// solve all constraints
	if (m_contactPool.m_Num > 0 || m_joints.m_Num > 0)
		Solver.Solve(m_contactPool, m_joints, dt, Constants.kNumIterations);
	// integrate forward in time
	for ( i=1; i<m_rigidBodies.m_Num; i++ )
		p.Integrate( dt );

I have simplified this down to make it more readable. This is only the physics part, so you'd do your rendering afterwards.

Note the call to GenerateMotionBounds() in the first loop where I'm applying gravity. Looking at the code I am actually transforming all the points to generate the AABB for the predicted next frame and then combining the current frame's AABB with next frames to generate the motion bounds. However, you might just be able to get away with transforming the AABB verts and then generating a new AABB from that and the current frame. It wasn't a performance concern for me, so I never attempted that.

As you can see, the broad-phase is just AABB vs AABB intersection, which is very simple.

If you have a lot of objects, you absolutely need something more intelligent than a simple nested for loop - I've used Sort & Sweep in the past and hash-grid. Hash-grid is great if your objects are similar sizes. AABB trees are the latest kid on the block in that regard, although I've never used them. The goal is to only consider objects which have moved - objects which are stationary should do little to no work.

for object A to have passed through object B, object A must move to opposite sides of object B on all three world-coordinate axes (X, Y, Z)

Is that true? What about if object A is moving in only one axis?
I'm not a big fan of complex maths either - luckily collision detection is all geometry which I can get my head around quite nicely :)

Cheers, Paul.

#4854698 Jump math

Posted by on 28 August 2011 - 05:25 AM

From Newton's equations of motion:


Posted Image

So, si is your position on the current frame, vi is your velocity and a is your acceleration (gravity and other forces) and t is the time. Just plug in the numbers :)

Cheers, Paul.

#4854695 help: advancing part of a frame

Posted by on 28 August 2011 - 05:01 AM

gun, or something blows up. What I mean is, sometimes objects will go from zero to FAST (and a significant distance) in less than one frame. And other cases exist too, including multiple ricochets of multiple objects that then collide on the next frame. How on earth could any engine ever anticipate all these cases?

'How' is that they first of all bound the motion of the object in question with an AABB. So you know where the object is now, and you know where it will be next frame (i.e. very far away), you just stick an AABB around the entire motion for the object, do the same for all other objects in the game and then you have the set of all possible interactions.

Regarding ricochets, all you need is to bound what 'could happen' with the AABB overlaps, this gives you your interaction islands. Then you let the solver run and find a feasible solution. If you use speculative contacts in the solver, you can move the TOI impact problem out of the collision code and into the physics solver. Check my blog article for details :)

I just wanted to leave you with a thought: your current technique of back-tracking from penetration - how do you deal with the bullet through paper problem? Seems like you would miss these collisions... That's one of the main reasons to go forward in time, not back-tracking :)

Cheers, Paul.

#4853973 help: advancing part of a frame

Posted by on 26 August 2011 - 03:34 AM

Tell me though. Compared to the techniques described above, what's the drawback of tracing back through the minkowski sum along the relative motion vector until we find the outer surface (can't go any further), and taking the length of that vector as the distance to backtrack to find approximate "first contact"?

The drawback is that you're doing things the wrong way around if you do it like this - letting objects get into penetration and then back-tracking is the same amount of work as firing a ray from the origin to the MD of the two shapes along the delta velocity (as described by Gino Van Den Bergen), and getting the point and time of first contact. If you do it like that, you don't need to worry about back-tracking at all and you'd save yourself the first collision check which tells you that you need to back-track :)

Well, that doesn't much help with rotation unless somehow we're recomputing the minkowski sum as we go (which I guess is possible, but obviously slower).

That's what conservative advancement does. Yes, its slower but it works very well, and if you only need an approximate result, just run it for a couple of iterations - likelihood is, objects are moving/rotating so fast that you can't see the slight error anyway.

Cheers, Paul.

#4853326 help: advancing part of a frame

Posted by on 24 August 2011 - 12:31 PM

Are you sure you really want to be backing up the entire simulation to find the collision time? There are much nicer (i.e quicker) ways to achieve the same result these days :)

For example, you can use conservative advancement to get the TOI without backing everything up.



And/or you can use speculative contacts if you want an even faster approximation (which was good enough for Little Big Planet and other AAA titles) :)


Both of these techniques work in 2d or 3d... :)

Cheers, Paul.