Pathfinding using Bullet Raycasting

Started by
4 comments, last by Steve_Segreto 11 years, 5 months ago
I'm trying to implement pathfinding to my 3D game using Bullet Raycasting.


I want to use Bullet Raycasting to find if the position is walkable or not and according to that the model will be moving to go a certain position.

Any code example would be appreciated.
Advertisement
Pretty much you can just use dynamicWorld->RayTest() for ray to world testing. Here's an example of how to do that and also setup some collision filters (like how to dynamically select one single object to ignore (collision filter) while ray testing against everything else).


typedef struct _COLLISION_DATA
{
class CCollideeInstance *m_pCollideeInstance;
class CCharacterController *m_pDynamicObj;
class btCollisionObject *m_pRigidBody;
} COLLISION_DATA;
#define GET_GHOST(x) (btGhostObject *)(((COLLISION_DATA *)x->getUserPointer())->m_pRigidBody)

class GhostPairCallback : public btOverlappingPairCallback
{
public:
GhostPairCallback()
{
}
virtual ~GhostPairCallback()
{

}
virtual btBroadphasePair* addOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1)
{
btCollisionObject* colObj0 = (btCollisionObject*) proxy0->m_clientObject;
btCollisionObject* colObj1 = (btCollisionObject*) proxy1->m_clientObject;
btGhostObject* ghost0 = btGhostObject::upcast(colObj0);
btGhostObject* ghost1 = btGhostObject::upcast(colObj1);
if (ghost0 && ghost0 != GET_GHOST(colObj1))
{
ghost0->addOverlappingObjectInternal(proxy1, proxy0);
}
if (ghost1 && ghost1 != GET_GHOST(colObj0))
ghost1->addOverlappingObjectInternal(proxy0, proxy1);
return 0;
}
virtual void* removeOverlappingPair(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1,btDispatcher* dispatcher)
{
btCollisionObject* colObj0 = (btCollisionObject*) proxy0->m_clientObject;
btCollisionObject* colObj1 = (btCollisionObject*) proxy1->m_clientObject;
btGhostObject* ghost0 = btGhostObject::upcast(colObj0);
btGhostObject* ghost1 = btGhostObject::upcast(colObj1);
if (ghost0 && ghost0 != GET_GHOST(colObj1))
ghost0->removeOverlappingObjectInternal(proxy1,dispatcher,proxy0);
if (ghost1 && ghost1 != GET_GHOST(colObj0))
ghost1->removeOverlappingObjectInternal(proxy0,dispatcher,proxy1);
return 0;
}
virtual void removeOverlappingPairsContainingProxy(btBroadphaseProxy* proxy0,btDispatcher* dispatcher)
{
btAssert(0);
//need to keep track of all ghost objects and call them here
//m_hashPairCache->removeOverlappingPairsContainingProxy(proxy0,dispatcher);
}
};
struct ActorFilterCallback : public btOverlapFilterCallback
{
// return true when pairs need collision
virtual bool needBroadphaseCollision(btBroadphaseProxy* proxy0,btBroadphaseProxy* proxy1) const
{
bool collides = (proxy0->m_collisionFilterGroup & proxy1->m_collisionFilterMask) != 0;
collides = collides && (proxy1->m_collisionFilterGroup & proxy0->m_collisionFilterMask);

//add some additional logic here that modifies 'collides'
btCollisionObject* colObj0 = (btCollisionObject*) proxy0->m_clientObject;
btCollisionObject* colObj1 = (btCollisionObject*) proxy1->m_clientObject;
if (GET_GHOST(colObj0) == colObj1)
{
return false;
}
if (GET_GHOST(colObj1) == colObj0)
{
return false;
}
return collides;
}
};
void ActorNearCallback(btBroadphasePair& collisionPair, btCollisionDispatcher& dispatcher, const btDispatcherInfo& dispatchInfo)
{
// Do your collision logic here
// Only dispatch the Bullet collision information if you want the physics to continue
btCollisionObject* colObj0 = (btCollisionObject*) collisionPair.m_pProxy0->m_clientObject;
btCollisionObject* colObj1 = (btCollisionObject*) collisionPair.m_pProxy1->m_clientObject;
if (GET_GHOST(colObj0) == colObj1)
{
return;
}
if (GET_GHOST(colObj1) == colObj0)
{
return;
}
dispatcher.defaultNearCallback(collisionPair, dispatcher, dispatchInfo);
}
D3DXVECTOR3 CPhysicsEngine::CastRayToWorld(
const D3DXVECTOR3 &rayOrigin,
const D3DXVECTOR3 &rayDir,
CCollidee **hitObj,
CCollideeInstance **hitInstance,
CCharacterController **hitDynamicObj,
bool skipDynamicObjects,
bool skipBackfaces,
CCharacterController *pSkipObj,
D3DXPLANE *pHitPlane
)
{
btVector3 rayFromW, rayToW, newRay;
short oldGroup1;
short oldGroup2;
if (pSkipObj &&
pSkipObj->getGhostObject() &&
pSkipObj->m_sphereCollider &&
pSkipObj->getGhostObject()->getBroadphaseHandle()
)
{
oldGroup1 = pSkipObj->getGhostObject()->getBroadphaseHandle()->m_collisionFilterGroup;
oldGroup2 = pSkipObj->m_sphereCollider->getBroadphaseHandle()->m_collisionFilterGroup;
pSkipObj->getGhostObject()->getBroadphaseHandle()->m_collisionFilterGroup = 0x00;
pSkipObj->m_sphereCollider->getBroadphaseHandle()->m_collisionFilterGroup = 0x00;
}
rayFromW = btVector3( rayOrigin.x, rayOrigin.y, rayOrigin.z );
rayToW = btVector3( rayDir.x, rayDir.y, rayDir.z );
btCollisionWorld::ClosestRayResultCallback cb(rayFromW, rayToW);
if (skipBackfaces)
{
cb.m_flags = 1 << 0;
}
*hitObj = NULL;
*hitDynamicObj = NULL;
newRay = rayToW;
m_dynamicsWorld->rayTest( rayFromW, rayToW, cb );
if (cb.hasHit ())
{
btCollisionObject *pObj = cb.m_collisionObject;
if (pObj)
{
COLLISION_DATA *pCD;
pCD = (COLLISION_DATA *)pObj->getUserPointer();
if (pCD && pCD->m_pCollideeInstance)
{
CCollideeInstance *pInstance = pCD->m_pCollideeInstance;
if (pInstance)
{
newRay = cb.m_hitPointWorld;
if (pHitPlane)
{
D3DXPlaneFromPointNormal( pHitPlane,
&D3DXVECTOR3( newRay.getX(), newRay.getY(), newRay.getZ() ),
&D3DXVECTOR3( cb.m_hitNormalWorld.getX(), cb.m_hitNormalWorld.getY(), cb.m_hitNormalWorld.getZ() ) );
}
*hitObj = pInstance->m_pCollidee;
if (hitInstance)
{
*hitInstance = pInstance;
}
}
}
//
// If we still haven't matched, it's likely we hit a ghost
// object.
//
if (*hitObj == NULL)
{
if (pCD && pCD->m_pDynamicObj)
{
if (!skipDynamicObjects)
{
newRay = cb.m_hitPointWorld;
if (pHitPlane)
{
D3DXPlaneFromPointNormal( pHitPlane,
&D3DXVECTOR3( newRay.getX(), newRay.getY(), newRay.getZ() ),
&D3DXVECTOR3( cb.m_hitNormalWorld.getX(), cb.m_hitNormalWorld.getY(), cb.m_hitNormalWorld.getZ() ) );
}
}
*hitObj = NULL;
if (hitInstance)
{
*hitInstance = NULL;
}
*hitDynamicObj = pCD->m_pDynamicObj;
}
}
}
if (pSkipObj &&
pSkipObj->getGhostObject() &&
pSkipObj->m_sphereCollider &&
pSkipObj->getGhostObject()->getBroadphaseHandle()
)
{
pSkipObj->getGhostObject()->getBroadphaseHandle()->m_collisionFilterGroup = oldGroup1;
pSkipObj->m_sphereCollider->getBroadphaseHandle()->m_collisionFilterGroup = oldGroup2;
}
return D3DXVECTOR3( newRay.getX(), newRay.getY(), newRay.getZ() );
}
void Example()
{
m_defaultContactProcessingThreshold = BT_LARGE_FLOAT;
m_collisionConfiguration = new btDefaultCollisionConfiguration();
m_dispatcher = new btCollisionDispatcher(m_collisionConfiguration);
m_overlappingPairCache = new btDbvtBroadphase();

m_ghostPairCallback = new GhostPairCallback();
m_overlappingPairCache->getOverlappingPairCache()->setInternalGhostPairCallback(m_ghostPairCallback);
m_constraintSolver = new btSequentialImpulseConstraintSolver();
m_dynamicsWorld = new btDiscreteDynamicsWorld( m_dispatcher,
m_overlappingPairCache,
m_constraintSolver,
m_collisionConfiguration
);
m_filterCallback = new ActorFilterCallback();
m_dynamicsWorld->getPairCache()->setOverlapFilterCallback(m_filterCallback);
m_dispatcher->setNearCallback(ActorNearCallback);
}


Also just to note ... I have implemented rudimentary enemy AI using this ray-casting in a 3d world however it doesn't approach pathfinding, more like bump-n-grind AI. For better pathfinding look into Detours and ReCast
I took a look over your code, but couldn't implement it as I want.

I'm trying to implement Pathfinding, so basically, I want a method like the following method:
void MoveTo(Model *model, D3DXVECTOR3 toPoint);

The model can be character, vehicle, or anything that can move, by using this method I want the model to move and TAKECARE of walls, trees, buildings and other physical objects.
What have you tried and which parts of the problem are you having trouble with?
@Hodgman:As I mentioned I'm trying to find a method with the EXACT prototype that I posted earlier:
void MoveTo(Model *model, D3DXVECTOR3 toPoint);

After calling this method, the model should start moving and rotating untill it arrive at 'toPoint', of course the model should takecare of the other physical objects around.

@Hodgman:As I mentioned I'm trying to find a method with the EXACT prototype that I posted earlier:
void MoveTo(Model *model, D3DXVECTOR3 toPoint);

After calling this method, the model should start moving and rotating untill it arrive at 'toPoint', of course the model should takecare of the other physical objects around.


Well, I'm not going to write your routine for you, because likely you would have to adapt it anyway :)

The basic approach I recommend for this type of movement is to have a "TurnToFace" routine and a "MoveForward" routine. Use Bullet collision shapes for static geometry in the game and use Bullet CharacterController's with Sphere or Cylinder ghost objects for the MOBs.

When you want a MOB to "chase" a point, turn the MOB to face the point, then push their character controller forwards. Stop when they reach the point or get "close enough" to the point. You could look up OpenSteer library for some examples and ideas about this kind of behavior and implementation.

So to sum up you need the following pieces:

1. A representation of collision objects using Bullet (including the ground plane or terrain mesh)
2. A representation of the collision shape of MOBs and a kinematic CharacterController from Bullet for each one.
3. The ability to animate the turning of a MOB towards a particular point.
4. The ability to push forward a MOB.

The Bullet CharacterController implementation will take care to bump-n-grind your MOB off the other collision shapes, and while this won't be a foolproof way for a MOB to chase something, it will work most of the time. If you want 100% exact pathfinding in a 3d space look at Recast and Detour library.

This topic is closed to new replies.

Advertisement