Box2d pathfinding using raytracing / predicted collisions

Question

I have a Box2d/Cocos2d iOS game with enemies that attempt to follow the player (to attack). I'm working on improving the pathfinding logic so that the enemies won't crash into objects in the world.

Using raytracing, I know when there's an obstacle between an enemy and the player. I know when the enemy can't see the player.

I'm attempting to find a good way for the enemy to navigate around the obstacle, no matter what direction it's facing.

Right now, I start with the angle between the enemy and the obstacle. I gradually increment the angle, looking for any on-obstructed path that will allow the enemy to travel further than the obstacle's distance. This seems to work well so far, but it doesn't take into account the size of the enemy.

For example, if I have a 32px-squared enemy, the raytrace may find a clear path that would involve the edges of the ship hitting an obstacle.

Is there a way I can run a raytrace, predict collisions for something with a known width? Or is there a better way for my enemies to navigate around an obstacle.

Answer 1

What you're describing sounds like Obstacle Avoidance (as pointed out by @nathan).

The easiest way to implement it is modeling both the characters and the obstacles as circles. In order to avoid the obstacle, we increase its radius by the radius of the character, so we can treat the character as a point. The angle θ to both sides of the obstacle can be calculated as theta = asin((R+r)/d).

With the angle you can calculate the vectors to avoid the obstacle to the right and to the left, using a rotation matrix to rotate the vector going from the character to the obstacle (the green line). Then you can see which side of the obstacle requires less steering, by calculating the sign of the z coordinate of the cross product of the movement direction and the vector to the obstacle.

If your objects have a different shape, you might still be able to use circles by making them large enough to include the object. The advantage of circles is that they make expanding the obstacle to turn the character into a point very easy. Other shapes require more complicated geometry.

Keep in mind this approach will only work if the world is sparse enough that steering to avoid an object won't push you into another one. If that's the case, you'll have to resort to more sophisticated approaches, possibly including pathfinding.