id provides an excellent axis aligned bounding box class called idBounds found in idLib (idLib/bv/Bounds.h). idBounds can be used to test for intersections against points, bounds, lines, and more. It works well if you need an axis aligned bounding box but what if you want to test for intersections between more complicated geometry?
Well, as you might expect some intersections are easier (cheaper) to calculate than others. It's computationally fast to check for collisions between an axis aligned bounding box and a point so it's usually a good idea to "cull" the set of entities against an idBounds before checking for more precise collisions. For example, say you wanted to find all the entities within 128 units of the player. First you should define an idBounds centered on the player and completely containing a sphere of radius 128. Then you can check for intersections against a specific subset of entities (this can be done without testing every entity and is very fast). If an entity intersects with your idBounds then you know it's close enough to the player to warrant additional computation. You still don't know if it's actually within 128 units but you know that it might be.
This is how idGameLocal :: RadiusDamage works so let's go over it as an example.
Open game/Game_local.cpp and find the RadiusDamage function. This function applies damage according to the passed damageDef to all entities near the passed origin.
if ( radius < 1 ) {
radius = 1;
}
bounds = idBounds( origin ).Expand( radius );
// get all entities touching the bounds
numListedEntities = clip.EntitiesTouchingBounds( bounds, -1, entityList, MAX_GENTITIES );
|
After retrieving some miscellaneous damageDef variables the function creates an idBounds centered on the passed origin. It also calls the idBounds :: Expand function which expands the idBounds' dimensions to (-radius,-radius,-radius) and (radius,radius,radius). At this point the function calls the EntitiesTouchingBounds function provided by idClip. EntitiesTouchingBounds fills the entityList array with the appropriate entities and returns the total number found; note that this function is extremely efficient and should be used to cull entities in almost every entity search.
The rest of the function is pretty boring but there is one piece missing - the spherical collision check.
dist = v.Length();
if ( dist >= radius ) {
continue;
}
|
During the main loop any entity further than radius units away from the origin will be skipped. That's all there is to a spherical collision check.
idClip is found in game/physics/Clip.h and provides access to the main collision functions. Collisions are checked in the physics code and are usually determined with tracelines rather than with entity searches. As an example let's take a look at how bullet collisions are determined; interestingly enough all projectiles are handled the same way whether they're bullets or plasma balls or rockets! This means that bullets follow the same physical rules (such as gravity although most projectiles are created with zero gravity) as everything else. Other games such as Half-Life perform completely straight tracelines to handle bullet collisions which are fast and cheap but rather inaccurate over long distances since bullets don't go completely straight in real life. These types of weapons are often called "hitscan" weapons. Anyway, open game/Weapon.cpp and find the Event_LaunchProjectiles function.
proj = static_cast |
This function is only ever called by a weapon script and does quite a lot of stuff; most of it we don't care about. We're interested in the above code where the projectiles are created and launched. Notice how several projectiles can be created at once when a weapon is fired even if they're fast moving bullets (e.g. the shotgun). This is much slower than performing a few quick tracelines but it's more accurate. Alright, projectiles are handled in the idProjectile class so crack open game/Projectile.h. Since we're concentrating on collisions and physics right now, notice that idProjectile uses rigid body physics.
idPhysics_RigidBody physicsObj; |
We're jumping all over the place today but it's pretty hard to pin down where projectile collisions are calculated. Open game/physics/Physics_RigidBody.cpp and look for the Evaluate function. How does this function fit into the big picture? Well, idProjectile :: Think is called every frame which calls idEntity :: RunPhysics which calls Evaluate. Notice that the comments above the function mention collisions so we're probably on the right track. This next bit of code appears in the Evaluate function.
// check for collisions from the current to the next state collided = CheckForCollisions( timeStep, next, collision ); |
Aha! Let's investigate the CheckForCollisions function.
// if there was a collision
if ( gameLocal.clip.Motion( collision, current.i.position, next.i.position, rotation, clipModel, current.i.orientation, clipMask, self ) ) {
// set the next state to the state at the moment of impact
next.i.position = collision.endpos;
next.i.orientation = collision.endAxis;
next.i.linearMomentum = current.i.linearMomentum;
next.i.angularMomentum = current.i.angularMomentum;
collided = true;
}
|
The idClip :: Motion function performs translations and rotations using the idCollisionModelManager class provided by the engine. We don't have access to the source code for this class but these functions are supposed to perform semi perfect collision detection (i.e. more precise than simple hitbox collisions). If a collision is detected the CollisionImpulse function alerts idProjectile by calling idProjectile :: Collide which applies damage and all that wonderful stuff.
Alright, let's write some code to display a list of nearby entities on the player's HUD. Open game/Player.cpp and find the DrawHUD function. Add this code to the very end.
// perform the idBounds culling first
idBounds bounds = idBounds( GetPhysics( )->GetOrigin( ) ).Expand( 100.0f );
idEntity *entityList[MAX_GENTITIES];
int numListedEntities = gameLocal.clip.EntitiesTouchingBounds( bounds, -1, entityList, MAX_GENTITIES );
// loop through entities
int x = 40;
int y = 40;
for( int e = 0; e < numListedEntities; e++ )
{
idEntity *ent = entityList[e];
// find simple distance between the player's origin and the entity's origin
// a better solution is found in idGameLocal :: RadiusDamage
idVec3 diff = ent->GetPhysics( )->GetOrigin( ) - GetPhysics( )->GetOrigin( );
float dist = diff.Length( );
if( dist > 100.0f )
continue;
idStr strTemp;
sprintf( strTemp, "%s: %d", ent->GetName( ), (int)dist );
renderSystem->DrawSmallStringExt( x, y, strTemp.c_str( ), idVec4( 1, 1, 1, 1 ), false, declManager->FindMaterial( "textures/bigchars" ) );
y += 20;
}
|
The DrawSmallStringExt function works similar to DrawBigStringExt which is explained in Tutorial 4.
You could easily apply this entity search technique to implement an Unreal Tournament domination style game mode or to implement a Front Line Force style morale system (where players in groups get bonuses). Doom 3 uses it for RadiusDamage and for the BFG ball to mention just a few examples.
November 17, 2004