How to make Angry Birds – part 2

ABpt2
Submit to StumbleUpon

Hello and welcome back to my blog!

This is the 2nd part of my series on how to make a game like Angry Birds by Rovio - and its been a while coming… You can read the first part here.

The Game

Ok, so here is the game so far; there are three demo levels to show the level progress system and some simple looking characters and block types. Apologies for the programmer art :)

Catch up

Ok, so last time I had covered how to draw the background graphics and made a start on how the world is going to be composed in terms of collision.

What I’m going to cover in this article is the physics part; stability and optimisations. The physics engine that I’ve created for this game is based on the technology I’ve discussed in my previous articles:

Physics engines for dummies
Collision detection for dummies
Speculative contacts – a continuous collision engine approach

Level

A level is defined as a bunch of instances of static rigid bodies and dynamic rigid bodies plus a visual layer which covers up the statics – I use this other layer because otherwise there would be a slight visible gap betweenadjacentstatic blocks, which we don’t want since the texture is supposed to be continuous.

A level must inherit the base class Code.Level. I’ve done this so I can predefine certain things about each level – such as the instance names for the hero characters, and the sling-shot which I need to reference in code.

Characters and blocks

Each of the two characters and every block used in the game are designed in the Flash IDE, and each of them references a base class that I’ve defined in the code. This is so that I can parse the children of a level at runtime and create the appropriate rigid bodies at the correct mapped locations for the physics engine.

Rigid-bodies

There are the following base classes (stone and wood use the same base class):

  • HeroCharacter
  • EnemyCharacter
  • ProxyRectangleIce
  • ProxyRectangle
  • ProxyRectangleStatic
  • ProxyTriangleStaticDown
  • ProxyTriangleStaticUp

These are interpreted at level creation time, using a loop similar to this:

// create physics objects to go with the render objects in level
for ( var i:int = 0; i<level.numChildren; i++ )
{
	var child:DisplayObject = level.getChildAt( i );
	if ( child is Character )
	{
		...
	}
	else if ( child is ProxyRectangleStatic )
	{
		...
	}
	else if ( child is ProxyRectangle )
	{
		...
	}
	else if ( child is ProxyRectangleIce )
	{
		...
	}
	else if ( child is ProxyTriangleStaticDown )
	{
		...
	}
	else if ( child is ProxyTriangleStaticUp )
	{
		...
	}
	child.cacheAsBitmap = true;
}

In each part of the if-else ladder I create the appropriate rigid body to match the proxy, and these get added to the physics engine.

Level sequence

Thanks to Flash’s neat way of storing class types as variables, I represent the level sequence as a simple array of class types:

private var m_currentLevel:int;
private var m_levelSequence:Array =
[
	Level3Fla,
	Level2Fla,
	LevelFla
];

Every time a level is completed, I can pick the new one from the array and instantiate it like this:

// create new level
m_level = new m_levelSequence[m_currentLevel];

It then gets passed to the SetupLevel function which handles all the rigid body instantiation that I talked about above.

Physics engine

The physics engine is similar in design to the one I laid out in Physics engines for dummies, except this one is a lot more advanced.

It now has the concepts of angular-velocity, polygon contact set generation, contact group generation, object sleeping, collision callbacks and persistent contacts. All these components were necessary to create the game.

Physics engine – angular velocity

Angular velocity is handled in a very similar way to linear velocity, except its a scalar and not a vector, since we’re in 2d and it gets integrated the same way. Where it gets more tricky is in the actual impulse equations.

I’m going to refer the reader to the following set of articles by Chris Hecker which describe the impulse equations for angular and linear velocity rather well: http://chrishecker.com/Rigid_Body_Dynamics.

I do intend to write a more in depth follow up on this subject at some point.

Physics engine – polygon contact set generation

Although, technically when two convex shapes collide there are only two closest points (one on each object) this is not enough for the physics engine to produce a stable simulation with anything more than circles. As soon as you have a rectangle or a polygon you need to have the full contact-set between both objects.

Figure 1

Figure 1 shows the full contact set between two polygons A and B. To generate this we need to start with the feature-pair returned by our collision system (vertex and edge, or edge and vertex).

Figure 2

Figure 2 shows one such possible case: a vertex from B and an edge from A were returned as the closest features. Starting with this information we can then do a local search of the the vertices adjacent to the red point on B (one on either side) to find which edge has a normal that is most opposed to our collision normal (the edge normal).

Figure 3

Figure 3 shows the correct edge and the other edge which was considered from B. Once we have these two edges we have all the information we need to generate the contact set. What we do is to project each vertex from each edge onto the other edge, making sure to clamp the projections so they lie wholly within the bounds of the edge.

Figure 4

Figure 4 shows the red vertices of the edge from A being projected onto the green edge of B. The first vertex becomes projected point b0 and the second becomes b1.

Figure 5

In Figure 5 we can see the same process repeated for the other edge; note how both projections of the green vertices would lie outside the bounds of the red edge. Because this would lead to an invalid contact we must clamp these at the bounds of the red edge. Vertices a0 and a1 result and this is the completed contact set!

Figure 6

Here is the code for projecting a point onto an edge and clamping against the edge bounds:

public function ProjectPointOntoEdge(p:Vector2, e0:Vector2, e1:Vector2):Vector2
{
	// vector from edge to point
	var v:Vector2 = p.Sub(e0);
 
	// edge vector
	var e:Vector2 = e1.Sub(e0);
 
	// time along edge
	var t:Number = e.Dot(v) / e.m_LenSqr;
 
	// clamp to edge bounds
	t = Scalar.Clamp(t, 0, 1);
 
	// form point and return
	return e0.Add( e.MulScalar(t) );
}

Contact group generation and object sleeping

The game logic for angry birds relies on being able to tell when all the movement in the level is stopped, because otherwise you would never know when an individual try is over since objects may yet fall down crushing an enemy character.

In order to facilitate this and also to act as an optimisation an object sleeping system is required. What this does is to deactivate or ‘sleep’ any rigid bodies which have become sufficiently still for a set period of time, thereby saving CPU cycles and also giving us an indication about the state of the game.

For this to be possible we first have to be able to generate contact groups. A contact group is a collection of rigid bodies which are all touching each other.

Figure 7

Figure 7 shows two contact groups.

In order to generate these, the simplest way is to use recursion. Each object must maintain a list of every object that’s touching it. An outer loop over all rigid bodies generates individual contact group containers and then recurses within adding objects which are touching to the given contact group.

Static objects are not followed because we don’t want to include them in any contact group – they would link the entire level together into one giant, inefficient contact group!

The code looks like this:

private function BuildContactGroup( r:RigidBody, cg:ContactGroup, dt:Number ):void
{
	if ( !r.m_visited && !r.m_Static )
	{
		r.m_visited = true;
		r.m_contactGroup = cg;
 
		// add the object
		cg.Add( r );
 
		for ( var i:int = 0; i<r.m_rbsTouching.m_Num; i++ )
		{
			BuildContactGroup( r.m_rbsTouching.Get(i), cg, dt );
		}
	}
}
 
///
/// Go through and build all the contact groups in the world
///
internal function BuildAllContactGroups( dt:Number, rigidBodies:ReferenceArray ):void
{
	Reset( );
 
	// start with a new group
	var cg:ContactGroup=null;
 
	for ( var i:int=0; i<rigidBodies.m_Num; i++ )
	{
		var r:RigidBody = rigidBodies.Get(i);
 
		// if this object isn't static and hasn't yet been visited...
		if ( !r.m_Static && r.m_visited==false )
		{
			if ( cg==null || cg.m_NumRigidBodies>0)
			{
				// get new contact group
				cg = GetNewContactGroup( );
			}
 
			// go an recursivly add objects to this new contact group
			BuildContactGroup(r, cg, dt);
		}
	}
 
	// sleep check the contact groups
	SleepCheck( );
}

Its actually quite simple and works rather well, taking minimal CPU time.

To enable the sleeping of rigid bodies, each rigid body maintains a counter which counts the number of seconds that rigid body has had angular and linear velocities below some threshold values. Then, once all the rigid bodies in a contact group have counter values over a threshold (1 second in this game’s case), the entire contact group is sent to sleep. Likewise, if any rigid body in a sleeping contact group wakes up, the entire contact group must wake up with it.

Physics engine – collision callbacks

For some objects the game needs to know about any collisions that happen between those objects and the hero character, or the world. To facilitate this, each rigid body has a collision callback delegate which can be set at runtime. Then, the physics engine will call this delegate whenever it detects a collision, passing the callback information about the collision including which objects were hit and what the relative normal velocities were at the time of collision. This information allows to game logic to kill enemies and smash blocks of ice.

Physics engine – persistent contacts

This physics engine feature is absolutely essential to the stability of the physics; without it, the game would not be possible with as much creative freedom in level design.

So, what are persistent contacts?

Regular contacts are the things which stop two rigid bodies from falling through each other – they are generated by the collision detection system and used by the physics solver but they are temporary and exist for the current frame only.

The impulses generated by the physics solver converge the entire simulation towards stability, but there are not enough CPU cycles for it to be resolved completely in one frame… So rather than throw away all of last frames impulses we would like to be able to remember them and then apply them next frame in order to ‘warm start’ the engine. This leads to massive stability improvements.

Persistent contacts are a way of caching the impulses between frames by identifying contacts which are logically the same across a series of frames. By logically I mean rather than using something crude like the position of two contacts, we want to use something which identifies contacts uniquely. To do this we can use feature pair indicies; so for example, the index of the vertex from object A combined with the index of the edge from object B. These will be combined together into one uint hash value which can be looked up and compared across frames. When the hash tags match, we have a cache hit and can copy the impulses across.

The code I use for caching the impulses looks like this:

public class TouchingContact
{
	public var m_featurePairKey:uint;
	public var m_accumulatedNormalImpulse:Number;
	public var m_accumulatedTangentImpulse:Number;
 
	public function TouchingContact( featurePairKey:int )
	{
		m_featurePairKey = featurePairKey;
		m_accumulatedNormalImpulse = 0;
		m_accumulatedTangentImpulse = 0;
	}
 
	///
	/// Something to identify this contact uniquely
	///
	static public function GenerateFeaturePairKey( featureToUse:FeaturePair, supportIndex:int ):uint
	{
		return featureToUse.m_fp|( featureToUse.m_face<<2 )|( supportIndex<<16 );
	}
}

When two objects touch for the first time, a persistent contact entry is generated for the collision and stored on the lower indexed object, so that I avoid duplicating data. When objects stop touching, these contact entries are deleted again. During the time when they are touching, I cache up to 4 feature pairs for later lookup – the reason I chose 4 and not 2 (which would be the logical choice) is that I noticed there was a fair amount of flip-flop over the course of a few frames in certain contact configurations; one frame two contacts would be generated from a certain feature pair, the next frame another two contacts from a different feature pair and then repeat forever. Rather than throw away and regenerating, storing 4 allowed me to catch this case and achieve a 100% cache hit rate for stable contact configurations.

Optimisation

After I had implemented all these features and gotten the engine stable enough to be able to run angry birds, I noticed that it was in fact, far too slow to actually use. This made me sad, but a little digging into action-script optimisation techniques netted me the answer.

References

In action-script, every complex type is passed by reference and there are no complex types which can be put on the stack, unlike c# or c++. This is particularly irksome if you have something like a Vector2 class for doing all your geometric calculations, because it means every time you do a new(), an allocation is made on the heap, which of course means you risk the slowness of the garbage collector when doing temporary calculations.

This is an absolute killer in terms of performance – I found I was doing something on the order of 7k-12k such temporary allocations every single frame!

The solution – pools

Of course, the internet informed me that the accepted solution here is to employ an object pool for complex types – pre-allocated up-front with a known fixed capacity. Allocations can then be made and freed using the pool, thereby avoiding the garbage collector.

I couldn’t find an implementation that did exactly what I wanted, so I wrote my own:

package Code.System
{
	import Code.Assert;
	import Code.System.UnexpectedCaseException;
 
	public class Pool
	{
		private var m_counter:int;
		private var m_maxObjects:int;
		private var m_pool:Array;
		private var m_type:Class;
 
		/// <summary>
		/// 
		/// </summary>	
		public function Pool( maxObjects:int, type:Class )
		{
			m_pool = new Array( maxObjects );
 
			// construct all objects
			for (var i:int=0; i<maxObjects; i++)
			{
				m_pool[i] = new type();
			}
 
			m_counter=0;
			m_type=type;
			m_maxObjects=maxObjects;
		}
 
		/// <summary>
		/// 
		/// </summary>	
		public function Allocate( ...args ):*
		{
			Assert( m_counter<m_maxObjects, "Pool.GetObject(): pool out of space!" );
 
			var obj:* = m_pool[m_counter++];
 
			if ( args.length>0 )
			{
				if ( args.length==1 )
				{
					obj.Initialise( args[0] );
				}
				else if ( args.length==2 )
				{
					obj.Initialise( args[0], args[1] );
				}
				else if ( args.length==3 )
				{
					obj.Initialise( args[0], args[1], args[2] );
				}
				else if ( args.length==4 )
				{
					obj.Initialise( args[0], args[1], args[2], args[3] );
				}
				else if ( args.length==5 )
				{
					obj.Initialise( args[0], args[1], args[2], args[3], args[4] );
				}
				else if ( args.length==6 )
				{
					obj.Initialise( args[0], args[1], args[2], args[3], args[4], args[5] );
				}
				else if ( args.length==7 )
				{
					obj.Initialise( args[0], args[1], args[2], args[3], args[4], args[5], args[6] );
				}
				else 
				{
					throw new UnexpectedCaseException;
				}
			}
 
			return obj;
		}
 
		/// <summary>
		/// 
		/// </summary>	
		public function Deallocate( obj:* ):void
		{
			Assert( typeof( obj )==typeof( m_type ), "Pool.Deallocate(): object doesn't belong to this pool!" );
			Assert( m_counter>0, "Pool.Deallocate(): too many deallocations!");
			m_pool[--m_counter] = obj;
		}
 
		/// <summary>
		/// 
		/// </summary>	
		public function get m_Num():int
		{
			return m_counter;
		}
 
		/// <summary>
		/// 
		/// </summary>	
		public function Get(i:int):*
		{
			Assert(i<m_counter, "Pool.Get(): index out of range!");
			return m_pool[i];
		}
 
		/// <summary>
		/// 
		/// </summary>	
		public function Clear():void
		{
			m_counter=0;
		}
	}
}

This one allows you to construct a pool with runtime type checking and also allows you to call an Initialise() function on the object being allocated. I couldn’t find a way of calling the object’s constructor in AS3, which would have been the ideal case – something like placement new in c++ would be nice. Equally, I couldn’t find a way of passing all the parameters directly to the function without manually indexing them or calling apply() which I’ve read is very slow. However, it works well in practice.

For the temporary calculations involving Vector2′s I used a large pool of Vector2s which only exists for one frame. The only caveat is that you need to be very careful not to persist a reference to one of these across frames because it will be overwritten. I really wish AS3 had struct like c# does to avoid having to do this.

I used the following profiler (which I highly recommend) to identify the slow parts of the engine: http://manuel.bit-fire.com/2007/10/17/an-as3-profiler/

Once I had identified all the slow parts and made pools for all the temporary objects I was still a little discouraged because it wasn’t running quite as fast as I’d have liked on my old desktop that I have here. I worked hard at it but eventually reached the point of diminishing returns and I was in danger of making the source code too hard to follow.

In desperation I fired up the real angry birds in my chrome browser to see how quickly that would run on my machine. I was shocked and relieved to discover that it actually ran a lot slower than my implementation did! Happy days.

Particles and blinking

Some little items of polish that I added to the game were a simple particle system which used Sprites defined in the Flash IDE as the particles and a simple blink controller that used named instances inside each character for the open eyes and the closed eyes and then animated them in code depending on a random waiting period to judge when to toggle the visibility of each.

Figure 8

Figure 8 shows an example character with blinked and open eyes and the corresponding eye shapes for each.

Conclusion

Of course the game contains many more little things which I don’t possibly have time to write about now, but if there is enough interest I can write another article of course! In this article I have covered some of the things which are necessary to turn theory into practice when it comes to talking about physics engines in games.

If you would like to do so, please purchase the source code and assets which go with this article; its very close to being a completed game which can be easily used as a template for your own 2d physics game, complete with editor (in the form of flash) which is delightfully easy to use.

This one is a little more expensive than my regular example code, but take into consideration that it took me two solid weeks of work which if I were contracted would be significantly more than this for one days work and also that what you are getting represents 10 years of industry experience and knowledge – if you think of it like that it really is a bargain… Remeber, Roivo spent $120k developing the original angry birds!

The only thing I ask is that no one just releases this as a game as it stands – please use it as a template for your own games! :) As ever, the licence allows you to use all the code and assets for commercial purposes or otherwise as long as you don’t just release it as it stands and that you don’t simply give the entire thing to anyone else.

Note: requires Flash CS4+ and builds with Amethyst or FlashDevelop.

49.99USD

I hope you make some exciting games with this and I look forward to playing them!

Until next time, have fun!

Cheers, Paul.

p.s. in the game if you get bored of playing by the rules, you can simply pick up any object with the mouse and smash it around for fun!

Submit to StumbleUpon

About Paul Firth

A games industry veteran of ten years, seven of which spent at Sony Computer Entertainment Europe, he has had key technical roles on triple-A titles like the Bafta Award Winning Little Big Planet (PSP), 24: The Game (PS2), special effects work on Heavenly Sword (PS3), some in-show graphics on the BBCs version of Robot Wars, the TV show, as well as a few more obscure projects.   Now joint CEO of Wildbunny, he is able to give himself hiccups simply by coughing.   1NobNQ88UoYePFi5QbibuRJP3TtLhh65Jp
This entry was posted in AS3, Collision Detection, Graphics, Making angry birds, Physics, Technical and tagged , , , , , . Bookmark the permalink.

145 Responses to How to make Angry Birds – part 2

  1. codeBeast says:

    captcha – or my maths is crap which it isn’t or the software has a bug.
    I will try again now (bet it works first time :D) NO
    Error: You entered in the wrong CAPTCHA phrase. Press your browser’s back button and try again
    times tried: 15 (now I’m starting to sweat)

    Flash IDE. I have added the swc BUT the assets.fla is not pointing to it’s doc class and the classes are also in other folders so they would have to be named appropriately ie: where it says package com.assets etc… If that’s the case I’ll get down to it.

    FlashDevelop – know nothing about it – you point FD to – from where – ie: could you just tell me like from the menu -
    Cheers

  2. codeBeast says:

    Changed my browser to firefox and went through first time. I was using chrome before.

  3. codeBeast says:

    Hi – that’s quick service.
    I have clicked the link but nothing is happening.

  4. codeBeast says:

    Thanks a lot for your effort – appreciated.
    Gerry

  5. Isak says:

    Hi Paul,

    Thanks for the great source. I have been attempting to setup all the dependencies in VS, but I am getting many errors and when I run the previous build it just takes me to the browser.

    I have installed Amethyst and the Flex SDK and I have attempted to follow all the tutorials for setup. I still am not able to build the project.

    I would appreciate if you can point to me to a blog or step by step on how to configure the project in Visual Studio 2010.

    Thanks

    • Paul Firth says:

      Hi Isak,

      Sorry you are having problems – what errors are you getting specifically?

      Have you told amethyst where the flex sdk is installed on your machine?

      Cheers, Paul.

  6. Isak says:

    Hi Paul,

    Thank you for the quick response. Yes I have pointed the SDK in the project properties.

    The errors are all code related, I have posted them below:

    Error 1 Call to a possibly undefined method BrokenIceFla
    Error 2 Call to a possibly undefined method EnemyFeatherFla
    Error 3 Access of undefined property Level3Fla.
    Error 4 Access of undefined property Level2Fla.
    Error 5 Access of undefined property LevelFla.
    Error 6 Call to a possibly undefined method TextFla.
    Error 7 Definition Level2Fla could not be found.
    Error 8 Compile failed. Exit code was 10

    I appreciate your help as I am very familiar with VS but I’m struggling to get this configured.

    Regards,

    Isak

    • Paul Firth says:

      Hi Isak,

      Those all sound like errors related to the compiler not being able to locate and link against assets.swc as those symbol names are all defined in that file. Have you re-exported that file from CS4 yourself, or are you using the one which came in the zip file?

      Just check that the ‘references’ in the project explorer include assets.swc?

      Cheers, Paul.

      • Isak says:

        Ha, I knew it was something simple.

        Lifesaver thanks. I’m looking forward to working through the tutorial.

        I was hoping you could help me with some advice. I am proficient with C++ and am looking to use this rather than AS. I know you have said in previous posts that the principles are ambiguous to languages.

        However I am struggling to figure out how to transfer how you have put together the graphics.

        Can I still use your graphics method with Flash as I am not clear if I could do that using C++. If not can you recommend any similar graphics engine or method for use with VS and C++?

        I am thinking about usig Marmalade SDK for all mobile development.

        Or would you recommend learning AS?

        Once again I appreciate your advice and recommendations and for the help with compilation.

        Regards,

        Isak

        • Paul Firth says:

          No problem, glad you got it working ok in the end! :)

          As for c++ – perfectly possible to get it working, you just have to handle the graphics differently. Most of the graphics would be replaced by straight bitmaps; probably on textured polygons using a 3d engine in 2d.

          Should be a simple matter to get them exported from flash into bitmap form, then just a question of getting them into your engine of choice.

          However, if you’re thinking about mobile, you might consider adobe air, as that will let you cross compile the code as it stands and have it running on mobile in no time at all – of course, that means learning AS3, but its really quite similar to c++ in a lot of ways, sans the stack objects for complex types.

          Cheers, Paul.

  7. David says:

    I am trying to change the characters in angry birds. Am I correct in thionking that I mak e the changes to the asset.fla then export it to an .swc to get them to appear when I rebuild in Visual Studio? If so I cannot seem to get the .swc to export from the original source files, and I am wondering if it is due to some of the conflicts that are popping up:

    Symbol ‘Level2′ 1152: A conflict exists with inherited definition Code:Level.m_flaSlingshot in namespace public.
    Symbol ‘Level2′ 1152: A conflict exists with inherited definition Code:Level.m_flaBird2 in namespace public.
    Symbol ‘Level2′ 1152: A conflict exists with inherited definition Code:Level.m_flaSlingshotBack in namespace public.
    Symbol ‘Level2′ 1152: A conflict exists with inherited definition Code:Level.m_flaBird3 in namespace public.
    Symbol ‘Level2′ 1152: A conflict exists with inherited definition Code:Level.m_flaBird1 in namespace public.

    any help is appreciated I have tried every thing I can think of ( file permissions , file paths). I am out of ideas. Thanks

    • Paul Firth says:

      Hi there,

      Yes you are correct about the export process. Were you able to build the project before you exported from flash?

      Have you set the class-paths up in the Flash IDE to point to the location you unzipped your files?

      Cheers, Paul.

  8. Emanuel Warzel says:

    Hey,
    can you help me with creating a similar game like this for android? I really wanna learn!
    Please,I have tried so many times,also is there a Script so when all baddies are destroyed theres like a score and next level? Another suggestion is achievements…
    THANKS YOU! Your tutorials are awesome.
    regards
    Emanuel

  9. Jose says:

    Can i use this development to use it in a tablet (iOS, Android)?

  10. Kyle says:

    Hey Paul, thanks a lot for the tutorial, just getting into games programming now and this is the perfect app to start off on.

    again very much appreciated

  11. Antony says:

    how to replace the text with the movie clip at the end of the game?

  12. Anonymous says:

    Sorry to bother but what is the difference between ‘point of contact’ and ‘contact set’?
    I’m also wondering how is the closest feature-pair computed?

  13. Derek says:

    Hello, Can it support Flash CS6?
    I want to purchase & download this source fla to research.

  14. John says:

    Paul,

    You say that Flash CS4+ is required; I use FlashDevelop, can I use this without CS4+?

    Thanks

  15. Jon Slater says:

    Hi Paul,
    As always, thanks for a fascinating article, and I briefly wanted to make a request of your knowledge and experience.
    In the section entitled ‘Persistent Contacts’, you mention ‘When two objects touch for the first time, a persistent contact entry is generated for the collision and stored on the lower indexed object, so that I avoid duplicating data’, sounds good.
    So but lets imagine A is the lower indexed object, so you get the entry for that, but then presumably you then have to find object B under this object A entry. so im a bit confused -do you have a list of lists?
    would it be better to hash together A and B indices (lets say the key is something like: iA > iB ? iA << 16 | iB & 0xffff : iB << 16 | iA & 0xffff), and put the objects ptrs in a chained map?
    ..but then i've still got to find the feature pair:-(

    my question is: whats the best type of structure for this?

    thanks for your articles:)
    Jon

    • Paul Firth says:

      Hi Jon,

      I had to look at the code since its been a while since I’ve worked on this! :)

      Touching contacts are indeed stored only on the lower indexed object and within the touching contacts the feature pairs are stored by key (just in a short, dumb list inside the touching contact). Whenever touching contacts need to be accessed I always have a pair of objects – for example when two objects first touch, there are we have access to both objects and when the contacts are solved for there is a reference to each object stored inside the contact so we never need to look one object up via the other, if that makes sense?

      Cheers, Paul.

      • Jon Slater says:

        Thanks for your reply Paul:)

        so when you determine that a contact is indeed touching, presumably have to check that it’s not already in your list before you can add it.
        so before you add a new touching contact, say you have your 2 objects, and you find an entry in your table using the lower index. but then lets say that the other object is not referenced in the touching contact at that index.
        do you then add another touching contact after the (incorrect) found one? if so, isn’t this basically a chained hash table?

        thanks very much for your thoughts on this
        Jon

        • Paul Firth says:

          Hi Jon,

          When two objects first touch, the lower indexed object has its touching contact list searched to see if it contains an entry for the other object, if not one is created… I’m not quite sure what you mean when you refer to the incorrectly found one?

          Cheers, Paul.

          • Jon Slater says:

            ok, i got it; sorry for seeming obtuse!:) so this appears similar to box2d, where the contact list (although owned by the world) is accessed in lists maintained in the b2Body class, so that a linear search is done at object level to find the other body once you got the first one.
            I was attempting to speed this up in my own project, for objects with potentially large numbers of contacts/feature pairs; i think i may use a hash table possibly using a std::pair as a key or something.
            thanks a lot for this info; i have found your site inspiring.
            cheers, Jon

          • Paul Firth says:

            No problem, happy to help :)

  16. cristian says:

    hello, wanted to know if this project is very complicated to change the resolution?
    I consult you because as you can physically altering the game to change the size of the stage. The project brings the graph?

    • Paul Firth says:

      Hi Cristian,

      No, its quite simple, you’d need to recompile the code, though because the resolution for the swf is specified at a metatag around the entry-point.

      Cheers, Paul.

  17. Before I buy this, can I compile this using Flash CS6? I don’t know what FlashDevelop is and I am on Mac so no Visual Studio. I am in a Flash class right now where we are to build a game based on what is in our book and I would rather learn something more up to date. Any help would definitely be appreciated.

    Nic

  18. Samuel says:

    Hi!
    First of all, thank you for the awesome tutorials!
    Your blog spiked my interest in game physics, and I’ve been playing with the speculative contacts concept for some time now. Recently I bought your code, which was very helpful for finding stupid mistakes in my code :-)

    Now I’m having a small issue with the solver, which I’m tempted to consider as a side effect of speculative contacts rather than a bug of mine. Maybe you can tell me if what I’m experiencing is normal:
    - I’m moving a fast Rectangle against a fixed Circle (with infinite mass). This is a controlled test case, with penetration correction turned off.
    - The goal was to check whether the separation distance is correctly calculated, and if the solver really leaves the objects “just touching” at the beginning of the next frame.
    - However, although the point of contact is indeed left “just touching”, since the Rectangle rotates due to the collision, the neighbouring points end up penetrating the circle.
    - This is quite visible over time, since penetration keeps increasing as the rectangle rotates over the circle.

    Of course, the problem goes away if I enable penetration correction, but I was expecting that penetration should only occur if there are more bodies pushing each other in the system. I’m also wondering if there is something I’m missing here? Does it make any sense to generate an approximated contact set for the Rectangle vs. Circle case? Or am I just being paranoid?

    • Paul Firth says:

      Hi Samuel,

      Fast rotation can cause penetration to occur since this is only an approximate method – you can see this in the article with the thin rotating rectangle vs the small cube. You shouldn’t need any kind of extended contact set between a circle and a rectangle – there is only one collision point. I wouldn’t worry about it; such penetration will be unnoticeable in practice because of the fast moving nature of the objects and with penetration resolution even less so.

      Hope that helps!

      Cheers, Paul.

      • Samuel says:

        Hi again!
        Thanks for the fast reply, it helped indeed. Now I can close this test case and move to the next one.
        I’m testing each collision detection case individually, because I decided to try SAT instead of the Minkowsky difference… and I have a bunch of stupid bugs which I’m fixing step by step :-)

        This question about the penetration between circles and rotating polygons was just something that had me confused meanwhile..

        Again, thanks for the help, and congratulations for the awesome blog!

        Samuel.

  19. finscn says:

    $49.99 is too expensive for a chinese guy … TEARS :’(

  20. bohr says:

    very nice information…
    i’m quite interest to develop an agent to solve this game… (gameplay)
    any idea which one is the best algorithm to apply ?.. thanks…

  21. Xiaoyu says:

    Hi Paul,

    Thanks for the effort you put into this excellent article!

    But I am having a question about angular momentum, even after reading Chris Hecker’s articles, who suggested a force/acceleration model rather than your impluse/momentum model. In my little demo I have the contact point/normal/velocity, radius vector(from contact point to rotation center), inertia and inverse mass. Is it sufficient to get the change of angular velocity from the above information?

    Thanks :)
    Xiaoyu

    • Paul Firth says:

      Hi Xiaoyu,

      As long as you have inverse masses and inverse moments of inertia for both bodies in contact, it is possible to compute an impulse which will give both change in linear and angular velocity.

      The equation itself is rather large and unwieldy, though. Equation 9 in Chris’ article here: http://chrishecker.com/images/e/e7/Gdmphys3.pdf gives you the impulse J, which you then multiply by the inverse mass (to get change in linear velocity) and inverse moment of inertia (to get change in angular velocity).

      Hope that helps!

      Cheers, Paul.

      • Xiaoyu says:

        Hi Paul,

        I just read the Part 2 where velocity is integrated from accl, then jump to that hasty conclusion…

        Thanks for your help! I think I have to dig more into Chris Hecker’s good old articles :)

        Xiaoyu

  22. Ian says:

    Why did it cost 140,000$ to make angry birds? Couldnt a skilled programmer make an app from scratch just using their skills.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

WP-SpamFree by Pole Position Marketing