How to use physics sim. to help pathfinding get around walls

[hunter9000]

I'm working on a FPS game, and I've gotten a lot of the basics down. I have very rudimentary pathfinding for the enemies done. My game uses the A* algorithm to determine the path that the enemies take to get from their position to the player's position, and then I create two Curves that define the path to get there. At each update, the enemy moves a small amount along that Curve, which determines it's new position. Right now I'm manually doing checks to see if the enemies (and the player) intersect with the walls, and if they do, I don't move them. This makes the enemies stop in their tracks if they touch a wall.

The problem I'm trying to use BEPU to solve is how to make the enemies move along the wall until they can continue. Here's a picture to illustrate what I mean.

This is what I currently have:

The red line is the enemy's path from A to B, and when it hits the blue wall, it just stops now. The path itself doesn't intersect with the wall, but it comes close enough that the bounding box of the enemy does intersect.

This is what I want:

When the path hits the wall, the physics engine should move it along the wall until it no longer collides.

Because I'm calculating the path the enemy should take myself, I'm not applying forces or setting velocities, I'm simply changing it's position. How can I take advantage of the collision detection and correction in BEPU to do what I illustrated without modifying my code to use velocities to move the enemy?

So far I know that I should add the triangles that make up the walls and probably the ground to a Static Group, and create a Box for the enemy, but I don't know how to make them interact without setting velocities and applying forces.

If something doesn't make sense, let me know and I'll try to explain it further. Thanks!

[Norbo]

The main thing you'll have to do is handle interpenetrations manually.

The engine normally handles it by taking the contact data (position, normal, depth) and correcting any penetrating velocity (and introducing a small extra velocity to separate already intersecting objects).

You can use that same contact data to change the target position. For example, if your enemy hits a wall and creates a contact with normal (1,0,0) and depth .046, you can add normal * depth = (.046, 0, 0) to the goal position. Now the enemy is not intersecting with the wall.

To get the contact data, you can look at the enemy entity's list of collision pairs (Entity.collisionPairs) and examine each collision pair's contact list (CollisionPair.contacts). Watch out if you're running the engine asynchronously; this data could change at any time if the engine is updating.

Given that each collision pair can have multiple contacts, you need to decide which contact to correct. Generally, picking the contact with the greatest penetration depth is a good heuristic. Ignore the rest of that collision pair's contacts.

So the position 'correction' would look like this:

Code: Select all

Vector3 positionCorrection = Vector3.Zero;
foreach (CollisionPair pair in entity.collisionPairs)
{
    positionCorrection += getBestSeparationVector(pair);
}

where getBestSeparationVector computes the 'best' separation vector according to some heuristic (like the deepest contact approach above). Here, a separation vector just means the normal times depth. You could also put in an extra test to ensure that the current collision pair involves something the enemy even needs to worry about; if it doesn't, just continue to the next pair.


A few more miscellaneous details:

• The enemy entity will probably be a Kinematic entity; that is, don't give it a mass when you create it (or call entity.becomeKinematic).
• Kinematic entities, by default, do not collide and do not generate contacts with other kinematic entities since it doesn't make sense in general for two infinite-mass objects to try to collide. You can change this most simply by changing the entity's collision group. By giving it a new collision group, the default behavior is to try to collide with everything. It won't be able to undergo collision response and the solver system will ignore it (as it should), but the collision detection system will run. You can check out the documentation page on the website for in-depth details on the collision rules system, but here's how you would give the entity a new group:

  Code: Select all

  entity.collisionRules.group = new CollisionGroup();

• Continuous collision detection will not be active; it is based entirely on velocities.
• This correction scheme won't stop your object from being totally inside the hollow triangular world mesh if the curve expects the object to be there at some point. One way to avoid this is to recompute the path (or the first part of it) based on the new corrected position. Based on your second picture, that's the behavior you were thinking of. Some additional tweaking may be necessary to get the motion to feel right. If the target position is around a corner and close to the wall, the enemy could end up sliding very slowly along the wall until it slips past the corner and continues. It'd be nicer if the path could take into account the newly found obstacle.
• Depending on how you have the geometry laid out for the pathfinding algorithm, you may also be able to logically 'expand' obstacles by some amount. This would force the algorithm to leave room for the fat character body. It would probably be good to still have this position correcting system in place, but it would be used mostly as a last resort.

[JHOW]

This is just another suggestion and may not be the best way but it is what i use.
I took a robotics course in high school where we had to get a robot to go through a maze.
We used infrared lights in the front to tell the distance from the wall and then turn in the opposite direction according to how close the object was.
I decided that i could use this same concept but using rays instead of infrared light . It worked out surprisingly well.
Here is a video of a car with three rays projecting out from the front.

http://www.facebook.com/video/video.php ... 9899601003