Godsend Programming #3: Refactoring the Collision code and Bitmasks
In this entry, I will be going through how I refactored the collision detection system, the implications of it and how it makes the collision code nicer, easier to read and lets the programmer focus on what’s important rather typing chunks of type checking code.
The problem
Obviously, I would not be refactoring such a thing if there weren’t any problems with it. Both myself and Zafar could see that the existing code could be improved somehow.
Box2D gives you a B2Contact object when a collision occurs. The contact contains two fixtures that collided (where the order could be different each time, so we can’t rely on it). We want to execute some game logic once a collision happens between two objects that we are interested in, say, the player and an enemy. To check if this has happened, we would have to write the following code:
Where pGcSprPhysA and pGcSprPhysB are CGCObjSpritePhysics instances that contain the fixtures which collided. We have to check both orderings in the collision, as the enemy could have walked into the player, or the player could have walked into the enemy first.
Then, we would probably want to call some function on the player to injure or knock them back. We would need to cast the CGCObjSpritePhysics object to a particular player type. This would then be done as such:
We already know that one of the objects colliding is the player, but we still need an additional check to see which one of the objects is actually the player!
The problem is that the type checking if statement only checks the type, but does not give us any information to use when it does the check! Furthermore, what if we wanted to play a smirky animation on the enemy when this behaviour happens as well? We would have to do that check once again to figure out which object is the enemy! Or, we would have to write another if-statement (rather than a ternary operator) doing just a single check to identify one of the objects, then cast both of them based on that information. But maybe we don’t need to do anything with the enemy! Why did we cast it then?
And imagine if your code needs this type of check for every single interaction between objects that we are interested in! This is exactly what we had, and the collision code was ugly, difficult to read and doing more checks than necessary.
Refactoring collision variable duplication
Now that the problem was understood, I had to look for a good way of eliminating as much of it as I can. The first problem, is that I would have to pass in references to the CGCObjSpritePhysics objects to the helper function. Furthermore, these are initialised in the exact same way in four different locations – BeginContact, EndContact, PreSolve, HandleCollisions:
// return if either physics body has null user data
CGCObjSpritePhysics* pGcSprPhysA = (CGCObjSpritePhysics*) pBodyA->GetUserData();
if( !pGcSprPhysA )
{
return;
}
Obviously, is something is repeated several times exactly, we ought to try and factor it out into common code. This took me several passes to get it in a way that’s flexible enough for the helper functions, but I ended up making pFixtureA, pFixtureB, pGcSprPhysA, pGcSprPhysB into member variables that would get updated when each new B2Contact is being considered:
m_pcCollisionObjects[ 0 ] = ( CGCObjSpritePhysics* ) m_pcCollisionFixtureObjects[ 0 ]->GetBody()->GetUserData();
// if( this is not an alex object )
if( ( nullptr == m_pcCollisionObjects[ 0 ] ) )
{
return false;
}
m_pcCollisionObjects[ 1 ] = ( CGCObjSpritePhysics* ) m_pcCollisionFixtureObjects[ 1 ]->GetBody()->GetUserData();
// if( this is not an alex object )
if( nullptr == m_pcCollisionObjects[ 1 ] )
{
return false;
}
return true;
}
Finally, the calls in BeginContact, EndContact, PreSolve and HandleCollisions would use this function as such:
//update member variables for collision checking
//if colliders don't have user data, return
if( UpdateCollisionReferences( pB2Contact ) == false )
{
return;
}
So it’s now just a single function call and duplicated initialisation code is eliminated. The only concern that I have is that the B2Contact information (variables) would probably fit better within the local collision code and should be encapsulated within it, whereas making the information into member variables breaks this encapsulation. I should probably re-inforce this by nullifying all of the member variables at the end of each collision, such that the information is only valid during collision resolution, not before and not after. This would probably reinforce the encapsulation better.
Helper functions
I initially had the Fixtures and SpritePhysics objects stored separately, rather than coupled in arrays. To help explain the choice of moving them into arrays, I will give a sample collision helper function that tackles the problem case described at the start of this entry:
i32 CGCGameLayerPlatformer::CheckCollisionBetweenTwoTypes( GCTypeID type1, GCTypeID type2 ) const
{
i32 iReturn = -1;
//check for the first type
if( m_pcCollisionObjects[ 0 ]->GetGCTypeID() == type1 && m_pcCollisionObjects[ 1 ]->GetGCTypeID() == type2 )
{
iReturn = 0;
}
//check the other way around
if( m_pcCollisionObjects[ 1 ]->GetGCTypeID() == type1 && m_pcCollisionObjects[ 0 ]->GetGCTypeID() == type2 )
{
iReturn = 1;
}
return iReturn;
}
Here, the helper function checks whether objects of the two types we are interested in have collided and returns the index to the object matching the first argument (or -1 if no match is found).
Here, we check if a match was found by simply checking that the return value was valid. Furthermore, we already know which of the two colliding objects is the player, as we have the index to access it! So no additional checks are required.
This brings me to explaining why I stored the collision objects in an array. Initially, I had the helper function return a reference to the object that we want to execute game logic on – in this case, the player. However, I mentioned that we might want to change the animation on the enemy when this collision happens. Returning a reference to the player object does not help and we would need to do this check again, but in reverse order! This is not efficient at all, so I figured I would store the objects in an array, return the index of the first object, and then we would have all of the information to figure out the second object! This is done as such:
So now, we only have to do a single collision check and we get all of the information we need from it! The one thing I don’t like about this is that ternary operator. Especially since you have to do this every time you want to use the second object. This is the state of the code as it is now, but I think I should make a small helper function, such as GetOtherIndex(i32 iObjectIndex) just to make it look a bit nicer. Another issue with this code is efficiency and the fact that there are several ways to figure out the other index.
One of them would be to perform a modulo operation. I wondered which of these would run faster, so I went to google to see if I could find that out. This StackOverflow thread(StackOverflow, 2013) I stumbled into has asked the same question and timed modulo to be the more expensive operation.
Furthermore, I could do a regular if/else statement to accomplish the same, and I actually stumbled upon a post titled Efficient C Tips #6 – Don’t use the ternary operator (Embedded gurus, 2009) suggesting me to indeed do so. The author claims that on most compilers, the ternary operator compiles to slower assembly code than an if/else statement. I should probably research this myself, as my statement is incredibly simple.
At the time of writing, I figured out what is probably the most efficient way of determining the other index: using bit-wise operators:
i32 iOtherIndex = iObjectIndex ^ 1;
So if the first index is a 0, then an x-or operator would make it a 1, and if the first index is a 1, the x-or operator would make it a 0. I will implement this when I get an opportunity.
Other helper functions and classifying collisions
There are a few other helper functions that I have made, as I factored out common cases when type identification is required:
These are heavily commented in code, but I will briefly go through them and the implications that they hold. CheckCollisionForSingleType is a function that only cares about one of the collision objects and whether it’s colliding with something. An example use case of this is the Pressure Plate, where anything should be able to step on it.
CheckCollisionSensorID requires some introduction. Box2D fixtures can be given an ID string, so that we can identify the fixture, rather than the whole collision body collision. An example of this is the player’s ground sensor, which keeps track of whether the player is on the ground. A big implication when using IDs, is that we can’t rely on the string ID before casting the object, as Zafar pointed out. The ID is defined by the programmer, and so the compiler can not possibly know if this is a valid type cast or not. Therefore, we should assert that the sensor ID corresponds to the correct type of object before casting.
CheckSensorIDAgainstBitmaskIdentity introduces bitmasks. Box2D stores a number of bits in each fixture to help classify what it is. For example, a spikes object could be an obstacle and a baddie at once. These bits can be used in a similar way to layers in Unity. Therefore, we defined bits to identify different groups of objects:
This allows us to generalise collision logic a bit more, as we can simply say that a player colliding with a baddie would mean that the player needs to get injured. Ideally, we would want probably want to use inheritance and identify base types for this, but a Spikes object is a really good example of why this works slightly better: Spikes have none of the properties of any other enemy, but it should still hurt the player. Therefore, such a way to classify objects becomes incredibly useful indeed.
The rest of the functions compare a mixture of the ways to identify collision objects based on the most common use cases when identifying collisions.
Conclusions
I think having these helper functions removes a lot of redundant code from the collision handling routines, and it enables the programmer to not worry about the actual fixtures and the order of collision, as they only need to specify what collisions they are interested in. The resulting code seems to be more readable as well.
I think this approach works really well and could potentially be expanded on in the future if more use cases arise. An improvement I think I should consider would be to separate out all of this helper code into a different class, as the GameLayer (which currently contains it all) seems to be a bit too exposed to the collision logic right now. Rather, the GameLayer should probably only hold a reference to a CollisionHelper class and use its functions as necessary.
Godsend Programming #3: Refactoring the Collision code and Bitmasks
In this entry, I will be going through how I refactored the collision detection system, the implications of it and how it makes the collision code nicer, easier to read and lets the programmer focus on what’s important rather typing chunks of type checking code.
The problem
Obviously, I would not be refactoring such a thing if there weren’t any problems with it. Both myself and Zafar could see that the existing code could be improved somehow.
Box2D gives you a B2Contact object when a collision occurs. The contact contains two fixtures that collided (where the order could be different each time, so we can’t rely on it). We want to execute some game logic once a collision happens between two objects that we are interested in, say, the player and an enemy. To check if this has happened, we would have to write the following code:
Where pGcSprPhysA and pGcSprPhysB are CGCObjSpritePhysics instances that contain the fixtures which collided. We have to check both orderings in the collision, as the enemy could have walked into the player, or the player could have walked into the enemy first.
Then, we would probably want to call some function on the player to injure or knock them back. We would need to cast the CGCObjSpritePhysics object to a particular player type. This would then be done as such:
We already know that one of the objects colliding is the player, but we still need an additional check to see which one of the objects is actually the player!
The problem is that the type checking if statement only checks the type, but does not give us any information to use when it does the check! Furthermore, what if we wanted to play a smirky animation on the enemy when this behaviour happens as well? We would have to do that check once again to figure out which object is the enemy! Or, we would have to write another if-statement (rather than a ternary operator) doing just a single check to identify one of the objects, then cast both of them based on that information. But maybe we don’t need to do anything with the enemy! Why did we cast it then?
And imagine if your code needs this type of check for every single interaction between objects that we are interested in! This is exactly what we had, and the collision code was ugly, difficult to read and doing more checks than necessary.
Refactoring collision variable duplication
Now that the problem was understood, I had to look for a good way of eliminating as much of it as I can. The first problem, is that I would have to pass in references to the CGCObjSpritePhysics objects to the helper function. Furthermore, these are initialised in the exact same way in four different locations – BeginContact, EndContact, PreSolve, HandleCollisions:
// return if either physics body has null user data CGCObjSpritePhysics* pGcSprPhysA = (CGCObjSpritePhysics*) pBodyA->GetUserData(); if( !pGcSprPhysA ) { return; }CGCObjSpritePhysics* pGcSprPhysB = (CGCObjSpritePhysics*) pBodyB->GetUserData(); if( !pGcSprPhysB ) { return; }Obviously, is something is repeated several times exactly, we ought to try and factor it out into common code. This took me several passes to get it in a way that’s flexible enough for the helper functions, but I ended up making pFixtureA, pFixtureB, pGcSprPhysA, pGcSprPhysB into member variables that would get updated when each new B2Contact is being considered:
And the code to update them:
bool CGCGameLayerPlatformer::UpdateCollisionReferences( const b2Contact* pB2Contact ) { m_pcCollisionFixtureObjects[ 0 ] = pB2Contact->GetFixtureA(); m_pcCollisionFixtureObjects[ 1 ] = pB2Contact->GetFixtureB();m_pcCollisionObjects[ 0 ] = ( CGCObjSpritePhysics* ) m_pcCollisionFixtureObjects[ 0 ]->GetBody()->GetUserData(); // if( this is not an alex object ) if( ( nullptr == m_pcCollisionObjects[ 0 ] ) ) { return false; }m_pcCollisionObjects[ 1 ] = ( CGCObjSpritePhysics* ) m_pcCollisionFixtureObjects[ 1 ]->GetBody()->GetUserData(); // if( this is not an alex object ) if( nullptr == m_pcCollisionObjects[ 1 ] ) { return false; }Finally, the calls in BeginContact, EndContact, PreSolve and HandleCollisions would use this function as such:
//update member variables for collision checking //if colliders don't have user data, return if( UpdateCollisionReferences( pB2Contact ) == false ) { return; }So it’s now just a single function call and duplicated initialisation code is eliminated. The only concern that I have is that the B2Contact information (variables) would probably fit better within the local collision code and should be encapsulated within it, whereas making the information into member variables breaks this encapsulation. I should probably re-inforce this by nullifying all of the member variables at the end of each collision, such that the information is only valid during collision resolution, not before and not after. This would probably reinforce the encapsulation better.
Helper functions
I initially had the Fixtures and SpritePhysics objects stored separately, rather than coupled in arrays. To help explain the choice of moving them into arrays, I will give a sample collision helper function that tackles the problem case described at the start of this entry:
i32 CGCGameLayerPlatformer::CheckCollisionBetweenTwoTypes( GCTypeID type1, GCTypeID type2 ) const { i32 iReturn = -1; //check for the first type if( m_pcCollisionObjects[ 0 ]->GetGCTypeID() == type1 && m_pcCollisionObjects[ 1 ]->GetGCTypeID() == type2 ) { iReturn = 0; } //check the other way around if( m_pcCollisionObjects[ 1 ]->GetGCTypeID() == type1 && m_pcCollisionObjects[ 0 ]->GetGCTypeID() == type2 ) { iReturn = 1; } return iReturn; }Here, the helper function checks whether objects of the two types we are interested in have collided and returns the index to the object matching the first argument (or -1 if no match is found).
So how is this used in our sample scenario?
iObjectIndex = CheckCollisionBetweenTwoTypes( GetGCTypeIDOf( CGCObjPlayer ), GetGCTypeIDOf( CGCObjEnemy ) ); if( iObjectIndex != -1 ) { CGCObjPlayer* pPlayer = static_cast<CGCObjPlayer*>(m_pcCollisionObjects[iObjectIndex]); }Here, we check if a match was found by simply checking that the return value was valid. Furthermore, we already know which of the two colliding objects is the player, as we have the index to access it! So no additional checks are required.
This brings me to explaining why I stored the collision objects in an array. Initially, I had the helper function return a reference to the object that we want to execute game logic on – in this case, the player. However, I mentioned that we might want to change the animation on the enemy when this collision happens. Returning a reference to the player object does not help and we would need to do this check again, but in reverse order! This is not efficient at all, so I figured I would store the objects in an array, return the index of the first object, and then we would have all of the information to figure out the second object! This is done as such:
So now, we only have to do a single collision check and we get all of the information we need from it! The one thing I don’t like about this is that ternary operator. Especially since you have to do this every time you want to use the second object. This is the state of the code as it is now, but I think I should make a small helper function, such as GetOtherIndex(i32 iObjectIndex) just to make it look a bit nicer. Another issue with this code is efficiency and the fact that there are several ways to figure out the other index.
One of them would be to perform a modulo operation. I wondered which of these would run faster, so I went to google to see if I could find that out. This StackOverflow thread(StackOverflow, 2013) I stumbled into has asked the same question and timed modulo to be the more expensive operation.
Furthermore, I could do a regular if/else statement to accomplish the same, and I actually stumbled upon a post titled Efficient C Tips #6 – Don’t use the ternary operator (Embedded gurus, 2009) suggesting me to indeed do so. The author claims that on most compilers, the ternary operator compiles to slower assembly code than an if/else statement. I should probably research this myself, as my statement is incredibly simple.
At the time of writing, I figured out what is probably the most efficient way of determining the other index: using bit-wise operators:
So if the first index is a 0, then an x-or operator would make it a 1, and if the first index is a 1, the x-or operator would make it a 0. I will implement this when I get an opportunity.
Other helper functions and classifying collisions
There are a few other helper functions that I have made, as I factored out common cases when type identification is required:
These are heavily commented in code, but I will briefly go through them and the implications that they hold. CheckCollisionForSingleType is a function that only cares about one of the collision objects and whether it’s colliding with something. An example use case of this is the Pressure Plate, where anything should be able to step on it.
CheckCollisionSensorID requires some introduction. Box2D fixtures can be given an ID string, so that we can identify the fixture, rather than the whole collision body collision. An example of this is the player’s ground sensor, which keeps track of whether the player is on the ground. A big implication when using IDs, is that we can’t rely on the string ID before casting the object, as Zafar pointed out. The ID is defined by the programmer, and so the compiler can not possibly know if this is a valid type cast or not. Therefore, we should assert that the sensor ID corresponds to the correct type of object before casting.
CheckSensorIDAgainstBitmaskIdentity introduces bitmasks. Box2D stores a number of bits in each fixture to help classify what it is. For example, a spikes object could be an obstacle and a baddie at once. These bits can be used in a similar way to layers in Unity. Therefore, we defined bits to identify different groups of objects:
This allows us to generalise collision logic a bit more, as we can simply say that a player colliding with a baddie would mean that the player needs to get injured. Ideally, we would want probably want to use inheritance and identify base types for this, but a Spikes object is a really good example of why this works slightly better: Spikes have none of the properties of any other enemy, but it should still hurt the player. Therefore, such a way to classify objects becomes incredibly useful indeed.
The rest of the functions compare a mixture of the ways to identify collision objects based on the most common use cases when identifying collisions.
Conclusions
I think having these helper functions removes a lot of redundant code from the collision handling routines, and it enables the programmer to not worry about the actual fixtures and the order of collision, as they only need to specify what collisions they are interested in. The resulting code seems to be more readable as well.
I think this approach works really well and could potentially be expanded on in the future if more use cases arise. An improvement I think I should consider would be to separate out all of this helper code into a different class, as the GameLayer (which currently contains it all) seems to be a bit too exposed to the collision logic right now. Rather, the GameLayer should probably only hold a reference to a CollisionHelper class and use its functions as necessary.
Related Files
GCGameLayerPlatformer.h – https://drive.google.com/open?id=0B_BnvnFZLH7mTER4czNMd24wU28
GCGameLayerPlatformer.cpp – https://drive.google.com/open?id=0B_BnvnFZLH7mQ25jcnpHWDFITFU
GCObjectCategory.h – https://drive.google.com/open?id=0B_BnvnFZLH7mS19PSDRYRklKeUU