There are still a few days left before the semester starts and right now I'm trying to make the most of them. As I said in the last post I wanted to put the entity system aside for a while and work on A) gameplay mechanics and B) presentation. However as I played the game I realized that the collisions were in a much worse state than I had thought, so it had to be resolved. Then there was the sound component too. Short things first.
Sound component:
There isn't that much to say here really. I wrapped up the previous AudioSource object in a new component. In order to make a gun component able to play a sound when it shoots I had to add an event to trigger when shooting, then attach the play command to that event. I already had some events in the system, like an onKill event for entities and an onDone event for components that have limited operation time. It's a primitive system, simply a function pointer, but it works for now.
I had to do some modifications to the audio API layer to streamline the workings of the sound component. It feels great to be able to go back to old code and apply new ideas to it. It shows to me that my skills are improving. While there I noted down some things in the TODO list on how I'd like the API layer to work (but when will I find the time).
Improved collision response:
Note: Obstacle component has been scrapped, see this entry.
The most annoying thing about the collisions was that obstacles (the colliding objects) tended to get stuck together sometimes. This was a result of the system not doing any inter-frame checks, like sweeping or sub-sampling, and that it uses an impulse response that mirrors the velocity along the surface axis. Even worse it did not project the obstacles out of intersection, causing the them to remain so unless their velocities were great enough to move them apart in a single frame.
At this time the only thing I did was adding a projection step to guard them from sticking together. I could have done more but it solved the problem at hand and I didn't want to overwork it. The system uses circle-circle tests now and, eventually, I'll change it to use general polygons instead.
I still get some strange jumps at times, [deja vu]but unless it acts up more than usual it can wait. It works most of the time. [rolleyes][/deja vu]
Broad phase culling:
The fact that collisions slowed things down wasn't much of a surprise since I only did narrow testing on all participating obstacles. Given n obstacles the number of narrow tests amounted to T = n(n-1)/2, testing each pair once and not testing against self.
My first attempt was a naive implementation of a quad-tree. Had I done my homework I would have anticipated this to be a bad fit since the obstacles tend to be clustered together and not evenly distributed in space. Many cells were unpopulated while some became crowded so the cut in tests did not outweigh the overhead for using the tree. Lesson learned.
In my second attempt I used the fact that groups of obstacles tend to gang up. Each obstacle gets a group id, currently an enum but I'll likely use strings eventually. The obstacles is kept in separate collections, one for each group.
The manager keeps a mapping for which groups will be tested against each other. F.ex. an enemy will collide with other enemies, the player and with player fire but not with enemy fire. The culling is done as follows:
- Test on manager level.
- Compute an AABB for each group.
- For each active group, get a list of other group ids it is allowed to collide with.
- Check each group against each other. If two groups can collide, enter group level test.
- Test on group level.
- Make sure the two groups' AABBs intersect.
- For each obstacle in one of the groups, make sure that its AABB intersects the other group's AABB. If so, do narrow test on it against each obstacle in other group.
The translation of which groups are allowed to collide with each other is implemented as a std::multimap in the manager. It maps one id to a number of other allowed ids.
The manager also keeps a std::map, that maps group ids to group collection objects. When a new obstacle is added to the manager it is passed on and added to a group object based on its group id. This is the container being iterated over when group objects are tested against each other.
There is still some room for improvement here. In 2.2 we have two options, either test the members of group A against group B or test the members of group B against group A. The order would matter since the members of the groups can be distributed differently. One could argue that selecting the group with fewer members and testing them against the group with more could eliminate many tests in one go if the selected member is out of the group bounds. One could also argue that the members of the group with biggest bounding area should be tested against the other group, since chances are better that the members are not inside the smaller area. This would simply have to be tested and evaluated.
Yeah whatever, what about the results?
In my current setup I have one player, 10 enemies that fire periodically from two guns each. With the player firing away as well I end up with about 70 obstacles on average. With the broad phase culling the system does somewhere between 100-300 narrow tests. Without the broad phase we have by the formula 2415 narrow tests. Good show!
The relevant code:
I've tried to edit out irrelevant code to make it less confusing.
ObstacleManager.hpp
#ifndef CN_OBSTACLEMANAGER_H#define CN_OBSTACLEMANAGER_H#include "ComponentManagerBase.hpp"#include "Obstacle.hpp"namespace cn { class EntityManager; // -------------------------------------------------------------- class ObstacleGroup { public: void updateBounds( ); void testCollisions( ObstacleGroup &otherGroup, const Collider &collider ); void addObstacle( Obstacle *o ); void removeObstacle( Obstacle *o ); private: typedef std::set ObstacleSet; ObstacleSet obstacles; rect boundingBox; }; // -------------------------------------------------------------- class ObstacleManager : public ComponentManagerBase { public: ObstacleManager( EntityManager *entityManager ); void updateByFrame( ); void addObstacleToGroup( uint entityId ); void removeObstacleFromGroup( uint entityId ); private: CircleCollider defaultCollider; typedef std::multimap GroupIdMap; typedef std::pair GroupIdMapIteratorPair; typedef std::pair GroupIdPair; GroupIdMap collisionTargets; typedef std::map GroupIdGroupMap; GroupIdGroupMap groups; };}#endifThe updateByFrame() function is the motor here and the entering pint to the whole process. If you'd like to trace the code, that's where you start. The add/removeFromGroup() functions are called externally at add and remove times. The CircleCollider class inherits Collider and works like a functor performing the narrow test. There are several extra typedefs in the manager that are used in updateByFrame() to make it cleaner.
ObstacleManager.cpp
#include "Prerequisites.hpp"#include "ObstacleManager.hpp"#include "Obstacle.hpp"#include "EntityManager.hpp"namespace cn { // -------------------------------------------------------------- // ObstacleManager class // -------------------------------------------------------------- ObstacleManager::ObstacleManager( EntityManager *entityManager ) : ComponentManagerBase( entityManager ), defaultCollider( entityManager ) { // Here the allowed collision targets for each id are defined. // Allies maps to Allies, Enemies and EnemyFire, etc. collisionTargets.insert( GroupIdPair( Allies, Allies )); collisionTargets.insert( GroupIdPair( Allies, Enemies )); collisionTargets.insert( GroupIdPair( Allies, EnemyFire )); collisionTargets.insert( GroupIdPair( Enemies, Enemies )); collisionTargets.insert( GroupIdPair( Enemies, Allies )); collisionTargets.insert( GroupIdPair( Enemies, AlliedFire )); collisionTargets.insert( GroupIdPair( AlliedFire, Enemies )); collisionTargets.insert( GroupIdPair( EnemyFire, Allies )); } // -------------------------------------------------------------- void ObstacleManager::updateByFrame( ) { // Make the bounds up to date. // NOTE: However intermediate changes during collisions will not be caught. GroupIdGroupMap::iterator it; for ( it = groups.begin( ); it != groups.end( ); it++ ) { it->second.updateBounds( ); } // A-loop: Iterate over all present groups. for ( it = groups.begin( ); it != groups.end( ); it++ ) { // Find which groups the current group responds to. GroupIdMapIteratorPair targetIds = collisionTargets.equal_range( it->first ); // Proceed if the range is not empty. if ( targetIds.first != targetIds.second ) { // B-loop: Iterate over all groups at same position and after. GroupIdGroupMap::iterator jt; for ( jt = it; jt != groups.end( ); jt++ ) { // Proceed if A-element id responds to B-element id. GroupIdMap::iterator kt; for ( kt = targetIds.first; kt != targetIds.second; kt++ ) if ( kt->second == jt->first ) break; if ( kt != targetIds.second ) { // Now we know the two groups respond to each other. // TODO: Make a decision on the test order, f.ex. by greatest area or least count. it->second.testCollisions( jt->second, defaultCollider ); } } } } } // -------------------------------------------------------------- void ObstacleManager::addObstacleToGroup( uint entityId ) { groups[it->second->getGroupId( )].addObstacle( it->second ); } // -------------------------------------------------------------- void ObstacleManager::removeObstacleFromGroup( uint entityId ) { groups[it->second->getGroupId( )].removeObstacle( it->second ); } // -------------------------------------------------------------- // ObstacleGroup class // -------------------------------------------------------------- void ObstacleGroup::updateBounds( ) { boundingBox = rect( 0, 0, 0, 0 ); ObstacleSet::iterator it; for ( it = obstacles.begin( ); it != obstacles.end( ); it++ ) { (*it)->updateBoundingBox( ); fit( boundingBox, (*it)->getBoundingBox( )); } } // -------------------------------------------------------------- void ObstacleGroup::testCollisions( ObstacleGroup &otherGroup, const Collider &collider ) { PROFILE_FUNC( ); // Check if groups intersect at all. if ( intersect( boundingBox, otherGroup.boundingBox )) { // Iterate over all local obstacles. ObstacleSet::iterator it; for ( it = obstacles.begin( ); it != obstacles.end( ); it++ ) { // Check if the current local obstacle intersects the other group. if ( intersect( (*it)->getBoundingBox( ), otherGroup.boundingBox )) { // Check against all in other group. ObstacleSet::iterator jt; for ( jt = otherGroup.obstacles.begin( ); jt != otherGroup.obstacles.end( ); jt++ ) { // Don't check against self. if ( (*it)->getId( ) != (*jt)->getId( )) { collider.apply( *it, *jt ); } } } } } } // -------------------------------------------------------------- void ObstacleGroup::addObstacle( Obstacle *o ) { obstacles.insert( o ); } // -------------------------------------------------------------- void ObstacleGroup::removeObstacle( Obstacle *o ) { obstacles.erase( o ); }}Note that there are two classes here ObstacleManager and ObstacleGroup. The updateByFrame() function is really STL-messy, I know, so do ask.
Obstacle.hpp
#ifndef CN_OBSTACLE_H#define CN_OBSTACLE_H#include "ComponentManagerBase.hpp"#include "ComponentBase.hpp"namespace cn { class EntityData; class Obstacle; // This is the group id definition. enum ObstacleGroupId { Allies, Enemies, Neutrals, AlliedFire, EnemyFire, NeutralFire }; // -------------------------------------------------------------- class Obstacle : public ComponentBase { public: Obstacle( uint entityId, EntityData *entityData, const ComponentParameters ¶ms ); uint getId( ) { return id; } const rect &getBoundingBox( ) { return boundingBox; } void updateBoundingBox( ); ObstacleGroupId getGroupId( ) { return params.group; } private: // This object contains the group id for the obstacle. ComponentParameters params; rect boundingBox; };}#endifHere rect is simply a class describing a rectangle parallel to the coordinate axes.
Obstacle.cpp
#include "Prerequisites.hpp"#include "Obstacle.hpp"#include "EntityData.hpp"namespace cn { // -------------------------------------------------------------- void Obstacle::updateBoundingBox( ) { // I didn't include the two functions below but they should be obvious. vec2 pos = getPos( ); real radius = getRadius( ); boundingBox.left = pos.x - radius; boundingBox.right = pos.x + radius; boundingBox.bottom = pos.y - radius; boundingBox.top = pos.y + radius; }}Currently collisions are based on circles but if that changes, so will this function, obviously.
That's it for today folks.
